Design And Implementation Of Image Compression Routine Using Enhanced SPIHT

Design And Implementation Of Image Compression Routine Using Enhanced SPIHT

Pallavi Chaudhary1, Dr.Vinod Shokeen2, Bhupendra Singp

PG Scholar (EC)1, Assistant Professor-III (EC)2, Assistant Professor-I (EC)3 Amity University Noida, Sec-125, U.P, India

Abstract

The objective of this paper is to design and implement an image compression routine using SPIHT proposed here for achieving higher compression ratio. This paper focuses on the study of SPIHT algorithm and compares its result with SPIHT proposed in terms of compression ratio. First of all on gray scale image (i.e. standard image), discrete wavelet transform (DWT) is applied to break it into wavelets (i.e. high pass wavelet coefficients and low pass wavelet coefficients).Then applying proposed SPIHT on the DWT process output, which is followed by reconstruction of original gray scale image by using SPIHT decoding algorithm and inverse discrete wavelet transform. At last, experimental results show that for obtaining higher compression ratio, proposed SPIHT is more beneficial than the conventional SPIHT.

1. Introduction

   Image compression is one of the most valuable and commercially successful technologies in the field of digital image processing. In ideal case, an image compression technique removes redundant and/or irrelevant information. But practically, it is a lot necessary to throw away both non-redundant information and relevant information to achieve the required compression. Many well-organized compression techniques for still image compression with different features have been developed [1]-[5]. Without degrading the quality of image, image compression is used to minimize the size in bytes of a graphics file. Presently there are two categories of image compression, one is lossy compression and other is lossless[5] compression. In lossless compression the image after compression and decompression is identical to the original. While in lossless compression, the reconstructed image contains degradations with respect to original image but is tolerated as it gives a high compression ratio. Mathematically, a measure of

   compression is given by the compression ratio (Cr) defined as,

   Cr = (Number of bits in original image) (Number of bits in compressed image)

   Wavelet[8][9] transform based image compression using set partitioning in hierarchical trees (SPIHT) is a dominant, well-organized and yet a very simple image compression algorithm. SPIHT coding algorithm alone cannot give higher image compression ratio. For this problem, here in this paper an improved SPIHT image coding algorithm is proposed for obtaining higher compression ratio.

2. Flow diagram of experimental system

   In figure 1, experimental system can be divided into two parts: one is a discrete wavelet transform (DWT), that will perform the decomposition of gray scale image and other is a SPIHT encoder part that will produce compressed bit stream by coding the wavelet coefficients.

   Gray scale image

   DWT

   enhanced SPIHT

   Gray scale image

   DWT

   enhanced SPIHT

   Compressed bit stream

   Compressed bit stream

   Figure 1. SPIHT coding structure

