Introduction to Wavelets II
Lecture #2: | Thursday, 2 October 1997
|
Lecturer: | Denis Zorin
|
Scribe: | Scott Cohen
|
Reviewer: | John Owens
|
Filter Banks as Transformations
A filter bank H transforms an input x into an output y=H(x).
Figure 1 shows the familiar example of a synthesis filter bank
that separates the low and high frequencies of a discrete input signal.
Figure:
A synthesis filter bank.
|
If the filter bank is linear, then the corresponding transformation can be
represented as a matrix H, and applying H to x is achieved by
computing the matrix product y=Hx.
As an example, we shall now compute the matrix H for the Haar synthesis
filter bank, assuming an input x consisting of n samples (
).
Recall that the Haar low pass filter H0 simply averages adjacent entries
of its input. This operation can be represented by the
matrix
The Haar high pass filter H1 computes half the difference between
successive input samples, and can be represented
as
The downsampling operation is represented as the matrix
which picks out the first, third, etc. entries of x. The combined action
of low pass filtering and then downsampling is represented by the matrix
Similarly, the combined action of high pass filtering and then downsampling
is represented as
The top and bottom branches of the filter bank produce (see
figure 1)
respectively. The output of the filter bank is
Thus, we have expressed the operation of the Haar filter bank on an input
of length n as the matrix H(n) shown above.
The output of the top branch of the filter bank is a coarse version of the
input signal. We can build a hierarchical representation of a signal
by recursively filtering the low pass output of the filter bank. This
process is illustrated in figure 2.
Figure:
Hierarchical decomposition of a signal.
|
In each step of the recursion, the signal rate decreases by a factor of two.
If the signal is discrete and finite (and a power of two in length),
then we eventually reach a signal with
one sample. In the case of the Haar synthesis filter bank, this sample will be
the average of the elements of the original signal. The sum of the sizes of
all the outputs from the high pass steps and the output of the final low pass
step is equal to the size of the original input. The final, hierarchical
representation of an input
signal is a collection of signal details at various resolution levels
(scales) and a coarse version of the original signal (which is the
output of the final low pass filter). The entire process can be represented as
a single transformation matrix
which one can think of as
rewriting the input x in terms of another basis to produce the output
.
Figure 2 shows the
matrix
that results when the Haar filter bank is applied three times.
When the input to the system is an image (a 2D signal), the
first filter bank application produces a blurred version of the image
(the low pass output) and the details of the original image (sharp edges)
which are not contained in the blurred version (the output of the high pass
filter). The second low pass filter application takes the blurred version
from step one and blurs it even further. The differences between the second
blurred image and the first blurred image are captured in the output of the
second high pass filter. This recursive process transforms an image into a
collection of images that capture image details at different scales
and one final coarse image.
The Haar Wavelet Basis
If a hierarchical decomposition via filter banks writes a signal in terms
of new basis, what is this new basis? Answering this question is where
the dilation equation
|
(1) |
and the wavelet equation
|
(2) |
come into the picture. The function
is called the
scaling function, and the function w(t) is called the
wavelet function. The dilation equation and wavelet equation
must hold for all t. Replacing t by 2j-1t gives
This last set of equations is more convenient for describing the
construction of the wavelet basis corresponding to a filter bank.
We now illustrate the wavelet basis construction from the dilation equations
using the Haar filter bank. Recall that the low pass Haar filter H0is defined by
h0(0)=h0(1)=1/2 (all other coefficients are zero).
Substituting the Haar low pass filter into equation (1),
we get
The solution to this recurrence is the Haar scaling function
|
(5) |
The functions ,
,
and
are shown in
figure 3.
Figure:
The Haar scaling functions ,
,
and
.
|
The high pass Haar filter H1 is defined by
h1(0)=1/2 and
h1(1)=-1/2. Substituting into (2) yields
It follows easily from (5) that the Haar wavelet function is
The wavelet function w(t) is shown in figure 4.
Figure:
The Haar wavelet function w(t).
|
The scaling function
is the continuous analog of the discrete
low pass filter H0. Applying
to f(t) yields
the average value of f over the interval [0,1).
The wavelet function w(t) is the continuous analog of the discrete
high pass filter H1. Applying w(t) to f(t) yields
The filter
is an averaging operator, and the filter w is a
differencing operator.
Now consider functions defined on the interval [0,1). Let Vj denote
the set of functions that are constant on the 2j subintervals
[l/2j,(l+1)/2j),
.
Any
function in Vj can be represented exactly by a linear combination of the
2j functions
This should be clear (at least for the case j=3) from the upper left hand
corner in figure 5 which shows the 2j=8 functions
,
.
Figure:
The Haar wavelet basis.
|
Similarly, the wavelet functions are denoted by
We collect the scaling and wavelet functions at fixed resolution level jin the sets
respectively.
As previously mentioned,
is a basis for Vj.
Applying equations (3) and (4) with
j=3 to the functions
,
yields
the functions
,
and
w2k(t) = w(22t-k),
.
In detail,
The results of this step are shown in the middle and last columns of the
first row. The final column in the
first row shows the separation of the low pass output functions from the high pass output functions .
Note that
is also a basis for V3. The low pass output functions are further refined
by once again applying equations (3)
and (4), this time with j=2. In matrix notation,
This defines the
four new functions
,
k=0,1, and
w1k(t) = w(2t-k), k=0,1 shown in the second row of
figure 5. The last column of this row shows the separation
of the low pass outputs
and high pass outputs .
The set
is, again, a basis for V3. Finally,
the third row shows the result of applying the dilation and wavelet equations
with j=1to
,
k=0,1 to produce the scaling function
,
k=0 and the wavelet function
w0k(t) = w(t-k), k=0. More precisely,
The eight functions ,
w00, w10, w11, w20, w21,
w22, w23 in
form the the Haar wavelet basis for V3. In general, the Haar wavelet
basis for Vj contains the 2j functions in
.
Some Examples
Suppose we have a function
x(t) defined on [0,1) by
The function x(t) is in the space V2. In terms of the basis ,
x(t) has representation
A graphical representation of x(t) in terms of the basis
is
.
Applying the Haar sythesis filter bank H(4) to x gives
The elements of z are the coefficients of the representation of x(t)in terms of the basis
.
.
Applying the Haar synthesis filter bank H(2) to the first two elements
in z and leaving the high pass outputs in place gives
The elements in y are the coefficients of the representation of x(t)in terms of the Haar wavelet basis
.
.
The Haar wavelet transform of the signal
is
.
We can also compute the wavelet transform of x by multiplying the system
filter bank matrix
by x. Figure 2 shows
when
the Haar
synthesis filter bank is applied three times. In the example in this section,
we only need two applications and the input vector has length n=4. This
results in the matrix
The system output is
just as we derived previously using the hierarchical construction.
In general, computing the
representation of an n-dimensional vector in a different basis via an
matrix-vector multiplication requires O(n2)arithmetic operations. For computing the Haar wavelet transform, however,
we can do better. The hierarchical construction given at the beginning of
this section requires only O(n) arithmetic operations. In fact, if
applying the synthesis filter bank to an n-sample signal requires
at most kn operations for some constant k (as it does for the Haar
filter bank), then the total number of operations to compute the wavelet
transform is at most
Essentially, the hierarchical construction implements a fast matrix-vector
multiply by taking advantage of the structure of
.
Another informative example to consider is the Haar transform of a constant
signal, say
.
Computing
the Haar transform of x is equivalent to decomposing the function
,
in terms of the basis
for V3. Applying the Haar
synthesis filter bank three times gives
The output y contains only one nonzero coefficient, namely the coefficient
for
.
This transform result is obvious from the
functional point of view since
.
Discarding the zero
coefficients in the output leaves a very compact representation of the signal
x (one which is eight times smaller than the original representation). In
general, the Haar basis provides a compact representation for parts of a
signal with little variation.
For the final example of this section, consider the Haar transform of
the delta signal
Note that 11 of the 16 output coefficients are zero. This is not the case
for the Fourier transform of x which contains energy at all frequencies.
The coefficients of the Haar basis functions whose
support interval (i.e. the interval over which the basis function is
nonzero) does not overlap with the support of the represented
function are all zero. The Haar basis allows one to make spacially localized
(at some scale) changes to a function by simply adjusting the coefficient(s)
for the basis function(s) of the appropriate scale (j) and location
(k). This is very different from the Fourier representation in which a
change to a single basis function coefficient causes spacially global
changes to the represented function.
Orthogonal Filter Banks and Wavelet Bases
In section 1, we showed how to view a filter bank as a
transformation represented by a square matrix H (assuming the input
and output are the same size). We say that a filter bank is orthogonal
if its corresponding matrix is orthogonal. A matrix H is orthogonal if its
inverse is equal to its transpose:
HT H = H HT = I. The set of column
vectors and the set of row vectors of an orthogonal matrix are both
orthonormal sets of vectors (it would make more sense to call
such matrices orthonormal, but the historical term for such matrices is
orthogonal). With a suitable scaling of the input before low pass
and high pass filtering, the Haar filter bank is indeed orthogonal. For
example, for n=4 we have
and
Therefore, the matrix
is orthogonal. A modified Haar
filter bank which includes a scaling by
before the
low pass and high pass operations is orthogonal.
A basis of functions
(for some class of functions on the
real line) is an orthonormal basis iff
It is very easy to write a function f in terms of an orthonormal
basis. Taking the inner product with fj with both sides of
gives
Therefore, the coefficient aj in the decomposition of f is simply the
inner product
of f with the jth basis function fj. In
section 2 we saw how a filter bank gives rise to a wavelet
basis via the dilation and wavelet equations (at least in the case of the
Haar filter bank). What conditions on the filters will guarantee an
orthonormal wavelet basis?
It turns out that orthogonality of a filter bank implies orthonormality
of the basis generated by the filter bank though the dilation and wavelet
equations.
The proof of this fact will be given in the next lecture. Since the
normalized Haar filter bank is orthogonal, this fact implies that the
corresponding normalized Haar wavelet basis is orthonormal. The wavelet basis
given in section 2 is not normalized, but its
orthogonality can be verified directly from the equations for its scaling
function
and wavelet function w(t).
Introduction to Wavelets II
This document was generated using the
LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)
Copyright © 1993, 1994, 1995, 1996, 1997,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 lect02.tex.
The translation was initiated by Scott Cohen on 1998-11-27
Footnotes
- ...
matrix
- Note that H0(n) averages the final entry of xwith zero since there is no next element. This is a moot point since the
downsampling step that follows throws away the last entry of
H0(n) x.
- ... represented
- The filter
matrix H1(n) differences the final entry of x with zero since there is
no next element. This boundary anomaly is, once again, a moot point since the
downsampling step that follows throws away the last entry of
H1(n) x.
- ... matrix
- Here we
have tacitly assumed that n is even. Since the downsampling operation
picks out the first, third, etc. components of its input, the last
component will be discarded.
- ... function
- This example is taken directly from
the paper ``Wavelets for Computer Graphics: A Primer (Part 1)'' by
Eric J. Stollnitz, Tony D. DeRose, and David Salesin in
IEEE Computer Graphics and Applications, 15(3):76-84, May 1995.
It is also available online at
http://www.cs.washington.edu/research/graphics/projects/wavelets/article/.
Scott Cohen
1998-11-27