What is Embedded Zerotree of Wavelet Coefficient (EWZ) Algorithm


Introduction

The Embedded Zerotree of Wavelet Coefficient (EZW) algorithm is a popular lossy image compression technique that was introduced by Shapiro in 1993. This algorithm is based on wavelet transforms and provides excellent compression ratios for still images with high visual quality. The algorithm is designed to achieve high compression by exploiting the self-similarity and statistical redundancy present in natural images.

The EZW algorithm is considered to be the precursor to the modern JPEG2000 standard, which is also based on wavelet transforms. EZW is used in many applications where high-quality images need to be transmitted or stored with minimal storage requirements, including satellite imaging, medical imaging, and multimedia applications.

Wavelet Transform

Before discussing the EZW algorithm, it is essential to understand the wavelet transform. The wavelet transform is a mathematical technique that decomposes a signal or image into multiple sub-bands of different frequencies and scales. The decomposition is performed by convolving the signal or image with a series of wavelet filters.

The wavelet transform has many advantages over other transforms such as the Fourier transform. The wavelet transform can efficiently represent signals or images with discontinuities and can localize features in time and frequency. This property makes the wavelet transform an excellent tool for image compression.

Embedded Zerotree of Wavelet Coefficient (EZW) Algorithm

The EZW algorithm is a wavelet-based image compression technique that exploits the redundancy present in natural images. The EZW algorithm can compress an image by a factor of 10 to 100 with high visual quality. The algorithm works by encoding the wavelet coefficients of the image using a combination of zerotree coding and adaptive arithmetic coding.

Zerotree Coding

The EZW algorithm exploits the fact that many wavelet coefficients in an image are small or zero. The algorithm works by grouping the wavelet coefficients into blocks of increasing resolution. The blocks are encoded using a technique called zerotree coding.

In zerotree coding, the wavelet coefficients are scanned in a specific order, and for each coefficient, the algorithm checks whether it is zero or not. If the coefficient is zero, then the algorithm checks whether all the coefficients in its immediate neighborhood are also zero. If all the coefficients are zero, then the block is marked as a zerotree.

If the block is marked as a zerotree, then the algorithm does not need to encode the coefficients in the block since they are all zero. Instead, the algorithm encodes a symbol indicating that the block is a zerotree.

Adaptive Arithmetic Coding

The EZW algorithm uses adaptive arithmetic coding to encode the non-zero wavelet coefficients. Arithmetic coding is a technique for lossless compression that assigns shorter codes to frequently occurring symbols and longer codes to less frequently occurring symbols. In adaptive arithmetic coding, the code assignments are updated based on the previous symbols in the stream.

The EZW algorithm uses a variant of adaptive arithmetic coding called MQ-coder. MQ-coder is a fast and efficient variant of adaptive arithmetic coding that was developed by Said and Pearlman in 1996.

The EZW algorithm encodes the non-zero wavelet coefficients by performing the following steps:

1. Thresholding: The wavelet coefficients are thresholded at a certain level. The thresholding ensures that only the significant coefficients are encoded.

2. Sorting: The significant coefficients are sorted by magnitude.

3. Encoding: The significant coefficients are encoded using adaptive arithmetic coding.

4. Refinement: The encoding process is repeated with a lower threshold, and the additional coefficients are encoded using adaptive arithmetic coding.

5. Termination: The encoding process is terminated when the desired compression ratio is achieved or when the error introduced by the encoding process is below a certain threshold.

Advantages and Disadvantages of EZW

Advantages:

1. High Compression Ratio: The EZW algorithm can achieve high compression ratios with minimal loss of image quality. This makes it an ideal algorithm for applications where storage or bandwidth is limited.

2. Fast Decoding: The EZW algorithm is relatively easy to decode, making it suitable for applications that require fast image decompression.

3. Robustness: The EZW algorithm is robust to transmission errors since the decoder can detect and correct errors in the encoded data.

4. Scalability: The EZW algorithm can be used to compress images at different resolutions by changing the resolution of the wavelet decomposition.

Disadvantages:

1. Slow Encoding: The EZW algorithm is computationally expensive and can take a long time to encode large images.

2. Lossy Compression: The EZW algorithm is a lossy compression technique, which means that some information is lost during the compression process.

3. Sensitivity to Noise: The EZW algorithm is sensitive to noise in the image since noise can increase the number of significant coefficients, which increases the amount of data that needs to be encoded.

Example

Let's take an example to illustrate the EZW algorithm. Suppose we have an 8x8 grayscale image with the following pixel values:

27 23 20 17 15 14 15 17
22 18 14 11 10 10 11 13
19 14 10 7 6 6 7 9
16 11 7 4 3 3 4 6
14 10 6 3 2 2 3 5
13 9 6 3 2 2 3 5
14 10 7 4 3 3 4 6
16 12 9 6 5 5 6 8

Step 1: Wavelet Transform

The image is first decomposed into its wavelet coefficients using a 2-level wavelet transform. The resulting wavelet coefficients are shown below:

9.56  0.13 -0.05  1.77 -0.04 -0.71 -0.19 -1.68
 0.14 -0.08  0.38  0.09 -0.07  0.28  0.01 -0.19
-0.05  0.37 -0.38 -0.02  0.17 -0.10 -0.16  0.12
 1.73  0.10 -0.02  0.50  0.03 -0.05 -0.08  0.04
 0.07 -0.08  0.26  0.05 -0.04  0.12  0.01 -0.07
