Communications and Network, 2013, 5, 245248 http://dx.doi.org/10.4236/cn.2013.53B2045 Published Online September 2013 (http://www.scirp.org/journal/cn) An Improved SPIHT Algorithm for Image Compression in Low Bit Rate Ping Liu, Guanfeng Li School of Physical and Electrical Information Engineering, Ningxia University, Yinchuan, China Email: nx_liuping@163.com Received May, 2013 ABSTRACT Aiming at shortage of the SPIHT algorithm, an improved image compression algorithm is proposed, in order to over come the shortcomings of decoding image quality and coding time, LS9/7 lifting wavelet transform is adopted. Ac cording to the characteristics of the human visual system (HVS), the scanning mode and the method to determine the threshold of algorithm are changed to improve th e quality of reconstruction image. On the question of repeating scan of SPIHT algorithm, using maximum list thought, greatly reduce the computation and save operating time. The experi mental results have proved that the improved algorithm of image decoding time and the quality of reconstruction im ages are better than the original algorithm , especially in the case of low bit rate. Keywords: Wavelet Transformation; Lifting Scheme; Thresho ld; Set Partitioning in Hierarchical Trees(SPIHT); Human Vis ual S y s te m(HVS); I mage Compression; Low Bit Rate 1. Introduction Wavelet transform has a good locality character of time frequency domain, overcome the limitations of Fourier transform in dealing with the smooth complex image signal effectively, the subimage after transformation has strong comparability. It is convenient for coding the subsequent, made the wavelet transform widely used in image compression field. J. M. Shapiro proposed EZW (Embedded Zerotree Wavelet) [1] algorithm in 1993, the complexity of this algorithm is not high, and the stream ing is embedded. It is easy to control compression ratio and realize scalable coding. A. Said and W. A. Pearlman proposed a new efficient improvement method in 1996, namely SPIHT (Set Partitioning In Hierarchical Tree) [2,3], using the spatial direction tree, this method shows wavelet coefficients of zero tree structure efficient and accurate, which increased the compression efficiency and reduced the complexity of the coding. SPIHT algorithm treat the lowest frequency subband coefficient the same importance, so when sorting and scanning process using LIP determine the importance of the wavelet coefficients, only a small part of the bits are used for coding important information, especially in low bit rate, it will inevitably lead to the quality o f the recov ery image descend. Need a lot of storage space, and ex ists the disadvantage of repeating problem, this paper focused on the problems of SPIHT algorithm and pro posed an improved scheme, combined with the human visual characteristics. To reduce the algorithm of middle storage and the time consumption, meanwhile improved the quality of the decoded image in low bit rate. 2. Related Algorithm Principle 2.1. Lifting Wavelet Transform Sweldens using lifting format (Lifting Scheme, LS) con struct wavelet transform in 1994.The basic idea is by a inertia Wavelet (Lazy Wavelet, LW),and gradually con struct a new wavelet [46]. Lifting format gives a simple and effective method to construct the biorthogonal wavelet. It use the basic polynomial interpolation to get the signal of the high frequency components, by con structing scale function to get the signal of the low fre quency components. Th is scheme consists of three steps: split, predict and update. Supposed the original signal is x[n], the exchange process of the signal is as shown in Figure 1. s[n] is the low frequency components of x[n], and d[n] is the high frequency components of x[n]. 1) Split: split signal x[n] into two related parts, a[n] and b[n]. Sampling interval according to the parity serial number of data, namely: a[n]=x[2n], b[n]=x[2n+1]. 2) Predict: using the correlation among the data: using a[n] predict b[n].adopt prediction operatormakes: d[n] = b[n]P(a[n]). )(P 3) Update: using update operator , using d[n] re vise x[n], the revised signal x[n] (recorded as c[n]) con tains the low frequency part of signal x[n] only, namely: c[n]=a[n]+U(d[n]). U() C opyright © 2013 SciRes. CN
P. LIU, G. F. LI 246 Because 97 integral wavelet lifting scheme has good energy concentration, vanishing moment is bigger. So adopt the 97 integral wavelet lifting scheme in this arti cle. As shown in Figure 2. Biorthogonal lifting wavelet coefficient can obtain by solving FIR wavelet filters in time domain. Here, gives LS9/7 wavelet coefficient di rectly: 1.586134342 0.05298011854 0.88291107602 0,4435068522 K 1.149604398 (1) Take the approximate value: (3/2 1/164/5,15/32, 42/5 ) K ，，，， ，， (2) 2.2. SPIHT Algorithm 1) Partition rules of algorithm The main idea of SPIHT algorithm [2,3 ] is by reduced progressively threshold sequence generating a series of important diagram (or bitmap) to approximate every wavelet coefficients gradually. For any node bring in four sets as follow: (, )ij (, )Oi j (, )Di j : The coordinate sets of the four direct subse quent node o f ; (, )ij : The coordinate sets of all the subsequent node of ; (, )ij (, )Li j: The coordinate sets of all the subsequent node except direct subsequent node of namely: (, )ij (, )(, )(, )Li jDi jOi j H: The top of coordinate sets in decomposition of the wavelet py ramid. For all child nodes except root node of : (, )ij ( ,){(2,2),(2 ,21),(21,2), (21,21)} Oi jijijij ij SplitPredict Update x[ ]n [] n []dn 1[]dn [] e Xn [] o Xn Figure 1. Decomposition of lifting algorithm. 1 Z k k/1 j S j d ][nXe 1j S ][nXo 2 2 Figure 2. 97 integral lifting wavelet scheme. a) The initial segmented set consists of and , (, )ij (, )Di j(,)Di jH . b) If is important, split it into and four single element sets. . (, )Di j(, )Li j (,) (,)kl ij c) If is important, split it into four sets , (, )Li j (, )Di j(,)kl (,)Oij . The basic operations of SPIHT algorithm are set test, it description as follows: (, ) 1,max{(,)}2 (, )0others n ij T n Ci j ij S ， (3) 2) Algorithm description: SPIHT algorithm consists of three linked list to record coding information: LIS: List of Insignificant Sets; LIP: List of Insignificant Pixels; LSP: List of Significant Pixels; a) Initialization Suppose (, ), 2 2, () log max nij ij Tn c , are , Cij wavelet coefficients, the initial LSP is empty. {( ,)( ,)LIPi jijH {(,)(,) }LISDij ijH are coordinate sets of all roots. b) Classification scanning This process scanning LIP and LIS only. For each co ordinates of LIP, if , Cn ij T , record , as the un important coefficient, and sign "0". On the contrary sign "1" as important symbol and output the symbol of ,, and moved this table from LIP to LSP tail. For unimpor tant subset LIS, each table corresponding to a wavelet coefficients set Cij Cij , Cij , if , Cn ij T , record ,ij as important subset, and output important symbol "1", up date LIP and LSP. Otherwise, output "0". C c) Fine scanning This process scanning LSP only, for each of LSP, if is not a new add in the scanning process has just, according to the current quantitative threshold n, judging the size of the most significant bit of the wavelet coefficients, and output the nth important bit of (, )ij (, )ij T , Cij in binary. d) Update the threshold Order n = n + 1 and quantized threshold as n+1n for the next scanning. For LIP, LSP and LIS use the same rules to update. = TT 2.3. Improved SPIHT Algorithm According to the human visual characteristics, the sensi tivity of the human for the high frequency information is far less than the low frequency, therefore do the follow ing treatment: weighted each subband coefficient as in [79] which shown in Table 1 , multiplied by each coeffi Copyright © 2013 SciRes. CN
P. LIU, G. F. LI 247 cient when coding and divided by it while decoding. 1) Adopt different threshold for the different low fre quency and high frequency subband, LL layer are dif ferent from the other three layers, so the lowest fre quency subband and other three bit allocation adaptive when coding, make the output streaming distribution more bits to the lowfrequency coefficients. So, it will gain higher signaltonoise ratio (SNR) in the same bit rate situation. In the case of the same SNR, due to improve detailing the threshold, the system exist more zerotree. It can reduce the coding time computation effectively. 2) Improvement of the low frequency subband After processing as step 1), to the lowest layer coeffi cient LLN of the nth decomposition, output priority as fine scanning streaming, it will receive this information the first while decoding, according to this message restore the scanning process and decoding. Using this op timi zation measures to ensure that transmit important visual coefficient priority, also is the standard of the fre quency for priority, the low frequency information should be transmit prior than high frequency, and when two princi ples (frequency priority and absolute value priority) con flict, consider frequency priority at first. Improved the quality of reconstruction image in low bit rate. 3) Improvement of the high frequency subband For the other three high frequency sub band as in [10 12], using maximum list thought as follows: establish maximum linked list MAX in the initial process, store the maximum coefficient of corresponding elements node of LIS, if maximum number exceeds the threshold, then scanning corresponding coefficient position of LIS, otherwise, don’t consider the current threshold. In the later process, will compare the threshold and maximum value only, do not need to compare on e b y one, and thereby reducing the large amount of calculation. Improved algo rithm initialization as the formulation given in (4) _, _, _, _ _ _ ___ ij LL 2 ij HL 2 ij LH 2 ij HH 2 nmax1=ij log max C nmax2=ij log max C nmax3= ij log max C nmax4= ij log max C n=nmax1 n max=max(n max2,n max3,n max4) （，） （，） （，） （，） , (4) Table 1. Weighted coefficient of each subband. Subband LL5 LH5 HL5 HH5 LH4 HL4 HH4LH3 HVW 1 0.798 0.798 0.684 0.962 0.962 0.8490.981 Subband HL3 HH3 LH2 HL2 HH2 LH1 HL1HH1 HVW 0.981 0.938 0.843 0.843 0.516 0.362 0.3620.082 3. Results and Analysis 3.1. The Influence of Test Performance in Different Decomposition Layers and Coding Level (256 * 256 * 8 bit Lena Images) Table 2 shows the experimental data of improved algo rithm of different decomposition layers and coding level. By experiment we find that the best result are three lay ers of wavelet decomposition and eight level coding. 3.2. The Comparison of the Basic Algorithm and the Improved Algorithm in This Paper Table 3 shows the comparison of the basic algorithm and the improved algorithm. In this experiment, Take 512 * 512 * 8 bit Lena as the test image when in the case of three layers of wavelet decomposition and eight level coding. By experimental, we found that the SNR are improved of the improved algorithm, It is more apparent especially in low bit rate, at the time the coding time faster 0.1s to 0.3s or so than the basic algorithm. Figures 3(a), (b), and (c) are reconstruction images for the original image, the basic algorithm and improved algorithm in the bit rate of 0.0625 respectively, (d) is the image of three layers of wavelet decomposition and eight level coding, through observation subjective, we found that the improved algorithm of image decoding time and the quality of reconstruction images are better than the original algorithm, especially in the case of low bit rate. Table 2. The experimental data of improved algorithm of different decomposition layers and coding level. decomposition layer coding level PSNR（db） 6 37.1115 7 42.8990 3 8 50.4635 6 36.1419 7 41.9839 4 8 49.3562 6 35.364 7 41.3681 5 8 48.7538 Table 3. The comparison of the basic algorithm and the improved algorithm. Improved algorithm Basic algorithm Bit rate (bpp) PSNR (db) coding time(s) decoding time(s) PSNR (db) coding time(s) decoding time (s) 0.015625 25.4350.1400.016 17.320 0.1400.063 0.0312526.8760.1870.031 21.668 0.3210.092 0.0625 30.7040.3280.062 28.390 0.6500.120 0.125 32.9970.5470.125 31.100 0.9100.180 0.25 35.5800.9060.269 34.110 1.2600.270 0.5 37.4601.5630.465 37.210 1.6700.480 Copyright © 2013 SciRes. CN
P. LIU, G. F. LI Copyright © 2013 SciRes. CN 248 [2] ANTONINI Metal, “Image Coding Using Wavelet Trans form,” IEEE Transactions on Image Processing, Vol. 1, 1992, pp. 2052203. doi:10.1109/83.136597 (a) Original image (b) Basic algorithm (c)Improved algorithm (d) The image of three layers of wavelet decomposition and eight level coding [3] A. Said and W. Pearlman, “A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Tress,” IEEE Transactions on Circuit and System for Video Technology, Vol. 6, 1996, pp. 243250. [4] Sweldens. W, “The lifting scheme: a customdesign con struction of biorthogonal wavelets,” Applied and Com putional Harmonic Analysis, Vol. 6, No. 2, 1996, pp. 186200. doi:10.1006/acha.1996.0015 [5] W. B. Fan, J. Chen and J. N. Zhen, “SPIHT Algorithm Based on Fast Lifting Wavelet Transform in Image Com pression,” LNAI, Vol. 2, 2005, pp. 838844. [6] Y. F. Yang and Z. X. Su, “An Improved Based on Wave let Zerotree Image Coding Algorithm,” China journal of Image and Graphics, Vol. 6, 2001, pp. 542546. [7] L. Y. Li, C. L. Zhan and L. Huang, “The Algorithm of SPIHT Coding Based on LS9/7 Lifting Wavelet,” Com munication Technology, Vol. 40, 2007, pp. 362363. [8] P. Yu, X. H. Ma and J. G. Li, “The Algorithm of Image Compression Based on LS9/7 Lifting Wavelet,” Microe lectronics and Computer, Vol. 40, 2008, pp. 110111. Figure 3. The comparison of simulation results. 4. Conclusions [9] Z. G. Pan and X. Gao, “Improved SPIHT of Image Com pression Algorithm for Texture,” The Chinese Academy of Sciences of Graduate School, Vol. 27, 2010, pp. 222227. According to the shortage of the SPIHT algorithm, it proposes an improved image compression algorithm, using LS9/7 lifting wavelet transform, improved the operation speed and reduce the complexity of the calculation. According to the characteristics of the HVS, the scanning mode and the method to determine the threshold of algorithm are changed, which greatly reduced the computation time. The experimental results have proved that the improved algorithm of image decoding time and the quality of reconstruction images are better than the original algorithm, especially in the case of low bit rate. [10] Q. Gong and H. Ruan, “The Improved SPIHT Algorithm of Image Compression Based on Integer Lifting Wavelet Transform,” Computer Simulation, Vol. 26, 2009, pp. 195197. [11] K. Wang, J. W. Zhang, L. L. Wu and Q. Ge, “An Im proved SPIHT Algorithm of Image Compression Based on Human Visual System,” Computer Application and Software, Vol. 27, No. 2, 2010, pp. 277279. [12] B. Yan and H. Zhang, “SPIHT Algorithm and Its Im provement,” Computer Application and Software, Vol. 25, No. 8, 2008, pp. 245247. [13] H. Q. Su, M. Lv and F. Tan, “Research and Improve ment of Image Coding Algorithm,” Journal of Xihua Uni versity of Natural Science, Vol. 28, No. 6, 2009, pp. 5154. 5. Acknowledgements We would like to thank the Education Department of the Ningxia Hui Autonomous Region, China for financially supporting this research project under the grant NGY2012024. [14] Y. B. Qi and G. X. Chen, “An Image Compression Algo rithm Based on SPIHT Algorithm,” Journal of Guilin University of Electronic Technology, Vol. 30, No. 4, 2010, pp. 313315. REFERENCES [15] C. W. Deng, B. J. Zhao, “A Approach to Modify Fast SPIHT Algorithm,” Transations of Beijing Institute of Technology, Vol. 30, No. 4, 2010, pp. 478482, 2010. [1] J. M. Shapiro, “Embedded Image Coding Using Zerotree of Wavelet Coefficients,” IEEE Transactions on Signal Processing, Vol. 41, No. 12, 1993, pp. 34453462. doi:10.1109/78.258085
