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:
G0zH0z+G1zH1z≡2
G0
z
H0
z
G1
z
H1
z
2
(1)
and
G0zH0-z+G1zH1-z≡0
G0
z
H0
z
G1
z
H1
z
0
(2)
The usual way of satisfying the anti-aliasing condition (
Equation 2), while permitting
H0
H0
and
G0
G0
to have lowpass responses (passband where
ℜz>0
z
0
) and
H1
H1
and
G1
G1
to have highpass responses (passband where
ℜz<0
z
0
), is with the following relations:
H1z=z-kG0-z
H1
z
z
k
G0
z
(3)
and
G1z=zkH0-z
G1
z
z
k
H0
z
(4)
where
kk must be odd so that:
G0zH0-z+G1zH1-z=G0zH0-z+zkH0-z-z-kG0z=0
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:
Pz=H0zG0z
P
z
H0
z
G0
z
(5)
and substitute relations
Equation 3 and
Equation 4 into identity
Equation 1 to get:
G0zH0z+G1zH1z=G0zH0z+H0-zG0-z=Pz+P-z=2
G0
z
H0
z
G1
z
H1
z
G0
z
H0
z
H0
z
G0
z
P
z
P
z
2
(6)
This requires all
Pz
P
z
terms in even powers of
zz to be zero, except the
z0
z
0
term which should be 1. The
Pz
P
z
terms in odd powers of
zz
may take any desired values since they cancel out in
Equation 6.
A further constraint on
Pz
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
Pz
P
z
should be of the form:
Pz=…+p5z5+p3z3+p1z+1+p1z-1+p3z-3+p5z-5+…
P
z
…
p5
z
5
p3
z
3
p1
z
1
p1
z
-1
p3
z
-3
p5
z
-5
…
(7)
The design of a set of PR filters
H0
H0
,
H1
H1
and
G0
G0
,
G1
G1
can now be summarised as:
-
Choose a set of coefficients
p1
p1
,
p3
p3
,
p5
p5
… to give a zero-phase lowpass product
filter
Pz
P
z
with desirable characteristics. (This is
non-trivial and is discussed below.)
-
Factorize
Pz
P
z
into
H0z
H0
z
and
G0z
G0
z
, preferably so that the two filters have similar
lowpass frequency responses.
-
Calculate
H1z
H1
z
and
G1z
G1
z
from Equation 3 and Equation 4.
It can help to simplify the tasks of choosing
Pz
P
z
and factorising it if, based on the zero-phase
requirement, we transform
Pz
P
z
into
PtZ
Pt
Z
such that:
Pz=PtZ=1+p
t
,
1
Z+p
t
,
3
Z3+p
t
,
5
Z5+…
P
z
Pt
Z
1
p
t
,
1
Z
p
t
,
3
Z
3
p
t
,
5
Z
5
…
(8)
where
Z=12z+z-1
Z
1
2
z
z
. To calculate the frequency response of
Pt
Pt
, let
z=ⅇⅈωTs
z
ω
Ts
: therefore,
Z=12ⅇⅈωTs+ⅇ-ⅈωTs=cosωTs
Z
1
2
ω
Ts
ω
Ts
ω
Ts
(9)
This is a purely real function of
ωω, varying from 1 at
ω=0
ω
0
to -1 at
ωTs=π
ω
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
H0z
H0
z
and
G0z
G0
z
must both have a number of zeros at half the sampling
frequency (at
z=-1
z
-1
). These will also be zeros of
Pz
P
z
, and so
Ptz
Pt
z
will have zeros at
Z=-1
Z
-1
.
The simplest case is a single zero at
Z=-1
Z
-1
, so that
Ptz=1+Z
Pt
z
1
Z
. Therefore,
Pz=12z+2+z-1=12z+11+z-1=G0zH0z
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
Z
-1
. However to maintain PR, we must also ensure that all
terms in even powers of ZZ are
zero, so the next more complicated
Pt
Pt
must be of the form:
Ptz=1+Z21+αZ=1+2+αZ+1+2αZ2+αZ3
Pt
z
1
Z
2
1
α
Z
1
2
α
Z
1
2
α
Z
2
α
Z
3
(10)
if
α=-12
α
1
2
to suppress the term in
Z2
Z
2
,
Ptz=1+32Z-12Z3
Pt
z
1
3
2
Z
1
2
Z
3
If we allocate the factors of
Pt
Pt
such that (
1+Z
1
Z
) gives
H0
H0
and
1+Z1+αZ
1
Z
1
α
Z
gives
G0
G0
, we get:
H0z=12z+2+z-1
H0
z
1
2
z
2
z
(11)
G0z=18z+2+z-1-z+4-z-118-z2+2z+6+2z-1-z-2
G0
z
1
8
z
2
z
z
4
z
1
8
z
2
2
z
6
2
z
z
-2
(12)
Using
Equation 3 and
Equation 4 with
k=1
k
1
, the corresponding highpass filters then become:
G1z=zH0-z=12z-z+2-z-1
G1
z
z
H0
z
1
2
z
z
2
z
(13)
H1z=z-1G0-z=18z-1-z2-2z+6-2z-1-z-2
H1
z
z
G0
z
1
8
z
z
2
2
z
6
2
z
z
-2
(14)
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
H0
and
H1
H1
above, and their frequency responses are shown in
Figure 1. The scaling function
(bottom left) converges to a pure triangular pulse and the
wavelets are the superposition of two triangular pulses.
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
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
G0
and
G1
G1
above, whose wavelets and frequency responses are
shown in Figure 2.
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
PtZ
Pt
Z
to
H0
H0
and
G0
G0
is a free design choice, so we may swap the factors
(and hence swap GG and
HH) in order that the smoother
3,5-tap filters become
G0
G0
,
G1
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.
In the above analysis, we used the factorisation of
PtZ
Pt
Z
to give us
H0
H0
and
G0
G0
. This always gives unbalanced factors if terms of
Pt
Pt
in even powers of ZZ
are zero.
However each of these factors in
ZZ may itself be factorised into
a pair of factors in zz, since:
αz+11+αz-1=αz+1+α2+αz-1=1+α2+2αZ=1+α21+βZ
α
z
1
1
α
z
α
z
1
α
2
α
z
1
α
2
2
α
Z
1
α
2
1
β
Z
(15)
where
β=2α1+α2
β
2
α
1
α
2
.
For each factor of
PtZ
Pt
Z
, we may allocate one of its
zz subfactors to
H0z
H0
z
and the other to
G0z
G0
z
. Where roots of
PtZ
Pt
Z
are complex, the subfactors must be allocated in
conjugate pairs so that
H0
H0
and
G0
G0
remain purely real.
Since the subfactors occur in reciprocal pairs (roots at
z=α
z
α
and
α-1
α
), we find that
G0z=H0z-1
G0
z
H0
z
(16)
which means that the impulse response of
G0
G0
is the time-reverse of
H0
H0
.
Therefore the frequency responses are related by
G0ⅇⅈωTs=H0ⅇ-ⅈωTs
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
z
k
.)
Daubechies wavelets may be generated in this way, with the
added constraint that the maximum number of zeros of
PtZ
Pt
Z
are placed at
Z=-1
Z
-1
(producing pairs of zeros of
Pz
P
z
at
z=-1
z
-1
), consistent with terms in even powers of
ZZ being zero.
If
PtZ
Pt
Z
is of order
2K-1
2
K
1
, then it may have KK
zeros at
Z=-1
Z
-1
such that
PtZ=1+ZKRtZ
Pt
Z
1
Z
K
Rt
Z
(17)
where
RtZ
Rt
Z
is of order
K-1
K
1
and its
K-1
K
1
roots may be chosen such that terms of
PtZ
Pt
Z
in the
K-1
K
1
even powers of
ZZ are
zero.
Equation 10 is the
K=2
K
2
solution to Equation 17. Therefore,
RtZ=1-12Z
Rt
Z
1
1
2
Z
so
β=-12
β
1
2
and, from Equation 15, the
factors of
Rz
R
z
are
Rz=αz+11+αz-11+α2
R
z
α
z
1
1
α
z
1
α
2
where
α=3-2
α
3
2
. Also
1+Z2=12Z+12121+z-12
1
Z
2
1
2
Z
1
2
1
2
1
z
2
Hence
H0z=121+α21+z-121+αz-1=0.4830+0.8365z-1+0.2241z-2-0.1294z-3
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
H1z=z-3G0-z=z-3H0-z-1=0.1294+0.2241z-1-0.8365z-2+0.4830z-3
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 Figure 3. 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
G0
,
G1
G1
filters give the time reverse of these wavelets and
identical frequency responses.
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.
To ensure that the filters
H0
H0
,
H1
H1
and
G0
G0
,
G1
G1
are linear phase, the factors in
ZZ must be allocated to
H0
H0
or
G0
G0
as a whole and not be split, as was done for the
Daubechies filters. In this way the symmetry between
zz and
z-1
z
is preserved in all filters.
Perfect balance of frequency responses between
H0
H0
and
G0
G0
is then not possible, if PR is preserved, but we
have found a factorisation of
PtZ
Pt
Z
which achieves near balance of the responses.
This is:
PtZ=1+Z1+aZ+bZ21+Z1+cZ
Pt
Z
1
Z
1
a
Z
b
Z
2
1
Z
1
c
Z
(18)
This is a
5th
5th
order polynomial, and if the terms in
Z2
Z
2
and
Z4
Z< 
