Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

GDAL includes a resampling method beyond the normal mix of nearest neighbor, bilinear, cubic and splines: "Lanczos windowed sinc resampling". I understand that its a convolution filter, but unlike images where results tend to be subjective, the resampling used for spatial data has other implications. What's Lanczos and how does using it affect the output?

share|improve this question
4  
This is an exact duplicate of stackoverflow.com/questions/1854146/… which has a good answer. –  whuber Jun 12 '11 at 17:50
    
Section 4 of a 1979 paper by Claude Duchon may be helpful. –  whuber Jun 12 '11 at 17:53

3 Answers 3

up vote 22 down vote accepted
+150

What is Lanczos resampling?

Although the theory is described in an early paper and the Wikipedia article, a "feel" for resampling methods is best obtained by computing them on simple or standard images. This can be a vast topic, requiring extensive experimentation, but some simplifications are available:

  • These operators work separately in each color channel. Therefore it suffices to study how they work on a monochromatic ("black and white") image.

  • Most convolution operators used in image processing work the same way in the x and y directions and independently in both directions. In effect, they are really one dimensional operators applied first to the rows and then to the columns. This means we can study them by studying "1D" images, which can be plotted in detail.

  • Everything we need to know about a linear operator (which includes all convolution operators) can be inferred from how an operator works on the simplest non-constant image of all: this is a sudden jump from one value to another.

Let's look at an illustration of several popular resampling methods. Actually, we need two illustrations: one to show what happens in "downsampling," where the new image is coarser than the old, and another to look at "upsampling," where the new images is refinement of the old. Let's start with the latter, because it shows more detail.

Upsampling

Resampling from 7 to 80 cells as images

The original 7 by 7 image on the left is really one-dimensional because each row is the same. The resampling occurs across the columns. The dimension of the other five images is 80 by 80, showing in detail how each method interpolates between the original coarse pixels. Nearest-neighbor sampling retains the sharp division between dark and light while the other four methods blur the intervening region to some extent. Notably, the Lanczos resampler creates some regions that are darker than any in the original and others that are lighter than any in the original. (This can have implications for GIS work, because such an extrapolation of the original values can potentially cause the new values to be invalid. They can also extend beyond the range of the original color map, sometimes causing the extreme values in the resampling image to be rendered incorrectly. This is a problem with bicubic convolution resampling in ArcGIS, for example.)

(NB: The "bicubic" method shown here is a bicubic spline, not the "bicubic convolution" of ArcGIS.)

Using lightness to depict image values, although natural, is not very precise. The next illustration rectifies this by graphing the cell values (vertical axis) by column (horizontal axis).

Resampling from 7 to 80 cells as plots

Lower values on the graphs correspond to darker parts of the images. A thoughtful examination of the original uncovers a hidden assumption: although the original image looks like a sharp jump from dark to light, the jump actually occurs over one-seventh (1/7) of the extent of the columns. Who is to say what really happens in that interval in the original scene the image is depicting? We therefore should not be too critical of differences among the resampling methods that occur within this short interval: each one is giving a different but potentially equally valid rendering of what might be occurring in the original scene. In this sense, it is no longer apparent that nearest neighbor sampling is the most faithful interpolation method.

One conclusion we should draw is that the accuracy of any upsampling method depends on the nature of the underlying scene. If the scene consists of values that should smoothly vary from one point to the next, then the nearest neighbor method is likely to be the least faithful way of resampling among those shown.

Downsampling

Downsampled images

Here we see the result of downsampling a 16 by 16 image to 8 by 8 images (a 2 by 2 aggregation). Nearest neighbor accurately retains the sharp boundary. Lanczos differs from the others by enhancing the apparent sharpness. A close look shows that it darkens the dark area on one side of the boundary and lightens the light area on the other side. The graphs clarify this:

Graphs of downsampled images

