 Open Access
 Total Downloads : 4
 Authors : Namita Bothra, Gopal Gupta
 Paper ID : IJERTCONV2IS10070
 Volume & Issue : NCETECE – 2014 (Volume 2 – Issue 10)
 Published (First Online): 30072018
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Image Compression Using DWTSPIHT 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

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 (widesense) zerotrees 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.

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

Sorting Pass:

for each(i, j) LIP do:

output Sn(ij)

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


for each (i, j) LIS do:

if (i, j) is type A then

output Sn((i,j))

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

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




if (i, j) is type B then

output Sn( (I,j) )

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


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

output the nth MSB of i,j


Quantization Pass:

decrement n by 1

goto step 2)


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

Initialization:

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

set LSP =;

set LIP = (i,j) H;

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 3level 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.



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 variablelength encoding naturally Reached the further compressed
Using the output bit stream of above example to introduce the new encoding method process

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

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

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 abovementioned


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

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.

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

Ahmed,N.; Natarajan,T.; Rao,K.R. Discrete Cosine Transform, IEEE Trans. on Computers, vol. C32, pp. 9093, Jan. 1974.

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

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

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

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

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

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. 243250,1996.

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.