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.

If the filter bank is linear, then the corresponding transformation can be represented as a matrix

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 *H*_{0} simply averages adjacent entries
of its input. This operation can be represented by the
matrix^{}

The Haar high pass filter

The downsampling operation is represented as the matrix

which picks out the first, third, etc. entries of

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

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.

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

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

and the wavelet equation

come into the picture. The function is called the

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 *H*_{0}is defined by
*h*_{0}(0)=*h*_{0}(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

The functions , , and are shown in figure 3.

The high pass Haar filter

It follows easily from (5) that the Haar wavelet function is

The wavelet function

The scaling function is the continuous analog of the discrete low pass filter

the average value of

The filter is an averaging operator, and the filter

Now consider functions defined on the interval [0,1). Let *V*^{j} denote
the set of functions that are constant on the 2^{j} subintervals
[*l*/2^{j},(*l*+1)/2^{j}),
.
Any
function in *V*^{j} can be represented exactly by a linear combination of the
2^{j} functions

This should be clear (at least for the case

Similarly, the wavelet functions are denoted by

We collect the scaling and wavelet functions at fixed resolution level

respectively.

As previously mentioned,
is a basis for *V*^{j}.
Applying equations (3) and (4) with
*j*=3 to the functions
,
yields
the functions
,
and
*w*_{2k}(*t*) = *w*(2^{2}*t*-*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

This defines the four new functions ,

The eight functions ,

Some Examples

Suppose we have a function^{}
*x*(*t*) defined on [0,1) by

The function

A graphical representation of

.

Applying the Haar sythesis filter bank The elements of

.

Applying the Haar synthesis filter bank The elements in

.

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*(*n*^{2})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 *V*^{3}. Applying the Haar
synthesis filter bank three times gives

The output

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

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:
*H*^{T} *H* = *H H*^{T} = *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

gives

Therefore, the coefficient

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*).

This document was generated using the
**LaTeX**2`HTML` 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

- ...
matrix
^{} - Note that
*H*_{0}^{(n)}averages the final entry of*x*with zero since there is no next element. This is a moot point since the downsampling step that follows throws away the last entry of*H*_{0}^{(n)}*x*. - ... represented
^{} - The filter
matrix
*H*_{1}^{(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*H*_{1}^{(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/`.