|
Academic Open Internet Journal |
Volume 13, 2004 |
A Novel
Image Compression Algorithm using Ridgelet Transformation with Modified SPIHT
N. Malmurugan
Assistant Professor
Department of Electronics and Communication Engineering
n_malan@mail.com
A. Shanmugam
The Principal
Bannariamman
Institute of Technology, Sathyamanagalam 638 401,
S. Jayaraman
Professor
A.R. Abdul Rajak
Assistant Professor
Department of Electronics and Communication Engineering
Abstract--An effective image coding technique
which involves transforming the image into another domain with Ridgelet
function and then quantizing the coefficients with modified SPIHT has been
presented in this paper. Ridge functions are effective in representing
functions that have discontinuities along straight lines. Normal Wavelet
transforms fail to represent such functions effectively. SPIHT has been defined
for normal wavelet decomposed images as an embedded quantization process. If
the coefficients obtained from Ridgelet transform of the image with more
discontinuities along straight lines have to subject to quantization process
with SPIHT, the existing structure of the SPIHT should be modified to suit with
the output of the Finite Ridgelet Transform (FRIT) . In this paper, a modified
SPIHT algorithm for FRIT coefficients has been proposed. The results obtained
from the combination of FRIT with modified SPIHT found much better than that
obtained from the combination of Wavelet Transform with SPIHT
Key words-- Ridgelets, Wavelets, Ridge function, Image coding,
Modified SPIHT, Partitioning, and Radon Transform.
A
Novel Image Compression Algorithm using Ridgelet Transformation with Modified
SPIHT
N. Malmurugan , A. Shanmugam, S. Jayaraman , A.R.
Abdul Rajak
Abstract--An effective image coding technique which involves
transforming the image into another domain with Ridgelet function and then
quantizing the coefficients with modified SPIHT has been presented in this
paper. Ridge functions are effective in representing functions that have
discontinuities along straight lines. Normal Wavelet transforms fail to
represent such functions effectively. SPIHT has been defined for normal wavelet
decomposed images as an embedded quantization process. If the coefficients
obtained from Ridgelet transform of the image with more discontinuities along
straight lines have to subject to quantization process with SPIHT, the existing
structure of the SPIHT should be modified to suit with the output of the Finite
Ridgelet Transform (FRIT) . In this paper, a modified SPIHT algorithm for FRIT
coefficients has been proposed. The results obtained from the combination of
FRIT with modified SPIHT found much better than that obtained from the
combination of Wavelet Transform with SPIHT
Index Terms-- Ridgelets, Wavelets, Ridge
function, Image coding, Modified SPIHT, Partitioning, and Radon Transform.
I.
INTRODUCTION
Candes[1],
in 1998 developed a new set of ideas, ridgelet
analysis, for solving important problems such as constructing neural
networks or approximating and estimating multivariate functions by linear
combinations of ridge functions. Candes and Donoho [2], in 1999 introduced the ridgelet transform as a
new multiscale representation for functions on
continuous spaces that are smooth away from discontinuities along lines. Then
Minh N.Do and Martin Vetterli [5] proposed an
Orthonormal version of the ridgelet transform for discrete and finite-size
images. It uses the finite Radon transform proposed by Bolker
[6] (1987) and Matus and Flusser
[7] (1993) as a basic building block. The transform is invertible,
non-redundant and computed via fast algorithms. Furthermore, this construction
leads to a large family of directional and Orthonormal bases for images.
Many
image processing tasks take advantage of sparse representations of image data
where most information is packed into a small number of samples. Typically,
these representations are achieved via invertible and non-redundant transforms.
Currently, the most popular choices for this purpose are the wavelet transform
and the discrete cosine transform.
The success of wavelets is mainly due to the good
performance for piecewise smooth functions in one dimension. Unfortunately,
such is not the case in two dimensions. In essence, wavelets are good at
catching zero-dimensional or point singularities, but two-dimensional piecewise
smooth signals resembling images have one-dimensional singularities.
Intuitively, wavelets in two dimensions are obtained by a tensor-product of one
dimensional (1-D) wavelets and they are thus good at isolating the
discontinuity across an edge, but will not see the smoothness along the edge.
This fact has a direct impact on the performance of wavelets in many applications
[5]. While simple, these methods work very effectively, mainly due to the
property of the wavelet transform that most image information is contained in a
small number of significant coefficients around the locations of singularities
or image edges. However, since wavelets fail to represent efficiently
singularities along lines or curves, wavelet-based techniques fail to explore
the geometrical structure that is typical in smooth edges of images. Therefore,
new image processing schemes which are based on true two-dimensional (2-D)
transforms are expected to improve the performance over the current
wavelet-based methods.
To overcome the weakness of wavelets in higher
dimensions, Candes and Donoho
[2] recently pioneered a new system of representations named ridgelet which
deal effectively with line singularities in 2-D. The idea is to map a line
singularity into a point singularity using the Radon transform. Then, the
wavelet transform can be used to effectively handle the point singularity in
the Radon domain. Their initial proposal was intended for functions defined in
the continuous R2 space.
II.
CONTINOUS & DISCRETE RIDGELET TRANSFORM
CONTINOUS RIDGELET TRANSFORM:
The continuous ridgelet transform of an integrable bivariate function
f(x) is given by
(1)
where ridgelets 
in 2-D are defined
from a wavelet type function in 1-D 
as
.
. (2)
Wavelets: 
point-position
Ridgelets: 
line-position
The Fig 1 shows the Ridgelet function oriented at an
angle 
and constant along the
lines 
.
Fig 1 Ridgelet Function
In 2-D, points and lines are related through the
Radon transform, thus the wavelet and ridgelet transforms are linked through
the Radon transform. More precisely, denote the Radon transform as
................. (3)
Then the ridgelet transform is the application of a
1-D wavelet transform to the slices (also referred to as projections) of the
Radon transform, and is denoted as
..
.
..
.. (4)
Instead of taking a 1-D wavelet transform on the
radon transform, the application of a 1-D Fourier transform would result in the
2-D Fourier transform. Let 
be the 2-D Fourier
transform of
, and then we have
................................. (5)
This is the famous projection-slice theorem and is commonly used in image
reconstruction from projection methods. In short, the ridgelet transform is the
application of 1-D wavelet transform to the slices of the radon transform,
while the 2-D Fourier transform is the application of 1-D Fourier transform to
those radon slices.
DISCRETE RIDGELET TRANSFORM:
For practical applications, the development of
discrete versions of the ridgelet transform that lead to algorithmic
implementations is a challenging problem. Due to the radial nature of
ridgelets, straightforward implementations based on discretization
of continuous formulae would require interpolation in polar coordinates, and
thus result in transforms that would be either redundant or can not be
perfectly reconstructed. We take up a discrete ridgelet transform proposed by
Minh N. Do and Martin Vetterli [5] that achieves both invertibility
and non-redundancy and its construction leads to a large family of orthonormal
and directional bases for digital images, including adaptive schemes. The
inverse transform is numerically stable and uses the same algorithm as the
forward transform. This discrete version of the Ridgelet Transform uses the
discrete Radon transform discussed earlier to obtain Radon Projections of the
digital image. Then the conventional 1-D Discrete Wavelet Transform is applied
individually on the projections and arranged in a matrix form to result in the
FRIT we are looking for.
III.
ORTHONORMAL FINITE RIDGELET TRANSFORMS
An invertible discrete ridgelet transform can be
obtained by taking the discrete wavelet transform (DWT) on each FRAT projection
sequence 
where the direction 
is fixed. The overall
result is called Finite Ridgelet
Transform as shown in Fig 2. Typically 
is not dyadic,
therefore a special border handling is required. Due to the periodicity
property of the FRAT coefficients for each direction, periodic wavelet
transforms are chosen for
Fig 2 Finite Ridgelet Transform
processing. Since FRAT is redundant and not orthogonal, this
redundancy can be removed by applying 1-D DWT on the projections of the FRAT,
and by this we can obtain an orthonormal transform. For a more general setting,
let us assume that we have a collection of 
1-D orthonormal
transforms on 
(which can be the
same), one for each projection 
of FRAT, that have
bases as
By definition, the FRIT can be written as
.
.(6)
By applying DWT decomposition applied on the FRAT
projections, all of the non-orthogonality and redundancy
of the FRAT is pushed into the scaling coefficients. When the DWTs are
taken to the maximum number of levels then all of the remaining scaling
coefficients at different projections are the same, hence we can drop all but
one of them. The result is an Orthonormal FRIT.
We prove the above result for the general setting
where different transforms can be applied on different FRAT projections. The
choice of transforms can be either adaptive, depending on the image, or
pre-defined. The orthogonality holds as long as the
all lowpass branch of the general tree-structured
filter bank is decomposed to a single coefficient. All other branches would
contain at least one highpass filter thus leading to
zero-mean basis functions. Due to the wrap around effect of the FRAT, some of
its projections could contain strong periodic components so that a Fourier-type
transform like the DCT might be more efficient.
IV.
PROPOSED IMAGE CODING
TECHNIQUE AND ALGORITHMS USED
In this paper we propose the following coding technique
for images with straight singularities. The proposed model shown in Fig 3 is
very effective in overcoming the shortcomings of the wavelet transform based
coding methods when applied to images with linear edges. The technique is as
follows:
1. Represent the image data as intensity values
of pixels in the spatial co-ordinates.
2. Apply Ridgelet Transform (Orthonormal Ridgelet
Transform, to be specific) on the image matrix and get the Ridgelet coefficients of
the image.
3. Quantize the available coefficients using the SPIHT Algorithm, specially modified for the Orthonormal Ridgelet Transform.
4. Use any
form of entropy coding on the bit stream available from the SPIHT encoder.
MODIFIED SPIHT:
The SPIHT Algorithm as given in the literature is a very
useful tool for uniformly quantizing the coefficients obtained from the wavelet
sub band decomposition of images [8], [9],[10]. It forms
Fig 3 Proposed Image Compression Techniques
Lists using the approximation and Nth level
decomposition detail coefficients and then checks them for significance against
a threshold. Offspring are established using quad tree spatial orientation
structures and then each significant coefficient is bit plane coded in the
order of descending entropy. Roots are coded prior to the offspring.
The problem in applying such an algorithm to the
Ridgelet decomposed image is that the form in which ridgelet decomposes the
image is different from that of wavelets.
1. Also the
wavelet decomposition of Radon Projections in the Ridgelet analysis is not
necessarily dyadic.
2. The
approximation and nth level detail coefficients are arranged in the
transform matrix in a different order. So LIST formation should be changed.
3. Moreover
the offsprings are established in a different format.
So modifications must be made in the normal SPIHT
Algorithm to make it comply with the Ridgelet Transform. The following are the
solutions proposed to address these problems in applying SPIHT to Ridgelet
Transformed image:
1. The
Orthonormal Ridgelet Transform which uses dyadic Decomposition of Radon
Projections to the maximum number of levels is chosen for the coding technique.
2. In
Orthonormal RT we find that each column (Wavelet transformed Radon Projection)
has one Approximation coefficient, one nth level detail coefficient,
two (n-1)th level coefficients, four (n-2)th level coefficients and so on. Hence it can be
seen that all approximation coefficients fall in the 1st row of the
RT image and all nth level detail coefficients fall in the 2nd
row.
Fig 4 List Formation in Modified SPIHT Algorithm
So it is very clear that from Fig 5 that the Modified
SPIHT has different type of list contents against Normal SPIHT as described
below:
In
In Modified SPIHT LIP contains 1st
and 2nd row which is again approximation coefficients with nth
level detail coefficients. But, LIS will have 2nd row which is nth
level detail coefficients.
3. Every root has its offspring in the same
column, which means that the spatial orientation trees are mapped considering
each column as a 1-D vector individually. Every nth detail
coefficients has two offspring in (n-1)th
detail coefficients set lying in the corresponding position from the top, as
its root is in the nth level detail coefficients set.
Hence as a
generalization offspring can be mapped by the following formula:
O(i,j) = { (2i,j),(2i+1,j) }
Fig 5 Image Decomposition and Offspring dependencies
using Ridgelet Transform
As a result each parent has two offspring in contrast
to the four offspring for each parent in the normal SPIHT encoding. These are
the important changes made in the SPIHT procedure to be used for Ridgelets
(Orthonormal, to be specific).Rest of the procedure is identical to the one
applied to wavelets including thresholding, refinement and decoding. The
changes made in the encoding process must be considered in the decoding process
and appropriately reflected in the inverse way for faithful reconstruction.
V.
RESULTS AND
COMPARISONS
For testing the performance
of the proposed image coding system, the following test images were taken up:
(a) Object (b) Saturn (c)
Truncated
Gaussian
Fig 6 Test Images
These images in Fig 7 were subjected to orthonormal
Ridgelet transform which uses 1-D dyadic wavelet decomposition. Hence it
provided means for SPIHT encoding. The standard parameters like MSE, PSNR and
CR were calculated for various numbers of planes excluded during the SPIHT
encoding. The results obtained are compared with the SPIHT encoded images after
normal 2-D wavelet decomposition up to the equal number of levels. The wavelet
named db1 was used in both cases.
In the following sections we use the terms proposed
technique for Orthonormal FRIT (OFRIT) followed by Modified SPIHT and
existing technique for 2-D Wavelet Transform followed by Conventional SPIHT. The subject quality of the Reconstructed
Images from Proposed technique is much better than that from the existing
technique which is much evident from the Fig 10.
The
results given in Table I clearly show the superiority of Ridgelet Transforms
over wavelet transforms with straight edges. Moreover the smooth distribution
of the intensity levels
contributes
to the compaction of most part of the image energy in the low frequency range,
so that the compression becomes much easier and effective. Ridgelets outdo the
wavelets in all parameters taken for comparison for the given object image.
Since the edges are captured in a
TABLE I
Comparison results of OBJECT image
|
No. of bit planes excluded |
CR |
RMSE |
PSNR |
|||
|
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
|
|
6 |
52.0891 |
67.1132 |
19.8702 |
30.7691 |
24.1152 |
20.2246 |
|
5 |
26.0074 |
31.2467 |
18.9722 |
30.2331 |
24.5735 |
20.5078 |
|
4 |
8.4370 |
16.2444 |
18.6265 |
29.9898 |
25.1293 |
21.0340 |
|
3 |
3.6959 |
9.5448 |
17.3571 |
29.9418 |
25.3914 |
21.0664 |
TABLE II
Comparison results of SATURN image
|
No. of bit planes excluded |
CR |
RMSE |
PSNR |
|||
|
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
Proposed scheme |
Existing scheme |
|
|
6 |
63.6080 |
57.9196 |
14.6810 |
19.8392 |
29.0424 |
22.3071 |
|
5 |
43.8937 |
31.5551 |
14.3753 |
19.5026 |
29.4098 |
22.4515 |
|
4 |
20.8719 |
19.1304 |
13.9449 |
19.4416 |
29.1155 |
22.4620 |
|
3 |
7.5464 |
12.3840 |
13.6012 |
19.3265 |
26.6214 |
22.6305 |
very small number of ridgelet coefficients,
the performance is very good even when most of the coefficients are dropped. In
the case of wavelets it is not the same. They fail in capturing the two
dimensional singularity as effectively as the Ridgelet transform.
Statistics in Table II provides a clear insight in the efficiency of the Ridgelet transform in coding the Saturn image which has a curved edge. Even though the boundary is curved, we can very well observe different shades of intensity along straight lines. This aspect has contributed to the success of Ridgelet over Wavel