Embedded zerotree wavelets coding based on adaptive fuzzy clustering for image compression

https://doi.org/10.1016/j.imavis.2007.08.019Get rights and content

Abstract

In this paper, a new quantization approach based on an adaptive fuzzy c-means clustering for image compression is presented. The fuzzy cluster theory is applied to quantizing the wavelet coefficients of low-frequency subband after the image has been decomposed by wavelet transform. The method can automatically label the importance degree of coefficients of wavelets, and get new constraints on membership condition by weighted average method of the importance and 1 qk=θk(1)·1+θk(2)·λk,θk(1)+θk(2)=1. Based on this condition, we cluster again. The proof of convergence of the algorithm is given. The experimental results show that exacter reconstructed values of wavelet coefficients can be obtained at low bit-rates, the subjective and objective quality of the reconstructed image is improved. This technique is shown to yield PSNR of reconstructed images improvement from 0.2 dB to 2.8 dB. This paper has brought about some new ideas in combining the fuzzy cluster algorithm with the embedded zerotree wavelets algorithm.

Introduction

Since the introduction of EZW (Embedded Zerotree Wavelets) [1], wavelet image coding technology has advanced significantly. Some of state-of-the-art wavelet coding algorithms include Said and Pearlman’s set partitioning in hierarchical tree (SPIHT) [2], Chrysafis and Ortega’ context entropy coding (C/B) [3], Wu embedded conditional entropy coding of wavelet coefficients (ECECOW) [4], ECECOW with context quantization guided by Fisher discriminant (FD) [5], especially Taubman’s embedded block coding with optimized truncation (EBCOT) [6].

During the past year, many scholars developed refined methods [8], [9], [10], [11], [12], [13], [14], [15], [16]. In [9], John A. Robinson presented a method for still-image compression called adaptive prediction trees. Efficient lossy and lossless compression of photographs, graphics, textual and mixed images was achieved by ordering the data in a multicomponent binary pyramid, applying an empirically optimized nonlinear predictor, exploiting structural redundancies between color components, the coding with hex-trees and adaptive runlength/Huffman coders. The method outperforms standard lossless and lossy alternatives. The competing lossy alternatives used block transforms and wavelets in well-studied configurations. The major result of this paper was that predictive coding is a viable and sometimes preferable alternative to these methods. In [10], Aaron T. Deever examined sign coding in detail in the context of an embedded wavelet image coder. In addition to using intraband wavelet coefficients to be incorporated into the context model, a projection technique is described that allows nonintraband wavelet coefficients to be incorporated into the context model. At the decoder, accumulated sign prediction statistics were also used to derive improved reconstruction estimates for zero-quantized coefficients. These techniques were shown to yield PSNR gain averaging 0.3 dB, and were applicable to any genre of embedded wavelet image code. In [11], Chengjie Tu presented a simple, fast and efficient adaptive block transform image coding algorithm based on a combination of prefiltering, postfiltering, and high-order space-frequency context modeling of block transform coefficients. Despite the simplicity constraints, coding results showed that the proposed coder achieves competitive rate-distortion performance compared to the best wavelet coders in the literature. In [12], Kewu Peng limited the modeling to “pixel classification”, the relationship between wavelet pixels in significance coding. Similarly, the ordering was limited to “pixel sorting”, the coding order of wavelet pixels. They used pixel classification and sorting to provide a better understanding of previous works. The image pixels in wavelet domain were classified and sorted, either explicitly or implicitly, for embedded image compression. A new embedded image code was proposed based on a novel pixel classification and sorting scheme in wavelet domain. In fact, pixels to be coded were classified into several quantized contexts based on a large context template and sorted based on their estimated significance probabilities. The purpose of pixel classification was to exploit the intraband correlation in the wavelet domain. Pixel sorting employed several fractional bit-plane coding passes to improve the rate-distortion performance. The proposed pixel classification and sorting technique was simple, yet effective, producing an embedded image code with excellent compression performance. In addition, their algorithm was able to provide either spatial or quality scalability with flexible complexity.

