Chapter 27: Geometric Transforms and Interpolation

When you rotate or zoom an image, the output pixels no longer land exactly on the grid points of the input; they point between the grid points. Estimating the value at that in-between point from the surrounding pixels is interpolation. It is an unglamorous but foundational operation needed for every geometric transform, and it runs inside backprojection (Chapters 3 and 4), MPR (Chapter 28), and registration (Chapter 34).

Three interpolation methods

The standard methods differ in how many surrounding pixels they mix, and how.

• Nearest neighbor: uses the value of the single closest pixel. It is fast and does not change the original values, which suits transforming label images and masks (the segmentation results of Chapter 32). But zooming produces blocky stairsteps.
• Bilinear: weights the $2\times2$ neighborhood linearly by distance and averages. It is smooth, fast, and the most standard. Edges soften, but the value never exceeds the range of the neighbors.
• Bicubic: weights the $4\times4$ neighborhood with a cubic kernel. It is sharper and smoother than bilinear, but near a step the value slightly exceeds the neighbor range (overshoot, ringing).

The figure above shows it in one dimension. Between the sample points (white dots), nearest fills with steps, linear with straight lines, and cubic with a smooth curve. Notice that the cubic overshoots just after the step. The 2D bilinear and bicubic apply this along both axes. There is also Lanczos interpolation, which uses a wider neighborhood and is sharper still, but with stronger ringing.

Simulation: zoom in and compare

A coarse source image is enlarged to the same display size with nearest, bilinear, and bicubic. The lower the source resolution, the higher the magnification and the clearer the differences. Nearest is blocky, bilinear is smooth, bicubic is sharper, and near the diagonal edge the slight overshoot fringe of bicubic becomes visible.

Downscaling and aliasing

Shrinking an image, the opposite of enlarging, needs a different precaution. Re-sampling a fine pattern onto a coarser grid, in violation of the sampling theorem (Chapter 11), makes stripes or moiré appear that were never there. This is aliasing. To prevent it, apply a low-pass filter (the Gaussian of Chapter 28, for example) before downscaling to remove in advance the high frequencies the grid cannot represent. Downscaling by simply dropping samples produces moiré for this reason.

Key points

For every rotation, zoom, and warp, the output pixels point between the input grid, so interpolation is needed to estimate values from the surrounding pixels. Nearest neighbor keeps values unchanged and suits labels but is blocky; bilinear is smooth and standard; bicubic is sharper but overshoots at steps. When downscaling, the sampling theorem means aliasing (moiré) appears unless a low-pass is applied first. Interpolation is the foundation of every process involving a geometric transform: backprojection, MPR, and registration.

References

• Keys R. Cubic convolution interpolation for digital image processing. IEEE Transactions on Acoustics, Speech, and Signal Processing 29, 1153–1160 (1981).
• Lehmann TM, Gönner C, Spitzer K. Survey: Interpolation Methods in Medical Image Processing. IEEE Transactions on Medical Imaging 18, 1049–1075 (1999).
• Thévenaz P, Blu T, Unser M. Interpolation Revisited. IEEE Transactions on Medical Imaging 19, 739–758 (2000).