Comparison between WDR & ASWDR Techniques using Image Compression with Different Wavelet

Comparison between WDR & ASWDR Techniques using Image Compression with Different Wavelet

Abstract In this paper, two different Wavelet based Image Compression techniques are compared. The techniques involved in the comparison process are WDR and ASWDR. The above two techniques are implemented with different types of wavelet codecs. Wavelet difference reduction (WDR) has recently been proposed as a method for efficient embedded image coding. This method retains all of the important features like low complexity, region of interest, embeddedness, and progressive SNR. ASWDR adapts the scanning procedure used by WDR in order to predict locations of significant transform values at half thresholds. Here, there are two types of Wavelet transforms are applied on the images before compression. They are DD 2+2,2 Integer Wavelet transform and Daub 9/7 Wavelet transform. The quality of the reconstructed images is calculated by using three performance parameters PSNR, MSE and SNE values. The images yield high PSNR values and low MSE values.

KeywordsWavelet Image Compression, WDR, ASWDR

1. INTRODUCTION

   Image compression has been the key technology for transmitting massive amount of real-time image data via limited bandwidth channels [4]. The data are in the form of graphics, audio, video and image. These types of data have to be compressed during the transmission process. Some of the compression algorithms are used in the earlier days [2] and [3] and it was one of the first to be proposed using wavelet methods [1]. Wavelet transforms have been widely studied over the last decade [7]. For still images the widely used coding algorithms based on wavelet transform include the embedded zero-tree wavelet (EZW) algorithm [5], the set partitioning in hierarchical trees (SPIHT) algorithm [6] and the wavelet difference reduction (WDR) algorithm [10, 11]. The SPIHT algorithm improves upon the EZW concept by replacing the raster scan with a number of sorted lists that contain sets of coefficients (i.e., zero-trees) and individual co- efficients. Already the results are compared and it is identified that WDR provides better results [14, 15].

   1. Motivation and Justification

      For a given compression algorithm, the choice of wavelet filter used can make a significant difference in performance. The Haar and Daubechies 8 filters have been mentioned earlier. The Antonini 9/7 filter has become nearly ubiquitous for compression with biorthogonal wavelets. It represents a good trade-off between filter length (and thus run-time of the

      wavelet transform) and PSNR; it also tends to have visually pleasing smoothing of quantization error. In this section, two wavelets are selected and it is applied to the various images. The wavelets are DD 2+2,2 Integer and Daub 9/7 wavelet transform.

   2. Outline of the Approach

   The WDR algorithm combines run-length coding of the significance map with an efficient representation of the run- length symbols to produce an embedded image coder. In both SPIHT and WDR techniques, the zerotree data structure is precluded, but the embedding principles of lossless bit plane coding and set partitioning are preserved. In the WDR algorithm, instead of employing the zerotrees, each coefficient in a decomposed wavelet pyramid is assigned a linear position index. The output of the WDR encoding can be arithmetically compressed [8, 9]. The method that they describe is based on the elementary arithmetic coding algorithm described in [12]. One of the most recent image compression algorithms is the Adaptively Scanned Wavelet Difference Reduction (ASWDR) algorithm of Walker [13]. The adjective adaptively scanned refers to the fact that this algorithm modifies the scanning order used by WDR in order to achieve better performance.

   Fig. 1 WDR / ASWDR Compression & Decompression System

   The process of WDR and ASWDR compression and Decompression system is shown in Fig. 1. The rest of the paper is organized as follows. The WDR algorithm is briefly discussed in Section II. The ASWDR algorithm is briefly presented in Section III. Experimental results are discussed in Section IV. In Section V, the performance evaluation of the two algorithms is discussed. Finally, conclusion is discussed in Section VI.

2. WDR ALGORITHM

   One of the defects of SPIHT is that it only implicitly locates the position of significant coefficients. This makes it difficult to perform operations, such as region selection on compressed data, which depend on the exact position of significant transform values. By region selection, also known as region of interest (ROI), which means selecting a portion of a compressed image, which requires increased resolution. Such compressed data operations are possible with the Wavelet Difference Reduction (WDR) algorithm of Tian and Wells [10, 11]. The term difference reduction refers to the way in which WDR encodes the locations of significant wavelet transform values. In WDR, the output from the significance pass consists of the signs of significant values along with sequences of bits which concisely describe the precise locations of significant values.

   1. WDR Algorithm

      The WDR algorithm is a very simple procedure. A wavelet transform is first applied to the image, and then the bit-plane based WDR encoding algorithm for the wavelet coefficients is carried out. WDR mainly consists of five steps as follows:

      1. Initialization: During this step an assignment of a scan order should first be made. For an image with P pixels, a scan order is a one-to-one and onto mapping = Xk , for k =1,2,…, P between the wavelet coefficient () and a linear ordering (Xk). The scan order is a zigzag through sub bands from higher to lower levels. For coefficients in sub bands, row-based scanning is used in the horizontal sub bands, column based scanning is used in the vertical sub bands, and zigzag scanning is used for the diagonal and low- pass sub bands. As the scanning order is made, an initial threshold T0 is chosen so that all the transform values satisfy

         |Xm|< T0 and at least one transform value satisfies |Xm|>= T0

         / 2.

      2. Update threshold: Let Tk=Tk-1 / 2.

      3. Significance pass: In this part, transform values are deemed significant if they are greater than or equal to the threshold value. Then their index values are encoded using the difference reduction method of Tian and Wells [4]. The difference reduction method essentially consists of a binary encoding of the number of steps to go from the index of the last significant value to the index of the current significant value. The output from the significance pass includes the signs of significant values along with sequences of bits, generated by difference reduction, which describes the precise locations of significant values.

      4. Refinement pass: The refinement pass is to generate the refined bits via the standard bit-plane quantization procedure like the refinement process in SPHIT method [3]. Each refined value is a better approximation of an exact transform value.

      5. Repeat steps (2) through 4) until the bit budget is reached.

