Image Compression Using DWT-SPIHT Algorithm on Gray Scale images

Image Compression Using DWT-SPIHT Algorithm on Gray Scale images

Namita Bothra,

Student, Dept of ECE, IES IPS Academy Indore, India Bnamita23bothra@gmail.com

Gopal Gupta

Department of Electronics and Communication Institute of Engineering & Science, IPS Academy Indore, India

Gopalgupta45@gmail.com

Abstract: In present digitalize world maximum of data is also electronic form of soft copy of data which had given us ample of benefits but also gave a problem of storage capacity giving rise to work on Compression of data to reduce size with minimal loss. The term Image compression is a compression coding technology used in digital image applied to reduce redundant information in image data and making unit storage and ring data transfer more efficient. SPIHT (Set Partitioning In Hierarchical Tree) is among the best image compression algorithms and computationally very fast. As per statistic analysis of the output binary stream of SPIHT encoding, propose a simple and effective method combined with Huffman encode for further compression. In this paper the results from the SPHIT algorithm are compared with the existing methods for compression like discrete cosine transform (DCT) and discrete wavelet transform (DWT).

Keywords- Encoding; Decoding; DCT; DWT; SPIHT; Huffman coding

1. INTRODUCTION

   The discrete cosine transforms (DCT) [1] is a technique for converting a signal into elementary frequency components. It is widely used in image compression. Here we develop some simple functions to compute the DCT and to compress images [2]. These functions illustrate the power of Mathematical in the prototyping of image processing algorithms. In recent years, wavelet transform [3][4] as a branch of mathematics developed rapidly, which has a good localization property[5] in the time domain and frequency domain, can analyze the details of any scale and frequency. So, it is superior to Fourier and DCT. It has been widely applied and developed in image processing and compression. Wavelet Transform (WT) has received more and more significant attention in signal compression. However, many differences lie in the performance of different wavelets. There is a need to select the optimal matched wavelet bases to analyze the signal and the signal needs to be expressed with the fewest coefficients, i.e. sparse coefficients. The signal compression with wavelet is a procedure in which the input signal is expressed with a sum of a few of power terms for wavelet function. The more similar the bases function is to input signal, the higher the compression ratio is. But, at higher compression ratios we may

   experience more errors, i.e. mean square error will be high at the receiving end and hence PSNR will be very low.

   More improvements over DWT are achieved by SPIHT [6][7], by Amir Said and William Pearlman, in 1996 article, "Set Partitioning in Hierarchical Trees"[5]. In this method, more (wide-sense) zero-trees are efficiently found and represented by separating the tree root from the tree, so, making compression more efficient. Experiments are shown that the images through the wavelet transform, the wavelet coefficients value in high frequency region are generally Small , so it will appear seriate "0" situation in quantify [8]. SPIHT does not adopt a special method to treat with it, but direct output. In this paper, focus on this point, propose a simple and effective method combined with Huffman encode for further compression. A large number of experimental results are shown that this method saves a lot of bits in transmission, further enhanced the compression performance.

2. SPIHT ALGORITHM

   A. Description of the Algorithm

   Image data through the wavelet decomposition, the coefficient of the distribution turn into a tree. According to this feature, defining a data structure: spatial orientation tree. 4- level wavelet decomposition of the spatial orientation trees structure are shown in Figure1.We can see that each coefficient has four children except the red marked coefficients in the LL subband and the coefficients in the highest subbands (HL1;LH1; HH1).

   The following sets of coordinates of coefficients are used to represent set partitioning method in SPIHT algorithm. The location of coefficient is notated by (i,j),where i and j indicate row and column indices, respectively.

   H: Roots of the all spatial orientation trees

   O(i, j) :Set of offspring of the coefficient (i, j), O(i, j) = {(2i, 2j), (2i, 2j + 1),(2i + 1, 2j), (2i + 1, 2j + 1)}, except (i, j) is in LL;

   When (i,j) is in LL subband, O(i; j) is defined as: O(i, j) = {(i, j

   + ), (i + , j), (i + , j + )}, where and

   is the width and height of the LL subband, respectively.

   D (i, j): Set of all descendants of the coefficient (i, j), L (i, j): D (i, j) – O (i, j)

   A significance function Sn() which decides the Significance of the set of coordinates, , with respect to the threshold 2n is defined by:

   Sn () = 1, if max (i,j) {|ci,j|}

   0, else

   Where ci,j is the wavelet coefficient.

   In this algorithm, three ordered lists are used to store the significance information during set partitioning. List of

   1. Sorting Pass:

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

         1. output Sn(ij)

         2. if Sn(ij)= 1 then move (i, j) to LSP and output Sign (ci,j)

      2. for each (i, j) LIS do:

      1. if (i, j) is type A then

         1. output Sn((i,j))

         2. if then Sn((i,j)) = 1 then

            1. for each (k, l) O(i, j)

               insignificant sets (LIS), list of insignificant

               Figure 1 parent child relationship in SPIHT

               • output Sn(k,l)

               • if Sn(k,l) = 1 then append (k, l) to LSP,

                 output Sign(k,l),and k,l = k,l 2n sign(k,l)

                 else

                 append (k; l) to LIP B. move (i, j) to the end of LIS as type B

      2. if (i, j) is type B then

      1. output Sn( (I,j) )

      2. if Sn( (I,j) ) = 1 then

      • append each (k, l) O(i, j) to the end of LIS as type A

      • .remove (i,j) from LSP

   2. Refinement Pass:

      1. for each (i,j) in LSP, except those included in the last sorting pass

      • output the n-th MSB of |i,j|

   3. Quantization Pass:

      1. decrement n by 1

      2. goto step 2)

   1. Analyses of SPIHT Algorithm

      pixels (LIP), and list of significant pixels (LSP) are those three lists. Note that the term pixel is actually indicating wavelet coefficient if the set partitioning algorithm is applied to a wavelet transformed image.

      Algorithm: SPIHT

      1. Initialization:

         1. output n= [log2 max{|(i,j)|}]

         2. set LSP =;

         3. set LIP = (i,j) H;

         4. set LIS = (i,j) H, where D(i; j) and set each entry in LIS as type A ;

         Here a concrete example to analyze the output binary stream of SPIHT encoding. The following is 3-level wavelet decomposition coefficients of SPIHT encoding:

         = [log2 max {|c(i,j)|}] = 5, so, The initial threshold value:T0 = 25, for T0,

         the output binary stream: 11100011100010000001010110000, 29 bits in all.

         By the SPIHT encoding results, we can see that the output bit

         stream with a large number of seriate "0" situation, and along with the gradual deepening of quantification, the situation will become much more severity, so there will have a great of redundancy when e direct output.

   2. Modified SPIHT Algorithm

   For the output bit stream of SPIHT encoding with a large number of seriate "0" situation, we obtain a conclusion by a lot of statistical analysis: 000 appears with the greatest probability value, usually will be about 1/4.Therefore, divide the binary output stream of SPIHT every 3 bits as a group, every group recorded as a symbol, a total of eight kinds of symbols, statistical probability that they appear, and then encoded using variable-length encoding naturally Reached the further compressed

   Using the output bit stream of above example to introduce the new encoding method process

   1. First, divide the binary output stream every 3 bits as a group: 111 000 111 000 100 000 010 101 100 00. In this Process, there will be remain 0, 1, 2 bits can not participate. So, in order to unity, in the head of the output bit stream of Huffman encoding cost two bits to record the number of bits that do not participate in group and those remainder bits direct output in end. Figure 2 is shown the output bit stream structure of Huffman encoding

      Number of remain bits

      Bit stream

      Remain bits

      Figure 2 The bit stream structure of Huffman encoding

   2. The emergence of statistical probability of each symbol grouping results are as follows:

      P(000)= 0.3333 P(001)= 0

      P(010)= 0.1111 P(011)= 0

      P(100)= 0.2222 P(101)= 0.1111

      P(110)= 0 P(111)= 0.2222

   3. According to the probability of the above results, using Huffman encoding, then obtain code word book, as follow table1

   Table 1: Code word comparison table

   Through the above code book we can get the corresponding output stream: 10 00 01 00 01 11 01 1001 101 11 00, a total of

   25 bits, the 10 in the head is binary of remainder bits number. The last two bits 00 are the result of directly outputting remainder bits. Compared with the original bit stream save four bits.

   Decoding is inverse process of the above-mentioned

