Evaluation of Wavelet Filters For Image Compression: G. Sadashivappa, and K. V. S. Anandababu
Evaluation of Wavelet Filters For Image Compression: G. Sadashivappa, and K. V. S. Anandababu
Evaluation of Wavelet Filters For Image Compression: G. Sadashivappa, and K. V. S. Anandababu
features of wavelet functions and filters used in sub band coding to images can either be lossless or lossy. Images compressed in a
convert image into wavelet coefficients in MATLAB. Image quality
lossless manner can be reconstructed exactly without any
is measured objectively using peak signal to noise ratio (PSNR) and
its variation with bit rate (bpp). The effect of different parameters is
change in the intensity values. This limits the amount of
studied on different wavelet functions. Our results provide a good compression that can be achieved in images encoded using
reference for application designers of wavelet based coder. lossless techniques. However, many applications such as
satellite image processing and certain medical and document
Keywords—Wavelet, image compression, sub band, SPIHT, imaging, do not tolerate any losses in their data and are
PSNR. frequently compressed using lossless compression methods.
Lossy encoding is based on trading off the achieved
I. INTRODUCTION compression or bit rate with the distortion of the reconstructed
image. Lossy encoding for images is usually obtained using
D ATA compression techniques help in efficient data
transmission, storage and utilization of hardware
resources. Uncompressed multimedia requires considerable
transform encoding methods. Transform domain coding is
used in images to remove the redundancies by mapping the
pixels into a transform domain prior to encoding. The
storage capacity and transmission bandwidth. Despite rapid mapping is able to represent image information containing
progress in mass- storage density, processor speeds and digital most of the energy into a small region in the transform domain
communication system performance, demand for data storage requiring only a few transform coefficients to represent. For
capacity and data transmission bandwidth continues to compression, only the few significant coefficients must be
outstrip the capabilities of available technologies. The recent encoded, while a majority of the insignificant transform
growth of intensive digital audio, image and video (multi coefficients can be discarded without significantly affecting
media) based applications, have not only sustained the the quality of the reconstructed image. An ideal transform
compression of such signals central to signal storage and mapping should be reversible and able to completely decor
digital communication technology. Table I shows the relate the transform coefficients.
multimedia data types and its requirements. This information
clearly suggests the need of compression.
TABLE I
MULTIMEDIA DATA
II. IMAGE COMPRESSION SCHEMES Multimedia Size/duration Bits/pixel or Uncompressed
Image compression reduces the amount of data required to data Bits/sample size
represent an image by removing redundant information. Three Page of text 11” x 8.5” Varying 16-32 Kbits
types of redundancies typically exist in digital images that can resolution
be exploited by compression. These are, coding redundancy Telephone 1 Sec 8 bps 64 Kb/sec
quality
that arises from the representation of the image gray levels,
speech
interpixel redundancy that exists due to high correlation Gray scale 512 x 512 8 bpp 2.1 Mb/image
between neighboring pixels, and psycho visual redundancy image
that is obtained based on Human perception of the image Color 512 x 512 24 bpp 6.29 Mb/image
information [8]. An image compression system consists of an image
Medical 2048 x 2048 12 bpp 100 Mb/image
image
G. Sadashivappa is Assistant Professor in the Department of Full motion 640 x 640,10 24 bpp 2.21 Gbits
Telecommunication Engineering, R. V. College of Engineering, Mysore Road, Video Sec
Bangalore-59, Karnataka, India (e-mail:g_sadashivappa@yahoo.com).
K.V.S. Ananda Babu is the Principal of C.M.R.Institute of Technology,
No.132, AECS Layout; I.T.Park Road, Bangalore -37, Karnataka, India (e-
mail:anandkvs@hotmail.com).
International Scholarly and Scientific Research & Innovation 3(3) 2009 430 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
III. WAVELET BASED IMAGE CODING the resulting image. Steps must be therefore taken to protect
the encoded bit stream from being affected by various bit
errors and losses.
Fig. 1 shows the wavelet based coder has three basic And
components: a transformation, a quantizer and an encoder.
Most existing high performance image coders in applications PSNR = 20 * log10 (255 / sqrt(MSE)) (2)
are transform based coder [1]. In the transform coder, the
image pixels are converted from the spatial domain to the Where I(x,y) is the original image, I'(x,y) is the approximated
transform domain through a linear orthogonal or bi-orthogonal version (which is actually the decompressed image) and M,N
transform. A good choice of transform accomplishes a are the dimensions of the images. MSE and PSNR are the
decorrelation of the pixels, while simultaneously providing a most common methods for measuring the quality of
representation in which most of the energy is usually restricted compressed images, despite the fact that they are not adequate
to a few (relatively large) coefficients. This is the key to as perceptually meaningful measures of image quality.
achieve an efficient coding (i.e., high compression ratio). Equation (2) is for commonly used 8bpp images.
Indeed, since most of the energy rests in a few large transform In image compression systems, the truly definitive measure
coefficients, we may adopt entropy coding schemes, e.g., run- of image quality is perceptual quality. The distortion is
level coding or bit plane coding schemes, that easily locate specified by mean opinion score (MOS) or by picture quality
those coefficients and encodes them. Because the transform scale (PQS). MOS is perception based subjective evaluation
coefficients are highly decorrelated, the subsequent quantizer where as PQS is perception based objective evaluation. PQS
and entropy coder can ignore the correlation among the methodology uses some of the properties of HVS relevant to
transform coefficients, and model them as independent global image impairments, such as random errors, and
random variables. emphasizes the perceptual importance of structured and
The zerotree concept [1], provided an efficient and localized errors. PQS is constructed by regressions with MOS,
embedded representation of quantized wavelet coefficients which is 5-level grading scale developed for subjective
and lead to an image compression method, the embedded evaluation. (5-imperceptible, 4 – perceptible, but not
zerotree wavelet (EZW) coding. A zero tree is used to annoying , 3 – slightly annoying , 2 – annoying , 1 – very
represent a particular group of wavelet coefficients across annoying). The compression efficiency is defined by the
different wavelet sub bands that have insignificant values. The parameter compression ratio, CR and is given by,
zero tree approach exploits the multiresolution nature of the
wavelet decomposition and has lead to several other low
complexity and extremely efficient image compression Original Data
schemes. One of the more popular methods based on similar CR = ----------------------------- (3)
principles of the zerotree is the SPIHT [3], by Said and Compressed Data
Pearlman, which improves upon the EZW with better
management of the zerotrees. The SPIHT method is discussed Actual bpp
in more detail in the section-V. The JPEG2000 image coding Or, CR = --------------------- (4)
standard [7, 18] also achieves its superior performance due to Reduced bpp
the wavelet transform-based embedded block coding with
optimal truncation (EBCOT) scheme. These encoding For example, if actual bpp = 8 and reduced bpp = 0.5 then CR
schemes described above are fast, are efficient, have low = 16:1. If original data = 512 x 512 x 8 = 1.497152 Bits and
complexity, and provide high quality images at extremely low compressed data = 1.497152 Bits then CR = 1000:1.
bit rates, making them suitable for image transmission across
channels with bandwidth constraints. The progressive nature
of these schemes, however, results in the encoded data being
highly susceptible to bit errors, causing severe distortions to
International Scholarly and Scientific Research & Innovation 3(3) 2009 431 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
several different areas, like sub band coding, quadrature responses, respectively. The filter outputs at level n are given
mirror filters, pyramid schemes,etc. Further, wavelets permit by an, hn, vn, and dn, respectively. The lowpass filter output
multiresolutin analysis with the following properties: from the previous level serves as the input for the next level of
orthogonality, compact support, rational coefficients, decomposition. The use of biorthogonal wavelets has been
symmetry, smoothness, number of vanishing moments and found to be the most suitable for obtaining image wavelet
analytic expressions. Fig. 4 shows structural properties of db9 transforms for compression applications. The biorthogonal
and bior6.8 as a specific case. These are the low pass and high filters have linear phase and symmetric properties that are
pass filters used in the wavelet decomposition of image. In useful in avoiding boundary artifacts in images [8]. One of the
this experimentation, we Considered Lena most popular set of biorthogonal filters are the Daubechies’
512_reconstruct.bmp image which is available in MAT LAB 9/7 analysis and synthesis filters, used quite commonly for
to test different wavelet filters at different levels of image compression applications. The 2-D wavelet transform,
decomposition. By considering global thresholding, dbN when applied to images, provides decorrelation and yields a
filters tested for retained energy in % and number of zeros in spatial-frequency distribution of the image.
% where as bior Nd, Nr filters are tested for normal
coefficients recovery in% and number of zeros in %. Table-II,
TableIII (A) and III (B) gives the results, it is observed that
for better compression the level of decomposition should be
grater than 3. The type and order of filter depends on
symmetry and vanishing moments.
B. Wavelet Transform
Discrete Wavelet transform requires two sets of related
functions called scaling function and wavelet function. Most
of the scaling and wavelet functions are fractal in nature and
iterative methods are required to see its shape. Most good and
modern image compression schemes are based on the wavelet
transform. Wavelets have been identified as basis functions or
building blocks that can be used to produce all possible
functions. They can also quickly decorrelate data [19,20],
which can lead to a more compact representation than the
original data. In addition, wavelets have the special feature
that all the wavelet functions can be constructed from a single Fig. 2 n-level wavelet decomposition of a 2-D input
mother wavelet w(t), which is effectively a small wave. The
other wavelet functions, wij(t) are obtained from the mother
wavelet by translation and compression or dilation as shown a (x, y) - approximation coefficient , v( x, y ) – vertical
below. coefficient
h ( x ,y ) – horizontal coefficient , d ( x, y ) – diagonal
Wij (t) = w (2it − j), (5) coefficient
Where i and j represent the scaling (compression or dilation)
and the translation parameters, respectively. The compression
and translation allow the wavelet functions to represent
signals in multiple levels of time-frequency resolutions. The
multiresolution representation of wavelets along with their
International Scholarly and Scientific Research & Innovation 3(3) 2009 432 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
LL3 HL3 1
Decomposition low-pass filter
0.5
Decomposition high-pass filter
0.5 0
-0.5 -1
0 5 10 15 20 0 5 10 15 20
The four filters for bior6.8
International Science Index, Electronics and Communication Engineering Vol:3, No:3, 2009 waset.org/Publication/3559
-0.5 -1
0 5 10 15 20 0 5 10 15 20
The four filters for db9
International Scholarly and Scientific Research & Innovation 3(3) 2009 433 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
TABLE III (A) same logic holds good. For L=3, normal coefficients recovery
BIOR Nd,Nr WAVELET FILTER RESPONSE (ENERGY RECONSTRUCTION )
in % and number of zeros in % are not equal, it is equal for
NORMAL COEFFICIENTS RECOVERY IN %
L=5. Hence maximum value for L is 5, beyond which no
L 1 2 3 4 5
improvement in compression and further increases delay in
operation (MOP will increase).[12 ]
Wavelet
Table IV and Fig. 5 gives the variation of PSNR with
Bior1.1 99.88 99.42 98.30 98.85 98.91
respect to level of decomposition L by keeping CR at
Bior1.3 99.88 99.44 99.17 98.78 98.94
10:1.This will suggest selecting the optimum value of L
Bior1.5 99.88 99.33 98.57 98.97 99.15
Bior2.2 100 99.92 99.72 99.21 99.34 TABLE IV
Bior2.4 100 99.97 99.07 99.04 99.18 EFFECT OF LEVEL OF DECOMPOSITION (L), CR=10:1
Bior2.6 100 99.90 99.58 99.09 99.22 PSNR VALUES FOR DIFFERENT WAVELET FILTERS
Bior2.8 100 99.95 99.34 98.96 99.15 WF Db7 Db9 Bior2 Bior Sym5 Coif5
Bior3.1 100 99.97 99.45 98.94 99.10 L 2 4. 4
Bior3.3 100 99.97 99.55 98.93 99.06 2 16.91 16.92 17.88 16.73 16.92 16.93
Bior3.5 100 99.96 99.31 98.85 99.00
International Science Index, Electronics and Communication Engineering Vol:3, No:3, 2009 waset.org/Publication/3559
45
TABLE III(B) 40
BIOR Nd,Nr WAVELET FILTER RESPONSE (ENERGY RECONSTRUCTION) db7
NUMBER OF ZEROS IN %( biorNd,Nr ) 35
30 db9
L 1 2 3 4 5
PSNR
25 bior2.2
Wavelet 20 bior4.4
Bior1.1 75.00 93.75 98.30 98.85 98.90 15
Bior1.3 75.00 93.64 98.17 98.78 98.95 sym5
10
Bior1.5 75.00 93.46 98.18 98.97 99.20 5 coif5
Bior2.2 75.00 93.50 98.21 99.21 99.34 0
Bior2.4 75.00 93.46 98.18 99.04 99.18
2 3 4 5 6
Bior2.6 75.00 93.36 98.10 99.08 99.22
Bior2.8 75.00 93.32 98.02 98.96 99.15 LEVEL
Bior3.1 75.00 93.22 97.95 98.96 99.10
Bior3.3 75.00 93.18 97.92 98.93 99.08 Fig. 5 Graph for PSNR v/s LEVEL ( L) of decomposition
Bior3.5 75.00 93.08 97.84 98.86 99.00
Bior3.7 75.00 93.22 97.95 98.79 98.98
Bior3.9 75.00 93.08 97.84 98.61 98.74 C. Set-Partitioning in Hierarchical Trees (SPIHT)
Bior4.4 75.00 93.46 98.18 99.20 99.35 The SPIHT algorithm, developed by Said and Pearlman in
Bior5.5 75.00 93.36 98.10 99.23 99.41 1996 [3], is a fast and efficient image compression algorithm
Bior6.8 75.00 93.18 97.92 98.95 99.17 that works by testing ordered wavelet coefficients for
significance in a decreasing bit plane order, and quantizing
only the significant coefficients. The high coding efficiency
obtained by this algorithm is due to a group testing of the
coefficients that belong to a wavelet tree. Group testing is
advantageous because of the inter-band correlation that exists
Table III (A) and (B) gives the energy compaction and between the coefficients belonging to a tree. The SPIHT uses
reconstruction properties of orthogonal filters db and bior the fundamental idea of zero-tree coding from the EZW but is
category. It is observed that with respect to dbN category, for able to obtain a more efficient and better compression
L=3, the energy retained in % and number of zeros in % are performance in most cases without having to use an arithmetic
not equal. This suggests there is a scope for compression, encoder.
whereas for L=5, both the parameters are equal and it is The SPIHT algorithm groups the wavelet coefficients and
optimized level of decomposition. In the case of biorNd,Nr, trees into sets based on their significance information. The
International Scholarly and Scientific Research & Innovation 3(3) 2009 434 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
encoding algorithm consists of two main stages, sorting and 8bpp gray scale. The error metric used to compare different
refinement. In the sorting stage, the threshold for significance filters is PSNR.
is set as 2n, where n is the bit level, and its initial value is
determined by the number of bits required to represent the TABLE V (A)
PSNR PERFORMANCE OF DIFFERENT FILTERS
wavelet coefficient with the maximum absolute value.
Significance for trees is obtained by checking all the member L=5, LENA GRAY IMAGE 512 x 512, 8BPP.
detail coefficients. Approximation coefficients are tested as C Bpp Db1 db7 Db9 Bior2. Bior4.
individual entries. The initial listing that determines the order R (haar) 2 4
in which significance tests are done is predetermined for both 8 1 37.37 39.57 39.51 39.14 39.75
the approximation coefficients as well as the trees. The 16 0.5 33.29 36.02 35.87 35.74 36.35
algorithm searches each tree, and partitions the tree into one 32 0.25 29.83 32.40 32.29 32.30 32.79
of three lists: 1) the list of significant pixels (LSP) containing 64 0.125 26.95 28.83 28.78 28.90 29.26
the coordinates of pixels found to be significant at the current 12 0.062 24.05 25.57 25.48 25.63 25.61
threshold; 2) the list of insignificant pixels (LIP), with pixels 8 5
that are not significant at the current threshold; and 3) the list 25 0.031 20.84 21.75 21.62 22.18 21.63
6 25
International Science Index, Electronics and Communication Engineering Vol:3, No:3, 2009 waset.org/Publication/3559
International Scholarly and Scientific Research & Innovation 3(3) 2009 435 scholar.waset.org/1307-6892/3559
World Academy of Science, Engineering and Technology
International Journal of Electronics and Communication Engineering
Vol:3, No:3, 2009
K.V.S. Ananda Babu graduated from IIT Madras in 1969, obtained M.Tech
from IIT Delhi in 1983. He obtained doctorate from Osmania University,
Osmania in 2000. His research interests are Adaptive Signal Processing,
Image & Video Coding and Channel Coding. He has 31 years of research
experience in DRDO labs. Currently working as Principal CMRIT, Bangalore.
International Scholarly and Scientific Research & Innovation 3(3) 2009 436 scholar.waset.org/1307-6892/3559