Communications and Network, 2013, 5, 245-248
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 sub-image 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 Zero-tree 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 sub-band
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 [4-6]. 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 9-7 integral wavelet lifting scheme has good
energy concentration, vanishing moment is bigger. So
adopt the 9-7 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/16-4/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
[]
s
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. 9-7 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 sub-band coefficient as in
[7-9] 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 sub-band, LL layer are dif-
ferent from the other three layers, so the lowest fre-
quency sub-band and other three bit allocation adaptive
when coding, make the output streaming distribution
more bits to the low-frequency coefficients. So, it will
gain higher signal-to-noise 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 sub-band
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 sub-band
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 sub-band.
Sub-band LL5 LH5 HL5 HH5 LH4 HL4 HH4LH3
HVW 1 0.798 0.798 0.684 0.962 0.962 0.8490.981
Sub-band 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 PSNRdb
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. 205-2203. 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. 243-250.
[4] Sweldens. W, “The lifting scheme: a custom-design con-
struction of biorthogonal wavelets,” Applied and Com-
putional Harmonic Analysis, Vol. 6, No. 2, 1996, pp.
186-200. 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. 838-844.
[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. 542-546.
[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. 362-363.
[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. 110-111.
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.
222-227.
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.
195-197.
[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. 277-279.
[12] B. Yan and H. Zhang, “SPIHT Algorithm and Its Im-
provement,” Computer Application and Software, Vol. 25,
No. 8, 2008, pp. 245-247.
[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.
51-54.
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. 313-315.
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. 478-482, 2010.
[1] J. M. Shapiro, “Embedded Image Coding Using Zerotree
of Wavelet Coefficients,” IEEE Transactions on Signal
Processing, Vol. 41, No. 12, 1993, pp. 3445-3462.
doi:10.1109/78.258085