CS – 4802

Final Project

 

Jiri Sumbera

Wavelet Transform using Haar Wavelets

 

Introduction

 

The following project tried to accomplish the following:

Within application developed for CS-4802 labs:

-          add the ability to perform both forward and inverse WT using the Haar functions as the set of basis functions

-          add the ability to:           - threshold frequencies in the wavelet domain

 - extract image using only first n x n coefficients

 

Secondary Goals:

- investigate on the usability of WT as an effective compression technique.

 

 

Wavelet transform

The following pictures show a 256x256 original and its true mode and absolute value mode wavelet domain representations as well as a schematic picture showing how the frequency information is stored[1]. It is not surprising to see the original image emerge in each of the sub-rectangles as the position of the coefficients is directly related to the translation parameter of the WT[2].

 

 

Quad 4
 

Quad 3
 

Quad 2
 

Quad 1
 

 

Figure 1 – a) original picture, b) true mode wavelet representation, c) absolute mode wavelet representation, d) schematic diagram of frequency content storage within the transform

 

The absolute mode image shows more clearly where the important coefficients (i.e. non-zero) really are, whereas the true mode image shows that positive and negative coefficients usually occur together (i.e. when a sharp edge is present in the image).

 

Effect of thresholding

The original wavelet domain representation contains many regions with zero values (show as black in Fig. 1-c). In fact, the number of zeros[3] is 3992, which represents about 6.1% of all the points. The frequency coefficients range from –40 to 111. The following pictures show the effect of thresholding on the reconstructed image.

Thresholding in the interval (-1,1) (i.e. all coefficients between –1 an 1 were set to zero) increased the abundance of zeros to 45.1%. Notice, the image bears almost no signs of quality loss.

 

 

 

 

 

Figure 2 – a) thresholded in (-1,1) b) thresholded in (-2,2) c) thresholded in (-4,4) d) thresholded in (-8,8)

Threshold (-2,2) increased the abundance of zeros to 64.1% and first quality depreciation can be observed. Threshold (-4,4) increased the percentage of zeros to 82.8%. It is worthwhile noticing that quality loss is most obvious in regions with gradual changes in intensity. On the other hand, edges and regions of high contrast are still quite clearly distinguishable. Threshold (-8,8) deteriorates the quality of the image considerably, however it should be noted that only 5.0% of the points were left non-zero.

 

Effect of Extraction using only NxN coefficients[4]

The idea behind this approach is to be able to extract at least some amount of information about the whole image from a low volume of data[5] - also known as progressive extraction.

 

 

 

 

 

Figure 4 – images extracted using the first a) 32x32, b) 64x64, c) 128x128, d) 96x96 coefficients

The images on Fig 4a)b)c) show how the effect of the NxN extraction is equivalent to image pixelizing or downsampling[6]. In addition, the last image shows  NxN extraction, where N is not a power of 2. Clearly 96x96 pixels contain 225% more information than a 64x64 image, however this extra data is unevenly distributed as the precision doubles in the first quadrant only, the second and third quadrants are only partially affected[7].

 

 

Conclusion

 

It was shown that reasonable level of thresholding may greatly reduce the number of data points required for holding the data at a relatively low quality loss. Such a thresholding is appropriate only in the case of coefficients whose absolute values are low. In addition, the various thresholds shown that the at first unexplainable asymmetry in the extreme values of negative and positive coefficients could be explained by asserting the spectrum was symmetrical, the only asymmetrical value being the overall graylevel coefficient stored in pixel [1,1][8].

Finally it was also shown that wavelet transform is capable of supporting progressive extraction[9], which makes it ideal for bandwidth-limited applications, e.g. web-based graphics.

Further possible directions of improvement (which could not be pursued due to the limited scope of this paper) include:

-          investigating the effect of rounding-off of the wavelet coefficients to the nearest integer, or fraction possibly with adaptive rounding-off.

-         investigating the whole nature of the wavelet coefficients spectrum with the aim of reduction in the storage space required to store the coefficients

-         implementing other wavelet basis, such as the Daubechies basis

 

 

Bibliography

 

[1] J.R.Parker, Algorithms for Image Processing and Computer Vision, John Viley 1996, p. 250-254

[2] RobiPolikar, The Wavelet Tutorial,

http://engineering.rowan.edu/~polikar/WAVELETS/WTtutorial.html


Appendix

The images below show the effect on the wavelet coefficients by using image dimensions, which are not powers of two. Due to padding with zeros, corresponding multiple stripes in the wavelet domain are created

                           

 

             

 

                                         

Figure 6 – original images and their WT for sizes 128x256, 256x128 and 202x202


[1] (the relation between j and frequency is f » 2j, subscripts refer to horizontal and vertical information)

[2] Again, for more details why this is so, please refer to the Appendix.

[3] using the double storage type computing precision

[4] In fact, the extraction was simulated by setting the other coefficients to zero.

[5] This is useful during image download as an overall, continuously improving image may be reconstructed.

[6] which is exactly what it is – frequency f in a large image corresponds to frequency 2f in a downsampled image

[7] In quadrant 2, resolution improves in the vertical direction, while in quadrant 3 in the horizontal one

[8] In other words the original wavelet spectra could be greatly enhanced if the first pixel was excluded from the calculations of the extreme values – see the appendix for more.

[9] provided the data is accessed in a manner as to follow two sides of an increasing square as opposed to classical access by consecutive lines. This approach would also lead to great savings for images which are not powers of two (as the consecutive length of zeros would be much longer, i.e. ideal for RLC – see appendix for more