The main peculiarity of two-dimensional interpolation is that most two-dimensional algorithms are applicable only with rectilinear grids oriented to axes. It is this grid that is used by the two most important interpolation algorithms. These algorithms are: bilinear spline interpolation and bicubic spline interpolation.

Bilinear spline

The bilinear function is bivariate function f(t,u) which is linear in t when u is fixed and vice versa. The bilinear spline is a two-dimensional generalization of a one-dimensional linear spline and has the same pros and cons. It consists of bilinear functions which are defined in each grid square as having prescribed values. This interpolation method is simple and fast. The main disadvantage is the discontinuity of a derivative in the grid square boundaries. Besides, this method is relatively inaccurate.

The bilinear spline is constructed by using the BuildBilinearSpline subroutine. The result of this subroutine is a coefficient table which is passed into the SplineInterpolation2D subroutine. The algorithm of the coefficient table construction is not considered here, but it is described in Numerical Recipes ^[1] and in Wikipedia ^[2].

Bicubic spline

In many cases, the bilinear splines are too inaccurate. Derivative discontinuity also sometimes prevents this method from being used. In such cases, the problem could be solved by using the bicubic spline which guarantees the continuity of the first derivatives dS/dX and dS/dY, as well as the continuity of a cross-derivative d ²S/dXdY.

It is similar to one-dimensional splines, but there are some differences. The cubic spline guarantees the continuity of the first and second function derivatives. Bicubic spline guarantees continuity of only gradient and cross-derivative. Second derivatives could be discontinuous.

To construc at bicubic spline you need to know the function values in the grid nodes as well as the values of their gradient and cross-derivative. If you know all these values, you can start calculating spline coefficients. However, in practice, we usually know only the function values, and we need to calculate the gradient and cross-derivative values by ourselves (e.g. using difference scheme). In this module the following approach is implemented. First, on the basis of the function values table a sequence of one-dimensional splines is constructed. Then, these slpines are differentiated, and so we get gradient and cross-derivative values. After that the bicubic function coefficients could be easily calculated using the values we have got (this algorithm is described in National Recipes ^[1] and in Wikipedia ^[3]).

The bicubic spline is constructed by using the BuildBicubicSpline subroutine. The result of this subroutine is a coefficient table which is passed into the SplineInterpolation2D subroutine (this subroutine is applied to both bilinear and bicubic splines).

Another spline operations

Besides spline value calculation, this module supports other spline operations. Each of the following subroutines uses a coefficient table constructed by using BuildBilinearSpline or BuildBicubicSpline subroutines.

The SplineDifferentiation2D subroutine differentiates the given spline: it calculates first the derivatives dS/dX and dS/dY as well as the cross-derivative d ²S/dXdY. To create a copy of the coefficient table you can use the Spline2DCopy subroutine. To unpack the spline (i.e. get its coefficients in readable form), use the SplineUnpack2D subroutine. The spline arguments linear transformation is performed by using the Spline2DLinTransXY subroutine. The linear spline transformation is performed by using the Spline2DLinTransF subroutine.

Bilinear and bicubic resampling

One more problem which can be solved by using this module is resampling. Resampling is a problem of transition from the grid of M₁ ·N₁  nodes to the grid of M₂ ·N₂  nodes of the same area and calculation of function values in new grid. At that, the new grid could be more or less dense than the old one.

Resampling is a calculation of the function values using function values in another points, i.e. interpolation problem. But this case is special. We need to calculate the function values not in arbitrary points but in grid nodes. After that we get a new grid and do not return to the resource-intensive interpolation. Thus it is reasonable to implement a special subroutine solving this problem.

As two-dimensional splines could be either bilinear or bicubic, resampling could be bilinear or bicubic too. The first is performed by using BilinearResampleCartesian, the second is performed by using the BicubicResampleCartesian subroutine.

Links

1. '3.6 Interpolation in Two or More Dimensions', Numerical Recipes in C, Second Edition (1992)
2. 'Bilinear interpolation', Wikipedia
3. 'Bicubic interpolation', Wikipedia

Report a bug

C#

C# 1.0 source.
spline2d.csharp.zip - Bilinear and bicubic spline interpolation

C++

C++ source.
spline2d.cpp.zip - Bilinear and bicubic spline interpolation
ablas.zip - optimized basic linear algebra subroutines with SSE2 support (for C++ sources only)

Delphi

Delphi source.
Can be compiled under FPC (in Delphi compatibility mode).
spline2d.delphi.zip - Bilinear and bicubic spline interpolation

Visual Basic 6

Visual Basic 6 source.
spline2d.vb6.zip - Bilinear and bicubic spline interpolation

Zonnon ^beta

Zonnon source.
Zonnon is an experimental language developed at ETH Zurich.
See www.zonnon.ethz.ch for more information.
spline2d.zonnon.zip - Bilinear and bicubic spline interpolation