Enhanced SPIHT Algorithm for Image Compression

Enhanced SPIHT Algorithm for Image Compression

B. Kranthi1, Dr.B.Ananda Krishna2, Dr.M.kamaraju3, B.Rajasekhar4

1Student, M.Tech, DECS, Gudlavalleru Engineering College, Gudlavalleru,

2Prof., ECE Department, Gudlavalleru Engineering College, Gudlavalleru

3H.O.D,Prof.,Gudlavalleru Engineering College, Gudlavalleru.

4Associate Professor, ECE Department, Gudlavalleru Engineering College, Gudlavalleru.

Email:1krasece@gmail.com, anand_bk@rediffmail.com,

3madduraju@yahoo.com,4surajb2000@gmail.com

Abstract-In this paper a new method of image data compression has been proposed to achieve high PSNR (Peak Signal to Noise Ratio). Image compression using Set Partitioning in Hierarchical Trees (SPIHT) transform is wavelet based transform which is computationally very fast, yields good compression ratio and good image quality. To enhance further or to get better performance, this research paper presents an image compression algorithm using Modified Fast Haar Wavelet Transformation (MFHWT) and ESPIHT (Enhanced SPIHT) along with run length encoding to increase the above image compression requirements.The comparison is carried out in terms of coding efficiency, memory requirements, and image quality.

Keywords DWT, MFHWT, ESPIHT, Run Length Encoding.

I. INTRODUCTION

The application of image compression in the field of image processing has become an active area of research. A number of image compression techniques have been developed in the past for various applications. But, majority of the traditional image compression approaches available in the literature have poor visual quality and low PSNR (Peak Signal to Noise Ratio) value. In recent years, wavelet transform is observed to be very efficient in improving the performance of the image compression techniques. The main advantages of wavelet based methods lie in their energy compaction property and multiresolution decomposition capability. SPIHT (Set Partitioning in Hierarchical Trees) computationally very fast and among the best image compression algorithms known today. According to statistical analysis of the output binary stream of SPIHT encoding, propose a simple and effective method combined with run length encode for further compression [6].

Wavelets have recently been applied to several problems in Computer Graphics including image editing and compression, surface reconstruction, global illumination, and animation. Wavelet-based codingoffers considerable enhancements in picture quality at higher compression ratios. Recently, a wide variety of powerful and sophisticated wavelet-based approaches for image compression have been developed and implemented.

This paper uses a wavelet based approach for effective image compression due to the following advantages of the wavelets[6].

• Wavelet coding approaches at higher compression avoid blocking artifacts.

• Wavelet coding is better matched to the Human Visual System (HVS) characteristics.

• Wavelet based compression facilitate parametric gain control for image softening and Sharpening.

• Wavelet-based coding is more robust under transmission and decoding errors, and also allows progressive transmission of images.

• Wavelet compression is very competent at low bit rates.

• Wavelets offer an efficient decomposition of signals earlier to compression.

  SPIHT algorithm is used in this research work for better efficiency. SPIHT algorithm produces a pyramid structure based on a wavelet decomposition of an image. It has been discussed that the wavelet coefficients at the top of the pyramid have a strong spatial relationship with their children. This approach becomes very significant by iteratively searching for significant pixels throughout the pyramid tree.

  In order to improve the performance of the system, Improved SPIHT algorithm is used. This paper introduces an Enhanced SPIHT image compression technique using effective Modified Fast Haar Wavelet Transformation (MFHWT) along with run length encoding [2].

  SPIHT is a wavelet-based image compression coder that offers a variety of good characteristics. These characteristics include:

• Good image quality with a high PSNR.

• Fast coding and decoding.

• A fully progressive bit-stream can be used for lossless compression.

• Ability to code for exact bit rate or PSNR.

