15-05-2013, 04:44 PM
Embedded Zerotree Wavelet (EZW) Image Compression
Embedded Zerotree.pdf (Size: 648.82 KB / Downloads: 205)
Why Wavelets? [1]
• Traditional DCT & subband coding: trends “obscure” anomalies that carry
info
– E.g., edges get spread, yielding many non-zero coefficients to be coded
• Wavelets are better at localizing edges and other anomalies
– Yields a few non-zero coefficients & many zero coefficients
– Difficulty: telling the decoder “where” the few non-zero’s are!!!
• Natural images in general have a low pass spectrum.
– the wavelet coefficients will, on average, be smaller in the higher subbands than in
the lower subbands.
• Large wavelet coefficients are more important than smaller wavelet
coefficients.
• Significance map (SM): binary array indicating location of zero/non-zero
coefficients
– Typically requires a large fraction of bit budget to specify the SM
– Wavelets provide a structure (zerotrees) to the SM that yields efficient coding
Motivation for EZW (cont.)
But… Couldn’t we use entropy coding to make this more
efficient? Yes… in fact, that is what JPEG does. But it is easy
to see that even with entropy coding the significance map (SM)
idea get “expensive” as we go to low bit rates [1].
Total Bit Cost = Bit Cost of SM + Bit Cost of Nonzero Values
Under some simplifying conditions (see [1]) Shapiro argued
using entropy calculations that the percentage of total cost
taken up by SM coding increases as the bit rate decreases!!!
How Do Zerotrees Help?
The previous chart showed the prevalence of zerotrees.
Now… how do they help with the SM problem?
You only have to tell the decoder where a zero root lies… it
can figure out where all the descendent zeros on the tree lie
by using the rule for generating quadtrees.
So… there is an agreed upon a rule and it so happens that
zerotree roots happen alot when trying to code at low bit
rates…
At low bit rates, zerotree roots occur frequently even at the
coarse subband levels and that leads to long trees… and that
very efficiently conveys the SM info
Applying the SA quantizer with in EZW:
• Compute the wavelet transform of the image
• Set a threshold T0 near the middle of the range of WT coefficient
magnitudes
• This gives a large “dead zone” that creates of lots of “insignificant
values”
These give rise to lots of zerotrees
Zerotrees efficiently handle significance map problem
Send MSB’s of significant coefficients