Our main aim now is to search for better filters / wavelets which result in compression performance that rivals or beats the DCT. We assume that perfect reconstruction is a prime requirement, so that the only image degradations are caused by coefficient quantisation, and may be made as small as we wish by increasing bit rate. We start our search with the two PR identities from our discussion of Perfect Reconstruction, which we repeat here: G0 z H0 z G1 z H1 z 2 and G0 z H0 z G1 z H1 z 0 The usual way of satisfying the anti-aliasing condition (), while permitting H0 and G0 to have lowpass responses (passband where z 0 ) and H1 and G1 to have highpass responses (passband where z 0 ), is with the following relations: H1 z z k G0 z and G1 z z k H0 z where k must be odd so that: G0 z H0 z G1 z H1 z G0 z H0 z z k H0 z z k G0 z 0 Now define the lowpass product filter: P z H0 z G0 z and substitute relations and into identity to get: G0 z H0 z G1 z H1 z G0 z H0 z H0 z G0 z P z P z 2 This requires all P z terms in even powers of z to be zero, except the z 0 term which should be 1. The P z terms in odd powers of z may take any desired values since they cancel out in . A further constraint on P z is that it should be zero phase, in order to minimise the visibility of any distortions due to the high-band being quantised to zero. Hence P z should be of the form: P z … p5 z 5 p3 z 3 p1 z 1 p1 z -1 p3 z -3 p5 z -5 … The design of a set of PR filters H0 , H1 and G0 , G1 can now be summarised as: Choose a set of coefficients p1 , p3 , p5 … to give a zero-phase lowpass product filter P z with desirable characteristics. (This is non-trivial and is discussed below.) Factorize P z into H0 z and G0 z , preferably so that the two filters have similar lowpass frequency responses. Calculate H1 z and G1 z from and . It can help to simplify the tasks of choosing P z and factorising it if, based on the zero-phase requirement, we transform P z into Pt Z such that: P z Pt Z 1 p t , 1 Z p t , 3 Z 3 p t , 5 Z 5 … where Z 1 2 z z . To calculate the frequency response of Pt , let z ω Ts : therefore, Z 1 2 ω Ts ω Ts ω Ts This is a purely real function of ω, varying from 1 at ω 0 to -1 at ω Ts (half the sampling frequency). A Belgian mathematician, Ingrid Daubechies, did much pioneering work on wavelets in the 1980s. She discovered that to achieve smooth wavelets after many levels of the binary tree, the lowpass filters H0 z and G0 z must both have a number of zeros at half the sampling frequency (at z -1 ). These will also be zeros of P z , and so Pt z will have zeros at Z -1 . The simplest case is a single zero at Z -1 , so that Pt z 1 Z . Therefore, P z 1 2 z 2 z 1 2 z 1 1 z G0 z H0 z which gives the familiar Haar filters. As we have seen, the Haar wavelets have significant discontinuities so we need to add more zeros at Z -1 . However to maintain PR, we must also ensure that all terms in even powers of Z are zero, so the next more complicated Pt must be of the form: Pt z 1 Z 2 1 α Z 1 2 α Z 1 2 α Z 2 α Z 3 if α 1 2 to suppress the term in Z 2 , Pt z 1 3 2 Z 1 2 Z 3 If we allocate the factors of Pt such that ( 1 Z ) gives H0 and 1 Z 1 α Z gives G0 , we get: H0 z 1 2 z 2 z G0 z 1 8 z 2 z z 4 z 1 8 z 2 2 z 6 2 z z -2 Using and with k 1 , the corresponding highpass filters then become: G1 z z H0 z 1 2 z z 2 z H1 z z G0 z 1 8 z z 2 2 z 6 2 z z -2 This is often known as the LeGall 3,5-tap filter set, since it was first published in the context of 2-band filter banks by Didier LeGall in 1988. The wavelets of the LeGall 3,5-tap filters, H0 and H1 above, and their frequency responses are shown in . The scaling function (bottom left) converges to a pure triangular pulse and the wavelets are the superposition of two triangular pulses.