The bilinear, bicubic, and Gaussian resamplers show characteristics of convolution operators that have all positive weights (or very small negative weights): they average, or "smear," neighboring values. In downsampling this causes sharp features to be blurred. The extent of the blur depends on the width of the kernel. Like these others, the Lanczos resampler also blurs the jump, but it "overshoots" it on both sides. That's the contrast enhancement seen just above in the images themselves. Because of this tendency to increase contrast (the local differences between the highs and lows in the image), the Lanczos resampler is often called a "sharpening filter." These graphs show that this characterization requires a nuanced understanding, because evidently it does not actually reduce the averaging of values on both sides of the jump. At pixel 4, its value of 0.56 is comparable to the values computed by the other convolution filters.

How does using it affect the output?

Let's take a look at what happens in a more complex image.

Resamples of a complex image

The original, which is a 13 by 13 image now includes a pattern with the highest possible spatial frequency (alternating between light and dark with every column at the right). We cannot hope to reproduce such features when downsampling: the smaller amount of pixels simply cannot hold all this information. Let's focus, then, on what happens when such an image is upsampled. If we care about faithful reproduction of the scene, we will want this high-frequency pattern to be reproduced accurately.

The smaller images are resampled to 25 by 25 pixels: almost, but not quite, a 2:1 refinement. To my eye, the Lanczos and bilinear methods reproduce the stripes most sharply among the four convolution resamplers. Nearest neighbor is, of course, the most faithful (because it cannot average values at all).

Graphs of the complex image resampled

These graphs of the same results show that the Lanczos resampler was able to maintain the contrast in the stripes (as seen by the size of the vertical swings from lows to highs) at the expense of introducing a variation of intensity within the constant-value light area in the middle of the image (pixels 5, 6, 7 of the original). This variation shows up as stripe-like artifacts within the light part of the image (the middle). Of the resamplers shown here, it is alone in introducing such spurious detail.

What is it useful for in a spatial application?

Evidently, Lanczos resampling is not a panacea or omnibus solution to resampling. It is superior to many other convolution resamplers in maintaining (or even enhancing) local contrast. This can be useful when the resampled image is intended for viewing identification of detailed features or boundaries. When the resampled image will subsequently be analyzed or processed, Lanczos resampling may increase the ability to detect edges and linear features.

