WAVELET-BASED IMAGE COMPRESSION

With the growth of technology and the entrance into the Digital Age, the world has found itself amid a vast amount of information. Dealing with such enormous amount of information can often present difficulties. Digital information must be stored and retrieved in an efficient manner, in order for it to be put to practical use. Wavelet compression is one way to deal with this problem.

For example, the FBI uses wavelet compression to help store and retrieve its fingerprint files. The FBI possesses over 25 million cards, each containing 10 fingerprint impressions. To store all of the cards would require over 250 terabytes of space. Without some sort of compression, sorting, storing, and searching for data would be nearly impossible. Using wavelets, the FBI obtains a compression ratio of about 1:20.

The steps needed to compress an image are as follows:

1. Digitize the source image into a signal s, which is a string of numbers.
2. Decompose the signal into a sequence of wavelet coefficients w.
3. Use thresholding to modify the wavelet coefficients from w to another sequence w'.
4. Use quantization to convert w' to a sequence q.
5. Apply entropy coding to compress q into a sequence e.

The first step in the wavelet compression process is to digitize the image. The digitized image can be characterized by its intensity levels, or scales of gray which range from 0 (black) to 255 (white), and its resolution, or how many pixels per square inch. Each of the bits involved in creating an image takes up both time and money, so a tradeoff must be made.

In certain signals, many of the wavelet coefficients are close or equal to zero. Through a method called thresholding, these coefficients may be modified so that the sequence of wavelet coefficients contains long strings of zeros. Through a type of compression known as entropy coding, these long strings may be stored and sent electronically in much less space. There are different types of thresholding. In hard thresholding, a tolerance is selected. Any wavelet whose absolute value falls below the tolerance is set to zero with the goal to introduce many zeros without losing a great amount of detail. There is not a straightforward easy way to choose the threshold, although the larger the threshold that is chosen the more error that is introduced into the process. Another type of thresholding is soft thresholding. Once again a tolerance, h, is selected. If the absolute value of an entry is less than the tolerance, than that entry is set to zero. 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. A third type of thresholding is quantile thresholding. In this method a percentage p of entries to be eliminated are selected. The smallest (in absolute value) p percent of entries are set to zero.

Wavelets and thresholding help process the signal, but up until this point, no compression has yet occurred. One method to compress the data is Huffman entropy coding. With this method, and integer sequence, q, is changed into a shorter sequence, e, with the numbers in e being 8 bit integers. The conversion is made by an entropy coding table. Strings of zeros are coded by the numbers 1 through 100, 105, and 106, while the non-zero integers in q are coded by 101 through 104 and 107 through 254. In Huffman entropy coding, the idea is to use two or three numbers for coding, with the first being a signal that a large number or 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.

The fourth step of the process, known as quantization, converts a sequence of floating numbers w' to a sequence of integers q. The simplest form is to round 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 it introduces error into the process, since the conversion of w' to q is not a one-to-one function.

In order to process an image, symmetric biorthogonal wavelets are used. These have two father and two mother wavelets, and are required in order to compress a matrix of data. The Daubechies wavelet family is the most widely used wavelet for image compression, with six coefficients and biorthogonality.

Deslauriers wavelets are also symmetric biorthogonal wavelets. We used this set of wavelets for the transform of our image.

[back to main page]