Impulse responses and frequency responses of the 4-level tree of LeGall 3,5-tap filters. The triangular scaling function produces linear interpolation between consecutive lowband coefficients and also causes the wavelets to be linear interpolations of the coefficients of the H1 filter, -1, -2, 6, -2, -1 (scaled appropriately). These wavelets have quite desirable properties for image compression (note the absence of waveform discontinuities and the much lower sidelobes of the frequency responses), and they represent probably the simplest useful wavelet design. Unfortunately there is one drawback -- the inverse wavelets are not very good. These are formed from the LeGall 5,3-tap filter pair, G0 and G1 above, whose wavelets and frequency responses are shown in .

Impulse responses and frequency responses of the 4-level tree of LeGall 5,3-tap filters. The main problem is that the wavelets do not converge after many levels to a smooth function and hence the frequency responses have large unwanted sidelobes. The jaggedness of the scaling function and wavelets causes highly visible coding artefacts if these filters are used for reconstruction of a compressed image. However the allocation of the factors of Pt Z to H0 and G0 is a free design choice, so we may swap the factors (and hence swap G and H) in order that the smoother 3,5-tap filters become G0 , G1 and are used for reconstruction. We shall show later that this leads to a good low-complexity solution for image compression and that the jaggedness of the analysis filters is not critical. Unbalance between analysis and reconstruction filters / wavelets is nevertheless often regarded as being undesirable, particularly as it prevents the filtering process from being represented as an orthonormal transformation of the input signal (since an orthonormally transformed signal may be reconstructed simply by transposing the transform matrix). An unbalanced PR filter system is often termed a bi-orthogonal transformation. We now consider ways to reduce this unbalance.

Filters with balanced H and G frequency responses (but non-linear phase responses) - Daubechies wavelets: In the above analysis, we used the factorisation of Pt Z to give us H0 and G0 . This always gives unbalanced factors if terms of Pt in even powers of Z are zero. However each of these factors in Z may itself be factorised into a pair of factors in z, since: α z 1 1 α z α z 1 α 2 α z 1 α 2 2 α Z 1 α 2 1 β Z where β 2 α 1 α 2 . For each factor of Pt Z , we may allocate one of its z subfactors to H0 z and the other to G0 z . Where roots of Pt Z are complex, the subfactors must be allocated in conjugate pairs so that H0 and G0 remain purely real. Since the subfactors occur in reciprocal pairs (roots at z α and α ), we find that G0 z H0 z which means that the impulse response of G0 is the time-reverse of H0 . Therefore the frequency responses are related by G0 ω Ts H0 ω Ts . Hence the magnitudes of the frequency responses are the same, and their phases are opposite. It may be shown that this is sufficient to obtain orthogonal wavelets, but unfortunately the separate filters are no longer zero (or linear) phase. (Linear phase is zero phase with an arbitrary delay z k .) Daubechies wavelets may be generated in this way, with the added constraint that the maximum number of zeros of Pt Z are placed at Z -1 (producing pairs of zeros of P z at z -1 ), consistent with terms in even powers of Z being zero. If Pt Z is of order 2 K 1 , then it may have K zeros at Z -1 such that Pt Z 1 Z K Rt Z where Rt Z is of order K 1 and its K 1 roots may be chosen such that terms of Pt Z in the K 1 even powers of Z are zero. is the K 2 solution to . Therefore, Rt Z 1 1 2 Z so β 1 2 and, from , the factors of R z are R z α z 1 1 α z 1 α 2 where α 3 2 . Also 1 Z 2 1 2 Z 1 2 1 2 1 z 2 Hence H0 z 1 2 1 α 2 1 z 2 1 α z 0.4830 0.8365 z 0.2241 z -2 0.1294 z -3 and H1 z z -3 G0 z z -3 H0 z 0.1294 0.2241 z 0.8365 z -2 0.4830 z -3 The wavelets and frequency responses for these filters are shown in . It is clear that the wavelets and scaling function are no longer linear phase and are less smooth than those for the LeGall 3,5-tap filters. The frequency responses also show worse sidelobes. The G0 , G1 filters give the time reverse of these wavelets and identical frequency responses.

