Wavelet Based Image Compression Techniques

Image Compression Techniques: An Introduction Yumnam Kirani Singh Reseach Co-ordinator, Department of Electronics and Telecommunication Shri Shankaracharya College of Engineering and Technology Junwani Bhilai

Introduction In today’s digital world, when we see digital movie, listen digital music, read digital mail, store documents digitally, making conversation digitally, we have to deal with huge amount of digital data. So, data compression plays a very significant role to keep the digital world realistic. If there were no data compression techniques, we would have not been able to listen songs over the Internet, see digital pictures or movies, Or we would have not heard about video conferencing or telemedicine. How data compression made it possible? What are the main advantages of data compression in digital world? There may be many answers but the three obvious reasons are the saving of memory space for storage, channel bandwidth and the processing time for transmission. Every one of us might have experienced that before the advent MP3, hardly 4 or 5 songs of wav file could be accommodated. And it was not possible to send a wav file through mail because of its tremendous file size. Also, it took 5 to 10 minutes or even more to download a song from the Internet. Now, we can easily accommodate 50 to 60 songs of MP3 in a music CD of same capacity. Because, the uncompressed audio files can be compressed 10 to 15 times using MP3 format. And we have no problem in sending any of our favorite music to our distant friends in any corner of the world. Also, we can download a song in MP3 in a matter of seconds. This is a simple example of significance of data compression. Similar compression schemes were developed for other digital data like images and videos. Videos are nothings but the animations of frames of images in a proper sequence at a rate of 30 frames per second or higher. A huge amount of memory is required for storing video files. The possibility of storing 4/5 movies in DVD CD now rather than we used 2/3 CDs for a movie file is because compression. We will consider here mainly the image compression techniques.

Why do we use JPEG and GIF in the Internet? Everyone who surfs the Internet might have quite familiar with the term JPEG (Joint Expert Photography Group) [13] image format and GIF (Graphics Interchange Format) file format. There are several other image file formats, but these two are accepted as standard and are supported by most of the Internet Browsers. These two formats are different and used for different image sizes. GIF is mainly used for smaller images, such as Icon, thumbnail, etc. And JPEG is used for larger image files. JPEG compressed more while its image quality is poor. GIF compresses less but its image quality is high. If the smaller image files, like icons or Thumbnails, etc are compressed by using JPEG, the icon or thumbnail may be indistinguishably blurred. And if large image file is compressed using GIF, the file size will still be large and it would take more time to download the image to open a web page. And one has to wait idly around half an hour or

so to see a web page containing image of size approximately 5 inch by 5 inch. That will be a horrible experience and would loss patience of the surfer sometimes. That is why, we used JPEG file for compressing large file. It can compress and image 8 to 16 times without introducing much visually distinguishable artifacts in the image. However, if we compress more than 16 times, it starts introducing blocky artifacts in the image. Sometimes, you might have seen such blocky artifacts when you see a web page containing a very large image file that occupies full screen or much beyond the screen size. The image quality depends on the amount of the compression. If we compressed more, the quality of the image degrades more. So, while performing image compression, we have to keep in mind the acceptable quality of the target image. But there is no degradation in the image quality for GIF images. Why? In GIF image file format, the image data are losslessly compressed. Whereas in the case of JPEG mentioned above, the image data are lossily compressed. So there are two main types of compression techniques: Lossless compression and Lossy Compression. It is in the area of lossy compression where researchers put their efforts to evolve newer compression techniques. Research in lossless compression is almost stagnant now. This does not mean that lossless compression technique lose their grip in data compression. It is the indispensable part of text, the sensitive data compression and is being used as the last stage in most of the lossy compression schemes to achieve more compression.

Lossless and Lossy Compression Every compression scheme aims at the removal of data redundancy to represent the data in a more efficient and compact way. The type of redundancy may be different for different types of data. For a text data, the most common form of redundancy is the codeword redundancy where a code for certain symbols or words occur more frequently than others. If we can assign smaller codes for more frequently symbols or words, then we can get compression. Huffman coding, Arithmetic coding, LZW (Lampel Ziv Welch) coding, etc [8] aim at reducing coding redundancy. The next is the inter-element or inter pixel redundancy, also commonly known as spatial redundancy. This type of data redundancy mainly occurs in audio and image data. Predictive coding, differential coding and transform coding aim at the reduction of this type of redundancy. There are two more types of data redundancy called psychovisual redundancy and temporal redundancy. Psychovisual redundancy, also known as spectral redundancy refers to the occurrence of insignificant frequencies of speech or image. Removal of such types of data introduces hardly discernible distortion to our ears or eyes. The temporal redundancy occurs mainly for video data, which refers to the interframe data redundancy of a video signal. Any compression scheme while trying to reduce the redundancy occurred in a data may or may not lead to the loss of some information. Any compression scheme, which reduces the data redundancy without causing any loss of information is called lossless compression scheme.

