Tuesday, July 29, 2014

bilinear interpolation

In mathematics, bilinear interpolation is an extension of linear interpolation for interpolating functions of two variables (e.g., x and y) on a 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).

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 Q11 = (x1y1), Q12 = (x1y2), Q21 = (x2y1), and Q22 = (x2y2).
1) 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})
where point 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})
where point R_2 = (x,y_2).

where
f(Q11) is the function value at point (x1,y1)
f(Q12) is the function value at point (x1,y2)
f(Q21) is the function value at point (x2,y1)
f(Q22) is the function value at point (x2,y2)



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{array}{ l l}
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) \\
   \qquad          = & \, \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{array}
 
 
DXU: This bi-linear interpolation could be extended to N-linear interpolation. 
 

No comments:

Post a Comment