Bilinear and bicubic spline interpolation

This article is outdated due to the last updates in the ALGLIB package.
It will be rewritten soon. Till then you may find information you need in the reference manual.

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 2S/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 2S/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

This article is licensed for personal use only.

Download ALGLIB for C++ / C# / ...

ALGLIB Project offers you two editions of ALGLIB:

ALGLIB Free Edition:
delivered for free
offers full set of numerical functionality
extensive algorithmic optimizations
no low level optimizations
non-commercial license

ALGLIB Commercial Edition:
flexible pricing
offers full set of numerical functionality
extensive algorithmic optimizations
high performance (SMP, SIMD)
commercial license with support plan

Links to download sections for Free and Commercial editions can be found below:

ALGLIB 3.12.0 for C++

C++ library.
Delivered with sources.
Monolithic design.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for C#

C# library with native kernels.
Delivered with sources.
VB.NET and IronPython wrappers.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for Delphi

Delphi wrapper around C core.
Delivered as precompiled binary.
Compatible with FreePascal.
Editions:   FREE   COMMERCIAL

ALGLIB 3.12.0 for CPython

CPython wrapper around C core.
Delivered as precompiled binary.
Editions:   FREE   COMMERCIAL