3. RESULTS

   The experimental results show the standard Lena image 128×128 grayscale image compression with different

   comparison parameters. Average code length which is calculated as follows:

   Where p is the probability of symbols appeared, Li is the length of word code. The Performance of this algorithm is verified with respect to the existing algorithms like Discrete Cosine Transform and Discrete Wavelet Transform. For this performance analysis we have considered three parameters (Mean Square Error, Peak Signal to Noise Ratio, Compression Ratio). Mean square error, PSNR and compression ratio are calculated as follows.

   CR = (Number of bits in the original image) /(Number of bits in the compressed image)

   By using the above formulae in the proposedalgorithm the following parameters are calculated for the Lena image and given in the following table.

   Table 2 Result analysis for Lena image of size 128×128

   Algorithm	Parameters
   	Compression Ratio	MSE	PSNR	Compressed image size
   DCT	2.4059	3.4401	36.1236	6810
   DWT	1.4080	0.7479	48.1308	11636
   SPIHT	1.3507	0.0874	58.7156	12130

4. CONCLUSION

   The proposed lossy image compression algorithm is simple and effective method for gray scale image compression and is combined with Huffman encoding for further compression in this paper that saves a lot of bits in the range of practical value for today that have number of image data value for today that have a number of image data is to be transmitted.

5. FUTURE SCOPE OF THE WORK

In future this work may extend for the color image and video compression. With existing better algorithms and techniques for image compression

REFERENCES

1. Ahmed,N.; Natarajan,T.; Rao,K.R. Discrete Cosine Transform, IEEE Trans. on Computers, vol. C-32, pp. 90-93, Jan. 1974.

2. Liu,C.P.; Poularikas,A.D. A New Subband Coding Technique Using (JPEG) DCT for Image Compression, IEEE Trans. on Image processing, pp.317-321,1996.

3. Antonini,M.; Barlaud,M.; Mathieu, P.; Daubechies,I. Image Coding Using Wavelet Transform, IEEE Trans. on Image Processing, Vol. 1, No. 2, pp.205-220.1992.

4. Ronald A.DeVore; Bjorn Jawerth; Bradley J. Lucier " Image Compression Through Wavelet Transform Coding, " IEEE Trans. on Information Theory, Vol.38.NO.2,pp.719-746, MARCH 1992.

5. Lewis,A.S.; Knowles,G. " Image Compression Using the 2-D Wavelet Transform, " IEEE Trans. on Image Processing, Vol. I . NO. 2, PP. 244 – 250, APRIL 1992.

6. Shapiro,J.M. Embedded image coding using zerotree of wavelets coefficients, IEEE Trans. on Signal Processing,pp.3445-3462, 1993.

7. Said,A.; Pearlman,W.A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees, IEEE Trans. on Circuits and Systems for Video Technology, vol. 6, pp. 243-250,1996.

8. Wei Li, Zhen Peng Pang and Zhi Jie Liu, SPIHT algorithm combined with Huffman encoding, 3rdInternational Symposium on Intelligent Information Technology and Security Informatics, IEEE Trans. Page No 341- 343,2010.