Bilinear interpolation

It is usually applied to functions sampled on a 2D rectilinear grid, though it can be generalized to functions defined on the vertices of (a mesh of) arbitrary convex quadrilaterals.

Although each step is linear in the sampled values and in the position, the interpolation as a whole is not linear but rather quadratic in the sample location.

Suppose that we want to find the value of the unknown function f at the point (x, y).

This yields We proceed by interpolating in the y-direction to obtain the desired estimate: Note that we will arrive at the same result if the interpolation is done first along the y direction and then along the x direction.

[1] An alternative way is to write the solution to the interpolation problem as a multilinear polynomial where the coefficients are found by solving the linear system yielding the result The solution can also be written as a weighted mean of the f(Q): where the weights sum to 1 and satisfy the transposed linear system yielding the result which simplifies to in agreement with the result obtained by repeated linear interpolation.

Combining the above, we have 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 or equivalently, in matrix operations: Here we also recognize the weights: Alternatively, the interpolant on the unit square can be written as where In both cases, the number of constants (four) correspond to the number of data points where f is given.

As the name suggests, the bilinear interpolant is not linear; but it is linear (i.e. affine) along lines parallel to either the x or the y direction, equivalently if x or y is held constant.

Even though the interpolation is not linear in the position (x and y), at a fixed point it is linear in the interpolation values, as can be seen in the (matrix) equations above.

The interpolant is a bilinear polynomial, which is also a harmonic function satisfying Laplace's equation.

Its graph is a bilinear Bézier surface patch.

In general, the interpolant will assume any value (in the convex hull of the vertex values) at an infinite number of points (forming branches of hyperbolas[2]), so the interpolation is not invertible.

In particular, this inverse can be used to find the "unit square coordinates" of a point inside any convex quadrilateral (by considering the coordinates of the quadrilateral as a vector field which is bilinearly interpolated on the unit square).

Using this procedure bilinear interpolation can be extended to any convex quadrilateral, though the computation is significantly more complicated if it is not a parallelogram.

Alternatively, a projective mapping between a quadrilateral and the unit square may be used, but the resulting interpolant will not be bilinear.

In the special case when the quadrilateral is a parallelogram, a linear mapping to the unit square exists and the generalization follows easily.

be a vector field that is bilinearly interpolated on the unit square parameterized by

Inverting the interpolation requires solving a system of two bilinear polynomial equations:

Taking a 2-d cross product (see Grassman product) of the system with a carefully chosen vectors allows us to eliminate terms:

(opposite signs are enforced by the linear relation).

A weighted average of the attributes (color, transparency, 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.

[4] When an image needs to be scaled up, each pixel of the original image needs to be moved in a certain direction based on the scale constant.

In this case, those holes should be assigned appropriate RGB or grayscale values so that the output image does not have non-valued pixels.

Bilinear interpolation can be used where perfect image transformation with pixel matching is impossible, so that one can calculate and assign appropriate intensity values to pixels.

Bilinear interpolation considers the closest 2 × 2 neighborhood of known pixel values surrounding the unknown pixel's computed location.

It then takes a weighted average of these 4 pixels to arrive at its final, interpolated value.

[5][6] As seen in the example on the right, the intensity value at the pixel computed to be at row 20.2, column 14.5 can be calculated by first linearly interpolating between the values at column 14 and 15 on each rows 20 and 21, giving and then interpolating linearly between these values, giving This algorithm reduces some of the visual distortion caused by resizing an image to a non-integral zoom factor, as opposed to nearest-neighbor interpolation, which will make some pixels appear larger than others in the resized image.

These two repetitions can be assigned temporary variables whilst computing a single interpolation, which will reduce the number of calculations down to 14 operations, which is the minimum number of steps required for producing the desired interpolation.

Simplification of terms is good practice for application of mathematical methodology to engineering applications and can reduce computational and energy requirements for a process.