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.
\begin{figure}
\begin{center}
\IpeScale{80}\Ipe{fbank.ipe}
\end{center}\end{figure}

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 ( $x \in {\bf R}^{n}$). Recall that the Haar low pass filter H0 simply averages adjacent entries of its input. This operation can be represented by the matrix[*]

\begin{displaymath}H_0^{(n)} = \frac{1}{2}
\left[\begin{array}{ccccccc} 1 & 1 \...
...
& & & & & & 1 \end{array}\right]
\in {\bf R}^{n \times n}.
\end{displaymath}

The Haar high pass filter H1 computes half the difference between successive input samples, and can be represented[*] as

\begin{displaymath}H_1^{(n)} = \frac{1}{2} \left[\begin{array}{rrrrrrr} 1 & -1 \...
...
& & & & & & 1 \end{array}\right]
\in {\bf R}^{n \times n}.
\end{displaymath}

The downsampling operation is represented as the matrix[*]

\begin{displaymath}D^{(n)} = \left[\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 0 & \...
...& 1 & 0 \end{array}\right]
\in {\bf R}^{\frac{n}{2} \times n}
\end{displaymath}

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

\begin{displaymath}L^{(n)} = D^{(n)} H_0^{(n)} =
\frac{1}{2}
\left[\begin{arra...
... 1 & 1 \end{array}\right]
\in {\bf R}^{\frac{n}{2} \times n}.
\end{displaymath}

Similarly, the combined action of high pass filtering and then downsampling is represented as

\begin{displaymath}B^{(n)} = D^{(n)} H_1^{(n)} =
\frac{1}{2}
\left[\begin{arra...
...1 & -1 \end{array}\right]
\in {\bf R}^{\frac{n}{2} \times n}.
\end{displaymath}

The top and bottom branches of the filter bank produce (see figure 1)

\begin{displaymath}y_0 = L^{(n)} x \in {\bf R}^{\frac{n}{2}}
\quad\quad\mbox{ and }\quad\quad
y_1 = B^{(n)} x \in {\bf R}^{\frac{n}{2}},
\end{displaymath}

respectively. The output of the filter bank is

\begin{displaymath}y = \left[\begin{array}{c} y_0 \\ - \\ y_1 \end{array}\right]...
... - \\ B^{(n)} \end{array}\right]
\in {\bf R}^{n \times n}$ }.
\end{displaymath}

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.
\begin{figure}\begin{center}
\IpeScale{95}\Ipe{hier.ipe}
\end{center}\end{figure}

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 $H_{\rm sys}$ which one can think of as rewriting the input x in terms of another basis to produce the output $y = H_{\rm sys}x$. Figure 2 shows the $H_{\rm sys}$ 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

 \begin{displaymath}
\phi(t) = 2 \sum_k h_0(k) \phi(2t-k)
\end{displaymath} (1)

and the wavelet equation

 \begin{displaymath}
w(t) = 2 \sum_k h_1(k) \phi(2t-k)
\end{displaymath} (2)

come into the picture. The function $\phi(t)$ 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
  
$\displaystyle \phi(2^{j-1}t)$ = $\displaystyle 2 \sum_k h_0(k) \phi(2^jt-k)$ (3)
w(2j-1t) = $\displaystyle 2 \sum_k h_1(k) \phi(2^jt-k)$ (4)

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

\begin{displaymath}\phi(t) = \phi(2t) + \phi(2t-1).
\end{displaymath}

The solution to this recurrence is the Haar scaling function

 \begin{displaymath}
