Lanczos resampling

Incipit of a piece by Gaspar Sanz. Original, low quality scansion 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 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 Lanzos function indicates which pixels in the original image, and in what proportion, make up each 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. 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\neq 0\\1&x=0\\0&{\text{otherwise}}\end{cases}}$ with $a$ an arbitrary positive integer.

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 kernel. 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.

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 sets $a=3$. (Note, that the code below is not written in standard C++ and cannot be expected to compile with a standard C++ compiler, since it uses certain non-standard language extensions. GNU C++ compiler should be able to compile it though.)

#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdio>

static inline double Lanczos(double x)
{
  if(x == 0.0) return 1.0;
  if(x <= -3.0 || x >= 3.0)return 0.0;
  double tmp = x * M_PI, tmp2 = tmp / 3.0;
  return std::sin(tmp) * std::sin(tmp2) / (tmp * tmp2);
}   

    
static inline void Resample
    (const double* source, size_t src_len,  
           double* result, size_t dest_len)
{
    const double filter_support = 3.0;
    const double blur = 1.0;
    const double factor = dest_len / (double)src_len;
    
    double contribution[dest_len];
    
    double scale   = std::min(factor, 1.0) / blur;
    double support = filter_support / scale;
    
    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;
        for(size_t n=0; n<nmax; ++n, ++s)
        {
            contribution[n] = Lanczos(s * scale);
            density += contribution[n];
        }
        if(density != 0.0 && density != 1.0)
        {
            /* Normalize. */
            for(size_t n=0; n<nmax; ++n)
                contribution[n] /= density;
        }
        
        result[x] = 0;
        for(size_t n=0; n<nmax; ++n)
            result[x] += source[start+n] * contribution[n];
    }
}

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.

Applications

The Lanczos resampling kernel is known to be used in:

• VirtualDub
• IrfanView
• AviSynth
• FFDShow
• GraphicConverter
• ImageMagick
• MPlayer
• Mac OS X - Quartz (graphics layer) and vImage
• Avidemux
• Lightwave
• Pixel image editor (1.0 Beta 8 and above)
• GIMP (2.3 and above)
• Panorama Tools (as sinc interpolation)
• Mental Ray
• XnView
• Google Picasa
• Dr. Divx 2.0 OSS

See also

• Bicubic interpolation
• Bilinear interpolation
• Spline interpolation
• Nearest neighbor interpolation

External links

• PDF from Apple Computer
• Resampling Kernels