Digital Signal Processing Reference
In-Depth Information
Image Compression Based on Hierarchical Clustering
Vector Quantization
*
Shi Wang, Long Ye, Wei Zhong, and Qin Zhang
Key Lab of Media Audio & Video of Ministry of Education,
Communication University of China, Beijing 100024, China
hfwangshi168@126.com, {yelong,wzhong,zhangqin}@cuc.edu.cn
Abstract.
Vector quantization (VQ) is an efficient tool for lossy compression
due to its simple decoding algorithm and high compression rate. The key tech-
nique of VQ is the codebook design. In this paper, based on fuzzy c-means
clustering algorithm, we firstly generate the initial classified codebooks accord-
ing to the image features of different blocks. And then the proper codebooks are
selected by adjusting the PSNR thresholds which are based on the quality of the
reconstructed image. Since the proposed hierarchical clustering VQ framework
is more adaptable to the specific regions of an image, we can reconstruct the
different regions of the image hierarchically. Experimental results show that the
proposed coding framework can achieve satisfactory quality measured by
PSNR while reducing the codebook size significantly.
Keywords:
vector quantization, hierarchical clustering, image compression,
fuzzy c-means.
1
Introduction
Vector quantization (VQ) is an important technology for image compression to gener-
ate a significant codebook which can represent the large amounts of image data [1].
The process of the codebook generation can be regarded as a data clustering process.
Training vectors are classified into the specific codebook which contains much small-
er size of codewords based on the minimization of average distortion between the
training vectors and codebook vectors. The size of the codebook is much less than
that of original image data, and thus the purpose of higher image compression rate is
definitely achieved.
VQ consists of three parts, codebook design, encoding and decoding. The most
important technique of a VQ algorithm is the codebook generation. In 1980 based on
a training sequence, an iterative design algorithm was proposed by Linde, Buzo and
Gray (LBG) [2] to generate a locally optimal codebook. Although this LBG algorithm
has a solid theoretical foundation and its implementation is simple, it is very sensitive
to the initial codebook and thus easy to fall into local optimum. In recent years, there
*
This work is supported by the National Natural Science Foundation of China under grant Nos.
60832004 and 61101166.