In this paper, a new method of image compression based on an self-adaptive fuzzy c-means cluster quantization approach is presented. The fuzzy cluster theory is applied to quantizing the wavelet coefficients of low-frequency subband resulting from a wavelet transform. The method can automatically label the importance degree of coefficients of wavelet, and get new constraints on membership function by weighted average method of the importance and 1qk=θk(1)·1+θk(2)·λk,θk(1)+θk(2)=1. Meanwhile, this paper uses Chiu’s method to identify the cluster prototypes, and the proof of global convergence is given. The experimental results show that exacter reconstructed value of wavelet coefficients can be obtained under low bit rates and that the subjective and objective quality of the reconstructed image is improved. This paper has brought about some new ideas in combining the fuzzy cluster algorithm with the embedded zerotree wavelets algorithm.

The following is an outline of this paper: in Section 2 we study fuzzy cluster of wavelet coefficients based on objective function and research into fuzzy c-means clustering of wavelet coefficients. Section 3 provides the experimental results. In Section 4 we present discussion and conclusions. In Appendix A the convergence of the proposed algorithm is proven.

Section snippets

Fuzzy clustering of wavelet coefficients based on an objective function

As for some manipulations to wavelet coefficients such as quantifying and reconstructing, we classify wavelet coefficients according to certain criterions and take the cluster center of every category as reconstructed value of all the members of the category. However, these wavelet coefficients do not have strict properties, and are of certain medi-attributes. By fuzzy clustering, we can get the degree of uncertainty that samples have, and can obtain descriptions of uncertainty that the given

Experimental results

In this paper, we applied the above coding algorithm for 10 grid image, Lena (512 × 512), Goldhill (512 × 512), Barbara (512 × 512), Couple (512 × 512), Girl (512 × 512), Boat (512 × 512), Woman (512 × 512), Harour (512 × 512), Pepper (512 × 512) and Baboon (512 × 512), using Antonini’s 9/7 filter, then quantify wavelet coefficients of the lowest-frequency subband using an adaptive approach of fuzzy c-means cluster, and quantify wavelet coefficients of the high-frequency subband using EZW, then entropy code data

Discussion and conclusions

Applying fuzzy clustering in this paper purposes to classify the coefficients of wavelets of those haven’t been clustered into c categories according certain distances. By solving the prototypes of clusters of each set, we can obtain relatively good reconstructed values of wavelets. However, FCM has its deficiency since it doesn’t take the basic properties of coefficients of wavelets into consideration, and the variety of influence of coefficients caused by the variety of location is more or

References (21)

  • W. Wei et al.

    Optimality tests for the fuzzy c-means algorithm

    Pattern Recogn.

    (1994)
  • N.R. Pal et al.

    Sequential competitive learning and the fuzzy c-means clustering algorithms

    Neural Netw.

    (1996)
  • J.M. Shaprio

    Embedded image coding using zerotrees of wavelet coefficients

    IEEE Trans. Signal Process.

    (1993)
  • A. Said et al.

    New, fast, and efficient image coeffcients based on set partitioning in hierarchical trees

    IEEE Trans. Circuits Syst. Video Technol.

    (1996)
  • C. Chrysafis, A. Ortega, Efficient contex-based entropy coding for lossy wavelet image compression, in: Proceedings of...
  • X. Wu, High-order contex modeing and enbeded conditional entropy coding of wavelet coefficients for image compression,...
  • X. Wu, Context quantization with fisher discriminant for adaptive embedded wavelet image coding, in: Proceedings of...
  • D. Taubman

    High performance scalable image compression with EBCOT

    IEEE Trans. Image Process.

    (2000)
  • Y. Yoo et al.

    Image subbabd coding using context-based classification and adaptive quantization

    IEEE Trans. Image Process.

    (1999)
  • Robinson John A

    Adaptive prediction trees for image compression

    IEEE Trans. Image Process.

    (2006)
There are more references available in the full text version of this article.

Cited by (0)

This work was supported by the NSFC (60775018) and (60505007), the Equipment Advanced Research Project, and the Program for New Century Excellent Talents in University.

View full text