Appendix G: Compression via DWT with Thresholding
An important applicationofdiscrete wavelet transformation is image compression. Anyone who has stored high-resolution digital images or videos knows that such files can be very large. DWT can reduce image size significantly with just a minimal loss of quality by storing only a small number of smooth components and only as many detailed components as needed for a fixed resolution. To compress an image, we compute and store the DWT of each row of the image, setting all wavelet coefficients smaller than acertain threshold to zero (thresholding). When the image is needed, the inverse wavelet transform is used to reconstruct each row of the original image. For example, Table G.1 shows file sizes resulting from using DWT for image compression. We note (columns 1 and 2) that there is a factor-of-2 reduction in size arising from storing the DWT rather than the data themselves, and that this is independent of the threshold criteria (it still stores the zeros). After the compression program WinZip removes the zeros (columns 3 and 4), we note that the DWT file is a factor of 3 smaller than the compressed original, and a factor of 11 smaller than the noncompressed original.
A usual first step in dealing with digital images is to convert from one picture format to another.1 We started with a 3073 ×2304 pixel (picture element) jpg (Joint Photographic Experts Group) color image. For our example (Figure G.1 left) we reduced the image size to 512 × 512 (a power of 2)and converted it to gray scale. You can do this with the free program IrfanView [irfanview] (Windows),the GNU image editor The Gimp (Unix/Linux) [Gimp], or Netpbm [Netpbm]. We used Netpbm’s utility jpegtopnm to convert the .jpg to the portable gray map image in Netpbm format:
If you open mariana.pnm (available on the CD: http://press.princeton.edu/landau_survey/), you will find strings such as
P5
512 512
255
yvttsojgrvv|yngcawbRQ] …
This format is not easy to work with, so we converted it to mariana,
Except for the first three lines that contain information about the internal code (width, height, 0 for black, and 255 for white), we now have integers:
TABLE G.1
Compression of a Data File Using DWT with a 20% Cutoff Threshold
Original File |
DWT Reconstructed |
WinZipped Original |
WinZipped DWT |
25,749 |
11,373 |
7,181 |
2,447 |
Figure G.1 Left: The original picture of Mariana. Middle: The reconstituted picture for a compression ratio of 8 (ε = 9). Right: The reconstituted picture for a compression ratio of 46 (ε = 50). The black dots in the images are called “salt and pepper” and can be eliminated.
Because Java is not very flexible with I/O formats, we wrote a small C program to convert mariana to the one-column format mariana.dat:
Now that we have an accessible file format, we compress and expand it:
1. Read the one-column file and form the array fg[512][512] containing all the information about the image.
2. Use the program DaubMariana.java on the CD (available online: http://press.princeton.edu/landau_survey/) to apply the Daubechies 4-wavelet transform to each row of fg. This forms a new 2-D array containing the transformed matrix.
3. Use DaubMariana.java again, now transforming each column of the transformed matrix and saving the result in a different array.
4. Compress the image by selecting the tolerance level eps=9 and eliminating all signals that are smaller than eps:
if abs(fg[i][j]) < eps, fg[i][j]=0
5. Apply the inverse wavelet transform to the modified array, column by column and then row by row.
6. Save the reconstituted image to Marianarec via output redirection:
> java DaubMariana > Marianarec
7. The program also creates the file comp-info.dat containing information about the compression:
If the program is compiled and run again, the resulting output will contain the compression image in a file with many zeros:
Although this is an image file, it is not meant for viewing as an image (it will be mainly black).
G.1 More on Thresholding
Often in practical applications, a good number of the wavelet coefficients are nearly equal to zero. When these coefficients are set to zero via some thresholding scheme [D&J 94], DWT files containing long strings of zeros result. Through a type of compression known as entropy coding, the amount of memory needed to store files of this sort can be greatly reduced.
Before we go on to compression algorithms, it is important to note that there are different types of thresholding. In hard thresholding, a rather arbitrary tolerance is selected, and any wavelet coefficient whose absolute value is below this tolerance is set to zero. Presumably, these small numbers have only small effects on the image. In soft thresholding, a tolerance h is selected, and, as before, any wavelet coefficient whose absolute value is below this tolerance is set to zero. However, all other entries d are replaced with sign(d) d — h. Soft thresholding can be thought of as a translation of the signal toward zero by the amount h. Finally, in quantile thresholding, a percentage p of entries are selected, and p percent of those entries with the smallest absolute values are set to zero.
DWT with thresholding is useful in analyzing signals and for compressing signals so that less memory is needed to store the transforms than to store the original signals. However, we have yet to take advantage of the frequent occurrence of zeros as wavelet coefficients. Huffman entropy coding is well suited for compressing data that contain many zeros. With this method, an integer sequence q is changed to a shorter sequence e that is stored as 8-bit integers. Strings of zeros are coded by the numbers 1-100,105, and 106, while nonzero integers in q are coded by 101-104 and 107-254. The idea is to use two or three numbers for coding, with the first being a signal that a large number or a long zero sequence is coming. Entropy coding is designed so that the numbers that are expected to appear the most often in q need the least amount of space in e.
A step in compression, known as quantization, converts a sequence w of floatingpoint numbers to a sequence q of integers. The simplest technique is to round the floats to the nearest integer. Another option is to multiply each number in w by a constant k and then round to the nearest integer. Quantization is called lossy because information is lost when a float is converted to an integer. In Table G.1 we showed the effect of compression using the WinZip data compression algorithm. This is a hybrid of LZ77 and Huffman coding also known as Deflate.
G.2 Wavelet Implementation and Assessment
1. Write a program to plot Daub4 wavelets. (Our sample program is Daub4.java.) Observe the behavior of the wavelet functions for different values of the coefficients. In order to do this, place a 1 in the coefficient vector for the wavelet structure you want and place 0’s in all other locations. Then perform the inverse transform to produce the physical domain representation of the wavelet.
2. Run the code Daub4.java for different threshold values.
3. Run the code DaubCompress.java that uses other functions to give input data.
4. Write a Java program or applet that compresses a 512 × 512 image using Daub4 wavelets. To do this, extend method wt1 so that it performs a 2-D wavelet transform. Note that you may need some methods from the java.awt.image package to plot the images. First, create an Image object using Image img. The MemoryImageSource class is used to create an image from an array of pixel values using the constructor MemoryImageSource(int w, int h, int pix[], int depls, int scan). Here w and h are the dimensions of the image, pix [] is an array containing the pixels values, depls is the deployment of data in pix [], and scan is the length of a row in pix []. Finally, draw the image using drawImage(Image img, int x, int y, this), where x and y are the coordinates of the left corner of the image. Alternatively, you can use a program such as Matlab or Maple to display images from an array of integers.
5. Modify the program DaubCompress.java so that it outputs the DWT to a file.
6. Pick a different function to analyze, the more complicated the better.
7. Plot the resulting DWT data in a meaningful way.
8. Show in your plots the effects of increasing the threshold parameter in order to cut out more of the smaller transform values.
9. Examine the reconstituted signal for various threshold values including zero and note the effect of the cutoff on the image quality.
1 We thank Guillermo Avendanño-Franco for help with image programs.