4.5 Embedded zero tree wavelet (EZW) algorithm

The combination of the zero tree roots with successive approximation has opened up a very interesting coding tool for not only efficient compression of wavelet coefficients, but also as a means for spatial and SNR scalability [4].

The encoding algorithm with slight modification on the successive approximation, for efficient coding, according to EZW [4] is described as follows:

The image mean is computed and extracted from the image. This depends on how the lowest band LL is coded. If it is coded independently of other bands, such as with DPCM in MPEG-4, then this stage can be ignored.
An R stage (3R+1 band) wavelet transform is applied to the (zero mean) image.
The initial yardstick length l is set to half of the maximum absolute value of the wavelet coefficients.
A list of the coordinates of the coefficients, called the dominant list, is generated. This list determines the order in which the coefficients are scanned. It must be such that coefficients from a lower frequency band (higher scale) are always scanned before the ones from a higher frequency band. Two empty lists of coefficient coordinates, called the subordinate list and the temporary list, are also created.
The wavelet transform of the image is scanned and, if a wavelet coefficient is smaller than the current yardstick length l, it is reconstructed to zero. Otherwise, it is reconstructed as ±3l/2, according to its sign.
Dominant pass: the reconstructed coefficients are scanned again, according to the order in the dominant list, generating a string of symbols as follows. If a reconstructed coefficient is positive or negative, a + or a - is added to the string, and the coordinates of this coefficient are appended to the subordinate list. If a reconstructed coefficient is zero, its coordinates are appended to the temporary list. In the case of a zero-valued reconstructed coefficient, two different symbols can be appended to the string; if all its corresponding coefficients in bands of the same orientation and higher frequencies are zero, a zero tree root (ZT) is added to the string, and its corresponding coefficients are removed from the dominant list and added to the temporary list (since they are already known to be zero, they do not need to be scanned again). Otherwise, an isolated zero (Z) is added to the string. The strings generated from the four-symbol alphabet of +, -, ZT and Z are encoded with an adaptive arithmetic encoder [15], whose model is updated to four symbols at the beginning of this pass. However, during the scanning of the highest horizontal, vertical and diagonal frequency bands (HL₁, LH₁ and HH₁ of Figure 4.12), no zero tree roots can be generated. Therefore, just before the scanning of the first coefficient of these bands, the model of the arithmetic coder is updated to three symbols of +, - and Z.
The yardstick length l is halved.
Subordinate pass: the coefficients which previously have not been reconstructed as zero are scanned again according to their order in the subordinate list, and each one has added to it either +l/2 or -l/2 in order to minimise the magnitude of its reconstruction error. If l/2 is added, a + is appended to the string, and if l/2 is subtracted, a - is appended. At the end of the subordinate pass the subordinate list is reordered so that the coefficients whose reconstructed values have higher magnitudes come first. The + and - symbols of this pass are encoded with the arithmetic coder, which had its model updated to two symbols (+ and -) at the beginning of this pass.
The dominant list is replaced by the temporary list, and the temporary list is emptied.
The whole process is repeated from step 5. It stops at any point when the size of the bit stream exceeds the desired bit rate budget.

An observation has to be made on the dominant pass (step 6). In this pass, only the reconstructed values of the coefficients that are still in the dominant list can be affected. Therefore, in order to increase the number of zero tree roots, the coefficients not in the dominant list can be considered zero for determining if a zero-valued coefficient is either a zero tree root or an isolated zero.

The bit stream includes a header giving extra information to the decoder. The header contains the number of wavelet transform stages, the image dimensions, the initial value of the yardstick length and the image mean. Both the encoder and decoder initially have identical dominant lists. As the bit stream is decoded, the decoder updates the reconstructed image, as well as its subordinate and temporary lists. In this way, it can exactly track the stages of the encoder, and can therefore properly decode the bit stream. It is important to observe that the ordering of the subordinate list in step 8 is carried out based only on the reconstructed coefficient values, which are available to the decoder. If it was not so, the decoder would not be able to track the encoder, and thus the bit stream would not be properly decoded.

4.5.1 Analysis of the algorithm

The above algorithm has many interesting features, which make it especially significant to note. Among them one can say:

The use of zero trees exploits similarities among the bands of the same orientation and reduces the number of symbols to be coded.
The use of a very small alphabet to represent an image (maximum number of four symbols) makes adaptive arithmetic coding very efficient, because it adapts itself very quickly to any changes in the statistics of the symbols.
Since the maximum distortion level of a coefficient at any stage is bounded by the current yardstick length, the average distortion level in each pass is also given by the current yardstick, being the same for all bands.
At any given pass, only the coefficients with magnitudes larger than the current yardstick length are encoded nonzero. Therefore, the coefficients with higher magnitudes tend to be encoded before the ones with smaller magnitudes. This implies that the EZW algorithm tends to give priority to the most important information in the encoding process. This is aided by the ordering of the subordinate in step 8. Thus for the given bit rate, the bits are spent where they are needed most.
Since the EZW algorithm employs a successive approximation process, the addition of a new symbol (+, -, ZT and Z) to the string just further refines the reconstructed image. Furthermore, while each symbol is being added to the string it is encoded into the bit stream; hence the encoding and decoding can stop at any point, and an image with a level of refinement corresponding to the symbols encoded/decoded so far can be recovered. Therefore, the encoding and decoding of an image can stop when the bit rate budget is exhausted, which makes possible an extremely precise bit rate control. In addition, due to the prioritisation of the more important information mentioned in item d, no matter where in the bit stream the decoding is stopped, the best possible image quality for that bit rate is achieved.
Spatial/SNR scalability: in order to achieve spatial or SNR scalability, two different scanning methods are employed in this scheme. For spatial scalability, the wavelet coefficients are scanned in the subband-by-subband fashion, from the lowest to the highest frequency subbands. For SNR scalability, the wavelet coefficients are scanned in each tree from the top to the bottom. The scanning method is defined in the bit stream.