Multispectral Image Compression using FCM-Based Vector Quantization
3. The Modified Fuzzy C-Means Algorithm
From equation (1) we can find that each cluster center vi is computed as the weighted average of samples in the data set Y. The weight used for each sample is that sample's membership in the ith cluster. In the original algorithm this is computed by performing a pass over the entire data set and membership matrix.
The following describes an improvement to the algorithm whereby the computation of cluster centers is performed in sequence with the membership matrix updating. This effectively eliminates an entire pass of the data set. The outcome is not a decrease in the number of iterations required for convergence, but decrease in the time of each iteration.
We maintain two extra data structures, a cxn matrix, P = {pi}, and a vector q of length c. We can obtain these two matrix from the first iteration when the random membership matrix is created. If we represent the numerator and denominator of equation (1) by P and q, respectively, then keep them as initial values. So now the equation (1) is replaced by equation (3)
where pi is a vector of length n, and q.i is a scalar. The dot-i subscript is used to avoid confusion between vectors and scalars.
Each time an element uki of the membership matrix is computed there is an increment in the numerator of equation (1), that is an increase in pi of
And an increment in the denominator of equation (1), that is, an increase in q.i of
These increments are accumulated into P and q respectively as the membership matrix is updated. At the beginning of the next iteration the new cluster centers are again computed by equation (3).
The Modified FCM algorithm
1. set values for c, A, m, e, and loop counter t=1
2. create a random Nxc membership matrix U(t)
3. initialize data structures P and q using equation (1)
4. compute c cluster centers using equation (3)
5. update the membership matrix using equation (2) as each membership is computed, increment the corresponding element of P and q using equation (4) and equation (5)
6. if max
increment t and go to step 4.
4. FCM-Based Vector Quantization
In this paper, FCM process is used to calculate the reference vector or average vector from each cluster. The output of this process is a membership matrix and a set of reference vectors that used to design the vector quantization codebook. The training vector will be encoded with this codebook. The algorithm of this compression method is shown in Figure 1.
Figure 1:
Figure 1: Block diagram of the proposed method.
The evaluation was performed by using the following measures:
5. Experimental Results
The proposed image compression algorithm was implemented using Matlab. Several multispectral images were used in experimental. Table 1 shows the experimental results when applied to a three-band (24 bits) image, size of 256x256 pixels. The input image size is 196 Kbyte. The experiments were carried out with the number of clusters of 4, 16 and 64.
Table 1: Experimental results.
| Number of clusters |
bpp |
PSNR (dB) |
MSE |
| 4 |
2.0016 |
22.0651 |
404.1790 |
| 16 |
4.068 |
27.4127 |
117.9196 |
| 64 |
6.0293
| 31.2498
| 48.7638
|
6. Conclusion
The experimental result shown that the proposed method can compress the multispectral image data. The compressibility of this method and the image distortion from quantizing process depends on the number of clusters used in FCM process. The major problem of this method is the execution time spent in clustering process caused by the computation complexity of FCM algorithm even we use the modified version of FCM.
References
- Bezdek, J.C., Ehrlich, R., and Full, W., 1984. FCM : The fuzzy c-means clustering algorithm. Computers and Geosciences, 10, pp. 191-203.
- Elachi, C., 1987. Introduction to The Physics of Remote Sensing. Intersciences, New York.
-
Gray, R.M., 1984. Vector quantization. IEEE ASSP Magazine, 1(2), pp. 4-29.
- Hsieh, C.H., 1992. DCT based codebook design for vector quantization of images. IEEE Trans. Circuits and Systems, 2, pp. 40-1-409.
- Hsieh, C.H., Lu. P.C. and Chung. J.C., 1991. Fast codebook generation algorithm for vector quantization of images. Pattern Recogn. Lett., 12, pp. 605-609.
- Linde, Y., Buzo, A. and Gray, R.M., 1980. An algorithm for vector quantization design. IEEE Trans. Commun., 28, pp. 84-95.
- Makhoul, J., Roucos, S. and Gish, H., 1985. Vector quantization in speech coding, Proc. IEEE, 73(11), pp. 1551-1588.
- Nasrabadi, N. and King, R.A., 1988. Image coding using vector quantization: A review. IEEE Trans. Commun., 36(8), pp. 957-971.
- Netravali, A.N. and Mounts F.W., 1980. Ordering techniques for facsimile coding: A review. Proc. IEEE, 68, pp. 796-807.
- Wu, X. and Guan, L., 1994. Acceleration of the LBG algorithm. IEEE Trans. Commun., 42, pp. 1518-1523.
- Zadeh, L.A, 1965. Fuzzy sets. Information and Control, 8, pp. 338-353.