• The main advantage of SPIHT is that it is fully progressive, meaning that we do not need the whole file to see the image.

  1. EXISTING SYSTEM

     Images require much storage space,large transmission bandwidth and long transmission time. The only way currently to improve onthese resource requirements is to compress images, such that they can be transmitted quicker and then decompressed at the receiver. The block diagram of the existing system is as shown in the Fig.1.

     LL LH	HL HH	HL	HL
     LH		HH
     LH			HH

     Original DWT (Haar SPIHT image Transform) Algorithm Compressed image Storage or Transmission Compressed image
     	Reconstructed image		IDWT (Haar Transform)		ISPIHT Algorithm

     Fig.3 Pyramidal decomposition

     VI.

     Fig.1 Block diagram of existing system

     1. WAVELET TRANSFORM

        1. The DWT of an Image

           One of the most important characteristics of wavelet transform is multi resolution decomposition. An image decomposed by wavelet transform can be reconstructed with desired resolution. In our experiments, an image is decomposed using the Modified Fast Haar Wavelet Transformation (MFHWT). The Fig.2 shows Successive low pass/high pass filtering and down sampling.

           Fig.2 Wavelet decomposition

           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 sub sampled 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 labeled 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 sub bands. This can be done up to any level, thereby resulting in a pyramidal decomposition as shown in the Fig.3.

           In this figure, 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. [11]

        2. The Inverse DWT of an Image

        Just as a forward transform us 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 is 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 column wise first and then row wise, and proceed to the next level, till we reach the first level[11].

     2. HAAR TRANSFORM

        The Haar transform (HT) is one of the simplest and basic transformations from a space domain and a frequency domain. This method reduces the calculation work.HT decomposes each signal into two components. One component is called average (approximation) and other is known as difference (detail) [2].

     3. C. ORIGINAL SPIHT

        SPIHT algorithm is based on Embedded Zero tree Wavelet (EZW) coding method; it employs spatial orientation trees and uses set partitioning sorting algorithm [4][6]. Coefficients corresponding to the same spatial location in different sub bands in the pyramid structure display self-similarity characteristics. SPIHT defines parent children relationships between these self- similar sub bands to establish spatial orientation trees. The SPIHT Algorithm is shown in the Fig.4.

        SPIHT Algorithm over view

        Step1: In the sorting pass, the List of Insignificant Pixel (LIP) is scanned to determine whether an entry is significant at the current threshold. If an entry is found to be significant, output a bit 1 and another bit for the sign of the coefficient, which is marked by either 1 for positive or 0 for negative. Now the significant entry is moved to the list of significant pixel (LSP). If an entry in LIP is insignificant, a bit 0 is output.

        Step2: Entries in List of Insignificant Set (LIS) are processed. When an entry is the set of all descendants of a coefficient, named type A, magnitude tests for all descendants of thecurrent entry is carried outto decidewhether theyare

        	Initialization
        Next Quantization Sorting level Refinement Last Quantization No level? End

        Fig.4 Flow chart for SPIHT Algorithm

        Significant or not. If the entry is found to be as significant, the direct offsprings of the entry undergoes magnitude tests. If direct offspring is significant, it is moved into LIP; otherwise it is moved into LSP. If the entry is deemed to be insignificant, this spatial orientation tree rooted by the current entry was a zero-tree, so a bit 0 is output and no further processing is needed. Finally, this entry is moved to the end of LIS as type B, which is the set of all descendants except for the immediate offspring of a coefficient.If the entry in LIS is type B, significance test is performed on the descendants of its direct offspring. If significance test is true, the spatial orientation tree with root of type B entry is split into four sub-trees that are rooted by the direct offspring and these direct offsprings are added in the end of LIS as type A entries. The important thing in LIS sorting is that entire sets of insignificant coefficients, zero-trees, are represented with a single zero. The purpose behind defining spatial parent- children relationships is to increase the possibility of finding these zero-trees.

        Step3: Finally, refinement pass is used to output the refinement bits (nthbit) of the coefficients in LSP at current threshold. Before the algorithm proceeds to the next round, the current threshold is halved [4].

     4. IMAGE COMPRESSION REQUIREMENTS

     Image compression requires both compression ratio and PSNRare to be high. But these two are inversely proportional to each other. For this purpose we select the lossy image compression techniques because theyhave high compression ratios.

     Peak Signal to Noise Ratio(PSNR): Peak Signal to Noise Ratio is defined as the ratio between signal variance and reconstruction error variance. Peak Signal to Noise Ratio and Compression Ratios are calculated from the following expressions.

     PSNR = 10log10 (2552/MSE)

     Mean Square Error (MSE): Among the quantitative measures, a class of criteria used often is calledthe mean square criteria. It refers to some sort of average or sum (or integral) of squares of theerror between two images.

     Compression Ratio (CR): Compression ratio is defined as the ratio between the original image size and compressed image size.

     In [12] the authors choosing different images and perform original SPIHT algorithm. The Table 1 shows the experiment results for existing system.

     Image	PSNR	Compression Ratio
     Baboon	27.364	15.236
     Girl	28.818	18.263
     Lena	27.532	16.994
     Baby face	23.891	22.658

     Table 1 Experiment Results for Existing System

  2. PROPOSED SYSTEM

     In the proposed system shown in the Fig.5 we are going to modify the Haar transform and SPIHT algorithm to reduce the memory requirements and to maintain good image quality.

     Original DWT image (MFHWT)
     	ESPIHT Algorithm
     Compressed image
     	Storage or Transmission
     Compressed image
     Reconstructed IDWT image (MFHWT)	IESPIHT Algorithm

     Fig.5 Block diagram for proposed system

     A. MODIFIED FAST HAAR WAVELET TRANSFORM (MFHWT)

     MFHWT can be done by just taking (w + x + y + z) /4 instead of (x + y)/2 for approximation and (w + x – y – z) /4 instead of (x – y)/2 for differencing process. Four nodes are considered at a time. The calculation for (w + x – y – z)/4 will yield the detail coefficients in the level of n-2. To get detail coefficients, differencing process (x – y)/2 still need to be done. The decomposition can be done by using matrix formulation. Also, it is used to reduce the memory requirements and the amount of inefficient movement of Haar coefficients. The drawback in the number of addition and subtraction operation can be balanced by decreasing the number of division operations, especially when used at low bit rates[2].

     1. ENHANCED SPIHT (ESPIHT)

        In modified SPIHT to support both spatial and SNR scalability by adding a new list to the SPIHT lists and modifying the SPIHT sorting pass. The ESPIHT algorithm proposed in this paper solves the spatial scalability problem through the introduction of multiple resolution-dependent lists and a resolution-dependent sorting pass. For each spatial resolution level we define a set of LIP, LSP and LIS lists, therefore we have LIPk, LSPk and LISk, for k=kmax, kmax-1 1 where kmax is the maximum number of spatial resolution levels supported by the encoder. In each bit plane, the ESPIHT coder starts encoding from the maximum

        resolution level (kmax) and proceeds to the lowest level (level 1). For the resolution-dependent sorting pass of the lists that belong to level k, the algorithm first does the sorting pass for the coefficients in the LIPk in the same way as SPIHT and then processes the LISklist. During processing the LISk, sets that lie outside the resolution level k are moved to the LISk-1. After then the sorting and refinement passes for level k it will do the same procedure for the lists related to level k-1. According to the magnitude of the coefficients in the wavelet pyramid, coding of higher resolution bands usually starts from lower bit planes. The total number of bits belonging to a particular bitplane is the same for SPIHT and ESPIHT, but ESPIHT aranges them according to their spatial resolution dependency [3].

     2. PROPOSED ALGORITHM

        Start

        Apply MFHWT, along row and column wise on entire matrix

        End

        In the proposed work, MFHWT is combined with Enhanced SPIHT to obtain the better compression without losing much information. The ESPIHT method is not a simple extension of traditional methods for image compression. The method deserves special attention because it provides the best image quality. ESPIHT is used with MFHWT for the decomposition of an image. To perform the operation of compression using Enhanced SPIHT (ESPIHT), following algorithm is used:

        Read the image as a matrix

        Make all the coefficients of this MFHWT positive

        Apply ESPIHT on the MFHWT obtained and ignoring the sign bit and compressed bit stream is obtained

        RLE (Run Length Encoding) has to be applied to the resulting

        For reconstruction process, applying the inverse

        Calculate MSE and PSNR for reconstructed image

        Fig.6 ESPIHT Algorithm over view

     3. ESPIHT WITH RUN LENGTH ENCODING

     RLE consists of the process of searching for repeated runs of symbols in an input stream, and replacing them by a run count. RLE (Run Length Encoding) has to be applied to the resulting bit stream after ESPIHT is applied to the MFHWT. It will help to reduce the size of the bit stream already generated. At the receiving end, the original bit stream can be easily recovered by applying inverse RLE [5].

  3. EXPECTED RESULTS

     Two metrics are mainly used to determine the performance of the image compression. They are PSNR and Compression Ratio [7] [12] which are inversely related with one another. We expected that the PSNR of the proposed system is much better than the existing system. Also we

     expect that this modified algorithm will increase the compression ratio to around 10-15 %.

  4. CONCLUSION AND FUTURE WORK

