The eighties: an image processing view

Consequently, reconstruction methods better than linear interpolation became an attractive filed of research. Hou and Andrews [19] investigated, at the end of the seventies, the applicability of B-splines for image processing tasks like interpolation, smoothing, filtering, enlargement, and reduction. They concentrate on how to choose an optimal and yet easy to implement basis function, the so-called B-spline, and use it for interpolation and data smoothing. Only a visual comparison of B-spline interpolation to other interpolation methods is given by the authors, whereby they compare it only to nearest neighbor and linear interpolation. For testing purposes they performed magnification and minification on digital pictures and come to the result that B-spline interpolation is superior.

Keys [25] defines the cubic interpolation kernel as piecewise cubic polynomials on the intervals [-2,-1],[-1,0],[0,1] and [1,2] (see Eq. 4.7). Outside the interval [-2,2] the kernel is zero, which means that the number of sample points that contribute to one reconstructed value reduce to four. Since an interpolation kernel must be symmetric this leads to eight unknown coefficients. Further, the kernel must be one at position zero and zero at all other integer positions and it must be continuous and have continuous derivatives. These constraints lead to the one-parametric family of cardinal splines:

$$h(x)=\left \{ \begin{array}{ll} (a+2)\vert x\vert^3-(a+3)\ve... ...eq \vert x\vert < 2$}\\ 0 & \textrm{else} \end{array} \right.$$ (2.1)

To get an optimal value for a it is shown that only for $a=-\frac{1}{2}$ the Taylor series expansion of the interpolating function agrees with the first three terms of the original function. A fourth-order convergence could be achieved by increasing the filter length to the interval [-3,3] and it is noted that this is the highest order of convergence that can be achieved with piecewise cubic polynomials.

This cubic convolution kernel then is compared to nearest neighbor and linear interpolation both by comparing their frequency responses and by visual comparison of interpolated images. Again, conclusions are that cubic convolution kernels are more accurate than nearest neighbor or linear interpolation. However, Keys notes that they are not as accurate as cubic splines but can be performed much more efficiently.

Park and Schowengerdt [44] point out that the parameter a of the cardinal cubic splines has a physical meaning since it is the slope of the filter at x=1. They further analyze the cardinal splines in frequency domain and come to the same result as Keys in spatial domain that $a=-\frac{1}{2}$ is superior which is not the standard value commonly referenced in the literature (that would be a = -1.0 which duplicates the slope of the ideal interpolation function (i.e., the sinc function) at x = 1.0 so that simple-minded researchers obviously concluded that would be best for the cardinal splines too). Also, they rewrite Equation 2.1 as

h(x)=h₀(x)+ah₁(x) (2.2)

with

$$h_0(x)=\left \{ \begin{array}{ll} 2\vert x\vert^3-3\vert x\v... ...f $\vert x\vert < 1$}\\ 0 & \textrm{else} \end{array} \right.$$ (2.3)

and

$$h_1(x)=\left \{ \begin{array}{ll} \vert x\vert^3-\vert x\ver... ...eq \vert x\vert < 2$}\\ 0 & \textrm{else} \end{array} \right.$$ (2.4)

which clearly illustrates the linear dependence of this family of interpolators upon the parameter a. It is also immediately recogniceable that if a = 0 the number of contributing samples reduces to two.

The introduction of the B-splines and cardinal splines entailed some work of researchers comparing different reconstruction methods. Parker et al. [45] compared five different interpolation filters, namely nearest neighbor and linear interpolation, cubic B-splines and cardinal splines (which they call high-resolution cubic splines) with a=-1 and a=-0.5. The comparison is done in frequency domain as well as by visual inspection of resampled images. Nearest neighbor, being the cheapest method with just one contributing sample point, has a very poor stop zone response. Linear interpolation has a slightly better overall response but extends over two sample points. The B-spline and cardinal splines are even more expensive with four contributing sample points. However, they have better response in both the pass and stop band what is just to be expected from the increased filter length. They conclude that the choice between the length four interpolating functions depends upon the task. The cubic B-spline provides the most smoothing whereas the cardinal cubic spline with a=-1 provides the best high-frequency response along with some high frequency enhancement and the cardinal cubic spline with a=-0.5 has both a flat low-frequency response and good stop-band performance.

