Bilinear interpolation

From Wikipedia, the free encyclopedia

In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables on a regular grid. The key idea is to perform linear interpolation first in one direction, and then in the other direction.

The four red dots show the data points and the green dot is the point at which we want to interpolate.

Example of bilinear interpolation on the unit square with the z-values 0, 1, 1 and 0.5 as indicated. Interpolated values in between represented by colour.

Suppose that we want to find the value of the unknown function f at the point P = (x, y). It is assumed that we know the value of f at the four points Q₁₁ = (x₁, y₁), Q₁₂ = (x₁, y₂), Q₂₁ = (x₂, y₁), and Q₂₂ = (x₂, y₂).

We first do linear interpolation in the x-direction. This yields

$f(R_1) \approx \frac{x_2-x}{x_2-x_1} f(Q_{11}) + \frac{x-x_1}{x_2-x_1} f(Q_{21}) \quad\mbox{where}\quad R_1 = (x,y_1),$

$f(R_2) \approx \frac{x_2-x}{x_2-x_1} f(Q_{12}) + \frac{x-x_1}{x_2-x_1} f(Q_{22}) \quad\mbox{where}\quad R_2 = (x,y_2).$

We proceed by interpolating in the y-direction.

$f(P) \approx \frac{y_2-y}{y_2-y_1} f(R_1) + \frac{y-y_1}{y_2-y_1} f(R_2).$

This gives us the desired estimate of f(x, y).

$\begin{align} f(x,y) &\approx \frac{f(Q_{11})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y_2-y) \\ & + \frac{f(Q_{21})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y_2-y) \\ & + \frac{f(Q_{12})}{(x_2-x_1)(y_2-y_1)} (x_2-x)(y-y_1) \\ & + \frac{f(Q_{22})}{(x_2-x_1)(y_2-y_1)} (x-x_1)(y-y_1). \end{align}$

If we choose a coordinate system in which the four points where f is known are (0, 0), (0, 1), (1, 0), and (1, 1), then the interpolation formula simplifies to

$f(x,y) \approx f(0,0) \, (1-x)(1-y) + f(1,0) \, x(1-y) + f(0,1) \, (1-x)y + f(1,1) xy.$

Or equivalently, in matrix operations:

$f(x,y) \approx \begin{bmatrix} 1-x & x \end{bmatrix} \begin{bmatrix} f(0,0) & f(0,1) \\ f(1,0) & f(1,1) \end{bmatrix} \begin{bmatrix} 1-y \\ y \end{bmatrix}$

Contrary to what the name suggests, the interpolant is not linear. Instead, it is of the form

$(a_1 x + a_2)(a_3 y + a_4), \,$

so it is a product of two linear functions. Alternatively, the interpolant can be written as

$b_1 + b_2 x + b_3 y + b_4 x y \,$

where

$b_1 = f(0,0) \,$

$b_2 = f(1,0)-f(0,0) \,$

$b_3 = f(0,1)-f(0,0) \,$

$b_4 = f(0,0)-f(1,0)-f(0,1)+f(1,1). \,$

In both cases, the number of constants (four) correspond to the number of data points where f is given. The interpolant is linear along lines parallel to either the $x$ or the $y$ direction, equivalently if $x$ or $y$ is set constant. Along any other straight line, the interpolant is quadratic.

The result of bilinear interpolation is independent of the order of interpolation. If we had first performed the linear interpolation in the y-direction and then in the x-direction, the resulting approximation would be the same.

The obvious extension of bilinear interpolation to three dimensions is called trilinear interpolation.

[edit] In Image Processing

It has been suggested that this article or section be merged into Resampling. (Discuss)

In computer vision, bilinear interpolation is the one of the basic interpolatoin techniques.

It is "a texture mapping technique that produces a reasonably realistic image, also known as "bilinear filtering" and "bilinear texture mapping." An algorithm is used to map a screen pixel location to a corresponding point on the texture map. A weighted average of the attributes (color, alpha, etc.) of the four surrounding texels is computed and applied to the screen pixel. This process is repeated for each pixel forming the object being textured"Bilinear interpolation definition

When an image needs to be scaled-up, each pixel of the original image needs to be moved in certain direction based on scale constant. However, when scaling up an image, there are pixels (i.e. Hole) that are not assigned to appropriate pixel values. In this case, those holes should be assigned to appropriate image vlues so that the output image does not have non-value pixels.

Typically, bilinear interpolation can be used where perfect image transformation, matching and imaging is impossible so that it can calculates and assgin appropriate image vlues to pixels. Unlike, other interpolation techniques such as Nearest Neighbor Interpolation and Cubic interpolation, Bilinear Interpolation uses 4 nearest pixel values which are located in diagonal direction from that specific pixel in order to find appropritate color intensity value of a desired pixel.

In an image, we want to find the image value for pixel P(r, c) wheree 'r' represents row and 'c' is for column. Then, image value for this pixel can be represented as I(r₁, c1).

image value of X, A, B, C and D represent I, I1, I2, I3 and I4 in the above description respectively

In bilinear interpolation image values of 4 nearest points can be represented as followings, I1(r₀, c₀), I2(r₀, c₁), I3(r₁, c₀), I4(r₁, c₁)

in bilinear Interpolation, 4 pixels are weighted differenctly based on the disstance from pixel P(r,c) and the sum of those weighted value will the desired image value for specific pixel location.

This gives us the desired estimate image value I for the pixel P(r, c).

$\begin{align} I =\approx (1 - a)(1 - b) I_1 + a (1 - b) I_2 + (1 - a) b I_3 + a b I_4 \end{align}$

Where a and b are the horizontal and vertical distances from the pixel P(r, c) to P1(r₀, c₀). The equation clearly shows that pixels which are close to the P(r,c) gets more weight than pixels aren't. Vertical and horizontal weighs are independent to each other in this case. Therefore, Bilinear Interpolation performs a linear interpolation both in x (column) and y (row) direction separately. By putting more weight on close pixels, bilinear interpolation allows to produce a smoother output image from an origianl one.

Original image

3 itmes scaled-up image using Nearest Neighbor Interpolation

3 times scaled-up image using 4 pixels; but all with same weigths

3 times scaled-up image using correct Bilinear Interpolation

Limitation: Compare to the Nearest Neighbor Interpolation, Bilinear Interpolation requires 3 more calculations in order to calculate each desired pixel's color intesity value.

Advantage: However, as images shown above Bilinear Interpolation can produce smoother image from the original than Nearest Neighbor Interpolation.