In this paper we proposed a new algorithm for image compression. We expect that the ESPIHT algorithm increases PSNR with little increase in compressing time and decoding time. By Using RLE with ESPIHT algorithm cause increasing Compression Ratio with preserving image quality as it, and decreasing in the compress time. A computer program will be coded in MATLAB to implement this algorithm for image compression.

REFERENCES

1. Dr. B. Eswara Reddy and K Venkata Narayana, A Lossless Image Compression Using Traditional And Lifting Based Wavelets Signal & Image Processing : An International Journal (SIPIJ) Vol.3, No.2, April 2012.

2. Navjot Kaur, Preeti Singh, A New Method of Image Compression Using ImprovedSPIHT and MFHWT, International Journal of Latest Research in Science and Technology ISSN (Online):2278-5299 Vol.1, Issue2:PageNo124-126,July-August(2012). Habibollah Danyaliand Alfred Mertins, Fully Spatial and SNR Scalable, SPIHT-Based Image Coding for Transmission Over Heterogenous Networks,UniversityofWollongong, Wollongong,NSW2522,Australia.

3. Hualiang Zhu, ChundiXiu and Dongkai Yang, An improved SPIHT algorithm based on wavelet coefficient blocks for image coding, International Conference on Computer Application and System Modeling, 2010

