A SIMPLE RUN LENGTH ENCODING SCHEME FOR LOWER ENCODINGS OF
SPIHT IMAGE COMPRESSION
R. R. Lakkundi, M. V. Latte
Department of Electronics and Communication Engineering
S.D.M. College of Engineering and Technology,
Dhavalagiri, Dharwad-580002, Karnataka, INDIA
ravilakkundi@rediffmail.com, mvlatte@rediffmail.com
Abstract—Set Partitioning in Hierarchical Trees (SPIHT)
[1] uses scalar quantization for images that have
undergone subband decomposition by wavelet transform.
These algorithms use some sort of bit plane coding for
image coding and progressively transmit bit-planes in
successive passes including an embedded bit-map of
significant coefficient sets with each pass. SPIHT
compression is achieved by coding sets that share a
common characteristic with a single bit in the bit-map. The
choice of aggregate set is made via quad-tree according to
the structure of input images and the transform in SPIHT.
In SPIHT every transform coefficient is tested against a
threshold to exploit common characteristic. Unfortunately,
in some images there exist very few coefficients in the
initial pass that exceed this threshold. If just one coefficient
in a set were to exceed the threshold, it would still
necessitate the transmission of the complete significance
bit-map for that set in order to identify that coefficient. In
this paper a successful algorithm is developed to overcome
this problem. The algorithm developed is simple and
efficient, and is incorporated in already existing efficient
SPIHT algorithm, which improve the total performance of
the compression algorithm. Also it is shown that this
method can be efficiently used in hardware realization of
the codec using only additional 1-4 bytes of memory.
Index Terms—Lossy image compression, Tree based
coding, spatial orientation trees
I. INTRODUCTION
n SPIHT image compression every wavelet transform
coefficient is tested against a threshold to exploit
common characteristic. Unfortunately, in some images
there exist very few coefficients in the initial pass that
exceed this threshold. If just one coefficient in a set
were to exceed the threshold, it would still necessitate
the transmission of the complete significance bit-map
for that set in order to identify that coefficient.
A set H is formed in SPIHT by adding all spatial tree
root co-ordinates to it and the algorithm initializes List
of Insignificant sets (LIS) to co-ordinates those with
descendants as type A entry. The algorithm proceeds by
testing every element corresponding in List of
Insignificant Pixel (LIP) and then by testing every set of
LIS and marks them Type B set if necessary.
Now consider images where in few coefficients exceed
initial threshold, intuitively if the subband
transformation is ordered then those coefficients will be
in the DC subband. Since no corresponding coefficients
of LIS are significant, the significance check yields
zero, thus the same are transmitted. For an image of 512
× 512 decomposed to five levels, we will have initially
length of LIS, as 768 in addition there will be
coefficients from DC band also whose significance test
will result zero. Experiments show that many images
pass this test i.e. very few coefficients in initial 1-3
passes exceed the threshold.
A simple analysis test is used to determine the number
of initial passes or number of initial bits to be
considered for the proposed method. Once the coding
parameter i.e. number of initial passes or number of bits
is chosen, which is generally in the range of 1-3 passes
or 2000-8000 bits, run length encoding is used to code
the bit-stream. The computational complexity and time
involved in this process of simple form of run length
coding are less, compared to the existing methods
addressing the same problem. Although this method
consumes very small amount of additional memory i.e.
to the extent of 1-4 bytes, which is really negligible as
compared to 800 KB of memory used in No List SPIHT
algorithm [2] to an image size of 512 × 512, for 5 levels
of subband decomposition.
II.WAVELET TRANSFORMS BY LIFTING
Traditionally, a non-redundant wavelet transform has
been implemented as an iterative filter banks with
downsampling operations [3]. This is commonly known
as Mallat’s Fast Wavelet Transform (FWT), which is
derived from the multiresolution nature of the wavelet
approximation spaces as illustrated in Fig. 1 [4]. To
decompose a signal (analysis), the low and high-pass
filters
(
)
nh and
(
)
ng respectively are used in the filter
bank. The dual of these filters
(
)
nh and
(
)
ng , are used
I