-0.71  0.27 -0.10 -0.05  0.12 -0.06 -0.10  0.06
-0.19  0.01 -0.16 -0.08  0.01 -0.10 -0.01  0.04
-1.68 -0.19  0.12  0.04 -0.07  0.06  0.04 -0.07

Step 2: Zerotree Coding

The EZW algorithm scans the wavelet coefficients in a specific order and checks whether they are zero or not. For each coefficient, the algorithm checks whether all the coefficients in its immediate neighborhood are also zero. If all the coefficients are zero, the algorithm assigns a significance value of 0 to the coefficient, indicating that it belongs to the zerotree. If the coefficient is not zero and none of its neighbors are zero, the algorithm assigns a significance value of 1 to the coefficient, indicating that it is a significant coefficient.

In our example, the EZW algorithm scans the wavelet coefficients in the following order:

9.56  0.13 -0.05  1.77 -0.04 -0.71 -0.19 -1.68
 0.14 -0.08  0.38  0.09 -0.07  0.28  0.01 -0.19
-0.05  0.37 -0.38 -0.02  0.17 -0.10 -0.16  0.12
 1.73  0.10 -0.02  0.50  0.03 -0.05 -0.08  0.04
 0.07 -0.08  0.26  0.05 -0.04  0.12  0.01 -0.07
-0.71  0.27 -0.10 -0.05  0.12 -0.06 -0.10  0.06
-0.19  0.01 -0.16 -0.08  0.01 -0.10 -0.01  0.04
-1.68 -0.19  0.12  0.04 -0.07  0.06  0.04 -0.07

The algorithm starts at the top-left corner of the wavelet coefficients and moves left to right, top to bottom. The first coefficient it encounters is 9.56, which is a significant coefficient. The algorithm assigns a significance value of 1 to this coefficient.

Next, the algorithm encounters the coefficient 0.13. Since all the coefficients in its immediate neighborhood are not zero, the algorithm assigns a significance value of 1 to this coefficient as well.

The algorithm then encounters the coefficient -0.05. Since all the coefficients in its immediate neighborhood are zero, the algorithm assigns a significance value of 0 to this coefficient, indicating that it belongs to the zerotree.

The algorithm continues scanning the wavelet coefficients in this manner until all coefficients have been assigned a significance value.

Step 3: Sorting by Magnitude and Thresholding

The EZW algorithm sorts the significant coefficients by magnitude and then applies a threshold to the sorted list to select the most significant coefficients for encoding. The threshold is adjusted dynamically based on the available bandwidth or storage.

In our example, the algorithm sorts the significant coefficients as follows:

9.56
1.77
0.37
0.28
0.27
0.26
0.17
0.16
0.14
0.12
0.10
0.09
0.08
0.07
0.06
0.05
0.04
0.04
0.03
0.03
0.02
0.02

Assuming that we have a limited bandwidth and can only transmit the top 10 coefficients, the algorithm selects the top 10 coefficients from the sorted list and encodes them using variable-length coding.

The resulting compressed data for our example image would be:

1 9.56 1 1.77 1 0.37 1 0.28 1 0.27 0.26 0.17 0.16 0.14 0.12 0.10 0.09 0.08 0.07

The compressed data consists of a sequence of (significance, magnitude) pairs. The significance value indicates whether the coefficient is significant or not, while the magnitude value represents the value of the coefficient.

In our example, the compressed data indicates that the coefficients with magnitudes 9.56, 1.77, 0.37, 0.28, 0.27, 0.26, 0.17, 0.16, 0.14, and 0.12 are significant and should be transmitted.

Step 4: Encoding

The EZW algorithm uses variable-length coding to encode the (significance, magnitude) pairs. The variable-length codes are assigned to the pairs based on their frequency of occurrence.

In our example, the algorithm assigns the following variable-length codes to the pairs:

(significance, magnitude) = (1, 9.56)  ->  00
(significance, magnitude) = (1, 1.77)  ->  01
(significance, magnitude) = (1, 0.37)  ->  100
(significance, magnitude) = (1, 0.28)  ->  101
(significance, magnitude) = (1, 0.27)  ->  1100
(significance, magnitude) = (1, 0.26)  ->  1101
(significance, magnitude) = (1, 0.17)  ->  11100
(significance, magnitude) = (1, 0.16)  ->  11101
(significance, magnitude) = (1, 0.14)  ->  11110
(significance, magnitude) = (1, 0.12)  ->  11111

The compressed data is then represented as a sequence of variable-length codes:

0001011001101110010010111110111101110001110100111010

Step 5: Decoding

To decode the compressed data, the EZW algorithm reverses the steps of encoding. It first decodes the variable-length codes to obtain the (significance, magnitude) pairs, then applies the threshold and inverse wavelet transform to reconstruct the image.

The EZW algorithm is capable of achieving high compression ratios while maintaining good image quality. It has been widely used in various image and video compression applications. However, the algorithm is computationally expensive and requires a significant amount of memory to store the wavelet coefficients and intermediate data.

Conclusion

The Embedded Zerotree Wavelet (EZW) algorithm is a powerful technique for image and video compression. It exploits the spatial correlation and frequency-domain redundancy of the wavelet coefficients to achieve high compression ratios. The algorithm operates in a progressive manner, allowing the encoder to transmit data in a scalable fashion.

In this article, we provided a detailed explanation of the EZW algorithm, including its steps and examples. We also discussed the advantages and disadvantages of the algorithm, as well as its various applications. Overall, the EZW algorithm is a useful tool for data compression and can be used in a variety of settings where bandwidth and storage are limited.

       

Advertisements

ads