4. Ms.MansiKambli and Ms.Shalini Bhatia, Comparison of different Fingerprint Compression Techniques, Signal & Image Processing An International Journal(SIPIJ) Vol.1, No.1, September 2010.

5. VasanthiKumari and P.Thanushkodi,An Improved SPIHT Image Compression Technique using Daubechies Transform, European Journal of Scientific Research ISSN 1450-216X Vol.81 No.3 (2012), pp.425-435© EuroJournals Publishing, Inc. 2012. http://www.europeanjournalofscientificresearch.com

6. K.Puja, D.Saraf Deepti Sisodia, Amit Sinhal and Neetesh Gupta, Comparisons of wavelets based image compression methods, World Journal of Science and Technology 2012, 2(3):10-13 ISSN: 2231 2587 Available Online: www.worldjournalofscience.com

7. G.M.Padmaja, P.Nirupama, Analysis of Various Image Compression Techniques, ARPN Journal of Science and Technology, VOL.2, NO. 4, May 2012.

8. S.Narasimhulu, Dr.T.Ramashri, Gray-Scale Image Compression Using DWT-SPIHT Algorithm, International Journal of Engineering Research and Applications (IJERA) ISSN: 2248-9622 www.ijera.com Vol. 2, Issue 4, July-August 2012.

9. M. Sifuzzaman, M.R. Islam and M.Z. Ali ,Application of Wavelet Transform and its Advantages Compared to Fourier Transform, Journal of Physical Sciences, Vol. 13,2009,121-134ISSN:0972-8791.

10. PreetiPathak, Image Compression Algorithms for Fingerprint System, IJCSI Int. Journal of Computer Science Issues, Vol. 7, Issue 3, No 9, May 2010

11. KhairiyahSaeed Abdul jabbar & Dr. Ban NadeemDhannoon,Using Modified Set Partitioning In Hierarchical Tree Algorithm with Discreet Cosine Transform to Compress Color Image,Eng.&Tech.Journal,Vol.28,No.17,2010.

12. AllamMousa, NuhaOdeh, Optimizing the Wavelet Parameters To Improve Image Compression, International Journal of Advances in Engineering & Technology, Sept 2012.

13. Md. Rafiqul Islam, FarhadBulbulandShewliShamimShanta, Performance analysis of Coiflet-type wavelets for a fingerprint image compression by using wavelet and wavelet packet transform, International Journal of Computer Science & Engineering Survey (IJCSES) Vol.3, No.2, April 2012.