How do we compare between compression algorithms? There are various ways to compare between two compression algorithms. The parameters are different for lossless and lossy compression schemes. For lossless compression scheme, the first parameter we compare is their compression ratios. Then, we check the time complexity and the memory requirements. Any lossless compression scheme, which

yields higher compression ratio, lesser time complexity and requires lesser memory, is accepted to be a better lossless compression algorithm. For lossy compression, we also compare the quality of the decompressed image. The quality of the decompressed image is measured in terms of PSNR (Peak Signal to Noise Ratio) value. The decompressed image having the higher PSNR value is assumed to have retained better image quality of the original image. It is inversely proportional to the mean square error (MSE). The more the error, the less will be the PSNR value and vice versa. PSNR value is infinite for lossless image compression because the MSE value is zero in lossless compression. Hence, any lossy compression scheme, which gives more PSNR value and more compression ratio, is accepted to be the better compression algorithm.

Why wavelet image compression? We know that lossy JPEG compression introduces blocky artifacts in the decompressed image, which are not desirable and pleasing to the eyes. Lapped Orthogonal Transforms (LOT) [7] was proposed to solve this problem by using smoothing the overlapping blocks. LOT could reduce the blocking effects but its computational complexity is very high and hence LOT is not preferred to use over JPEG. On the other hand, wavelet based image compression introduces no blocky artifacts in the decompressed image. The decompressed image is much smoother and pleasant to eyes. Also, we can achieve much higher compression ratios much regardless of the amount of compression achieved. Another interesting feature of wavelet is that we can improve the quality of the image more and more and by adding more and more detail information. This feature is attractive for what is known as progressive transmission of images. Another lossy compression scheme developed for image compression is the fractal base image compression scheme [1]. However the fractal based image compression beginning to loss ground because it is very complex and time consuming. Moreover, the achievable compression ratio is not high enough as can be achieved by using wavelet. Wavelet can also be used for lossless image compression as well. This is possible by the use of what is known as integer wavelet transforms.

How wavelet image compression works? Wavelet signifies small wave. It was first used in approximating a function by linear combination of various waveforms obtained by translating and scaling the wavelet at various position and scales. It was very old from the time of Alfred Haars. But it was not so popular then because it found no application area. It becomes popular only when Ingrid Daubechies [5] shows that QMF (Quadrature Mirror Filter) filters [6] used in filterbank for subband coding can be generated from the wavelet by using the perfect reconstruction relation of the filter bank. So, what we obtain from the wavelet is a set of QMF filter banks that can be used for subband coding. In a QMF filter bank a signal is first decomposed into low pass and high pass components using low filters. The filter components are reduced their size by half either by rejecting the even or odd samples thereby the total size of the original signal is preserved. The low pass filter component retains almost all distinguishable features of the original signal. And the high pass filter component has little or no resemblance of the original signal. The low pass component is again decomposed into two components. The decomposition process can be continued up to the last possible level or up to a certain desired level. As the high pass filter

