UP PART 1PART 2
EZW encoding
(C) C. Valens, 1999-2004
NEW!
26/02/2004
I finally invested some time to learn how to make PDF files and updated my EZW tutorial PDF file.  06/10/2003
* EZW MatLab code update, again by Xiangang Li.
24/08/2003
* MatLab code !
Many people asked me for this, but I didn't have any. Now I do, thanks to Xiangang Li
(hawaii.edu) ! He implemented the EZW code in MatLab and I have his permission to distribute his code through my web site. I didn't test it because I do not have MatLab.  15/09/2002
* New links.
Finally some people did something useful with my code AND told me about it!
They are rewarded with a link to their work on this page:
Mow Song's Implementation of EZW
Eduard Kriegler's Webpage
25/03/2002
* New email address. The folks at iName now want money so I decided to let good old mindless go.
* All GIF files have been replaced by PNG files. These files are a bit smaller than GIF files and so this page should load a bit faster. (Saved over 8KB on this page!)
20/02/2001
I have finally added the extension of EZW to wavelet based noise reduction using wavelet shrinkage. Please note that this addition is not available in the PDF or postscript files.
02/11/2000
José António da Costa Salvado kindly converted this tutorial to a pdf file. So a big "Thank you!" from all the pdf lovers (including me) to you, José!
Downloads
Download this tutorial as a pdf file
Download the EZW example code in PASCAL or in C. These examples include both the encoder and decoder. Please note that there were some bugs in an earlier version of the C code. These bugs have been corrected. Also, they are now ANSI-C compatible. I use DJGPP to compile them.
Table of Contents
1.Introduction
2.EZW encoding
3.The zerotree
4.How does it work?
5.The algorithm
6.Example
7.Denoising using EZW
8.Coda
9.Notes
10.References
1. Introduction
In this text I will try to explain the implementation of an Embedded Zerotree Wavelet encoder or EZW encoder, which was presented in a paper by J. Shapiro[Sha93]. The reason for this is that I have never come across a good explanation of this technique, yet many researchers claim that they have implemented it. Of course there is Shapiro’s original paper but when reading his paper carefully many details are not immediately clear or even missing. Since I think that the approach of EZW encoding is a fruitful one (see for instance [Cre97]) I have decided to present the details here. This might save others some work in the future.
This text expects some understanding of wavelet transforms.
2. EZW encoding
When searching through wavelet literature for image compression schemes it is almost impossible not to note Shapiro’s Embedded Zerotree Wavelet encoder or EZW encoder for short [Sha93]. An EZ
W encoder is an encoder specially designed to use with wavelet transforms, which explains why it has the word wavelet in its name. The EZW encoder was originally designed to operate on images (2D-signals) but it can also be used on other dimensional signals.
The EZW encoder is based on progressive encoding to compress an image into a bit stream with increasing accuracy. This means that when more bits are added to the stream, the decoded image will contain more detail, a property similar to JPEG encoded images. It is also similar to the representation of a number like  Every digit we add increases the accuracy of the number, but we can stop at any accuracy we like. Progressive encoding is also known as embedded encoding, which explains the E in EZW.
This leaves us with the Z. This letter is a bit more complicated to explain, but I will give it a try in the next paragraph.
Coding an image using the EZW scheme, together with some optimizations results in a remarkably effective image compressor with the property that the compressed data stream can have any bit rate desired. Any bit rate is only possible if there is information loss somewhere so that the compressor is lossy. However, lossless compression is also possible with an EZW encoder, but of course with less
spectacular results.
3. The zerotree
The EZW encoder is based on two important observations:
1.Natural images in general have a low pass spectrum. When an image is wavelet transformed the
energy in the subbands decreases as the scale decreases (low scale means high resolution), so the wavelet coefficients will, on average, be smaller in the higher subbands than in the lower
subbands. This shows that progressive encoding is a very natural choice for compressing wavelet transformed images, since the higher subbands only add detail;
2.Large wavelet coefficients are more important than small wavelet coefficients.
These two observations are exploited by encoding the wavelet coefficients in decreasing order, in several passes. For every pass a threshold is chosen against which all the wavelet coefficients are measured. If a wavelet coefficient is larger than the threshold it is encoded and removed from the image, if it is smaller it is left for the next pass. When all the wavelet coefficients have been visited th
e threshold is lowered and the image is scanned again to add more detail to the already encoded image. This process is repeated until all the wavelet coefficients have been encoded completely or another criterion has been satisfied (maximum bit rate for instance).
The trick is now to use the dependency between the wavelet coefficients across different scales to efficiently encode large parts of the image which are below the current threshold. It is here where the zerotree enters. So, let me now add some detail to the foregoing. (As most explanations, this explanation is a progressive one.)
A wavelet transform transforms a signal from the time domain to the joint time-scale domain. This means that the wavelet coefficients are two-dimensional. If we want to compress the transformed signal we have to code not only the coefficient values, but also their position in time. When the signal is an image then the position in time is better expressed as the position in space. After wavelet transforming an image we can represent it using trees because of the subsampling that is performed in the transform.decoder
A coefficient in a low subband can be thought of as having four descendants in the next higher subband (see figure 1). The four descendants each also have four descendants in the next higher subband and we see a quad-tree emerge: every root has four leafs.
Figure 1
The relations between wavelet coefficients in different subbands as quad-trees.
We can now give a definition of the zerotree. A zerotree is a quad-tree of which all nodes are equal to or smaller than the root. The tree is coded with a single symbol and reconstructed by the decoder as a quad-tree filled with zeroes. To clutter this definition we have to add that the root has to be smaller than the threshold against which the wavelet coefficients are currently being measured.
The EZW encoder exploits the zerotree based on the observation that wavelet coefficients decrease with scale. It assumes that there will be a very high probability that all the coefficients in a quad tree will be smaller than a certain threshold if the root is smaller than this threshold. If this is the case then the whole tree can be coded with a single zerotree symbol. Now if the image is scanned in a predefined order, going from high scale to low, implicitly many positions are coded through the use of zerotree symbols. Of course the zerotree rule will be violated often, but as it turns out in practice, the probability is still very high in general. The price to pay is the addition of the zerotree symbol to our code alphabet.
4. How does it work?
Now that we have all the terms defined we can start compressing. Lets begin with the encoding of the coefficients in decreasing order.
A very direct approach is to simply transmit the values of the coefficients in decreasing order, but this is not very efficient. This way a lot of bits are spend on the coefficient values and we do not use the fact that we know that the coefficients are in decreasing order. A better approach is to use a threshold and only signal to the decoder if the values are larger or smaller than the threshold. If we also transmit the threshold to the decoder, it can reconstruct already quite a lot. To arrive at a perfect reconstruction we

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。