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
- 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
- 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
- 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
- Jensen; seems to be a filter you apply after interpolation
- Backprojection; turns another interpolation into some kind of mad
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
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.