2.1 The haar transform

Probably the simplest useful energy compression process is the Haar transform. In 1-dimension, this transforms a 2-elementvector $\begin{pmatrix}x(1) & x(2)\\ \end{pmatrix}^T$ into $\begin{pmatrix}y(1) & y(2)\\ \end{pmatrix}^T$ using:

Note that $T$ is an orthonormal matrix because its rows are orthogonal to each other(their dot products are zero) and they are normalised to unit magnitude. Therefore $T^{(-1)}=T^T$ . (In this case $T$ is symmetric so $T^T=T$ .) Hence we may recover $x$ from $y$ using:

If $$x=\begin{pmatrix}a & b\\ c & d\\ \end{pmatrix}$$ then $$y=\frac{1}{2}\begin{pmatrix}a+b+c+d & a-b+c-d\\ a+b-c-d & a-b-c+d\\ \end{pmatrix}$$ These operations correspond to the following filtering processes:

• Top left: $a+b+c+d$ = 4-point average or 2-D lowpass (Lo-Lo) filter.
• Top right: $a-b+c-d$ = Average horizontal gradient or horizontal highpass and vertical lowpass (Hi-Lo) filter.
• Lower left: $a+b-c-d$ = Average vertical gradient or horizontal lowpass and vertical highpass (Lo-Hi) filter.
• Lower right: $a-b-c+d$ = Diagonal curvature or 2-D highpass (Hi-Hi) filter.

It is clear from that most of the energy is contained in the top left (Lo-Lo) subimageand the least energy is in the lower right (Hi-Hi) subimage. Note how the top right (Hi-Lo) subimage contains thenear-vertical edges and the lower left (Lo-Hi) subimage contains the near-horizontal edges.

The energies of the subimages and their percentages of the total are:

Total energy in and = $208.99E6$ .

We see that a significant compression of energy into the Lo-Lo subimage has been achieved. However the energy measurements donot tell us directly how much data compression this gives.

A much more useful measure than energy is the entropy of the subimages after a given amount of quantisation. This gives the minimum number of bitsper pel needed to represent the quantised data for each subimage, to a given accuracy, assuming that we use an idealentropy code. By comparing the total entropy of the 4 subimages with that of the original image, we can estimate the compressionthat one level of the Haar transform can provide.