Keywords: Image Compression, Vector Quantization, FCM
Abstract: Image compression is the process of reducing the number of bits required to represent an image. Vector Quantization method (VQ) is a method to deal with this operation. With this method a set of data points is encoded by a reduced set of reference vectors (the codebook). VQ is useful in compressing data that arises in wide range applications and it can achieve better compression performance than any conventional coding techniques which based on the encoding of scalar quantities. This paper presents a multispectral image compression method using Vector Quantization technique based on Fuzzy c-Means (FCM). In this method we first use FCM algorithm to generate a good initial codebook. A modified version of FCM is used to reduce the computational time. Experimental results are shown to illustrate the performance of the proposed method.
1. Introduction
Image Compression is a process of reducing the number of bits required to represent an image. There are several methods to compress an image data. One popular method is Vector Quantization (VQ). VQ was used for compressing data in wide range applications, including image processing (Gray, 1984), (Nasrabadi, 1988), speech processing (Makhoul, 1985), facsimile transmission (Netravali, 1980) and weather satellites (Elachi, 1987). In this method the training vectors in the image are encoded by a reduced set of reference vectors (the codebook). From rate distortion theory, it can be shown that VQ can achieve better compression performance than any conventional coding technique which based on the encoding of scalar quantities (Gray, 1984). The objective of VQ is to design the codebook. An optimum VQ system is that one uses a codebook that yields the least average distortion of the reconstructed image. Other methods for designing codebooks have been proposed in (Linde, 1980), (Hsieh, 1992), (Hsieh, 1991), (Wu, 1994). The most popular one is the LBG algorithm (Linde, 1980). In this paper we use FCM to design the codebook in Vector Quantization process. The major problem of this method is the huge execution time in the FCM process. So, this paper will also present the modification on the FCM algorithm that can reduce the execution time in each iteration.
2. Fuzzy C-Means Clustering Technique
The fuzzy c-means (FCM) algorithm (Bezdek, 1984) is an iterative clustering method that used to partition a data set. The objective of FCM segmentation is to compute the cluster centers and generate the class membership matrix (Zadeh, 1965). This class membership matrix is a cxN matrix, where c is the number of groups and N is the number of samples of image in n-space. Each column of the class membership matrix is the distribution of the class attribute of its corresponding sample. Each row of the class membership matrix is the membership value of each sample to be a member of that particular cluster.
An optimal fuzzy c-partition is one that minimizes the generalized least-squared errors function. We can explain the fuzzy clustering by the following equation.
Minimize: Jm (U,v) = 
Where : Y = {y1, y2, y3, …, yN}
Ì R
n is the data set,
c is the number of clusters in Y: 2
£ c < n,
m is a weighting exponent: 1
£ m <
¥,
U = {u
ki} is the fuzzy c-partition of Y,
||y
k-v
i||A is an induced a-norm on R
n, and,
A is a positive-definite (nxn) weight matrix.
The weighting exponent m has the effect of reducing the squared distance error by an amount that depends on the observation's membership in the cluster. As m
® 1 , the partitions that minimize J
m become increasingly hard. Conversely, higher values of m tend to soften a samples cluster membership, and the partition becomes increasingly blurred. Generally m must be selected by experimental means.
The first step of FCM algorithm is generate an initial random membership matrix and use this random membership matrix as weight of each samples to belong to each cluster. Then computes the centroid of each cluster. The new cluster centers are used to update the membership matrix. The updated membership matrix is compared with the previous ones. If the difference is greater than some threshold, then another iteration is computed, otherwise the algorithm is stopped. The algorithm is shown below. The notation x
(t) signifies the value of variable x at iteration t.
The FCM Algorithm
1. set value for c, A, m,
e, and the loop counter t = 1
2. create a random Nxc membership matrix U
3. compute each cluster centroid by equation
4. update the membership matrix by equation
where
5. If max
increment t and go to step 3.