3. Discrete Wavelet Transform (DWT)

   A Wavelet transform provides time-frequency representation. It is capable of providing the time and frequency information simultaneously. Wavelet transforms are based on small wavelets with limited duration, which overcomes the resolution related

   Problems in short time Fourier transform (STFT).Figure 2, shows the comparison of sine waves which are the basis of Fourier transform and wavelets.

   Figure 2. Sinusoidal wave and wavelet

   Discrete wavelet transform is a wavelet function that represent image on different resolution level i.e. it exhibit the property of multi-resolution. Discrete Wavelet analysis is computed using the concept of filter banks. Filters of different cut-off frequencies analyse the signal at different scales. Resolution is changed by the filtering; the scale is changed by upsampling and downsampling. If a signal is put through two filters, one is a high-pass filter (high frequency information is kept, low frequency information is lost and other one is a low pass filter (low frequency information is kept, high frequency information is lost), then the signal is effectively decomposed into two parts, a detailed part (high frequency), and an approximation part (low frequency). The subsignal produced from the low filter will have a highest frequency equal to half that of the original. According to Nyquist sampling this change in frequency range means that only half of the original samples need to be kept in order to perfectly reconstruct the signal. More specifically this means that upsampling can be used to remove every second sample. The scale has now been doubled. The resolution has also been changed, the filtering made the frequency resolution better, but reduced the time resolution. The approximation subsignal can then be put through a filter bank, and this is repeated until the level of decomposition has been reached. Figure 3,shows this process to be carried out on 2-D DWT required DWT.

   Figure 3. 2-D DWT

4. SPIHT

The SPIHT algorithm is simple, fast, self-adaptive, completely embedded and very efficient type of image compression algorithm. SPIHT[4] algorithm introduced by A.Said and W.Pearlman, is an improved version of Embedded zero wavelet (EZW)[3] given by Shapiro. Working of both algorithms is based on tree structure, called spatial orientation tree (SOT)[10] that defines the spatial relationships among wavelet coefficients in different decomposition subbands. During decoding step by using embedded bit stream, best reconstructed image can be extracted at various bit rates.

4.1 SPIHT algorithm

First we define the following sets: C(i,j): wavelet coefficient

O(i,j): set of coordinates of all offspring of node (i,j)

D(i,j): set of coordinates of all descendants (i,j)

H(i,j): set of all tree roots (nodes in the highest level of the pyramid.

L(i,j)=D(i,j)-O(i,j)(all descendents except the offspring

The following Significance test is considered while applying algorithm for encoding process.

1 , max{ Ci,j } 2n

Sn(i,j) =

0 , otherwise

Coding steps are as follows:

1. Initialization

   Output n = log2 (max(i,j) {|Ci,j|}) Set LIP = All elements in H

   Set LSP = Empty

   Set LIS = Ds of Roots,as type A entries.

2. Significance Map Encoding (Sorting Pass)

   1. for each entry (i,j) in the LIP do:

      1. Output Sn(i,j)

      2. If Sn(i,j)=1 then Move (i,j) to the LSP and output the sign of Ci,j

   2. for each entry (i,j) in the LIS

      1. if the entry is of type A then Output Sn(D(i,j)) then

         If Sn(D(i,j))=1 then

         for each (k,l) O(i,j) do: output Sn(k,l)

         If Sn(k,l)=1, then add (k,l) to the LSP and output sign of Ci,j

         If Sn(k,l)=0, then add (k,l) to the

         end of LIP

         if L(i, j) not equal to 0, move (i,j) to end of the LIS, as a type-B entry, and go to step 2.2.2 else remove entry (i, j) from the LIS:

      2. if the entry is of type B, then output Sn(L(i, j));

         if Sn(L(i, j)) = 1, then

         append each (k, 1) O(i,j) to the LIS as a type-A remove (i, j) from the LIS:

3. Refinement pass:

   for each entry (i, j) in the LSP, except those included in the last sorting pass (the one with the same) output the nth most significant bit of |Ci,j|

4. Update

   Decrement by 1and go to Significance Map Encoding Step if needed.

   4.2 Enhanced SPIHT

   When we used conventional SPIHT image compression then this algorithm compresses less number of bits in image. Here, first we will select a gray scale image. Then we will execute the wavelet decomposition on that image using db4 wavelet and 7 level of decomposition are being performed. After that we will perform SPIHT encoding and then it is further packed. Next we will perform unpacking and decoding of the same. Finally, wavelet reconstruction is performed. After performing all the above steps, we calculated the compression ratio which is higher than the conventional SPIHT. We are also comparing the results of Enhanced SPIHT with Conventional SPIHT in terms of compression ratio by changing the rate (bpp)

5. Performance Analysis

   The Above compression algorithm has been implemented in MATLAB 7.9. We are taking Lena image. The db4 wavelet is being used here, adopting seven levels of two dimensional (2-D) wavelet decomposition.

   Shown in Table 1, at different rates, the compression ratio of enhanced SPIHT applied in this paper is higher than the compression ratio of conventional SPIHT. In Figure 4, we are showing (i) is original image, (ii) pre-decoded image, (iii) decoded image.

   Table 1. Comparison of enhanced SPHIT with Conventional SPIHT

   Method Rate Cr	enhanced SPIHT	conventional SPIHT
   0.8	33:1	10:1
   0.9	21:1	9:1
   1.0	17:1	8:1

   (i)

   (ii)

   (iii)

   Figure 4. (i) original image, (ii) pre-decoded image

   (iii) decoded image.

6. Conclusion

   Most of the techniques used for image compression are having some type of redundancy. The experimental results show that the enhanced SPIHT proposed here is beneficial for achieving the higher compression ratio than the conventional SPIHT.

7. References

1. G. K. Wallace, The JPEG Still Picture Compression Standard, Communication of the ACM, Vol. 34, No.4, pp. 30-44,1991.

2. C. Christopoulos, A. Skodras, T. Ebrahimi, The JPEG2000 Still Image Coding System:An Overview, IEEE Trans. on Consumer Electronics, Vol.46, No.4, , pp. 1103- 1127, November 2000

3. J. M. Shapiro, Embedded Image Coding Using Zerotrees of Wavelet Coefficients, IEEE Transactions on Signal Processing, Vol. 41, pp. 3445-3462, December 1993

4. A. Said, W. A. Pearlman, A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 6, No. 3, pp. 243-249, June 1996

5. B. Carpentieri, M. J.Weinberger, G. Seroussi, Lossless Compression of Continuous-Tone Images, Proceedings of IEEE, Vol.88, No.11, pp.1797-1807, November 2000

6. Shapiro JM. Embedded image coding using zerotrees of wavelets coefficients. IEEE Transactions on Signal Processing1993;41:3445-62

7. Wang Xiangyang , Yang Hongying. A new embedded zerotree wavelet image coding algorithm. Journal of China Institute of Communication , 2002,23 (8) : 113-116

8. S. Mallat. A Wavelet Tour of Signal Processing[M].China Machine press, 2003.

9. S. Grgic, K. Kers, M. Grgic, Image Compression Using Wavelets, Proceedings of the IEEE International Symposium on Industrial Electronics, ISIE'99, Bled,

   Slovenia, pp. 99-104, 1999

10. A. Said, W.A. Pearlman. Image compression using the spatial-orientation tree. IEEE Int. Symp. on Circuits and Systems, Chicago, IL, pp. 279-282, 1993.