Image Compression
 
  Introduction
  Classifying image data
  Quantization
  Bit Allocation
  Entropy Coding
  Source Code

Back to main page


Classifying image data


An image is represented as a two-dimentional array of coefficients, each coefficient representing the brightness level in that point. When looking from a higher perspective, we can't differentiate between coefficients as more important ones, and lesser important ones. But thinking more intuitively, we can. Most natural images have smooth colour variations, with the fine details being represented as sharp edges in between the smooth variations. Technically, the smooth variations in colour can be termed as low frequency variations and the sharp variations as high frequency variations.

The low frequency components (smooth variations) constitute the base of an image, and the high frequency components (the edges which give the detail) add upon them to refine the image, thereby giving a detailed image. Hence, the smooth variations are demanding more importance than the details. 

Separating the smooth variations and details of the image can be done in many ways. One such way is the decomposition of the image using a Discrete Wavelet Transform (DWT). 

The DWT of an image

The procedure goes like this. A low pass filter and a high pass filter are chosen, such that they exactly halve the frequency range between themselves. This filter pair is called the Analysis Filter pair. First, the low pass filter is applied for each row of data, thereby getting the low frequency components of the row. But since the lpf is a half band filter, the output data contains frequencies only in the first half of the original frequency range. So, by Shannon's Sampling Theorem, they can be subsampled by two, so that the output data now contains only half the original number of samples. Now, the high pass filter is applied for the same row of data, and similarly the high pass components are separated, and placed by the side of the low pass components. This procedure is done for all rows.

Next, the filtering is done for each column of the intermediate data. The resulting two-dimensional array of coefficients contains four bands of data, each labelled as LL (low-low), HL (high-low), LH (low-high) and HH (high-high). The LL band can be decomposed once again in the same manner, thereby producing even more subbands. This can be done upto any level, thereby resulting in a pyramidal decomposition as shown below.

Fig 1. Pyramidal Decomposition of an Image

As mentioned above, the LL band at the highest level can be classified as most important, and the other 'detail' bands can be classified as of lesser importance, with the degree of importance decreasing from the top of the pyramid to the bands at the bottom.

Fig 2. The three layer decomposition of the 'Lena' image.


The Inverse DWT of an image

Just as a forward transform to used to separate the image data into various classes of importance, a reverse transform is used to reassemble the various classes of data into a reconstructed image. A pair of high pass and low pass filters are used here also. This filter pair is called the Synthesis Filter pair. The filtering procedure is just the opposite - we start from the topmost level, apply the filters columnwise first and then rowwise, and proceed to the next level, till we reach the first level.

Wavelet resources on the web

If wavelets seem to be interesting, you may follow the links given below to learn more.

The wavelet digest page at www.wavelet.org
Wavelab matlab software at www-stat.stanford.edu/~wavelab/
Wavelet papers at www.mathsoft.com/wavelets.html
Amara's wavelet page at www.amara.com/current/wavelet.html
Engineer's Guide to Wavelet Analysis by Polikar at  users.rowan.edu/~polikar/WAVELETS/WTtutorial.html
 
 


Introduction Quantization

Copyright (c) Satish Kumar. S 2001-2003. Last Modified - 22 Oct 2001
Suggestions/Broken links/queries? Write to satish@debugmode.com