Lanczos resampling

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (January 2008)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

Incipit of a piece by Gaspar Sanz. Original, low quality expansion with JPEG artifacts. Open the picture to see the details.

The same image magnified at 500% with Lanczos algorithm. JPEG artifacts were removed changing image's transfer function. Open the picture to see the details.

Lanczos resampling ("Lanzosh") is a multivariate interpolation method used to compute new values for any digitally sampled data. It is often used to resize digital images, but could be used for any other digital signal. In the case of digital image resizing, the Lanczos function indicates which pixels in the original image, and in what proportion, make up each pixel of the final image.

Lanczos filtering gives very high quality results compared to more commonly used but faster techniques such as linear or cubic interpolation because it more closely approximates the optimal resampling filter, the sinc function. While the sinc function is infinite, making it very computationally intensive, the Lanczos function defines an approximation over a given range (the "window"), allowing the implementor the ability to improve the approximation by increasing the size of the window.

Inside the window defined by the radius $a$ , the Lanczos filter is defined as a product of normalized sinc functions. That is, the ideal lowpass filter $sinc(x)$ is windowed by the sinc window function $sinc(x / a)$ . The resulting function is then used as a convolution kernel to resample the input field. In one dimension, its formula is given by:

$L(x) = \begin{cases} \mathrm{sinc}(x)\, \mathrm{sinc} \! \left( \frac x a \right) & -a < x < a, x \ne 0 \\ 1 & x = 0 \\ 0 & \text{otherwise} \end{cases}$

with $a$ a positive integer, typically 2 or 3, controlling the size of the kernel.

In the above, $\mathrm{sinc}(x) \mathrm{sinc} \! \left( \frac x a \right)$ can be expanded to:

$\frac{a \sin(\pi x) \sin \! \left( \frac \pi a x \right) }{\pi^2 x^2}.$

Lanczos kernels for the cases

a = 2

and

a = 3

. Note that the function obtains negative values.

The filter is named after Cornelius Lanczos, because he showed how to use Fourier series and Chebyshev polynomials for various problems where it was not used before.

1 Example code
2 Applications
3 See also
4 External links

[edit] Example code

This example C++ code, performs a 1-dimensional Lanczos transform to resample a signal consisting of 19 samples into 6 samples, and a signal consisting of 7 samples into 26 samples. It is loosely based on code from Imagemagick, and hard coded for the case $a = 3$ .

#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdio>
 
template<int Radius>
static inline double Lanczos(double x)
{
  if (x == 0.0) return 1.0;
  if (x <= -Radius || x >= Radius) return 0.0;
  double tmp = x * M_PI;
  return Radius * std::sin(tmp) * std::sin(tmp / Radius) / (tmp * tmp);
}
 
const int FilterRadius = 3;
 
static inline void Resample
    (const double* source, size_t src_len,  
           double* result, size_t dest_len)
{
    const double blur = 1.0;
    const double factor = dest_len / (double)src_len;
 
    double scale   = std::min(factor, 1.0) / blur;
    double support = FilterRadius / scale;
 
    std::vector<double> contribution(std::min(src_len, 5+size_t(2*support)));
    /* 5 = room for rounding up in calculations of start, stop and support */
 
    if (support <= 0.5) { support = 0.5 + 1E-12; scale = 1.0; }
 
    for (size_t x=0; x<dest_len; ++x)
    {
        double center = (x+0.5) / factor;
        size_t start = (size_t)std::max(center-support+0.5, (double)0);
        size_t stop  = (size_t)std::min(center+support+0.5, (double)src_len);
        double density = 0.0;
        size_t nmax = stop-start;
        double s = start - center+0.5;
        result[x] = 0;
        for (size_t n=0; n<nmax; ++n, ++s)
        {
            contribution[n] = Lanczos<FilterRadius> (s * scale);
            density += contribution[n];
            result[x] += source[start+n]*contribution[n];
        }
        if (density != 0.0 && density != 1.0)
        {
            /* Normalize. */
            result[x] /= density;
        }
    }
}
 
static void Test(const double* signal, size_t origlen, size_t newlen)
{   
    std::vector<double> newsig(newlen);
    Resample(signal, origlen, &newsig[0], newlen);
 
    size_t maxlen = std::max(origlen, newlen);
 
    std::printf("Original signal:\n");
    size_t bpos = 0;
    for (size_t a=0; a<origlen; ++a)   
    {
        size_t pos = a*(maxlen-1)/(origlen-1);
        while (bpos < pos) { ++bpos; std::printf(" .."); }
        std::printf("%3d", (int)(signal[a]*10)); ++bpos;
    }
    std::printf("\nResampled signal:\n");   
    bpos = 0;
    for (size_t a=0; a<newlen; ++a)
    {
        size_t pos = a*(maxlen-1)/(newlen-1);
        while (bpos < pos) { ++bpos; std::printf(" .."); }
        std::printf("%3d", (int)(newsig[a]*10)); ++bpos;
    }
    std::printf("\n-----\n");
}
 
int main(void)
{
    /* Test resampling into a smaller size */
    double smp1[] = { 0,9,0,0,9,0,0,0,9,0,0,0,9,9,9,9,9,9,9 };
    Test(smp1, sizeof(smp1)/sizeof(*smp1), 6);
 
    /* Test resampling into a larger size */
    double smp2[] = {9,0,3,0,9,6,9};
    Test(smp2, sizeof(smp2)/sizeof(*smp2), 26);
}

Example output:

Original signal:
  0 90  0  0 90  0  0  0 90  0  0  0 90 90 90 90 90 90 90
Resampled signal:
 33 .. .. 24 .. .. .. 20 .. .. 25 .. .. .. 91 .. .. .. 89
-----
Original signal:
 90 .. .. ..  0 .. .. .. 30 .. .. ..  0 .. .. .. 90 .. .. .. 60 .. .. .. .. 90
Resampled signal:
107 95 77 52 23  1 -3  9 25 29 19  4 -2  7 33 65 87 92 83 68 59 63 74 84 92 96
-----

As can be observed from the results, the values given by the algorithm are not exact copies of the source values ― they even extend beyond the original range of the samples ― but the general outline is retained when resampled to smaller size, and predicted when resampled to larged size. Among many uses, the algorithm can be applied to audio signal and image data.

Two-dimensional lanczos resampling of images can be performed by first scaling each scanline horizontally, then scaling each resulting column vertically. Such action can be optimized by handling each scanline/column in the inner loop, reusing the same contribution array.