components have less information discernible to the original signal, we can eliminate the information contents of the high pass filters partially or significantly at each level of decomposition during the reconstruction process. It is this possibility of elimination of the information contents of the high pass filter components that gives higher compression ratio in the case of wavelet based image compression. Simple decomposition and reconstruction by eliminating less informative parts of the high pass filter components may not always lead to the compression. For we have to use certain coding scheme to get higher compression ratios. Some of the most cited coding algorithms for wavelet based image compression are EZW (Embedded Zerotree Wavelet) [10], SPIHT (Set Partitioning in Hierarchical Tree) [9] and EBCOT (Embedded Block Coding with Optimal Truncation) [11]. EZW is now longer popular as it has been improved to SPIHT. Now SPIHT and EBCOT are the two main contenders for wavelet based image coding. JPEG group has accepted EBCOT as their wavelet based coding scheme to upgrade their JPEG to JPEG2000 version to achieve higher compression ratio and less distortion in the decompressed signal. So, now the main contender is between SPIHT and JPEG2000. In any wavelet based image compression scheme, the achievable compression ratio is not only dependent on the efficiency of the coding scheme, it is also dependent on the choice of appropriate wavelet filters. Different filters give different compression ratios for the same image and coding scheme [4]. There are numerous wavelet filters. It is our task to choice appropriate filters for our compression scheme. For JPEG2000, they used 9/7 biothogonal wavelet filters for lossy image compression and 5/3 for lossless image compression. For SPIHT coding scheme, usually 9/7 biorthogonal filters is used for lossy image compression and S+P transform filters for lossless image compression. However, 9/7 is not the optimal filters for lossy image compression, still lot of research is going on about the finding of optimal filters for lossy image compression for different image types [14]. Wavelet based image compression Example Just to show how wavelet based image compression is performed, a simple image compression example to given here. Fig-1a, is the original image. It is decomposed up to two levels using 9/7 biorthogonal filters. There are one low pass components and six high pass components. The low pass component is also most often referred to as approximation component as it basically represents the approximation of the original signal or image. The high pass components are often referred to as details. So, in figure1b, the top leftmost corner, the rest are the details. We see that the approximation component represents fairly represent the original signal even it is four times reduced in size. Figure-1c gives the decompressed image from the 16 times compressed data. And figure 1-d shows the decompressed image from the 32 times compressed data. However, we see that these decompressed image are visually similar to the original image. However, they are very different numerically. This is how the lossy compression works. Using wavelet based image compression we can compress an image up to 128 times, still we would get distinguishable approximation of the image.

(a) (b) Fig. 6(a) Original Image, and (b) Spectral decomposition and ordering. X

. (c) (d) Fig. 6(c) Compressed image at 16:1, and (d) compressed image at 32:1 References 1. Barnsley, M.F., "Fractal Image Compression", Notices of the AMS, June 1996, p. 657-662. 2. Calderbank, R. C., Daubechies, I., Sweldens, W., and Yeo, B. L. Wavelet Transforms that Map Integers to Integers, Applied and Computational Harmonic Analysis (ACHA), vol. 5, no. 3, pp. 332-369, 1998.

3. Cohen, A., Daubechies, I., and Feauveau, J. C. Biorthogonal Bases of Compactly Supported Wavelets, Comm. on Pure and Applied Mathematics, 1992, vol. XLV, pp. 485-560. 4. Coifman, R. R. and Wickerhauser, M. V. Entropy Based Algorithms for Best Basis Selection, IEEE Trans. Information Theory, vol. 38, no. 2, Mar. 1992, pp. 713718. 5. Daubechies, I. Orthonormal Bases of Compactly Supported Wavelets, Comm. Pure and Applied Math., vol. 41, Nov. 1988, pp. 909-996. 6. Estaban, D. and Galand, C. Application of Quadrature Mirror Filters to Split Band Voice Coding Schemes, Proc. ICASSP, May 1977, pp. 191-195. 7. Malavar, H. S. Signal Processing with Lapped Transforms, Norwood, MA, Artech House, 1992. 8. Nelson, M. The Data Compression Book,2nd ed., M&T books, Nov. 1995, 9. Said, A. and Pearlman, W. A. A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Trans. CSVT, vol. 6, no. 3, June 1996, pp. 243-250. 10. Shapiro, J. M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients, IEEE Trans. SP, vol. 41, no. 12, Dec. 1993, pp. 3445-3462. 11. Taubman, D. High Performance Scalable Image Compression with EBCOT, submitted to IEEE Tran. IP, Mar. 1999,. 12. Vetterli, M. and Herley, C. Wavelets and Filter Banks: Theory and Design, IEEE Trans. SP, vol. 40, no. 9, Sep. 1992, pp. 2207-2232. 13. Wallace, G. K. The JPEG Still Picture Compression Standard, Comm. ACM, vol. 34, no. 4, April 1991, pp. 30-44. 14. Y. K. Singh, S.K. Parui, Shuvransu Bannerjee, "A Comparative study between wavelet and ISITRA filters", IEEE INDICON-2004 conference, Dec, 2004 IIT Kharagpur.