 Open Access
 Total Downloads : 399
 Authors : Pallavi Chaudhary, Dr.Vinod Shokeen, Bhupendra Singh
 Paper ID : IJERTV2IS50743
 Volume & Issue : Volume 02, Issue 05 (May 2013)
 Published (First Online): 22052013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Design And Implementation Of Image Compression Routine Using Enhanced SPIHT
Pallavi Chaudhary1, Dr.Vinod Shokeen2, Bhupendra Singp
PG Scholar (EC)1, Assistant ProfessorIII (EC)2, Assistant ProfessorI (EC)3 Amity University Noida, Sec125, 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.

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 nonredundant information and relevant information to achieve the required compression. Many wellorganized 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, wellorganized 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.

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

Discrete Wavelet Transform (DWT)
A Wavelet transform provides timefrequency 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 multiresolution. Discrete Wavelet analysis is computed using the concept of filter banks. Filters of different cutoff 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 highpass 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 2D DWT required DWT.
Figure 3. 2D DWT

SPIHT
The SPIHT algorithm is simple, fast, selfadaptive, 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:

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.

Significance Map Encoding (Sorting Pass)

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

Output Sn(i,j)

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


for each entry (i,j) in the LIS

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 typeB entry, and go to step 2.2.2 else remove entry (i, j) from the LIS:

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 typeA remove (i, j) from the LIS:



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

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)

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 (2D) 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) predecoded 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) predecoded image
(iii) decoded image.

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.

References

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

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

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

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. 243249, June 1996

B. Carpentieri, M. J.Weinberger, G. Seroussi, Lossless Compression of ContinuousTone Images, Proceedings of IEEE, Vol.88, No.11, pp.17971807, November 2000

Shapiro JM. Embedded image coding using zerotrees of wavelets coefficients. IEEE Transactions on Signal Processing1993;41:344562

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

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

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

A. Said, W.A. Pearlman. Image compression using the spatialorientation tree. IEEE Int. Symp. on Circuits and Systems, Chicago, IL, pp. 279282, 1993.