Bicubic interpolation

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

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 nearest-neighbor interpolation. Bicubic interpolation can be accomplished using either Lagrange polynomials, cubic splines or cubic convolution algorithm.

In image processing, bicubic interpolation is often chosen over bilinear interpolation or nearest neighbor in image resampling, when speed is not an issue. Images resampled with bicubic interpolation are smoother and have fewer interpolation artifacts.

Bicubic interpolation on the square consisting of 9 unit squares patched together. Bicubic interpolation as per Matlab's implementation. Colour indicates function value. The black dots are the locations of the prescribed data being interpolated. Note how the color samples are not radially symmetric. They are more square-based (It may be easier to compare by zooming on the image)

Bicubic interpolation on the square $[0,3] \times [0,3]$ consisting of 9 unit squares patched together. Bicubic interpolation as per Matlab's implementation. Colour indicates function value. The black dots are the locations of the prescribed data being interpolated. Note how the color samples are not radially symmetric. They are more square-based (It may be easier to compare by zooming on the image)

Bilinear interpolation on the same dataset as above. Derivatives of the surface are not continuous over the square boundaries.

Nearest-neighbor interpolation on the same dataset as above. Note that the information content in all these three examples is equivalent.

1 Bicubic spline interpolation
2 Bicubic convolution algorithm
3 Use in computer graphics
4 References
5 See also
6 External links

[edit] Bicubic spline interpolation

Suppose the function values $f$ and the derivatives $f x$ , $f y$ and $f x y$ are known at the four corners $(0,0)$ , $(1,0)$ , $(0,1)$ , and $(1,1)$ of the unit square. The interpolated surface can then be written

$p(x,y) = \sum_{i=0}^3 \sum_{j=0}^3 a_{ij} x^i y^j.$

The interpolation problem consists of determining the 16 coefficients $a i j$ . Matching $p (x, y)$ with the function values yields four equations,

$f (0,0) = p (0,0) = a 00$
$f (1,0) = p (1,0) = a 00 + a 10 + a 20 + a 30$
$f (0,1) = p (0,1) = a 00 + a 01 + a 02 + a 03$
$f(1,1) = p(1,1) = \textstyle \sum_{i=0}^3 \sum_{j=0}^3 a_{ij}$

Likewise, eight equations for the derivatives in the $x$ -direction and the $y$ -direction

$f x (0,0) = p x (0,0) = a 10$
$f x (1,0) = p x (1,0) = a 10 + 2 a 20 + 3 a 30$
$f x (0,1) = p x (0,1) = a 10 + a 11 + a 12 + a 13$
$f_x(1,1) = p_x(1,1) = \textstyle \sum_{i=1}^3 \sum_{j=0}^3 a_{ij} i$
$f y (0,0) = p y (0,0) = a 01$
$f y (1,0) = p y (1,0) = a 01 + a 11 + a 21 + a 31$
$f y (0,1) = p y (0,1) = a 01 + 2 a 02 + 3 a 03$
$f_y(1,1) = p_y(1,1) = \textstyle \sum_{i=0}^3 \sum_{j=1}^3 a_{ij} j$

And four equations for the cross derivative $x y$ .

$f x y (0,0) = p x y (0,0) = a 11$
$f x y (1,0) = p x y (1,0) = a 11 + 2 a 21 + 3 a 31$
$f x y (0,1) = p x y (0,1) = a 11 + 2 a 12 + 3 a 13$
$f_{xy}(1,1) = p_{xy}(1,1) = \textstyle \sum_{i=1}^3 \sum_{j=1}^3 a_{ij} i j$

where the expressions above have used the following identities,

$p_x(x,y) = \textstyle \sum_{i=1}^3 \sum_{j=0}^3 a_{ij} i x^{i-1} y^j$

$p_y(x,y) = \textstyle \sum_{i=0}^3 \sum_{j=1}^3 a_{ij} x^i j y^{j-1}$

$p_{xy}(x,y) = \textstyle \sum_{i=1}^3 \sum_{j=1}^3 a_{ij} i x^{i-1} j y^{j-1}$ .

This procedure yields a surface $p (x, y)$ on the unit square $[0,1] \times [0,1]$ which is continuous and with continuous derivatives. Bicubic interpolation on an arbitrarily sized regular grid can then be accomplished by patching together such bicubic surfaces, ensuring that the derivatives match on the boundaries.

If the derivatives are unknown, they are typically approximated from the function values at points neighbouring the corners of the unit square, ie. using finite differences.

[edit] Bicubic convolution algorithm

Bicubic spline interpolation is required to solve the linear system described above for each grid cell. An interpolator with similar properties can be obtained by applying convolution with the following kernel in both dimensions:

$W(x) = \begin{cases} (a+2)|x|^3-(a+3)|x|^2+1 & \text{for } 0 < |x| \leq 1 \\ a|x|^3-5a|x|^2+8a|x|-4a & \text{for } 1 < |x| \leq 2 \\ 0 & \text{otherwise} \end{cases}$

where $a$ is usually set to -0.5 or -0.75.

This approach was proposed by Keys who showed that $a = - 0.5$ produces the best approximation of the original function^[1].

[edit] Use in computer graphics

The bicubic algorithm is frequently used for scaling images and video for display (see bitmap resampling). It preserves fine detail better than the common bilinear algorithm.

[edit] References

^ R. Keys, (1981). "Cubic convolution interpolation for digital image processing". IEEE Transactions on Signal Processing, Acoustics, Speech, and Signal Processing 29: 1153. doi:10.1109/TASSP.1981.1163711.