|
Interpolation Algorithms |
|
|
|
|
|
|
|
Nontrivial geometric transforms, that is, all of them except crop/expand, make use of some pixel interpolation algorithm. For example, when you resample an image to arbitrary dimensions, the resampling process generates a new image whose pixels have to be obtained exclusively from the original pixel data. The same is true for rotation. In general, resampled and/or rotated pixels in the resulting image will not map to exact integer pixel coordinates on the source image, but rather to intermediate locations between source pixels. This leads to interpolation. Many interpolation schemes have been successfully applied to implement geometric transformations of images. Pixel interpolation algorithms range from simplistic procedures like the nearest neighbor algorithm, to sophisticated strategies founded on multiresolution analysis and fractal theory. Most used and practical algorithms, however, follow some sort of polynomial interpolation. A pixel interpolation algorithm must target the detail preservation versus smoothness dilemma; the all-purpose ideal situation, of course, is to achieve a good balance between both paradigms. In this sense, each pixel interpolation algorithm has its own advantages and drawbacks. One must find the algorithm that best matches the requirements of a specific imaging task. Four pixel interpolation algorithms have been implemented in PixInsight LE 1.0. We encourage you to make your own experiments with them to decide what algorithm best suites to your particular imaging problems. If you do so, as we expect, we'll be glad to hear your experience. This is the numerically most accurate interpolation algorithm implemented. We must emphasize the word numerically in the previous sentence, since numerical accuracy does not ensure suitability to process any particular image. As implemented in PixInsight, the bicubic spline interpolation algorithm requires precalculation of second derivatives for all of the source image pixels. This makes the algorithm comparatively the least efficient in terms of memory usage and calculation speed. Bicubic spline interpolation takes an additional parameter: the size in pixels of the block used to construct smooth cubic interpolation spline functions. With the default block size value of 5, this algorithm interpolates each target pixel value from 25 source pixels. At the date of release, our implementation of bicubic spline interpolation is still under development, so enhanced versions are to be expected in incoming releases. Bicubic interpolation is the default pixel interpolation algorithm in PixInsight. It generates each target pixel by interpolation from the nearest sixteen mapped source pixels. Two cubic interpolation polynomials, one for each plane direction, are used. This algorithm yields a good balance between accuracy in detail preservation and smoothness for resampled and rotated images. At the same time, its performance is quite satisfactory as for execution time and memory usage. Bilinear interpolation is functionally identical to bicubic interpolation, except that four source pixels and two linear interpolation functions are used.
Our implementation is based on the paper Bicubic Interpolation for Image Scaling by Paul Bourke. Compared to the rest of algorithms, the bicubic b-spline interpolation algorithm gives by far the smoothest results. In fact, this algorithm usually yields too smooth resampled and rotated images. However, a nice feature of this algorithm is that after bicubic b-spline resampling a slight sharpening can be applied to the image. This method is especially useful to resample down images that must preserve accurate edges, like images containing text or well defined geometrical structures. In these cases, resampling with bicubic b-spline followed by a slight sharpening with unsharp mask or a wavelets transform gives excellent results. |