Bicubic interpolation

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 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 spline interpolation

Suppose the function values f and the derivatives f_x, f_y and f_{xy} 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_{ij}.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) = extstyle 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} + 2a_{20} + 3a_{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) = extstyle 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} + 2a_{02} + 3a_{03}
# f_y(1,1) = p_y(1,1) = extstyle sum_{i=0}^3 sum_{j=1}^3 a_{ij} j

And four equations for the cross derivative xy.
# f_{xy}(0,0) = p_{xy}(0,0) = a_{11}
# f_{xy}(1,0) = p_{xy}(1,0) = a_{11} + 2a_{21} + 3a_{31}
# f_{xy}(0,1) = p_{xy}(0,1) = a_{11} + 2a_{12} + 3a_{13}
# f_{xy}(1,1) = p_{xy}(1,1) = extstyle 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) = extstyle sum_{i=1}^3 sum_{j=0}^3 a_{ij} i x^{i-1} y^j
:p_y(x,y) = extstyle sum_{i=0}^3 sum_{j=1}^3 a_{ij} x^i j y^{j-1}
:p_{xy}(x,y) = extstyle 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] imes [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.

Bicubic convolution algorithm

Bicubic spline interpolation requires the solution of 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) = egin{cases}1 & ext{for } x = 0\ (a+2)|x|^3-(a+3)|x|^2+1 & ext{for } 0 < |x| < 1 \ a|x|^3-5a|x|^2+8a|x|-4a & ext{for } 1 < |x| < 2 \ 0 & ext{otherwise}end{cases}where a is usually set to -0.5 or -0.75. Note that W(0)=1 and W(n)=0 for all nonzero integers n.

This approach was proposed by Keys who showed that a=-0.5 (which corresponds to cubic Hermite spline) produces the best approximation of the original functioncite journal
author = R. Keys,
year = 1981
title = Cubic convolution interpolation for digital image processing
journal = IEEE Transactions on Signal Processing, Acoustics, Speech, and Signal Processing
doi = 10.1109/TASSP.1981.1163711
volume = 29
pages = 1153
] .

If we use the matrix notation for the common case a=-0.5, we can express the equation in a more friendly manner::p(t) = frac{1}{2}egin{bmatrix}

1 & t & t^2 & t^3 \

end{bmatrix}egin{bmatrix}

0 & 2 & 0 & 0 \-1 & 0 & 1 & 0 \2 & -5 & 4 & -1 \-1 & 3 & -3 & 1 \

end{bmatrix}egin{bmatrix}

a_{-1} \a_0 \a_1 \a_2 \

end{bmatrix}for t between 0 and 1 for one dimension (must be applied once in x and again in y)

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.

References

ee also

* Anti-aliasing
* Bézier surface
* Bilinear interpolation
* Cubic Hermite spline, the one-dimensional analogue of bicubic spline
* Lanczos resampling
* Sinc filter
* Spline interpolation

External links

* [http://www.geovista.psu.edu/sites/geocomp99/Gc99/082/gc_082.htm Application of interpolation to elevation samples]
* [http://www.all-in-one.ee/~dersch/interpolator/interpolator.html Comparison of interpolation functions]
* [http://sepwww.stanford.edu/public/docs/sep107/paper_html/node20.html Interpolation theory]
* [http://www.npac.syr.edu/projects/nasa/MILOJE/final/node36.html Lagrange interpolation]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • 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

  • bicubic — adjective Of or pertaining to interpolation in two dimensions using cubic splines or other polynomials (technique for sharpening enlargements of digital images) …   Wiktionary

  • Stairstep interpolation — In image processing, stairstep interpolation is a general method for interpolating the pixels after enlarging an image. The key idea is to interpolate multiple times in small increments using any interpolation algorithm that is better than… …   Wikipedia

  • 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… …   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

  • Tricubic interpolation — In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in 3D space of a function defined on a regular grid. The approach involves approximating the function locally by an… …   Wikipedia

  • Demosaicing — A demosaicing algorithm is a digital image process used to reconstruct a full color image from the incomplete color samples output from an image sensor overlaid with a color filter array (CFA). Also known as CFA interpolation or color… …   Wikipedia

  • Image scaling — In computer graphics, image scaling is the process of resizing a digital image. Scaling is a non trivial process that involves a trade off between efficiency, smoothness and sharpness. As the size of an image is increased, so the pixels which… …   Wikipedia

  • Bézier surface — Bézier surfaces are a species of mathematical spline used in computer graphics, computer aided design, and finite element modelling. As with the Bézier curve, a Bézier surface is defined by a set of control points. Similar to interpolation in… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

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