Multilinear Interpolation

There is a neat visualization of linear interpolation that generalizes to higher-dimensional spaces, including bilinear (2D) interpolation, trilinear (3D) interpolation and general multilinear interpolation. At all levels it is much easier to remember the visualization than the formulas directly. Let’s start with the simplest case…

Linear Interpolation

Linear interpolation is a weighted average of 2 neighbors. Consider the 1D domain between the 2 neighbors. This line is divided into 2 segments by the point in question. The weight of each neighbor is given by the length of the opposite segment, as a fraction of the whole line.linear_interpolation

If x has neighboring data points f_0 at x_0 and f_1 at x_1 then the linear interpolation at x is given by

\large{\frac{(x_1-x) f_0 + (x-x_0) f_1}{x_1-x_0}} .

Bilinear Interpolation

Bilinear interpolation is a weighted average of 4 neighbors. Consider the 2D domain between the 4 neighbors. This rectangle is divided into 4 sub-rectangles by the point in question. The weight of each neighbor is given by the area of the opposite sub-rectangle, as a fraction of the whole rectangle.

bilinear_interpolation

If (x,y) has neighboring data points f_{00} at (x_0,y_0) , f_{01} at (x_0,y_1) , f_{10} at (x_1,y_0) , and f_{11} at (x_1,y_1) , then the bilinear interpolation at (x,y) is given by

\large{\frac{(x_1-x)(y_1-y) f_{00} + (x_1-x)(y-y_0) f_{01} + (x-x_0)(y_1-y) f_{10} + (x-x_0)(y-y_0) f_{11}}{(x_1-x_0)(y_1-y_0)}}

Trilinear Interpolation

Trilinear interpolation is a weighted average of 8 neighbors. Consider the 3D domain between the 8 neighbors. This box is divided into 8 sub-boxes by the point in question. The weight of each neighbor is given by the volume of the opposite sub-box, as a fraction of the whole box.

This is easy to visualize but hard to draw – so sorry no diagram.

If (x,y,z) has neighboring data points f_{000} , f_{001} , f_{010} , f_{011} , f_{100} , f_{101} , f_{110} , f_{111} at (x_0,y_0,z_0) , (x_0,y_0,z_1) , (x_0,y_1,z_0) , (x_0,y_1,z_1) , (x_1,y_0,z_0) , (x_1,y_0,z_1) , (x_1,y_1,z_0) , (x_1,y_1,z_1) respectively, then the trilinear interpolation at (x,y,z) is given by

\large{\frac{(x_1-x)(y_1-y)(z_1-z) f_{000} + (x_1-x)(y_1-y)(z-z_0) f_{001} + (x_1-x)(y-y_0)(z_1-z) f_{010} + (x_1-x)(y-y_0)(z-z_0) f_{011}}{(x_1-x_0)(y_1-y_0)(z_1-z_0)}}

\large{ + }

\large{\frac{(x-x_0)(y_1-y)(z_1-z) f_{100} + (x-x_0)(y_1-y)(z-z_0) f_{101} + (x-x_0)(y-y_0)(z_1-z) f_{110} + (x-x_0)(y-y_0)(z-z_0) f_{111}}{(x_1-x_0)(y_1-y_0)(z_1-z_0)}}

General Multilinear Interpolation

N-linear interpolation is a weighted average of 2N neighbors. Consider the N-dimensional domain between the 2N neighbors. This hyper-box is divided into 2N sub-hyper-boxes by the point in question. The weight of each neighbor is given by the hyper-volume of the opposite sub-hyper-box, as a fraction of the whole hyper-box.

You get the idea…

2 Responses to “Multilinear Interpolation”

  • Tilman says:

    You might want to improve your description:
    1) explain that “f” is the value (or set of values) for that point.
    2) the formula has a result, with is f(x), i.e. the value (or set of values) of “f” for the point x.
    3) your formulas don’t work if x1 = x0 or y1 = y0, i.e. these case require a fallback on n-1 interpolation or whatever.

    • admin says:

      Thanks. I’ve incorporated number 1 and 2, and anyone concerned about special cases can come and find number 3 in your comment.


Leave a Reply

Your email address will not be published. Required fields are marked *

Cheap NFL Jerseys Cheap NFL Jerseys goedkope air max online Basket Air Jordan 11 Christian Louboutin Outlet Cheap Jerseys Wholesale Jerseys Michael Kors Outlet Online Ray Ban Sunglasses Jerseys Wholesale Coach Outlet Store michael jordan air jordan 11 Coach Outlet Cheap NFL Jerseys Kate Spade Outlet Sale air max 90 pas cher junior Wholesale Jerseys Jerseys Cheap nba jerseys vegas Jerseys Wholesale China