3. ASWDR ALGORITHM

   One of the most recent image compression algorithms is the Adaptively Scanned Wavelet Difference Reduction (ASWDR) algorithm of Walker [16]. ASWDR adapts the

   scanning order so as to predict locations of new significant values. If a prediction is correct, then the output specifying that location will just be the sign of the new significant value the reduced binary expansion of the number of steps will be empty. Therefore a good prediction scheme will significantly reduce the coding output of WDR. The scanning order of ASWDR dynamically adapts to the locations of edge details in an image, and this enhances the resolution of these edges in ASWDR compressed images.

   1. ASWDR Algorithm

      The ASWDR algorithm is a simple modification of the WDR algorithm ([l], [5]). Here is a 7-step procedure for performing ASWDR on a grey-scale image:

      Step 1: Perform a wavelet transform of the image. We used a 7-level Daub 9/7 transform.

      Step 2: Choose a scanning order for the transformed image, whereby the transform values are scanned via a linear ordering, say

      x[1], x[2]..x[M]

      where M is the number of pixels. In [1] and [5], the scanning order is a zig-zag through subbands from lower to higher [6]. Row-based scanning is used in the low-pass high-pass subbands and column-based scanning is used in the high- pass/low-pass subbands.

      Step 3: Choose an initial threshold, T, such that at least one transform value has magnitude less than or equal to T and all transform values have magnitudes less than 2T.

      Step 4: (Significance pass). Record positions for new significant values: new indices m for which |x[m]| is greater than or equal to the present threshold. Encode these new significant indices using difference reduction ([1], [5]).

      Step 5: (Refinement pass). Record refinement bits for significant transform values determined using larger threshold values. This generation of refinement bits is the standard bit-plane encoding used in embedded codecs ([6], [2]).

      Step 6: (New scan order). Run through the significant values at level j in the wavelet transform. Each significant value, called a parent value, induces a set of child values-four child values for all levels except the last, and three child values for the last described in the quad-tree definition in [2]. The first part of the scan order at level j – 1 contains the insignificant values lying among these child values. Run through the insignificant values at level j in the wavelet transform. The second part of the scan order at level j – 1 contains the insignificant values, at least one of whose siblings is significant, lying among the child values induced by these insignificant parent values. The third part of the scan order at level j – 1 contains the insignificant values, none of whose siblings are significant, lying among the child values induced by these insignificant parent values. Although this description is phrased as a three-pass process through the

      level j subband, it can be performed in one pass by linking together three separate chains at the end of the one pass.) Step 7: Divide the present threshold by 2. Repeat Steps 4-6 until either a bit budget is exhausted or a distortion metric is satisfied.

4. EXPERIMENTS

1. Images used in the Experiments

   The images Lena, Baboon, Cameraman and Boat are used for the experiments. The original images are shown in Fig. 2. The results of experiments are used to find the PSNR (Peak Signal to Noise Ratio) values, MSE (Mean Square Error) and SNE (Sub-Norm Error) values from the reconstructed images.

   Fig. 2 Input Images: Lena, Cameraman, Baboon and Boat

2. Performance of WDR with difference Wavelet Codes

   WDR employs similar encoding stages to SPIHT. It also conducts a sorting pass and a refinement pass for each bit plane. Fig. 3 and Fig. 4 show the results that are got by using the WDR technique with DD 2+2,2 & Daub 9/7 Wavelet transforms.

   Fig. 3 WDR Compression of Lena, Cameraman, Baboon & Boat image with DD 2+2,2 Wavelet Transform

   Fig. 4 WDR Compression of Lena, Cameraman, Baboon & Boat image with Daub 9/7 Wavelet Transform

3. Performance of ASWDR with difference Wavelet Codes

The main features of ASWDR are modified scanning order compared to WDR and prediction of locations of new significant values. Fig. 5 and Fig. 6 show the results that are got by using the ASWDR technique with DD 2+2,2 & Daub 9/7 Wavelet transforms.