Impulse responses and frequency responses of the 4-level tree of Daubechies 4-tap filters. Higher order Daubechies filters achieve smooth wavelets but they still suffer from non-linear phase. This tends to result in more visible coding artefacts than linear phase filters, which distribute any artefacts equally on either side of sharp edges in the image. Linear phase filters also allow an elegant technique, known as symmetric extension, to be used at the outer edges of images, where wavelet filters would otherwise require the size of the transformed image to be increased to allow for convolution with the filters. Symmetric extension assumes that the image is reflected by mirrors at each edge, so that an infinitely tessellated plane of reflected images is generated. Reflections avoid unwanted edge discontinuities. If the filters are linear phase, then the DWT coefficients also form reflections and no increase in size of the transformed image is necessary to accomodate convolution effects.

Filters with linear phase and nearly balanced frequency responses: To ensure that the filters H0 , H1 and G0 , G1 are linear phase, the factors in Z must be allocated to H0 or G0 as a whole and not be split, as was done for the Daubechies filters. In this way the symmetry between z and z is preserved in all filters. Perfect balance of frequency responses between H0 and G0 is then not possible, if PR is preserved, but we have found a factorisation of Pt Z which achieves near balance of the responses. This is: Pt Z 1 Z 1 a Z b Z 2 1 Z 1 c Z This is a 5th order polynomial, and if the terms in Z 2 and Z 4 are to be zero, there are two constraints on the 3 unknowns a b c so that one of them (say c) may be regarded as a free parameter. These constraints require that: a 1 2 c 2 2 1 c 2 and b c 1 2 c 2 1 c 2 c may then be adjusted to give maximum similarity between the left and right pairs of factors in as Z varies from 1 to -1 ( ω Ts varies from 0 to ). It turns out that c 2 7 gives good similarity and when substituted into , and gives: Pt Z 1 50 50 41 Z 15 Z 2 6 Z 3 1 7 7 5 Z 2 Z 2 We get G0 z and H0 z by substituting Z 1 2 z z into these two polynomial factors. This results in 5,7-tap filters whose wavelets and frequency responses are shown in .

Impulse responses and frequency responses of the 4-level tree of near-balanced 5,7-tap filters. The near balance of the responses may be seen from which shows the alternative 7,5-tap versions (i.e. with H and G swapped). It is quite difficult to spot the minor differences between these figures.

Impulse responses and frequency responses of the 4-level tree of near-balanced 7,5-tap filters.

Smoother Wavelets In all of the above designs we have used the substitution Z 1 2 z z . However other substitutions may be used to create improved wavelets. To preserve PR, the substitution should contain only odd powers of z (so that odd powers of Z should produce only odd powers of z), and to produce zero phase, the coefficients of the substitution should be symmetric about z 0 . A substitution, which can give much greater flatness near z ± 1 while still satisfying Z ± 1 when z ± 1 , is: Z p z 3 1 2 p z z p z -3 Z then becomes the following function of frequency when z ω Ts : Z 1 2 p ω Ts 2 p 3 ω Ts A high degree of flatness (with some ripple) is achieved near ω Ts 0 and , when p 3 32 . This is equivalent to more zeros near z -1 for each ( Z 1 ) factor than when Z 1 2 z z is used. The 2nd order factor in Pt Z now produces terms from z6 to z-6 and the 3rd order factor produces terms from z9 to z-9 . Hence the filters become 13 and 19 tap filters, although 2 taps of each are zero and the outer two taps of the 19-tap filter are very small ( ≈ 10 -4 ). shows the wavelets and frequency responses of the 13,19-tap filters, obtained by substituting into . Note the smoother wavelets and scaling function and the much lower sidelobes in the frequency responses from these higher order filters.

Impulse responses and frequency responses of the 4-level tree of near-balanced 13,19-tap filters. demonstrates that the near balanced properties of are preserved in the high order filters.

Impulse responses and frequency responses of the 4-level tree of near-balanced 19,13-tap filters. There are many other types of wavelets with varying features and complexities, but we have found the examples given to be near optimum for image compression.