Wavelets and their Applications

Appendix

The EZW Algorithm

This appendix supplements section 8.6.3.2 dedicated to the EZW algorithm used in wavelet image compression. It details the operation of the algorithm and presents an example of application. We successively tackle coding and decoding (we note by ⌊ x ⌋ the integer part of x).

For other insights on the EZW algorithm, see [CRE 97], [USE 01] and [VAL 99]. In the book by Strang and Nguyen (see [STR 96], p. 362-383), we will find a detailed presentation of the various operations related to compression: quantization, coding, etc.

A.1. Coding

A.1.1. Detailed description of the EZW algorithm (coding phase)

(1) Initialization. All the coefficients are placed on the principal list and the threshold is initialized by T₀ = 2^{⌊log2(C_max)⌋}, where C_max is the maximum of the absolute value of the coefficients.

(2) Principal stage. Go through the coefficients on the principal list in an appropriate order (see Figure 8.45) and compare each of them with the current threshold T_n. Attribute one of the four following symbols to each coefficient:

– P, if it is positive and has an absolute value higher than the threshold;

– N, if it is negative and has an absolute value higher than the threshold;

– Z, if its absolute value is lower than the threshold but if one of its children has an absolute value higher than the threshold;

– T if its absolute value is lower than the threshold and if all its children have absolute values lower than the threshold.

Thanks to the zerotree property ...