03-12-2012, 02:35 PM
On Zerotree Quantization for Embedded Wavelet Packet Image Coding
1On Zerotree Quantization.pdf (Size: 97.12 KB / Downloads: 25)
Abstract
Wavelet packets are an eective representation tool
for adaptive waveform analysis of a given signal. We
rst combine the wavelet packet representation with
zerotree quantization for image coding. A general ze-
rotree structure is dened which can adapt itself to any
arbitrary wavelet packet basis. We then describe an
ecient coding algorithm based on this structure. Fi-
nally, the hypothesis for prediction of coecients from
coarser scale to ner scale is tested and its eective-
ness is compared with that of zerotree hypothesis for
wavelet coecients.
Introduction
There has been a surge of interest in wavelet transforms
for image and video coding applications, in recent
years. This is mainly due to the nice localization
properties of wavelets in both time (or space)
and frequency. The zerotree quantization, proposed
by Shapiro [8], is an eective way of exploiting the selfsimilarities
among high-frequency subbands at various
resolutions. The main thrust of this quantization
strategy is in the prediction of corresponding wavelet
coecients in higher frequency subbands at the ner
scales, by exploiting the parent-ospring dependencies.
This prediction works well, in terms of eciently
coding the wavelet coecients, due to the statistical
characteristics of subbands at various resolutions, and
due to the scale-invariance of edges in high frequency
subbands of similar orientation. Various extensions of
zerotree quantization, such as [3, 9], have been proposed
ever since its introduction.
Compatible Zerotree Quantization
The wavelet packet basis [1] is adaptively selected
in order to tailor the representation to the contents
of a signal (an image, in our case). The nodes in
a full subband tree (or short-term Fourier transform,
namely STFT, tree) are pruned following a series of
split/merge decisions using certain criterion (see [2]
for entropy-based best basis selection and [6] for optimizing
the best basis from a rate-distortion viewpoint).
Suppose the best basis has been selected us
ing one of these methods. The issue is how to organize
the spatial orientation trees so as to exploit the selfsimilarities,
if any, among the subbands. The basis
selected by any of the above methods does not, in general,
yield the parent-ospring relationships like those
in wavelet subbands. Moreover, there can be an instance
in the wavelet packet tree where one or more of
the child nodes are at a coarser scale than the parent
node. This results in the association of each coecient
of such a child node to multiple parent coecients, in
the parent node, giving rise to a parenting con
ict.
To make the point clear, let us consider the segmentation
shown in Figure 1, for a 3-level wavelet packet
transform.
The Coder Algorithm
Once the compatible zerotrees have been generated,
based upon knowledge of the best basis, the encoding
takes place by repeatedly running the detection
stage and the ne-tuning stage until the bit budget
is expired. Our algorithm requires only one list of
detected coecients (LDC) to be maintained, as opposed
to two (three) lists kept by the EZW (SPIHT).
The decoder rst reads geometry of the best basis and
generates the compatible zerotrees, and then proceeds
by entropy decoding and interpreting the codewords
(see [5] for more details of the algorithm).