en>Magioladitis: Removing invisible Unicode character/ Replacing hard spaces See WP:CHECKWIKI error #16 fix + other fixes, replaced: → using AWB (10331)

2014-07-26T17:43:23Z

Removing invisible Unicode character/ Replacing hard spaces See WP:CHECKWIKI error #16 fix + other fixes, replaced: → using AWB (10331)

Show changes

en>Entropeter: /* Defect of a vertex */ added link

2013-06-03T07:51:57Z

Defect of a vertex: added link

New page

[[Image:Bilinear interpolation.png|right|thumb|The four red dots show the data points and the green dot is the point at which we want to interpolate.]]
[[Image:Bilininterp.png|right|thumb|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 color.]]
In [[mathematics]], '''bilinear interpolation''' is an extension of [[linear interpolation]] for [[interpolation|interpolating]] functions of two variables (e.g., <math>x</math> and <math>y</math>) on a [[regular grid|regular 2D grid]].

The key idea is to perform linear interpolation first in one direction, and then again in the other direction. 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 (details below).

==Algorithm==

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''11 = (''x''1, ''y''1), ''Q''12 = (''x''1, ''y''2), ''Q''21 = (''x''2, ''y''1), and ''Q''22 = (''x''2, ''y''2).

We first do linear interpolation in the ''x''-direction. This yields
:<math> 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})</math>
where <math>R_1 = (x,y_1)</math>,
:<math> 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})</math>
where <math>R_2 = (x,y_2). </math>

We proceed by interpolating in the ''y''-direction.
:<math> 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). </math>

This gives us the desired estimate of ''f''(''x'', ''y'').
:<math>
\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) \\
= & \, \frac{1}{(x_2-x_1)(y_2-y_1)} \Big( f(Q_{11})(x_2-x)(y_2-y) \, + \\
& \, \qquad \qquad \qquad \qquad \; \; f(Q_{21})(x-x_1)(y_2-y) \, + \\
& \, \qquad \qquad \qquad \qquad \; \; f(Q_{12})(x_2-x)(y-y_1) \, + \\
& \, \qquad \qquad \qquad \qquad \; \; f(Q_{22})(x-x_1)(y-y_1) \quad \Big)
\end{align}
</math>

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.
===Unit Square===

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
:<math> 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. </math>
Or equivalently, in matrix operations:
:<math> 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}.</math>

===Nonlinear===

Contrary to what the name suggests, the bilinear interpolant is ''not'' linear; nor is it the product of two [[linear functions]].

Alternatively, the interpolant can be written as
:<math> b_1 + b_2 x + b_3 y + b_4 x y \, </math>
where
:<math> b_1 = f(0,0) \,</math>
:<math> b_2 = f(1,0)-f(0,0) \,</math>
:<math> b_3 = f(0,1)-f(0,0) \,</math>
:<math> b_4 = f(0,0)-f(1,0)-f(0,1)+f(1,1). \,</math>

[[File:bilinear_interpolation_visualisation.svg|thumb|right|In this geometric visualisation, the value at the black spot is the sum of the value at each coloured spot multiplied by the area of the rectangle of the same colour, divided by the total area of all four rectangles.]]

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 (geometry)|parallel]] to either the <math>x</math> or the <math>y</math> direction, equivalently if <math>x</math> or <math>y</math> is set constant. Along any other straight line, the interpolant is [[Quadratic function|quadratic]]. However, even if the interpolation is ''not'' linear in the position (''x'' and ''y''), it ''is'' linear in the amplitude, as it is apparent from the equations above: all the coefficient ''bj, j=1..4'', are proportional to the value of the function ''f(,)''.

The result of bilinear interpolation is independent of which axis is interpolated first and which second. 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]].

== Application in image processing ==
In [[computer vision]] and [[image processing]], bilinear interpolation is one of the basic [[resampling]] techniques.

In [[texture mapping]], it is also known as [[bilinear filtering]] or ''bilinear texture mapping'', and it can be used to produce a reasonably realistic image. 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.<ref>[http://www.pcmag.com/encyclopedia_term/0,2542,t=bilinear+interpolation&i=38607,00.asp Bilinear interpolation definition at www.pcmag.com]</ref>

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. However, when scaling up an image by a non-integral scale factor, there are pixels (i.e., ''holes'') that are not assigned appropriate pixel values. 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. Unlike other interpolation techniques such as [[nearest neighbor interpolation]] and [[bicubic interpolation]], bilinear interpolation uses only the 4 nearest pixel values which are located in diagonal directions from a given pixel in order to find the appropriate color intensity values of that pixel.

Bilinear interpolation considers the closest 2x2 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. The weight on each of the 4 pixel values is based on the computed pixel's distance (in 2D space) from each of the known points.<ref>[http://www.cambridgeincolour.com/tutorials/image-interpolation.htm "Digital Image Interpolation"]</ref>

[[File:Bilin3.png|thumb|right|alt=Bilinear interpolation|Example of bilinear interpolation in grayscale values.]]

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
 <math>
\begin{array}{llll}
I_{20, 14.5} & = \tfrac{15 - 14.5}{15 - 14} \cdot 91 \, & + \; \tfrac{14.5 - 14}{15 - 14} \cdot 210 \, & = 150.5 \\
I_{21, 14.5} & = \tfrac{15 - 14.5}{15 - 14} \cdot 162 \, & + \; \tfrac{14.5 - 14}{15 - 14} \cdot 95 \, & = 128.5
\end{array}
</math> 
and then interpolating linearly between these values, giving
 <math>I_{20.2, 14.5} = \tfrac{21 - 20.2}{21 - 20} \cdot 150.5 + \tfrac{20.2 - 20}{21 - 20} \cdot 128.5 = 146.1</math>

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. Bilinear interpolation tends, however, to produce a greater number of interpolation artifacts (such as [[aliasing]], blurring, and edge halos) than more computationally demanding techniques such as bicubic interpolation.<ref>[http://www.optoiq.com/index/machine-vision-imaging-processing/display/vsd-article-display/308929/articles/vision-systems-design/volume-12/issue-10/departments/wilsons-websites/understanding-image-interpolation-techniques.html "Understanding image-interpolation techniques"]</ref>

== See also ==
*[[Bicubic interpolation]]
*[[Trilinear interpolation]]
*[[Spline interpolation]]
*[[Lanczos resampling]]
*[[Stairstep interpolation]]
*[[Barycentric coordinate system (mathematics)|Barycentric coordinates - for interpolating within a triangle or tetrahedron]]

==References==
<references/>

[[Category:Multivariate interpolation]]

Angular defect - Revision history

en>Magioladitis: Removing invisible Unicode character/ Replacing hard spaces See WP:CHECKWIKI error #16 fix + other fixes, replaced: → using AWB (10331)

en>Entropeter: /* Defect of a vertex */ added link