When the resampled image will be analyzed in other ways, though, the benefits of Lanczos resampling are doubtful. It typically will (artificially) increase local measures of spatial variability, such as focal ranges and focal standard deviations. It will not affect spatial means on the whole--like the other convolution resamplers, it is usually normalized (which means it's a local weighted average, with no bias introduced)--but it may increase some local averages and decrease others compared to the other resamplers.

The (necessarily brief) evaluation here suggests the Lanczos resampler generally should not be used for downsampling: for that application, it appears to offer nothing that simpler (and more commonly available) methods have, which retaining the potential disadvantage of extrapolating beyond the original range of data values.

Afterword: a general comment

The investigation described here is an example of what anybody can do when they have a question about how a GIS operation works. It uses the GIS itself as the subject of the investigation: to know what some operation or analytical method does, simply apply it under controlled experimental conditions. In this case that amounts to constructing simple test images, resampling them according to available methods, and examining the results.

There are three critical aspects of this approach to learning about how GIS works:

  1. Theory. The experimentation usually cannot be done "blind": it helps to know some theory. We don't usually need to know much, but we need the basics. In this case, the theory of convolutions greatly reduced the number and types of images that we need to experiment with. We didn't need to know anything about Fourier analysis, etc. (Make no mistake, such knowledge is beneficial. But lack of specialized knowledge of this sort shouldn't stop us.)
  2. Practice. By using our GIS itself to perform the experiment, we are able to see what it actually does. This avoids disconnects between theory (which tells us what the software should do) and practice (which is what it really does).
  3. Quantification. Unless the question concerns visual perception, for evaluating the results we should not rely solely on looking at maps (or, in this case, images). To get the best information, we need to quantify the output (done here with graphs) and, often, describe and summarize it with statistical methods.
share|improve this answer
    
An outstanding answer, thanks whuber! –  matt wilkie Aug 30 '13 at 19:38

You might know Lanczos filters or similar type of filters from your image programs, where they are often called 'sharpening filters'. A good example from this forumtopic: The first image shows the original file, and next to it how it would look like after reducing the grid size if you use a smooth interpolation method (like bicubic downsampling).

http://peltarion.eu/img/comp/moire/D_lanczos3.jpg However, if you apply a Lanczos filter to this image, or use it to resample, the differences are amplified, you could say that the contrast is locally increased. enter image description here

In the case of spatial data this can be very useful: imagine you are trying to reduce a gridded polygon map, or if you want to run algorithms which rely on edge detection (eg digitize a scanned polygon map, image segmentation (example) ).

On the other hand, you nay loose some spatial accuracy. Imagine that the 16x16 map represents air pollution in a city, than the resampling which uses the mean will more adequately represent the mean air polution within that grid cell.

share|improve this answer
    
I don't think these images are what you claim. The top right clearly is not the cell mean; if it were, the vertical stripes in its upper left quadrant wouldn't be there. Some form of "sharpening" was applied to that image to get the one beneath it (lower right), which is falsely aliased: this is not preservation of features, but creation of artifacts. Because (almost) all filters are unit normalized, including Lanczos filters, your point about the mean applies to every one of them, not just an unweighted neighborhood mean, and therefore is not a distinguishing characteristic. –  whuber Sep 2 '11 at 14:58
    
I've integrated your comments. But within the cell, the smooth interpolator would most likely yield a better prediction –  johanvdw Sep 2 '11 at 15:29

From Wikipedia:

Lanczos resampling (Hungarian pronunciation: [ˈlaːntsoʃ]) is an interpolation method used to compute new values for sampled data. It is often used in multivariate interpolation, for example for image scaling (to resize digital images), but can be used for any other digital signal. The Lanczos kernel indicates which samples in the original data, and in what proportion, make up each sample of the final data. 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.

Application: The Lanczos filter is a windowed form of the sinc filter, a theoretically optimal "brick-wall" low-pass filter. The sinc function is infinite in extent, and thus not directly usable in practice. Instead, one uses approximations, called windowed forms of the filter, as discussed in window functions: filter design, and the Lanczos filter is one such windowing. The windows vanish outside of a range, and using larger ranges allows one to improve accuracy in exchange for more computation.

Evaluation: The Lanczos filter has been compared with other filters, particularly other windowing of the sinc filter. Some have found the Lanczos (with a = 2) the "best compromise in terms of reduction of aliasing, sharpness, and minimal ringing", compared with truncated sinc and the Barlett, cosine, and Hann windowed sinc.

Limitation: Because the kernel assumes negative values for a > 1, output values can be negative even with non-negative input. Negative values are out of bounds for image signals and cause clipping artifacts. Negative lobes also induce ringing artifacts.

However, both undershoot and ringing are reduced compared to the (non-windowed) sinc filter, due to the windowing; the ringing is particularly small, as the positive side lobe size demonstrates, especially for a = 2.

share|improve this answer
    
Why down vote? What is wrong with this answer? I have given the original link as well. –  Chethan S. Jun 12 '11 at 16:27
6  
I don't see how the wiki extract answers the question of what effects the Lanczos filter has on spatial data and what it would be useful for. –  underdark Jun 12 '11 at 17:00
    
That's true. I just gave the answer in a general sense for What's Lanczos and how does using it affect the output? –  Chethan S. Jun 12 '11 at 17:03
8  
Most of this Wikipedia article is too vague to be helpful (as others have previously noted). The answer is indeed in the very last sentence, but would be understandable only by someone who knows what "undershoot" and "ringing" are (aka the "Gibbs oscillation" in 2D), knows what is being referred to by the "positive side lobe," and deeply understands the relationships between kernel shapes and their effects on Fourier transforms. In short, to be intelligible and useful this answer needs some amplification. –  whuber Jun 12 '11 at 17:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.