\phi(t) = \left\{ \begin{array}{rl}
1 & \mbox{if $t \in [0,1)$ } \\
0 & \mbox{otherwise}
\end{array} \right..
\end{displaymath} (5)

The functions $\phi(t)$, $\phi(2t)$, and $\phi(2t-1)$ are shown in figure 3.
  
Figure: The Haar scaling functions $\phi(t)$, $\phi(2t)$, and $\phi(2t-1)$.
\begin{figure}\begin{center}
\Ipe{haar-scaling.ipe}
\end{center}\end{figure}

The high pass Haar filter H1 is defined by h1(0)=1/2 and h1(1)=-1/2. Substituting into (2) yields

\begin{displaymath}w(t) = \phi(2t) - \phi(2t-1).
\end{displaymath}

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

\begin{displaymath}w(t) = \left\{ \begin{array}{rl}
1 & \mbox{if $t \in [0,1/2)...
...\in [1/2,1)$ } \\
0 & \mbox{otherwise}
\end{array} \right..
\end{displaymath}

The wavelet function w(t) is shown in figure 4.
  
Figure: The Haar wavelet function w(t).
\begin{figure}\begin{center}
\Ipe{haar-wavelet.ipe}
\end{center}\end{figure}

The scaling function $\phi(t)$ is the continuous analog of the discrete low pass filter H0. Applying $\phi(t)$ to f(t) yields

\begin{displaymath}<\!\phi,f\!>\; = \int_{-\infty}^{\infty} \phi(t) f(t) \;{dt} =
\int_0^1 f(t) \;{dt},
\end{displaymath}

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

\begin{displaymath}<\!w,f\!>\; = \int_{-\infty}^{\infty} w(t) f(t) \;{dt} =
\in...
...{\frac{1}{2}} f(t) \;{dt} -
\int_{\frac{1}{2}}^1 f(t) \;{dt}.
\end{displaymath}

The filter $\phi$ 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), $l=0, 1, \ldots, 2^j-1$. Any function in Vj can be represented exactly by a linear combination of the 2j functions

\begin{displaymath}\phi_{jk}(t) = \phi(2^jt-k), \quad k=0, \ldots, 2^j-1.
\end{displaymath}

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 $\phi_{3k} = \phi(2^3t-k)$, $k=0, \ldots, 7$.
  
Figure: The Haar wavelet basis.
\begin{figure}\IpeScale{90}\Ipe{haar-basis.ipe}
\end{figure}

Similarly, the wavelet functions are denoted by

\begin{displaymath}w_{jk}(t) = w(2^jt-k), \quad k=0, \ldots, 2^j-1.
\end{displaymath}

We collect the scaling and wavelet functions at fixed resolution level jin the sets

\begin{displaymath}\Phi_j = \{\; \phi_{jk}(t) \;:\; k=0, \ldots, 2^j-1 \;\}
\qu...
...quad
\Omega_j = \{\; w_{jk}(t) \;:\; k=0, \ldots, 2^j-1 \;\},
\end{displaymath}

respectively.

As previously mentioned, $\Phi_j$ is a basis for Vj. Applying equations (3) and (4) with j=3 to the functions $\phi_{3k}(t) = \phi(2^3t-k)$, $k=0, \ldots, 7$ yields the functions $\phi_{2k}(t) = \phi(2^2t-k)$, $k=0, \ldots, 3$ and w2k(t) = w(22t-k), $k=0, \ldots, 3$. In detail,

\begin{displaymath}\left[\begin{array}{c} \phi_{20} \\ \phi_{21} \\ \phi_{22} \\...
...34} \\ \phi_{35} \\ \phi_{36} \\ \phi_{37} \end{array}\right].
\end{displaymath}

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 $\Phi_2$from the high pass output functions $\Omega_2$. Note that $\Phi_2 \cup \Omega_2$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,

\begin{displaymath}\left[\begin{array}{c} \phi_{10} \\ \phi_{11} \\ w_{10} \\ w_...
...20} \\ \phi_{21} \\ \phi_{22} \\ \phi_{23} \end{array}\right].
\end{displaymath}

This defines the four new functions $\phi_{1k}(t) = \phi(2t-k)$, 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 $\Phi_1$ and high pass outputs $\Omega_1$. The set $\Phi_1 \cup \Omega_1 \cup \Omega_2$ is, again, a basis for V3. Finally, the third row shows the result of applying the dilation and wavelet equations with j=1to $\phi_{1k}(t) = \phi(2t-k)$, k=0,1 to produce the scaling function $\phi_{0k}(t) = \phi(t-k)$, k=0 and the wavelet function w0k(t) = w(t-k), k=0. More precisely,

\begin{displaymath}\left[\begin{array}{c} \phi_{00} \\ w_{00} \end{array}\right]...
...ft[\begin{array}{c} \phi_{10} \\ \phi_{11} \end{array}\right].
\end{displaymath}

The eight functions $\phi_{00}$, w00, w10, w11, w20, w21, w22, w23 in $\Phi_0 \cup \Omega_0 \cup \Omega_1 \cup \Omega_2$form the the Haar wavelet basis for V3. In general, the Haar wavelet basis for Vj contains the 2j functions in $\Phi_0 \cup \Omega_0 \cup \Omega_1 \cup \cdots \cup \Omega_{j-1}$.

   
Some Examples

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

\begin{displaymath}x(t) = \left\{\begin{array}{rl}
9 & \mbox{if $t \in [0,1/4)$...
...)$ } \\
5 & \mbox{if $t \in [3/4,1)$ }
\end{array} \right..
\end{displaymath}

The function x(t) is in the space V2. In terms of the basis $\Phi_2$, x(t) has representation

\begin{displaymath}x = \left[\begin{array}{c} 9 \\ 7 \\ 3 \\ 5 \end{array}\right].
\end{displaymath}

A graphical representation of x(t) in terms of the basis $\Phi_2$ is
.
Applying the Haar sythesis filter bank H(4) to x gives

