Smoothing-Resampling Algorithm (SRALG)  Robust Geometric Resampling Algorithm (RGR)  SRALG-Based Interpolation Algorithm  Free Utilities About the Author

ALGORITHM GRI

© Dmitry Grilikhes, 2013.    If you wish to use the materials on this page over the internet, you are obliged to preserve the link to it.

Introduction

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.



Formally speaking, if xi is the set of the points and yi is the set of corresponding values interpolating function f(x) satisfies the conditions:
(1)  system1

for each x on the segment between the adjacent midpoints

The system of five equations is enough to calculate the five coefficients  ci of 4-th degree spline assumed in the form:

(2)  eq2



Algorithm GRI

For each desired point x_ do

  1. Find closest data point xi.
  2. Calculate left midpoint for xi:
    ml

  3. Calculate right midpoint for xi:
    mr

  4. Calculate left slope:
    left slope

  5. Calculate right slope:
    right slope

  6. Solve the linear system
    (3)  linear system 3,

    using any convenient method and find the coefficients ci

  7. Calculatef(x) by formula (2).


Of course presented algorithm can and should be significantly altered and accelerated if desired interpolation points are not arbitrary but obey any rule.



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

(4)  eq4,

whereto4andto4 - 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:

static GRI3_API void resizeGRI  (InputArray _src, OutputArray _dst, Size dsize,double inv_scale_x, double inv_scale_y);

Tests showed that the predicted above performance gain compared to bicubic with this implementation of GRI is ~20-25%.

To obtain the full version that is more suitable for commercial use, contact me via e-mail.



Demo

The images presented here are for illustrative purposes only.


original
original

bilinear
bilinear

bicubic
bicubic

lanczos
Lanczos

gri
GRI
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.

GRI features:

  • Provides smoothness of the image (like bicubic).
  • ~20-25% faster than bicubic.
  • Less artifacts.

Appendices

  • The MATLAB code below is designed solely for demonstration purposes.
    It has no optimizations of any kind and is only applicable to a curve placed over a regular grid.
    [Show]
  • The MATLAB code below is a commented realization of the GRI algorithm for image resampling.
    [Show]

© Dmitry Grilikhes, 2013.   

If you wish to use the materials on this page over the internet, you are obliged to preserve the link to it.

www.000webhost.com