The interpolation algorithm, which I called GRI, is proposed here for the first time. It has at least two directions of application. One - to solve the regular resampling problem (in the form of interpolation of numeric data specified at given argument values to obtain a smooth continuous function), the other - for image scaling. This exactly corresponds to how linear and cubic interpolations, when applied to an image, become the bilinear and bicubic. However, it should be noted that the initial motivation for this development was to create a new image resampling algorithm which would insure bicubic-like smoothness, but exceed bicubic in speed. The proposed algorithm is preferable in every case where bicubic is currently used (except when artifacts of bicubic are desirable).
GRI main idea
The main idea of GRI lies in imposition of two additional conditions to the common formulation of the problem of interpolation of numeric data specified on a given data set. Let's assume (1) that the interpolative function passes through the midpoint of each segment defined by each pair of adjacent points and (2) tangent to it in this midpoint coincides with the straight line defined by this pair of points. It is clear that these conditions ensure the continuity of the function and its first derivative in the midpoints. We will search an interpolative function in polynomial form and then it is obvious that the proposed conditions allow to reduce the amount of given points needed for calculation of the smooth curve on the interval between two midpoints of the adjacent segments to the three points which define these two segments. It means that the GRI interpolation in the case of image scaling will consider 9 pixels (3x3) in contrast to bicubic interpolation which takes 16 pixels (4x4) into account. This will provide increased computing speed.
For each desired point do
Algorithm GRI for image scaling
Application of GRI to image scaling is very reminiscent to a similar generalization of linear or cubic interpolation. The key idea is to perform GRI interpolation first in one direction, and then again in the other direction. Of course regular grid significantly simplifies the calculation. In this case, obtaining the value of the GRI interpolating function in one direction (omitting the simple math transformations) is reduced to the following expression
whereand - some grid coordinate.
Therefore GRI interpolation in the given point on the plane can be represented as three calculations of the three intermediate values in one direction and one final application of the formula (4) to these intermediate values in other direction. Thus, the application of GRI to an image is equivalent to a convolution with a 3x3 kernel and it could be implemented significantly faster than bicubic with a 4x4 kernel.
Realization of GRI for image scaling as a DLL
I've realized the GRI algorithm as a DLL based on OpenCV package. Basic version of this realization can be downloaded here and used under the BSD license. Its working interface is very similar to the OpenCV resize function:
The images presented here are for illustrative purposes only.
As seen on the pictures, GRI resampling result
is closer to the original (look at the form of the cross)
and has less ringing artifacts.