Question

Wavelets. (12 p)

(a.) Explain some of the advantages of wavelet transformation.

            (b) Considering Haar wavelet transformation how the compression ratio is achieved?

            (c) Consider the following values of 8 pixels:

{x_{3, i}} = {18, 16, 20, 26, 10, 8, 12, 25}, 0 < i < 7

Perform all Haar steps to calculate {x_{2, i}}, {x_{1, i}}, {x_{0, i}}.

Answer 1

a)

A Haar wavelet is the simplest type of wavelet. In discrete form, Haar wavelets are related to a mathematical operation called the Haar transform. The Haar transform serves as a prototype for all other wavelet transforms. Like all wavelet transforms, the Haar transform decomposes a discrete signal into two subsignals of half its length. One subsignal is a running average or trend; the other subsignal is a running difference or fluctuation. The Haar wavelet transform has a number of advantages

• It is conceptually simple.

• It is fast.

• It is memory efficient, since it can be calculated in place without a temporary Array.

• It is exactly reversible without the edge effects that are a problem with other Wavelet transforms. The Haar transform also has limitations which can be a problem with for some applications. In generating each of averages for the next level and each set of coefficients, the

Haar transform performs an average and difference on a pair of values. Then the algorithm shifts over by two values and calculates another average and difference on the next pair. The high frequency coefficient spectrum should reflect all high frequency changes. The Haar window is only two elements wide. If a big change takes place from an even value to an odd value, the change will not be reflected in the high frequency coefficients. The audio de-noising by Haar wavelet is not always so effective, because the transform can’t compress the energy of the original signal into a few high-energy values lying above the noise threshold. Also if we try to use the Haar wavelet for threshold compression of audio signal, we get poor results. So Haar wavelet transform is not useful in compression and noise removal of audio signal processing. Haar 2-tap wavelet can be used to perform the Haar wavelet transforms.

b)

System operation a) Convert the image in the matrix form: In the computer image is stored in the form of array of pixels. These pixel values are ranging from zero (for black) to some positive number (for white). In order to transform a matrix representing an image using Haar Wavelet Transform. We will first discuss the method of transforming vectors called averaging and differencing. Consider a pixel matrix P representing 8x8 image.

576 704 1152 1280 1344 1472 1536 1536 576 60 1216134 1536 1600600 704 640 1156 1088 1344 1408 1536 1600 768 832 1216 1472 1472 1536 1600 1600 832 832 960 1344 1536 1536 1600 1536 832 832 960 1216 1536 1600 1536 1536 960 896 896 1088 1600 1600 1600 1536 768 768 832 832 1280 1472 1600 1600 448 768 704 640 1280 1408 1600 1600 1088 1412 1536 536536 9 32 640

b) Calculate the row-column transformed matrix (T) To demonstrate how wavelet transform works we first describe transforming data string called averaging and differencing. To understand what it actually does we treat each row as separate data string and the final results are:

576 704 1152 1280 1344 1472 1536 1536 640 1216 1408 1536 64 -64 -64 928 1472 288 64 64 64 -64 200 -272 288 64 64 64 64 1

Since the data string has length 2^3=8, there are three steps in transform process. The first four numbers in the second row are the averages of pairs in first row. Similarly, the first two numbers in the third row are the averages of those four averages taken two at a time and the first entry in the last row is the average of the preceding two computed averages. The remaining numbers, shown in bold, measure deviations from the various averages. The first from the first elements of the pairs that gave rise to them: subtracting 640, 1216, 140, 1536 from 576, 1152, 1344, 1536,element by element yields 64, 64, 64 and 0. These are called detail coefficients. They are repeated in each subsequent row of the table.The third and fourth entries in the third row are obtained by subtracting the first and second entries in that row from the first elements of the pairs that start row two subtracting 928, 1472 from 640,1408 element by element yields 288, 64.These two new detail coefficients are also repeated in each subsequent row of the table. Finally, the second entry in the last row,272 is the detail coefficient obtained by subtracting the overall average 1200 from the 928 that starts row three. Averaging and differencing is a reversible process. Here we have lost nothing during transformation. After completing this process on all rows, we move forward in doing the same transformation on columns. The final result is a new 8x8 matrix T, called the Haar wavelet transform of P.

Applying the averaging and differencing technique to P we get the transformed matrix T as follows:

212 306-14654 246840 4 -50-10-20 24 0 72-16 K?38.PA 68 48.M 30, -32 168-486 16 S161616 16 28-16-161616ó -8 44 36 0 80-16 16 0

This matrix has one overall average value in the top left hand corner, and 63 detail elements The point of the wavelet transform is that regions of little variation in the original data manifest themselves as small or zero elements in the wavelet transformed version. The 0's in T are due to the occurrences of identical adjacent elements in P , and the - 2; -4, and 4 in T can be explained by some of the nearly identical adjacent elements in P . A matrix with a high proportion of zero entries is said to be sparse

The real pay-off in the wavelet transmission game is not so much the expectation of sparsity of the transformed matrices, it's the fact that we can fiddle with the \mostly detail" versions to make lots of entries zero: we can alter the transformed matrices, taking advantage of \regions of low activity," and then apply the inverse wavelet transform to this doctored version, to obtain an approximation of the original data Thus we arrive at the door of wavelet compression: Fix a nonnegative threshold value ε and decree that any detail coefficient in the wavelet transformed data whose magnitude is less than or equal to ε will be reset to zero (hopefully, this leads to a relatively sparse matrix), then rebuild an approximation of the original data using this doctored version of the wavelet transformed data. The surprise is that in the case of image data, we can throw out a sizable proportion of the detail coefficients in this way and obtain visually acceptable results. This process is called lossless compression when no information is lost (e.g. if ε =0) otherwise it's referred to as lossy compression

Thresholding: For lossy image compression, we fix a non negative thresholding value and any detail coefficient wavelet data in the transformed matrix whose value is less than or equal to thresholding value is set to the zero. A matrix with high proportion of zero entries is said to be sparse. In lossy compression the transformed matrix is sparser than original

For the instant, we set a thresholding value i.e. ε =20. That means we reset the values in transformed matrix which are less than or equal to 20 to zero. We get the doctored matrix

1212-306-146-54 24 -68-400 36 90 0 D- 24 0 72 0 8238.PA 68ぷ.钢32 56 0 0 32 0 0 -48 80 0

Applying the inverse wavelet transform to D, we get this reconstructed approximation R

R= 742 694 1 178 1074 1344 1424 1540 1540 776 //6 '/60 勓ว้เ ร【งร์เ 135.4 14:38 1610 1610 456 760 668 676 1278 1422 1594 1594

The compression ratio is 99.5733

For application based knowlede you can refer to this link

http://aix1.uottawa.ca/~jkhoury/haar.htm

c) the algorithm is as follows

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

1. Treat the array as n/2 pairs called (a, b)
2. Calculate (a + b) / sqrt(2) for each pair, these values will be the first half of the output array.
3. Calculate (a - b) / sqrt(2) for each pair, these values will be the second half.
4. Repeat the process on the first half of the array.
   (the array length should be a power of two)

The haar transform for given example is as follows

(18+16)/2, (20+26)/2, (10+8)/2, (12+25)/2 (18-16)/2, (20-26)/2, (10-8)/2, (12-25)/2

18, 16, 20, 26, 10, 8, 12, 25

24.040 32.527 12.728 26.163 1.414 -4.243 1.414 -9.192

39.998 27.500 -6.001 -9.924 1.414 -4.243 1.414 -9.192

47.728 8.837 -6.001 -9.924 1.414 -4.243 1.414 -9.192