\begin{displaymath}z = H^{(4)} x = \left[\begin{array}{c} 8 \\ 4 \\ 1 \\ -1 \end...
...} (9+7)/2 \\ (3+5)/2 \\ (9-7)/2 \\ (3-5)/2 \end{array}\right].
\end{displaymath}

The elements of z are the coefficients of the representation of x(t)in terms of the basis $\Phi_1 \cup \Omega_1$.
.
Applying the Haar synthesis filter bank H(2) to the first two elements in z and leaving the high pass outputs in place gives

\begin{displaymath}y = \left[\begin{array}{c} H^{(2)} \left[\begin{array}{c} z_1...
...in{array}{c} (8+4)/2 \\ (8-4)/2 \\ 1 \\ -1 \end{array}\right].
\end{displaymath}

The elements in y are the coefficients of the representation of x(t)in terms of the Haar wavelet basis $\Phi_0 \cup \Omega_0 \cup \Omega_1$.
.
The Haar wavelet transform of the signal $x = [\;\;9\;\;7\;\;2\;\;5\;\;]$ is $y = [\;\;6\;\;2\;\;1\;\;-1\;\;]$.

We can also compute the wavelet transform of x by multiplying the system filter bank matrix $H_{\rm sys}$ by x. Figure 2 shows $H_{\rm sys}$ 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

\begin{displaymath}H_{\rm sys}= \left[\begin{array}{c} L^{(2)} L^{(4)} \\ B^{(2)...
... 0 \\
0 & 0 & \frac{1}{2}& -\frac{1}{2} \end{array}\right].
\end{displaymath}

The system output is

\begin{displaymath}y = H_{\rm sys}x = \left[\begin{array}{c} 6 \\ 2 \\ 1 \\ -1 \end{array}\right],
\end{displaymath}

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 $n \times n$ 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

\begin{displaymath}kn + k \frac{n}{2} + k \frac{n}{4} + \cdots + k \frac{n}{2^{\...
...leq kn (1 + \frac{1}{2}+ \frac{1}{4}+ \cdots) \leq 2kn = O(n).
\end{displaymath}

Essentially, the hierarchical construction implements a fast matrix-vector multiply by taking advantage of the structure of $H_{\rm sys}$.

Another informative example to consider is the Haar transform of a constant signal, say $x = [\;\;c\;\;c\;\;c\;\;c\;\;c\;\;c\;\;c\;\;c\;\;]$. Computing the Haar transform of x is equivalent to decomposing the function $x(t) \equiv c$, $t \in [0,1)$ in terms of the basis $\Phi_0 \cup \Omega_0 \cup \Omega_1 \cup \Omega_2$ for V3. Applying the Haar synthesis filter bank three times gives

\begin{displaymath}x = \left[\begin{array}{c} c \\ c \\ c \\ c \\ c \\ c \\ c \\...
...} c \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{array}\right] = y.
\end{displaymath}

The output y contains only one nonzero coefficient, namely the coefficient for $\phi_{00}(t)=\phi(t)$. This transform result is obvious from the functional point of view since $x(t)=c\phi(t)$. 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

\begin{displaymath}x = \left[\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\...
... \\ -\frac{1}{2}\\
0 \\ 0 \\ 0 \\ 0 \end{array}\right] = y.
\end{displaymath}

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

\begin{displaymath}H^{(n)} = H^{(4)} = \left[\begin{array}{c} L^{(4)} \\ - \\ B^...
...\\
& & 1 & 1 \\
1 & -1 \\
& & 1 & -1 \end{array}\right],
\end{displaymath}

and

\begin{displaymath}(H^{(n)})^T H^{(n)} = H^{(n)} (H^{(n)})^T = \frac{1}{2} I.
\end{displaymath}

Therefore, the matrix $\sqrt{2} H^{(n)}$ is orthogonal. A modified Haar filter bank which includes a scaling by $\sqrt{2}$ before the low pass and high pass operations is orthogonal.

A basis of functions $f_0, f_1, \ldots$ (for some class of functions on the real line) is an orthonormal basis iff

\begin{displaymath}<\!f_i,f_j\!>\; = \int_{t=-\infty}^{\infty} f_i(t) f_j(t) \;{...
...f $i=j$ } \\
0 & \mbox{if $i \neq j$ }
\end{array} \right..
\end{displaymath}

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

\begin{displaymath}f = \sum a_i f_i
\end{displaymath}

gives

\begin{eqnarray*}<\!f,f_j\!>\; & = & <\!\sum_i a_i f_i, f_j\!> \\
& = & \sum_i a_i <\!f_i,f_j\!> \\
<\!f,f_j\!>\; & = & a_j.
\end{eqnarray*}


Therefore, the coefficient aj in the decomposition of f is simply the inner product $<\!f,f_j\!>$ 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 $\phi(t)$ and wavelet function w(t).

About this document ...

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