The most important new feature we have implemented in the latest versions of the PixInsight platform (PixInsight Core 1.0.54.363 and PixInsight Class Library (PCL) 1.0.33.165) is a set of new pixel interpolation algorithms.
Pixel interpolation algorithms are crucial for processes involving geometric transformations, with the exception of non-interpolating procedures such as IntegerResample (pixel binning) and FastRotation (rotate +/-90 and 180 degrees, and specular transformations). In particular, the new pixel interpolation algorithms are directly available to the user in the Resample, Rotation and DynamicCrop standard processes. They are also used internally by other processes such as DynamicAlignment and ChannelMatch.
The pixel interpolation problem is quite simple conceptually. A digital image is a discrete representation composed by samples distributed on a uniform, rectangular lattice. Each sample (or set of samples in multichannel or color images) is what we identify as a
pixel. A pixel interpolation is necessary to obtain new pixel values at arbitrary --not necessarily integer-- coordinates.
In this figure, big dots represent existing pixels. A new pixel value is desired at the location represented by the small dot, defined by offsets dx and dy measured from the nearest pixel by coordinate truncation. This problem arises in a wide variety of geometric transformations; for example, to resize an image by arbitrary scaling ratios, new pixel values must be obtained from existing image data in this way.
New Pixel Interpolation AlgorithmsThe latest versions of the PixInsight platform come with a redesigned set of interpolation algorithms. This includes simple interpolations that were not present in previous versions (nearest neighbor), highly improved implementations (bicubic spline), and new, high-performance algorithms that address the subsampling and smooth upsampling tasks in an extremely efficient and versatile way (Mitchell-Netravali family of cubic filters).
At the end of this tutorial we have included a demonstrative example that compares the performance of all algorithms available for downsampling and upsampling a difficult test image. We offer now a brief description of these interpolation algorithms, including references.
Nearest NeighborThis is the simplest possible interpolation algorithm. Nearest neighbor interpolation selects the value of the nearest pixel by rounding the coordinates of the desired interpolation point.
BilinearA slightly more sophisticated interpolation method. The bilinear algorithm interpolates from the nearest four mapped source pixels. It builds and evaluates two linear interpolation functions, one for each plane direction.
Bicubic SplineThis new algorithm replaces our old Bicubic and Bicubic Spline algorithms. This is a high performance pixel interpolation that gives outstanding results, both in calculation speed and in quality of results. It is usually the best choice when not too radical downsampling operations are involved in geometrical transformations.
Bicubic interpolation algorithms interpolate from the nearest sixteen mapped source pixels. Our implementation uses the following cubic spline function as a separable filter to perform a convolution interpolation:
f(x) = (a+2)*x^3 - (a+3)*x^2 + 1 for 0 <= x <= 1
f(x) = a*x^3 - 5*a*x^2 + 8*a*x - 4*a for 1 < x <= 2
f(x) = 0 otherwise
Reference: Keys, R. G. (1981),
Cubic Convolution Interpolation for Digital Image Processing, IEEE Trans. Acoustics, Speech & Signal Proc., Vol. 29, pp. 1153-1160.
The
a constant parameter of the cubic spline (-1 <= a < 0) controls the depth of the negative lobes of the interpolation function. In our implementation we have set a fixed value a=-1/2 (see for example Parker, J. Anthony, et al. (1983),
Comparison of Interpolating Methods for Image Resampling, IEEE Trans. Medical Imaging, Vol. 2, No. 1).
Our implementation includes an automatic clamping mechanism to avoid discontinuity problems when interpolating linear images. This is necessary because the cubic spline function has negative lobes that may cause out-of-range interpolated values in presence of wild variations between neighbor pixels, which occur frequently in linear raw images.
Bicubic B-SplineAs bicubic spline interpolation, the bicubic B-spline interpolation algorithm also interpolates from the nearest sixteen source pixels. However, this algorithm uses B-spline interpolating functions instead of cubic splines, which in general yield quite (too?) smooth results.
This implementation is based on
Bicubic Interpolation for Image Scaling, by Paul Bourke. It performs a convolution with a nonseparable 2-D filter, so its performance is O(n^2). This is very poor compared to bicubic spline interpolation, which uses a convolution with a separable filter whose complexity is O(n). However, bicubic B-spline has interesting characteristics of smoothness that make it a good option in some cases.
Interpolation by Mitchell-Netravali parameterized cubic filtersThis is actually a category that comprises three different interpolations: Mitchell-Netravali cubic filter, Catmull-Rom spline filter, and cubic B-spline filter.
This category interpolates by convolution with two-parameter separable cubic filters, as described in Don P. Mitchell, Arun N. Netravali (1988),
Reconstruction Filters in Computer Graphics, Computer Graphics, Vol. 22, No. 4, pp. 221-228.
These interpolations are particularly good to downsample images, as we'll see in an interesting comparison later on this post.
- The Mitchell-Netravali cubic filter has the parameters recommended by the authors in the original paper (B=C=1/3). This filter has really excellent characteristics in our opinion; it is half way between sharpness (ringing) and smoothness.
Compared to Mitchell-Netravali:
- The Catmull-Rom spline filter yields sharper results.
- The B-spline cubic filter yields smoother results.
Downsampling TestIn this tutorial we have performed a test with a difficult target, which you can see below.
The test consists of downsampling the original image to 400 pixels tall, using the different interpolation algorithms available. This is roughly a 1:11 scaling factor. This is a difficult test case because the image has many high-contrast, small-scale structures, as the tree branches projected over the sky for example. These structures may easily lead to pixellation due to poor (or inappropriate / inappropriately applied) pixel interpolation algorithms.
Below you can see the results of this test. Resulting images have been upsampled 2:1 without interpolation (IntegerResample), in order to facilitate comparisons.
Nearest Neighbor
Bilinear
Bicubic Spline
Bicubic B-Spline (Bourke)
Mitchell-Netravali Cubic Filter
Catmull-Rom Spline Filter
Cubic B-Spline Filter
From the above results, it is evident that the new filter interpolation algorithms (particularly Mitchell-Netravali and Catmull-Rom) can be extremely efficient for downsampling images. The cubic B-spline filter interpolation is probably too smooth. The bicubic spline and bicubic B-spline algorithms give nearly the same poor results as nearest neighbor and bilinear.
This doesn't mean that bicubic spline is a bad interpolation algorithm; it is actually a high-performance, high-quality interpolation. It is just that bicubic spline is not well suited for so radical downsampling operations (1:11 in this case), as happens with all algorithms that interpolate from a fixed-size pixel boundary. Mitchell-Netravali is in our opinion the best option in this case.
Our implementation includes a user-adjustable smoothness parameter in the Resample process. This parameter allows you to fine-tune the degree of smoothness in the downsampled result. The default value is 1.5, but you can vary this parameter in the range from 1 to 5. You can see a few comparisons below.
Mitchell-Netravali Cubic Filter, Smoothness = 1.0
Mitchell-Netravali Cubic Filter, Smoothness = 1.5
Mitchell-Netravali Cubic Filter, Smoothness = 2.0
Upsampling TestIn this case we have taken a small crop of 100x100 pixels from the original image, and we have upsampled it to 650x650 pixels. Below are the most relevant results.
Original crop, enlarged 6:1 without interpolation (IntegerResample)
Bicubic Spline
Mitchell-Netravali Cubic Filter
Catmull-Rom Spline Filter
Cubic B-Spline Filter
This example clearly shows that bicubic spline interpolation is the most accurate option for upsampling images. The Mitchell-Netravali family of interpolation filters can be used to achieve higher smoothness in the upsampled result, which can be desirable in some applications.
New Auto Interpolation ModeWe have implemented an
automatic interpolation selection mode in the Resample and DynamicCrop standard tools. In this mode, Mitchell-Netravali and bicubic spline interpolation algorithms are automatically selected as a function of the scaling ratio, independently for each axis. Bicubic spline is always used for upsampling scaling ratios, and also for slight downsampling ratios, when the Mitchell-Netravali filters cannot be properly sampled (filter kernels smaller than 5x5 elements). Mitchell-Netravali cubic filters are used for the rest of downsampling operations. We think that this automatic selection mode is nearly optimal for most image rescaling tasks.
