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.

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.

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 2^N neighbors. Consider the N-dimensional domain between the 2^N neighbors. This hyper-box is divided into 2^N 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…

bilinear interpolation, interpolation, linear interpolation, multilinear interpolation, nearest neighbor, trilinear interpolation

Uncategorized

Zeno Bouncing

Addition in Other Domains

2 Responses to “Multilinear Interpolation”

Tilman says:

January 30, 2014 at 20:28

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.

Reply
- admin says:
  
  January 30, 2014 at 21:23
  
  Thanks. I’ve incorporated number 1 and 2, and anyone concerned about special cases can come and find number 3 in your comment.
  
  Reply

Multilinear Interpolation

Linear Interpolation

Bilinear Interpolation

Trilinear Interpolation

General Multilinear Interpolation

2 Responses to “Multilinear Interpolation”

Leave a Reply Cancel reply

Categories

Find

Recent Posts