CS – 4802
Final Project
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 1
Quad 2
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