# Interpolation

Interpolation algorithms! Who would have thought there were so many? Nobody! Here is a list of them:

• Nearest neighbour: find the sample closest to your interpolation point and use its value. It's simple, it's rubbish, there basically no reason to ever use it unless you are like programming for a NES or something
• Linear: look at the samples on either side of your interpolation point, imagine a linear gradient between them, and read off the value at the interpolation point. Very simple, slightly slower than nearest-neighbour but still pretty fast, and reasonably good.
• Bicubic: look at the 4x4 neighbourhood around the interpolation point, fit the values with some sort of cubic function (which can vary; there are two specified in JAI, IIRC), and read the value off it. This is the traditional high-quality option in most image processing tools, even thought it's not the best algorithm ever.
• Stair, aka stepped: iterated application of bicubic interpolation (or any other interpolation, i suppose), where instead of going straight from source to product, you make a series of intermediates. I am suspicious of this. Ah, yes, it's been looked into and it's bunk.
• Lanczos: no idea how this works. Is supported in Apple's Core Image, though. Jensen-Lanczos may be the same, may not. Based on a sinc kernel.
• B-Spline, Catmull-Rom: i guess you fit a spline through your samples and pull values off that.
• Sinc, square sinc, Hamming, Hann, tanh kernels
• Mitchell
• Xin Li, aka new edge directed interpolation, aka NEDI; there iss an improved implementation by a G. D. Haan, apparently; maybe also knoen as Zhao-Xin Lee
• Tschumperle-Deriche: some kind of mad science
• Jensen; seems to be a filter you apply after interpolation
• Backprojection; turns another interpolation into some kind of mad iterative thing

Software which does interpolation using sekrit proprietary algorithms includes Genuine Fractals, Photozoom (aka S-Spline), SAR (many algorithms!), Qimage (just uses Lanczos, i think), Smartscale.

Handy papers include 'Towards an overview of spatial up-conversion techniques' and 'Image resampling' (and its appendix A).

The Interpolate This boards are useful as a source of pointers to algorithms and software, if not expert knowledge.

The Richardson-Lucy algorithm for image reconstruction also sounds interesting; it's some kind of deconvolution. The Tschumperle-Deriche stuff mentioned above also has interesting noise-elimination applications. See also a dude's bookmarks.