Embedded Zerotree Wavelet Coding: A Review

Embedded Zerotree Wavelet Coding: A Review

Nidhi Jain , K. Mahima, Pooja Ameta

M. Tech Scholars, Department Of Electronics and Communication Shrinathji Institute of Technology and Engineering, Nathdwara

nidhijain745@gmail.com, k.mahima88@gmail.com, Pujaameta21@gmail.com

Abstract – Image compression is very important in many applications, especially for progressive transmission, image browsing and multimedia applications. The whole aim is to obtain the best image quality and yet occupy less space. Embedded zerotree wavelet compression (EZW) is a kind of image compression that can realize this goal. EZW algorithm is fairly general and performs remarkably well with most types of images. Also, it is applicable to transmission over a noisy channel. EZW is computationally very fast and among the best image compression algorithm known today. This paper proposes a technique for image compression which uses the Wavelet-based Image Coding.

Keywords: Image Coding, EZW Coding, Zerotree Wavelet.

1. INTRODUCTION

Image compression is very important for efficient transmission and storage of images. Embedded zero tree wavelet algorithm is a simple yet powerful algorithm having the property that the bits in the stream are generated in the order of their importance. Image compression can improve the performance of the digital systems by educing time and cost in image storage and transmission without significant reduction of the image quality. For image compression it is desirable that the selection of transform should reduce the size of resultant data set as compared to source data set. EZW is computationally very fast and among the best image compression algorithm known today. This is a technique for image compression which uses the wavelet based image coding. A large number of experimental results are shown that this method saves a lot of bits in transmission, further enhances the compression performance. The aim is to determine the best threshold to compress the still image at a particular decomposition level by using embedded zero-tree wavelet encoder. Compression ratio and peak-signal to ratio is determined for different threshold values ranging from 6 to 60 for decomposition level 8.

The basic objective of image compression is to find an image representation in which pixels are less correlated. The two fundamental principles used in image compression are redundancy and irrelevancy. Redundancy removes redundancy from the signal source and irrelevancy omits pixel values which are not noticeable by human eye. It reduces the number of bits needed to represent an image by removing the spatial and spectral redundancies. Image compression is typically comprised of three basic steps. Firstly, the image is transformed into wavelet coefficients which are then quantized in a quantizer and finally threshold which makes the coefficient

smaller than a chosen threshold value (zero) obtained from the quantizer. As a result, some bits are reduced producing an output bit stream[2].

1. ZEROTREE WAVELET CODING

   J. M. Shapiro developed the EZW algorithm in 1993. The EZW encoder was originally designed to operate on images (2D- signals) but it can also be used on other dimensional signals. It 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. Using an embedded coding algorithm, an encoder can terminate the encoding at any point thereby allowing a target rate or target accuracy to be met exactly. The EZW algorithm is based on four key concepts:

   1) a discrete wavelet transform or hierarchical sub band decomposition, 2) prediction of the absence of significant formation across scales by exploiting the self-similarity inherent in images, 3) entropy-coded successive approximation quantization, and 4) universal lossless data compression which is achieved via adaptive Huffman encoding[1]. 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 sub bands decreases as the scale decreases (low scale means high resolution), so the wavelet coefficients will, on average, be smaller in the higher sub bands than in the lower sub bands. This shows that progressive encoding is a very natural choice for compressing wavelet transformed images, since the higher sub bands 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 the 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[3]. The more significant bits of precision of most coefficients are allowed by this transformation to be efficiently encoded as part of exponentially growing zero trees. This transformation is considered to be lossless[5].

   Figure 1 Embedded Zerotree Wavelet Compression Chart

2. CONCEPT OF ZEROTREE WAVELET

   A wavelet transform transforms a signal from the time domain to the joint time-scale domain. i.e. the wavelet coefficients are two-dimensional. To compress the transformed signal not only the coefficient values, but also their position in time has to be coded. When the signal is an image then the position in time is better expressed as the position in space. After wavelet transforming an image it can be represented using trees because of the sub sampling that is performed in the transform. A coefficient in a lower sub band can be thought of as having four descendants in the next higher sub band as shown in Fig.2.1. The four descendants each also have four descendants in the next higher sub band, which gives a quad- tree, with every root having four leafs.

   A zero tree is defined as a quad-tree of which all nodes are equal to or smaller than the root and the root is smaller than the threshold against which the wavelet coefficients are currently being measured, has insignificant wavelet transform values at each of its locations.

   Figure 2 Quad Tree Structure

   Zerotrees can provide very compact descriptions of the locations of insignificant values because it is only necessary to encode one symbol, R say, to mark the root location. The decoder can infer that all other locations in the zerotree have insignificant values, so their locations are not encoded.. The tree is coded with a single symbol and reconstructed by the decoder as a quad-tree filled with zeroes. The EZW encoder codes the zero tree based on the observation that wavelet coefficients decrease with scale. In a zero tree all the coefficients are smaller than the threshold if the root is smaller than this threshold. Under this case the whole tree can be coded with a single zero tree (T) symbol.

   Figure 3 Examples of spatial coefficient trees corresponding to different wavelet packet transforms. (a) Wavelet transform. (b) An arbitrary wavelet packet transform. (c) Full subband transform. Arrows identify the parent-child dependencies.

3. CONCLUSION

   The Embedded Zero-tree Wavelet coding scheme was implemented. The effect of using different Wavelet transforms, using different block sizes and different bit rates were studied. This approach utilizes zero tree structure of wavelet coefficients at decomposition level 8 is very effectively, which results in higher compression ratio and better PSNR. The algorithm is tested on different images, and it is seen that the results obtained by Image encoded using EZW algorithm is better than other methods. Firstly, original image is applied to the compression program, EZW encoded image is obtained. To reconstruct compressed image, compressed image is applied to decompression program, by which EZW decoded image is obtained.

4. REFERENCE

1. Rafael C. Gonzalez, Richared E. Woods, Steven L. Eddins, Digital Image Processing Using MATLAB, 2008, Pearson Education

2. Majid Rabbani, Paul W. Jones, Digital Image Compression techniques,

   Jan 1991, SPIE Press

3. Shapiro J. M., Embedded Image Coding Using Zerotrees of Wavelet Cefficients, IEEE Transactions on Signal Processing, 41, No. 12 (1993), p. 3445-3462.

4. Rehna V.J., Jaya Kumar M.K., Wavelet Based Image Coding Schemes, International Journal of Computer Science & Communication, Vol. 3,

   No. 3, August 2012

5. Priyanka Singh, Priti Singh, Design & Implementation of EZW and SPIHT Image Coder for Virtual Images, IJCSI, vol. 5, Issue5, 2011.

6. Rehna V.J., Jaya Kumar M.K., Wavelet Based Image Coding Schemes, International Journal of Computer Science & Communication, Vol. 3,

   No. 3, August 2012

7. Neyre Tekbiyik, Hakan Sevkitozko, Embedded Zerotree Wavelet Compression, June 2005