Fig. 6 ASWDR Compression of Lena, Cameraman, Baboon & Boat image with Daub 9/7 Wavelet Transform

The above two techniques are implemented and the results are shown in the above figures. The PSNR, MSE and SNE values for the images compressed by the two techniques by using different wavelet transforms are tabulated in Table 1, Table 2 and Table 3. The PSNR and MSE values are calculated by using the following formula

TABLE I

PSNR VALUES FOR WDR & ASWDR COMPRESSION WITH DD 2+2,2 WAVELET TRANSFORM AND DAUB

9/7 WAVELET TRANSFORM

TABLE II

MSE VALUES FOR WDR & ASWDR COMPRESSION WITH DD 2+2,2 WAVELET TRANSFORM AND

DAUB 9/7 WAVELET TRANSFORM

TABLE III

SNE VALUES FOR WDR & ASWDR COMPRESSION WITH DD 2+2,2 WAVELET

TRANSFORM AND DAUB 9/7 WAVELET TRANSFORM

The comparison of WDR and ASWDR by using PSNR, MSE and SNE are shown in Fig. 7, Fig. 8 and Fig. 9

Fig. 7 Comparison of WDR & ASWDR with DD 2+2,2 Wavelet Transform and Daub 9/7 Wavelet Transform by using PSNR values

Fig. 8 Comparison of WDR & ASWDR with DD 2+2,2 Wavelet Transform and Daub 9/7 Wavelet Transform by using MSE values

VI. CONCLUSION

In this paper, the results were compared for the different wavelet-based image compression techniques. The effects of different wavelet functions, filter orders, number of decompositions, image contents and compression ratios were examined. The results of the above two techniques WDR & ASWDR were compared by using the parameters such as PSNR, MSE and SNE values from the reconstructed image. These techniques are successfully tested in many images.

The experimental results show that the ASWDR technique performs better than the WDR method in terms of the performance parameters and coding time with acceptable image quality, and is an alternative to the SPIHT method due to its low complexity. From the experimental results, it is identified that the PSNR values from the reconstructed images by using ASWDR compression is higher than WDR compression. And also it is shown that the MSE values from the reconstructed images by using ASWDR compression are lower than WDR compression. Finally, it is identified that ASWDR compression performs better when compare to WDR compression.

REFERENCES

1. M. Antonini, M. Barlaud, P. Mathieu, I. Daubechies. Image coding using wavelet transform. IEEE Trans. Image Proc., Vol. 5,

2. G.M. Davis, A. Nosratinia. Wavelet-based Image Coding: An Overview. Applied and Computational Control, Signals and Circuits, Vol. 1, No. 1, 1998. No. 1, pp. 205-220, 1992.

3. S. Mallat. A Wavelet Tour of Signal Processing. Academic Press, New York, NY, 1998.

4. S. Negahdaripour, A. Khamene. Motion-based compression of underwater video imagery for operations of unmanned submersible vehicles, Computer Vision and Image Understanding, 2000, 79(1), pp. 162-183.

5. A. Said, W.A. Pearlman. Image compression using the spatial- orientation tree. IEEE Int. Symp. on Circuits and Systems, Chicago, IL, pp. 279-282, 1993.

6. A. Said, W.A. Pearlman. A new, fast, and efficient image codec based on set partitioning in hierarchical trees. IEEE Trans. on Circuits and Systems for Video Technology, Vol. 6, No. 3, pp. 243- 250, 1996.

7. G. Strang, T. Nguyen, Wavelet and Filter Banks, Wellesley- Cambrige Press, Boston, 1996.

8. J. Tian, R.O. Wells, Jr. A lossy image codec based on index coding. IEEE Data Compression Conference, DCC 96, page 456, 1996.

9. J. Tian, R.O. Wells, Jr. Image data processing in the compressed wavelet domain. 3rd International Conference on Signal Processing Proc., B. Yuan and X. Tang, Eds., pp. 978{981, Beijing, China, 1996.

10. J. Tian, R.O. Wells. A lossy image codec based in index coding, IEEE Data Compression Conference, DCC96, 1996, pp.456.

11. J.S. Walker, T.O. Nguyen. Adaptive scanning methods for wavelet difference reduction in lossy image compression, Proceedings of IEEE International Conference on Image Processing, vol.3, 2000, pp. 182-185.

12. I. Witten, R. Neal, J. Cleary. Arithmetic coding for data compression. Comm. of the ACM, Vol. 30, No. 6, pp. 1278{1288, 1986.

13. J.S. Walker, T.O. Nguyen. Adaptive scanning methods for wavelet difference reduction in lossy image compression, Proceedings of IEEE International Conference on Image Processing, vol.3, 2000, pp. 182-185.

14. S.P.Raja, Dr.A.Suruliandi. Analysis of Efficient Wavelet based image compression techniques, ICCCNT 2010, pp 1-6.

15. S.P.Raja, Dr.A.Suruliandi. Performance evaluation on EZW & WDR image compression techniques, ICCCCT 2010, pp 661-664.