Schreiber and Troxel [53] conducted a series of experiments using ``perceptual rather than mathematical criteria''. They compared eight different interpolation methods, nearest neighbor (which they call sample-and-hold) and linear interpolation, a truncated sinc filter, B-splines, two types of sharpened cubic splines (which are not explained in more detail), a truncated Gaussian and a truncated sharpened Gaussian filter. Sharpening a Gaussian means that two negative Gaussian pulses are added to one central Gaussian pulse, one earlier and one later. They uses two test pictures, which were enlarged and shown to ten ``subjects'', whereas ``most of the subjects were affiliated with our laboratory and were considered experienced, if not expert, observers''. They conclude that the result show the clear superiority of the sharpened Gaussian to all the others with respect to image quality. However, the sharpened Gaussian is not a very popular reconstruction filter, so this conclusion is at least questionable.

Mitchell and Netravali [39] eventually introduced a quite popular family of cubic splines, the BC-splines. A cubic spline filter is in its general form given by

$$h(x)=\left \{ \begin{array}{ll} P\vert x\vert^3+Q\vert x\ver... ...eq \vert x\vert < 2$}\\ 0 & \textrm{else} \end{array} \right.$$ (2.5)

These eight free parameters are reduced to two by requiring the filter to be symmetric and smooth, i.e., value and first derivative are continuous at |x| = 1. Further, if all the samples are a constant value the reconstruction should be a flat signal. This results in the following family of cubic filters

$$h(x)=\left \{ \begin{array}{ll} (12-9B-6C)\vert x\vert^3+ & ... ...\vert x\vert+(8B+24C)\\ 0 & \textrm{else} \end{array} \right.$$ (2.6)

Some of the values for B and C correspond to well known filters, e.g., B=1 and C=0 yields the cubic B-spline, B=0 and C=-a is the family of the cardinal cubics (with $C=\frac{1}{2}$ or $a=-\frac{1}{2})$ being the Catmull-Rom spline) and C=0 is the family of Duff's tensioned B-splines.

They note that a reconstruction filter now has two tasks

• remove the extraneous replicas, which were introduced by the sampling process (see Chapter 3)
• pass the base band undistorted (the error if this is not done correctly is called base band attenuation)

From this requirements two types of aliasing can be distinguished

pre-aliasing

is due to under-sampling (or lack of pre-filtering), i.e., the replicas of the signal's spectrum overlap. This is often just called aliasing [64].

post-aliasing

is due to poor reconstruction. Note that this actually should be called reconstruction error and not aliasing [64].

Several types of distortion due to imperfect reconstruction filters (post-aliasing) are identified: sample-frequency ripple, blurring, ringing, and anisotropy. It is often necessary to trade off one of these types of distortion for another. The design of one general purpose filter perfect for all applications is unfortunately impossible.

Two new filters were proposed, the first with $B=\frac{3}{2}$ and $C=\frac{1}{3}$ suppresses post-aliasing but is unnecessarily blurring, the second with $B=\frac{1}{3}$ and $C=\frac{1}{3}$ turns out to be a satisfactory compromise between ringing, blurring, and anisotropy. Furthermore, a simple subjective test was carried out which allowed to divide the B,C parameter space into ringing, blurring, anisotropy, and satisfactory regions.This parameter space is depicted in Fig. 2.1 (image taken from the paper [39]).

Figure: The partitioning of the B,C parameter space into ringing, blurring, anisotropy, and satisfactory regions,as done by Mitchell and Netravali (image taken from the paper [39]).

They identify filters fulfilling the condition 2C+B=1 achieving quadratic convergence of fit, i.e., the Taylor series expansion of the reconstructed function matches the Taylor series expansion of the original function up to the second term. This line contains the cubic B-spline and the cardinal cubic splines (with the Catmull-Rom spline with a=-0.5 actually having cubic convergence).

At this point two excellent papers have to be mentioned, both by Jim Blinn published in Jim Blinn's corner of Computer Graphics & Applications and called ``What We Need Around Here Is More Aliasing'' [4] and ``Return of the Jaggy'' [3]. In these papers Jim Blinn first explains in a very comprehensive way the effects of sampling and reconstruction in frequency domain. He then explains the box filter (nearest neighbor interpolation), the tent filter (linear interpolation), Gaussian, and ideal (the sinc) filter.He notes that the sinc filter is impracticable because of its infinite extend in spatial domain and therefore some approximation must be used which results in the conclusion that an achievable filter never is a perfect low-pass filter.

Ken Turkowski [63] published a comparative study of some reconstruction filters. These include box, tent, and Gaussian filter. Further, he notes that the sinc function should be multiplied by an appropriate windowing function, where he states that the Lanczos window is most appropriate in a way that it ``produced the best quality with an acceptable amount of ringing.'' [62]. This was found out in an earlier study comparing the sinc function windowed with several windows like Hann, Hamming, or raised cosine window.