Haar Wavelet Transform

(hello CMPT 866 students)

To calculate the Haar transform of an array of n samples:

Find the average of each pair of samples. (n/2 averages)
Find the difference between each average and the samples it was calculated from. (n/2 differences)
Fill the first half of the array with averages.
Fill the second half of the array with differences.
Repeat the process on the first half of the array.
(The array length should be a power of two)

Average / Difference

Two samples, l and r, can be expressed as an average, a, and a difference, d, like in mid-side coding:

a = (l + r) / 2
d = a - l = r - a

This is reversible:

l = a - d
r = a + d

Example

Eight elements:

7 1 6 6 3 -5 4 2

Averages:

(7 + 1) / 2 = 4 (6 + 6) / 2 = 6 (3 + -5) / 2 = -1 (4 + 2) / 2 = 3
Differences:

(7 - 4) = ( 4 - 1) = 3 (6 - 6) = ( 6 - 6) = 0 (3 - -1) = (-1 - -5) = 4 (4 - 3) = ( 3 - 2) = 1

4 6 -1 3 3 0 4 1

Four elements:

4 6 -1 3 3 0 4 1

Averages:

( 4 + 6) / 2 = 5 (-1 + 3) / 2 = 1
Differences:

( 4 - 5) = (5 - 6) = -1 (-1 - 1) = (1 - 3) = -2

5 1 -1 -2 3 0 4 1

Two elements:

5 1 -1 -2 3 0 4 1

Averages:

(5 + 1) / 2 = 3
Differences:

(5 - 3) = (3 - 1) = 2

3 2 -1 -2 3 0 4 1

We can't recurse any further. Note that the first value in the resulting array is the average value of all the samples in the original array:

(7 + 1 + 6 + 6 + 3 - 5 + 4 + 2) / 8 = 3

2D Transform

Given a two-dimensional array of values, we can perform a 2D Haar transform by first performing a 1D Haar transform on each row:

- - - >

And then on each column:

|

|

|

V

Image Compression

The Haar transform can be used in lossy image compression:

1. Original image > > >
2. Haar coefficients

3. Quantized coefficients > > >
4. Reconstructed image

The blocky artifacts are interesting (mainly because we're all so used to JPEG artifacts). In the above example, I threw away 90% of the coefficients, so that only the strongest (in terms of amplitude) 10% remained.

This approach fails miserably when dealing with images that have strong noise:

before > > >
after

For better image quality, the quantization algorithm could be tuned to value coefficients based on their position (upper-left is more significant/obvious than lower right), and to degrade them gradually (using division or bit shifting) rather than zeroing them out.

Source Code

haar.c - forward and reverse Haar transforms, and a simple quantizer to simulate artifacts with.
You might also want my Targa reader/writer.

References

http://online.redwoods.cc.ca.us/instruct/darnold/laproj/Fall97/PMorton/imageComp3/

1. Original image	> > >	2. Haar coefficients

3. Quantized coefficients	> > >	4. Reconstructed image