Where can I find a good read about bicubic interpolation and Lanczos resampling?

Question

I want to implement the two above mentioned image resampling algorithms (bicubic and Lanczos) in C++. I know that there are dozens of existing implementations out there, but I still want to make my own. I want to make it partly because I want to understand how they work, and partly because I want to give them some capabilities not found in mainstream implementations (like configurable multi-CPU support and progress reporting).

I tried reading Wikipedia, but the stuff is a bit too dry for me. Perhaps there are some nicer explanations of these algorithms? I couldn't find anything either on SO or Google.

Added: Seems like nobody can give me a good link about these topics. Can anyone at least try to explain them here?

Answer 1

The basic operation principle of both algorithms is pretty simple. They're both convolution filters. A convolution filter that for each output value moves the convolution functions point of origin to be centered on the output and then multiplies all the values in the input with the value of the convolution function at that location and adds them together.

One property of convolution is that the integral of the output is the product of the integrals of the two input functions. If you consider the input and output images, then the integral means average brightness and if you want the brightness to remain the same the integral of the convolution function needs to add up to one.

One way how to understand them is to think of the convolution function as something that shows how much input pixels influence the output pixel depending on their distance.

Convolution functions are usually defined so that they are zero when the distance is larger than some value so that you don't have to consider every input value for every output value.

For lanczos interpolation the convolution function is based on the sinc(x) = sin(x*pi)/x function, but only the first few lobes are taken. Usually 3:

lanczos(x) = {
    0 if abs(x) > 3,
    1 if x == 0,
    else sin(x*pi)/x
}

This function is called the filter kernel.

To resample with lanczos imagine you overlay the output and input over eachother, with points signifying where the pixel locations are. For each output pixel location you take a box +- 3 output pixels from that point. For every input pixel that lies in that box, calculate the value of the lanczos function at that location with the distance from the output location in output pixel coordinates as the parameter. You then need to normalize the calculated values by scaling them so that they add up to 1. After that multiply each input pixel value with the corresponding scaling value and add the results together to get the value of the output pixel.

Because lanzos function has the separability property and, if you are resizing, the grid is regular, you can optimize this by doing the convolution horizontally and vertically separately and precalculate the vertical filters for each row and horizontal filters for each column.

Bicubic convolution is basically the same, with a different filter kernel function.

To get more detail, there's a pretty good and thorough explanation in the book Digital Image Processing, section 16.3.

Also, image_operations.cc and convolver.cc in skia have a pretty well commented implementation of lanczos interpolation.