I am trying to teach myself more about image compression using the wavelet transform method. What is it about certain wavelets that make them preferable when compressing images? Are they easier to compute? Do they produce smoother images?
Example: JPEG 2000 uses the Cohen-Daubechies-Feauveau 9/7 Wavelet. Why this one?
Overview
The short answer is that they have the maximum number of vanishing moments for a given support (i.e number of filter coefficients). That's the "extremal" property which distinguishes Daubechies wavelets in general. Loosely speaking, more vanishing moments implies better compression, and smaller support implies less computation. In fact, the tradeoff between vanishing moments and filter size is so important that it dominates the way that wavelets are named. For example, you'll often see the D4 wavelet referred to either as D4 or db2. The 4 refers to the number of coefficients, and the 2 refers to the number of vanishing moments. Both refer to the same mathematical object. Below, I'll explain more about what moments are (and why we want to make them disappear), but for now, just understand that it relates to how well we can "fold up" most of the information in the signal into a smaller number of values. Lossy compression is achieved by keeping those values, and throwing away the others.
Now, you may have noticed that CDF 9/7, which is used in JPEG 2000, has two numbers in the name, rather than one. In fact, it's also referred to as bior 4.4. That's because it's not a "standard" discrete wavelet at all. In fact, it doesn't even technically preserve the energy in the signal, and that property is the entire reason people got so excited about the DWT in the first place! The numbers, 9/7 and 4.4, still refer to the supports and vanishing moments respectively, but now there are two sets of coefficients that define the wavelet. The technical term is that rather than being orthogonal, they are biorthogonal. Rather than getting too deep into what that means mathematically, I'll just review the factors which led to using non-energy-preserving biorthogonal wavelets in the first place.
JPEG 2000
A much more detailed discussion of the design decisions surrounding the CDF 9/7 wavelet can be found in the following paper:
Usevitch, Bryan E. A Tutorial on Modern Lossy Wavelet Image Compression: Foundations of JPEG 2000.
I'll just review the main points here.
Quite often, the orthogonal Daubechies wavelets can actually result in increasing the number of values required to represent the signal. The effect is called coefficient expansion. If we're doing lossy compression that may or may not matter (since we're throwing away values at the end anyway), but it definitely seems counterproductive in the context of compression. One way to solve the problem is to treat the input signal as periodic.
Just treating the input as periodic results in discontinuities at the edges, which are harder to compress, and are just artifacts of the transform. For example, consider the jumps from 3 to 0 in the following periodic extension: $[0,1,2,3] \rightarrow [...0,1,2,3,0,1,2,3,...]$. To solve that problem, we can use a symmetric periodic extension of the signal, as follows: $[0,1,2,3] \rightarrow [...,0,1,2,3,3,2,1,0,0,1...]$. Eliminating jumps at the edges is one of the reasons the Discrete Cosine Transform (DCT) is used instead of the DFT in JPEG. Representing a signal with cosines implicitly assumes "front to back looping" of the input signal, so we want wavelets which have the same symmetry property.
Unfortunately, the only orthogonal wavelet which has the required characteristics is the Haar (or D2, db1) wavelet, which only as one vanishing moment. Ugh. That leads us to biorthogonal wavelets, which are actually redundant representations, and therefore don't preserve energy. The reason CDF 9/7 wavelets are used in practice is because they were designed to come very close to being energy preserving. They have also tested well in practice.
There are other ways to solve the various problems (mentioned briefly in the paper), but these are the broad strokes of the factors involved.
Vanishing Moments
So what are moments, and why do we care about them? Smooth signals can be well approximated by polynomials, i.e. functions of the form:
$$a + bx + cx^2 + dx^3 + ...$$
The moments of a function (i.e. signal) are a measure of how similar it is to a given power of x. Mathematically, this is expressed as an inner product between the function and the power of x. A vanishing moment means the inner product is zero, and therefore the function doesn't "resemble" that power of x, as follows (for the continuous case):
$$\int{x^n f(x) dx = 0 }$$
Now each discrete, orthogonal wavelet has two FIR filters associated with it, which are used in the DWT. One is a lowpass (or scaling) filter $\phi$, and the other is a highpass (or wavelet) filter $\psi$. That terminology seems to vary somewhat, but it's what I'll use here. At each stage of the DWT, the highpass filter is used to "peel off" a layer of detail, and the lowpass filter yields a smoothed version of the signal without that detail. If the highpass filter has vanishing moments, those moments (i.e. low order polynomial features) will get stuffed into the complementary smoothed signal, rather than the detail signal. In the case of lossy compression, hopefully the detail signal won't have much information in it, and therefore we can throw most of it away.
Here's a simple example using the Haar (D2) wavelet. There's typically a scaling factor of $1/\sqrt{2}$ involved, but I'm omitting it here to illustrate the concept. The two filters are as follows: $$ \phi = [1,1] \\ \psi = [1,-1]$$
The highpass filter vanishes for the zero'th moment, i.e. $x^0 = 1$, therefore it has one vanishing moment. To see this, consider this constant signal: $[2,2,2,2]$. Now intuitively, it should be obvious that there's not much information there (or in any constant signal). We could describe the same thing by saying "four twos". The DWT gives us a way to describe that intuition explicitly. Here's what happens during a single pass of the DWT using the Haar wavelet:
$$ [2,2,2,2] \rightarrow_{\psi}^{\phi} \left\{ \begin{array}{rr} \left[2 + 2, 2 + 2\right] = \left[4,4\right] \\ \left[2-2,2-2\right] = \left[0,0\right] \end{array}\right. $$
And what happens on the second pass, which operates on just the smoothed signal:
$$ [4,4] \rightarrow_{\psi}^{\phi} \left\{ \begin{array}{rr} \left[4 + 4\right] = \left[8\right] \\ \left[4-4\right] = \left[0\right] \end{array}\right. $$
Notice how the constant signal is completely invisible to the detail passes (which all come out to be 0). Also notice how four values of $2$ have been reduced to a single value of $8$. Now if we wanted to transmit the original signal, we could just send the $8$, and the Inverse DWT could reconstruct the original signal by assuming that all the detail coefficients are zero. Wavelets with higher-order vanishing moments allow similar results with signals that are well approximated by lines, parabolas, cubics, etc.
Further Reading
I'm glossing over a LOT of detail to keep the above treatment accessible. The following paper has a much deeper analysis:
M. Unser, and T. Blu, Mathematical properties of the JPEG2000 wavelet filters, IEEE Trans. Image Proc., vol. 12, no. 9, Sept. 2003, pg.1080-1090.
Footnote
The above paper seems to suggest that the JPEG2000 wavelet is called Daubechies 9/7, and is different from the CDF 9/7 wavelet.
We have derived the exact form of the JPEG2000 Daubechies 9/7 scaling filters... These filters result from the factorization of the same polynomial as $Daubechies_{8}$ [10]. The main difference is that the 9/7 filters are symmetric. Moreover, unlike the biorthogonal splines of Cohen-Daubechies-Feauveau [11], the nonregular part of the polynomial has been divided among both sides, and as evenly as possible.
[11] A. Cohen, I. Daubechies, and J. C. Feauveau, “Biorthogonal bases of compactly supported wavelets,” Comm. Pure Appl. Math., vol. 45, no. 5, pp. 485–560, 1992.
The draft of the JPEG2000 standard (pdf link) that I've browsed also calls the official filter Daubechies 9/7. It references this paper:
M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, “Image coding using the wavelet transform,” IEEE Trans. Image Proc. 1, pp. 205-220, April 1992.
I haven't read either of those sources, so I can't say for sure why Wikipedia calls the JPEG2000 wavelet CDF 9/7. It seems like there may be a difference between the two, but people call the official JPEG2000 wavelet CDF 9/7 anyway (because it's based on the same foundation?). Regardless of the name, the paper by Usevitch describes the one that's used in the standard.
The goodness of signal transforms is evaluated on two different metrics: compression, and in the case of lossy compression, quality. Compression is defined by energy compaction but quality is harder.
Traditionally quality has been measured by mean-square error or average per-pixel SNR. However, humans don't tend to evaluate signals with MSE or SNR. Humans are very sensitive to structured noise where MSE tends not to be. Developing algorithms that deliver human-like quality metrics is an active area of research. Bovik's Structural SIMilarity (SSIM) index is a good place to start.
As a very short answer - any transform is better than other transform when it has, what is known as "energy Compaction property" which is explained as below:
"when only a small fraction of transform coefficients have large magnitude such that keeping only a few co-efficient and discarding or quantizing others still allows re-construction is near perfect". Such property is related to the decorrelating capability of unitary transforms."
The transform with lesser energy compaction property is the one which will need smallest number of symbols and hence lesser bits.
The transform with highest energy compaction property is DCT.
Dipan.
The DCT has very good energy compaction for a lot of common signals, and it also meshes fairly well with how diffraction (the underlying physical process in imaging) works, as diffraction can be represented as a fourier kernel. These give it a lot of advantages.
The problem is that the DCT coefficients are necessarily delocalized over the entire transform area. This requires that many small transform areas (blocks) be created so that energy in one area does not spill over into another when transforming. This both restricts the ability of the transform to compact energy, and also introduces artifacts at the many block boundaries.
I haven't done much with wavelets so I could be wrong, but they're more delocalized, with different coefficients representing different area/frequency tradeoffs. This allows larger block sizes with less artifacts. No sure in practice how much of a difference that really makes though.
Natural images consist of different image features, we can broadly categorize them into smooth or slow-to-vary features, textures and edges. A good compression method is one that tranforms an image into a domain where all the energy of a signal is conserved in just a few coefficients.
The fourier transform tries to approximate an image using sines and cosines. Now sines and cosines can approximate smooth signals fairly concisely, but are notoriously bad for approximating discontinuities. If you are familiar with the Gibbs phenomenon, you'll know that one needs a large number fourier coefficients in order to avoid the artifacts of approximating a discontinuity in time. However, the smaller the number of coefficients, the better the compression. Therefore, there is an inherent tradeoff between number of coefficients and the lossiness of the compression method, which we usually refer to as the rate-distortion tradeoff.
When searching for a better compression scheme than jpeg, which uses fourier transforms, we would require a transformation that can approximate discontinuities with fewer coefficients than the fourier transform, for the same distortion. Enter wavelets which offers better approximation and therefore better compression of point singularities without the gibbs phenomenon like artifacts. Images are never purely smooth in practice and therefore wavelets are more versatile than fourier for diverse image features. If we were to compare the best k-term approximation of an image containing edges using both fourier and wavelets, the errors would decay as $k^{-2/3}$ and $k^{-1}$, respectively. For the same number of terms, the error decays faster for wavelets. This means that wavelets have better energy compaction when images are not perfectly smooth (slowly varying) and contain singularities.
However, we as yet do not have a single basis or transform that can approximate smooth features, point singularities, edges and textures.
When talking about better wavelets, we should consider they have the same encoder in the back: the performance of a transformation is heavily intertwined with the quantization and the encoding. The performance usually is: better compression for the same quality, or better quality for the same compression. Compression is an easy measure, quality is not. But suppose we have one.
Now, a wavelet (with encoder) can be better at a compression ratio (say low), and worse at another (say high). Only slightly in general, but depending on whether you would compress high ($\times 124$) or low ($\times 4$), you may choose different wavelets.
Finally, this depends on the class of images you want to compress: all purpose, or focused, like with medical images, or seismic data compression, with a restricted, specific types of data? Here again, wavelets can be different.
Now, what are the main morphological components of images, and how do wavelets deal with them:
So on the analysis side, the best wavelets are good a compacting the above features globally nicely. On the synthesis side, the best wavelets mitigate the compression effects, for instance quantization, to give ap pleasant aspect. The properties required at analysis/synthesis are a bit different, this is why biorthogonal wavelets are nice: you can separate analysis (vanishing moments)/synthesis (smoothness) properties, which you cannot do with orthogonal ones, and provokes an increase in filter length, quite detrimental to computational performance. Additional, biorthogonal wavelets can be symmetric, good for edges.
Finally, do you want some lossless compression? Then you need "integer"-like wavelets (or binlets).
And all of the above in mixed with computational issues: separable wavelets, not too long. And the process of standardization in the JPEG committee.
Finally, The 5/3 is quite good for lossless, short enough. Some of the 9/7 are good too. Much better than a 13/7 wavelet? Not really, and even if, that is in PSNR, not the best for image quality.
So the best wavelets are a whisker away, for traditional images, and personal communications with authors of
M. Unser, and T. Blu, Mathematical properties of the JPEG2000 wavelet filters, IEEE Trans. Image Proc., vol. 12, no. 9, Sept. 2003, pg.1080-1090.
make me believe that the "best" aspect of the 9/7 is neither fully explained, nor assured.
Because you may gain sensibly more with other filter banks (multi-bands or $M$-band). Maybe not enough to justify a novel standard.
