Exercise 4

In Example 3.2.7, we looked at a basis for \(\real^4\) that we called the Haar wavelet basis. The basis vectors are

\begin{equation*} \vvec_1=\fourvec{1}{1}{1}{1}, \vvec_2=\fourvec{1}{1}{-1}{-1}, \vvec_3=\fourvec{1}{-1}{0}{0}, \vvec_4=\fourvec{0}{0}{1}{-1}\text{,} \end{equation*}

which may be understood graphically as in Figure 3.3.11. We will denote this basis by \(\wcal\text{.}\)

Figure 3.3.11 The Haar wavelet basis represented graphically.

The change of coordinates from a vector \(\xvec\) in \(\real^4\) to \(\coords{\xvec}{\wcal}\) is called the Haar wavelet transform and we write

\begin{equation*} \coords{\xvec}{\wcal} = \fourvec{H_1}{H_2}{H_3}{H_4}\text{.} \end{equation*}

The coefficients \(H_1,H_2,H_3,H_4\) are called wavelet coefficients.

Let's work with the \(4\times4\) block of luminance values in the upper left corner of our larger \(8\times8\) block:

\begin{equation*} \left[\begin{array}{rrrr} 176 \amp 170 \amp 170 \amp 169 \\ 181 \amp 179 \amp 175 \amp 167 \\ 165 \amp 170 \amp 169 \amp 161 \\ 139 \amp 150 \amp 164 \amp 166 \end{array}\right]\text{.} \end{equation*}
  1. The following Sage cell defines the matrix W whose columns are the basis vectors in \(\wcal\text{.}\) If \(\xvec\) is the first column of luminance values in the \(4\times4\) block above, find the wavelet coefficients \(\coords{\xvec}{\wcal}\text{.}\)

  2. Notice that \(H_1\) gives the average value of the components of \(\xvec\) and \(H_2\) describes how the averages of the first two and last two components differ from the overall average. The coefficients \(H_3\) and \(H_4\) describe small-scale variations between the first two components and last two components, respectively.

    If we set the last wavelet coefficients \(H_3=0\) and \(H_4=0\text{,}\) we obtain the wavelet coefficients \(\coords{\yvec}{\wcal}\) for a vector \(\yvec\) that approximates \(\xvec\text{.}\) Find the vector \(\yvec\) and compare it to the original vector \(\xvec\text{.}\)

  3. What impact does the fact that \(H_3=0\) and \(H_4=0\) have on the form of the vector \(\yvec\text{?}\) Explain how setting these coefficients to zero ignores the behavior of \(\xvec\) on a small scale.

  4. In the JPEG compression algorithm, we looked at the Fourier coefficients of all the columns of luminance values and then performed a Fourier transform on the rows. The Sage cell below will perform the same operation using the wavelet transform; that is, it will first find the wavelet coefficients of each of the columns and then perform the wavelet transform on the rows. You only need to evaluate the cell to find the wavelet coefficients obtained in this way.

  5. Now set all the wavelet coefficients equal to zero except those in the upper left \(2\times2\) block and use them to define the matrix coeffs in the Sage cell below. This has the effect of ignoring all of the small-scale differences. Evaluating this cell will recover the approximate luminance values.

  6. Explain how the wavelet transform and this approximation can be used to create a lower resolution version of the image.

This kind of wavelet transform is the basis of the JPEG 2000 compression algorithm, which is an alternative to the usual JPEG algorithm.