Manipulation of digital images often requires resampling of the pixel data. Usually, the pixel positions in the transformed image do not coincide with grid positions. Therefore, an interpolation algorithm has to be applied to somehow derive the pixel data for these in-between positions. The effort spent for this interpolation is crucial for the image quality of the result image.
Most common in computer graphics applications is bilinear interpolation. As the name suggests, off-grid points are linearly interpolated between their four neighboring grid-pixels. Some professional packages like Photoshop offer cubic interpolation using higher order polynomials and more data points. The more data points are used, and the more sophisticated the interpolation function is, the better is the result and the slower is the program.
The following is a test performed on a variety of Graphics programs which were available to me. This test is biased since I used it explicitely to test my own program (the Photoshop/Gimp plug-in Panorama Tools ) against other solutions.
Several authors have judged interpolator quality by testing enlargements. However, there are quite a few problems associated with that, the most important being that there is no mathematically unique solution for digital image enlargements, and, hence, no really objective test. A more practical test is a rotation of an image by some arbitrary angle, which can be easily tested against the original image. The more such rotations the image survives intact, the better is the algorithm. This test is also readily available, since almost any Graphics-program has a rotate function.
Two images were used: One real-world photograph shown
to the left below, and one line drawing shown to the right. The images
are shown in original size; they are 200x200pixels each.
Both images were rotated in 5 degree steps until a total of 180 degrees was reached. This amounts to 36 resampling steps. Then the image is flipped back, which is a lossless transformation. To judge and compare image quality, one part of each image is enlarged three times (photo) or six times (line drawing) without any filtering and interpolation, so each source pixel appears as 3x3 (6x6) block in the result image. For this publication, the photos were compressed using high-quality JPEG, and the line-drawings using GIF-compression. The source images (without being rotated) then look like this:
Ken Turkowski has suggested another test image which gives a more quantitative estimate of the image sharpness. It is shown below. In this case it was determined how many of the concentric rings survived the 36 rotations. The count of clearly visible white rings is indidcated for each image.
Results:
Photoshop Bicubic Interpolation:
Number of visible bright rings : 8,5
Photoshop Bilinear Interpolation:
Color It (Macintosh):
GraphicConverter with Error Correction (Macintosh):
Picture Publisher (Windows 95)
Panorama Tools: Cubic Interpolator 'Poly 3'
Number of visible bright rings : 8,5
Panorama Tools: Spline 16 Pixels
Panorama Tools: Spline 36 Pixels
Number of visible bright rings : 10
Panorama Tools: Sinc 256 Pixels
The Interpolators in Panorama Tools are available from version 1.8b1. Earlier versions had the two Spline Interpolators, but the other two were different.
Some Comments:
The worst image quality is obtained with nearest neighbor
sampling which obviously is implemented in Picture Publisher. Bilinear
interpolation leads to significant losses, but is usually acceptable if
only one or two sampling steps are involved. The bicubic schemes vary depending
on the number of input pixels. Usually 16 pixels are used. Depending on
the choosen polynomial, either a very sharp image with some artefacts,
or a somewhat softer, but more homogeneous image is obtained. The Photoshop
polynomial has a distinct sharpening effect, as can be seen in the brightened
edges of dark features. This leads to artefacts most pronounced in the
structures of the line drawing. The interpolator 'poly 3' of Panorama
Tools has been tuned to closely resemble that of Photoshop.It sharpens
slightly more. 'Spline16' is equally fast, but much smoother, as can be
seen in the line drawing. It is also somewhat softer, as judged from the
rating using Ken's image. Spline36 is identical to Spline16, but uses 36
pixels instead of 16. This results in better resolution (see
the 1pixel wide line in the line drwaing) without significant artefacts.
The best results are obtained using the sinc-function. This not only is
more involved than the cubic polynomials, but in the present case also
requires 256 pixels to interpolate for each input pixel. The sinc-function
is the theoretical optimum, and can only be improved by using even more
pixels.
The Math:
In calculating the pixel value of a particular position in the result image, the interpolator combines several pixels of the source image. The closer these pixels are to this position, the more weight the pixel carries. However, this is not just a simple falling function of pixel distance x, but there are certain optimum weights.
Linear Interpolation
The weight of the source pixel is calculated by
Cubic Interpolation
Poly3 of Panorama Tools is a single parameter cubic polynomial with weights
Spline16 of Panorama Tools is a cubic-spline, with derivative set to 0 at the edges (4x4 pixels). The weight function thus becomes:
Spline36 is like Spline16, except that it uses 6x6=36 pixels. The weight function becomes
Sinc Interpolation
Sinc256 of Panorama Tools is a sinc() function windowed to 8 pixels (Lanczos-function). The weights are calculated
Copyright ©; H. Dersch 1999