[Bf-committers] High Quality Interpolation (Cubic B-Spline)

[Matthias Fauconneau]

Hi,

Summary:

Cubic B-Spline is as fast as "bicubic" but much more accurate (sharp
samples, smooth interpolation).

Long Version:

Interpolation is really important for computer graphics, since it is
used for texture filtering and more generally any image resampling
(e.g scale, warp, stabilize, distort).
For my GSOC, I did some research as I needed high quality
interpolation for the lens un/distortion (and also eventually for
subpixel tracking precision).

And I noticed that most applications (and even some papers!) use low
quality methods:
The most commonly used method is Third-Order Keys ("bicubic") because
it is fast to compute, is slightly better than bilinear and has C1
regularity ("smoothness").
For "high quality", truncated or windowed (e.g Lanczos) sinc kernels
are used but they are much slower for no significant quality
improvement.
Sometimes B-Spline are used but badly implemented (no prefilter)
making the sampled data smoother.

B-Spline based interpolators can be computed very quickly (cubic
B-Spline is as fast as Keys bicubic) while providing a much more
accurate interpolation.
They can also be exactly differentiated without additional computation
B-Splines are the most regular interpolant for a given order (e.g
cubic B-Spline is C2).

The ideal interpolant is a sinc with infinite support (no truncation/windowing).
B-Spline and windowed sinc are different approximation of the ideal sinc filter.
Prefiltering effectively give B-Spline interpolation infinite support
making it better than windowed sincs.
If the data wasn't prefiltered, cubic B-Spline sampling would smooth
the data [1 vs 2], it would have the same effect as blurring the
texture.
The prefilter is only needed once per image/texture (and can be
quickly computed) while the sampling is fast.

P.S: Nearest and bilinear are actually B-Spline order 0 and 1.

Links:

[1] No Prefilter:
http://wiki.blender.org/uploads/4/4c/GSoC-interpolation-bad.png
[2] Accurate Interpolation:
http://wiki.blender.org/uploads/c/c3/GSoC-interpolation-cubic.png

Interpolation revisited:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.9421&rep=rep1&type=pdf
(review and benchmark all interpolation method)
Authors C implementation: http://bigwww.epfl.ch/thevenaz/interpolation/
GLSL Cubic B-spline in 4 bilinear taps:
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter20.html
(they forget to prefilter)
Correct CUDA implementation: http://dannyruijters.nl/cubicinterpolation/
Educative sample application: https://gitorious.org/cubic-b-spline-interpolator