Bilinear interpolation

Bilinear interpolation

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 again in the other direction.

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: 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}) quadmbox{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}) quadmbox{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").: egin{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 egin{bmatrix}1-x & x end{bmatrix} egin{bmatrix}f(0,0) & f(0,1) \f(1,0) & f(1,1) end{bmatrix} egin{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.

Application in image processing

In computer vision and image processing, bilinear interpolation is the one of the basic resampling techniques.

It is a texture mapping technique that produces a reasonably realistic image, also known as "bilinear filtering" or "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 [ [http://www.pcmag.com/encyclopedia_term/0,2542,t=bilinear+interpolation&i=38607,00.asp Bilinear interpolation definition at www.pcmag.com] ]

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 values 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 calculate and assign appropriate image values to pixels. Unlike other interpolation techniques such as
nearest neighbor interpolation and bicubic interpolation, bilinear Interpolation uses the 4 nearest pixel values which are located in diagonal direction from that specific pixel in order to find the appropriate color intensity value of a desired pixel.

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

Image values of 4 nearest points can be represented as followings,"I1(r0, c0), I2(r0, c1), I3(r1, c0), I4(r1, c1)"

Four pixels are weighted differently based on the distance 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).

: egin{align}I =approx (1 - a)(1 - b) I_1 + a (1 - b) I_2 + (1 - a) b I_3 + a b I_4end{align}

Where a and b are the horizontal and vertical distances from the pixel P(r, c) to P1(r0, c0). The equation clearly shows that pixels which are close to P(r,c) get more weight than pixels which aren't. Vertical and horizontal weights are independent to each other in this case. Therefore, bilinear interpolationperforms 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 original one.

In some special cases of bilinearly upscaling, where every channel (color and alpha) is scaled by themselves there might be undesirable artifacts. Consider a fully visible blue pixel next to a fully transparent pixel. The color of the transparent pixel is undefined and might be any color (if color is stored at all in the underlying storage format). Lets assume the color of the transparent pixel happens to be red (even though this is not visible before upscaling the image), then the upscaled image will have a gradient from totally visible blue to totally transparent red, the in-between will be semi transparent grades of purple, a non-desirable result.

"Limitation": Compared to the nearest neighbor interpolation, bilinear interpolation requires 3 more calculations in order to calculate each desired pixel's color intensity value.

"Advantage": However, as images shown above bilinear interpolation can produce smoother image from the original than nearest neighbor interpolation.

See also

*Bicubic interpolation
*Trilinear interpolation
*Spline interpolation
*Lanczos resampling
*Stairstep interpolation

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Bilinear filtering — is a texture filtering method used to smooth textures when displayed larger or smaller than they actually are.Most of the time, when drawing a textured shape on the screen, the texture is not displayed exactly as it is stored, without any… …   Wikipedia

  • Bilinear — may refer to* Bilinear sampling, a method in computer graphics for choosing the color of a texture. * Bilinear form * Bilinear interpolation * Bilinear map, a type of mathematical function between vector spaces * Bilinear transform, a method of… …   Wikipedia

  • Interpolation — In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points. In engineering and science one often has a number of data points, as obtained… …   Wikipedia

  • Interpolation (Mathematik) — In der numerischen Mathematik bezeichnet der Begriff Interpolation eine Klasse von Problemen und Verfahren. Zu gegebenen diskreten Daten (z. B. Messwerten) soll eine stetige Funktion (die sogenannte Interpolante oder Interpolierende)… …   Deutsch Wikipedia

  • Bilinear — Im mathematischen Teilgebiet der linearen Algebra und verwandten Gebieten verallgemeinern die bilinearen Abbildungen die verschiedensten Begriffe von Produkten (im Sinne einer Multiplikation). Die Bilinearität entspricht dem Distributivgesetz bei …   Deutsch Wikipedia

  • Bilinear filtering — Filtrage bilinéaire Le filtrage bilinéaire est un algorithme utilisé en infographie permettant de calculer des pixels intermédaires entre les pixels d une image ou d une texture que l on change de taille. C est un des procédés les plus utilisés… …   Wikipédia en Français

  • Bicubic interpolation — In mathematics, bicubic interpolation is an extension of cubic interpolation for interpolating data points on a two dimensional regular grid. The interpolated surface is smoother than corresponding surfaces obtained by bilinear interpolation or… …   Wikipedia

  • Linear interpolation — is a method of curve fitting using linear polynomials. It is heavily employed in mathematics (particularly numerical analysis), and numerous applications including computer graphics. It is a simple form of interpolation. Lerp is a quasi acronym… …   Wikipedia

  • Trilinear interpolation — is a method of multivariate interpolation on a 3 dimensional regular grid. It approximates the value of an intermediate point (x, y, z) within the local axial rectangular prism linearly, using data on the lattice points. For an arbitrary,… …   Wikipedia

  • Multivariate interpolation — In numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable. The function to be interpolated is known at given points and the interpolation problem consist of yielding values… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”