Modified Fuzzy C-Means for Satellite Image Segmentation

Modified Fuzzy C-Means for Satellite Image Segmentation

Uthai Sangthongpraow, Punya Thitimajshima, and Yuthapong Rangsanseri
Department of Telecommunication Engineering
Faculty of Engineering
King Mongkut's Institute of Technology Ladkrabang
Bangkok 10520
Tel: (667-2)326-9967, Fax: (66-2)326-9086
E-mail: Kryutta@kmitl.ac.th , ktpunya@kmitl.ac.th

Abstract
The purpose of cluster analysis is to partition a data set into a number of disjoint groups or clusters. The members within a cluster are more similar to each other than members from different clusters. The fuzzy c-Means (FCM) clustering is an iterative partitioning method that produces optimal c-partitions. Since the standard FCM algorithm takes a long time to partition a large data set. Because FCM program must read the entire data set into a memory for processing. This paper presents a method to speed up the FCM algorithm by reducing the number of numeric operations performed in each iteration, while keeping the exact result as the standard algorithm. The application of this method to multispectral satellite images has been evaluated, about 40% of time saving was obtained.

Introduction
Satellite image segmentation is often accomplished by clustering when ground truth is not available to provide samples to train a supervised classifier (Richards, 1993). In this technique an image is segmented into unknown classes. It is the task of the user to label those classes afterwards. There is a great number of clustering methods. The fuzzy clustering is one proved to be very well suited to deal with the imprecise nature of geographical information, including remote sensing data. According to the fuzzy clustering framework, each cluster is a fuzzy set, and each pixel in the image has a membership value associated to each cluster, ranging between 0 and 1, measuring how much the pixel belongs to that particular cluster. There have been many different families of fuzzy clustering algorithms proposed in the last decade (Bezdek, 1992). The most popular is the Fuzzy c-Means (FCM) algorithm. The major drawback of this algorithm is the huge execution time due to its iterative nature.

Many research works have been proposed to speed up the FCM algorithm. The AFCM (approximate FCM) (Cannon, 1986) algorithm was achieved by replacing the real value data structures with integer values and used look up techniques where possible to reduce the execution time of each iteration. Two new FCM algorithm were presented in (Kamel, 1994). In the first algorithm the cluster centers are updated as the new membership grade for each sample and computed to produce more rapid convergence, although each iteration requires more computation. In the second algorithm the membership matrix is updated as each cluster center is recomputed.

In this paper, we present a modification on the FCM algorithm that can reduce the execution time in each iteration. While keeping the same number of iterations for convergence. The standard and modified algorithms are compared based on clustering multispectral satellite images.

Fuzzy C-Mean Algorithm
The Fuzzy c-Means (FCM) algorithm (Bezdek, 1984) is an iterative portioning method that produces optimal c-partitions. The method computes the cluster centers and generates the class membership matrix (Zadeh, 1965). An optimal fuzzy c-partition is one that minimizes the generalized least-squared error function:

The weight exponent m has the effect of reducing the square distance error by an amount that depends on the observations membership in the cluster. As m®1 , the partitions that minimize Jm 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 fine step of FCM algorithm is to generate an initial random membership matrix and use this random membership matrix as weight of each sample 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 FCm algorithm can be described as follows:

set value for c,A,m,e, and the loop counter t-1
create a random Nxc membership matrix U
compute each cluster centroid by equation

4. update the membership matrix by equation

where dk_t = ||y_k- vⁱ_t|| A

5. If max {|U_kt ^(t) - U_ki^(t-1)|} > e increment t and go to step 3.

Modified Fuzzy C-Means
From eq.(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 standard algorithm this is computed by performing a pass over the entire data set and membership matrix.

The following describes as improvement to the algorithm whereby the computation of cluster centers is performed in sequence with the membership matrix updating. This effectively eliminates as 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 c*n matrix, P={pi}, and a vector q of length c. The initial values of P and q are taken from the numerator and denominator of eq. (1) when the random membership matrix is created. Now the eq. (1) is replaced by eq. (3):

V_i=p_i/q_i     (3)

Where pi is a vector of length n, and qi 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 compared there is an increment in the numerator of eq. (1), that is an increase in pi of

((u_ki ^(t+1))^m- (u_ki^(t))^m))y_k     (4)

and an increment in the denominator of eq. (1), that is an increase in qi of

(u_ki ^(t+1))^m-(u_ki^(t))       (5)

These increments are accumulated into P and q respectively as the membership matrix is updated. At the beginning of the next the new cluster centers are again computed by eq. (3).

The modified FCM algorithm can be described as follows:

1. set values for c, A, m, e and loop counter t=1
2. create a random Nxc membership matrix U^(t)
3. inititalize data structures P and q using eq. (1)
4. compute c cluster centrers using eq. (3)
5. update the membership matrix using eq.(2) as each membership is computed, increnebt the corresponding element of P and q using eq. (4) and eq. (5)
6. if max {|u_ki ^(t) -u_ki ^(t-1) |}>e increment t and go to step 4.

Experiment Results
The standard and the modified FCm algorithms were implemented using Matlab. The comparison is performed on a PC workstation (Intel Celeron 400 MHz with 64 Mbyte of Rane) by using many multispectral satellite images. Table 1 compares the average execution time used in each iteration when clustering the three band JERS-1/OPS image in Figure 1 (256*256 pixels) into 3,4,and 5 clusters, respectively.

Table 1: Comparison of the standard and modified FCM programs.

Average execution time per iteration (min)
3 clusters		4 clusters		5 clusters
Standard FCM	Modified FCM	Standard FCM	Modified FCM	Standard FCM	Modified FCM
31.84	17.73	37.96	22.47	47.83	31.45

From the table above we cab see that the modified FCM algorithm can decreases the execution time of each iteratiiion in the order of 40%. The input parameters in each case were: m=2, A=1, c=3, and e=0.01. For a 512*512*3 image when partition inti 3 clusters, the standard FCM takes 495.96 minutes in each iteration, whereas the modified FCM algorithm takes 282.4 minutes. We found that in this case the modified algorithm can decrease the execution time in each iteration about 43%.

Conclusion
We have presented a modified Fuzzy algorithm that can reduce the execution time in each iteration to about 40%, comparing to the standard algorithm. This time saving is also gained with the increase of image size to be clustered. The algorithm is therefore useful for satellite image segmentation on low-cost computers.

Acknowledgement
The authors wish to thank the National Research Council of Thailand (NRCT) for providing the satellite image data.

References

Bezdek, J.C., Ehrlich, R., and Full, W., 1984. FCM: the Fuzzy c-Means clustering algorithm. Computers and Geosciences, 10, pp. 191-203.

Bezdek, J.C., and Pal, S.K., 1992. Fuzzy Models for pattern Recognition, IEEE Press.

Cannon, R.L., Dave, J.V., and Bezdek, J.C., 1986. Efficient implementation of the Fuzzy c-Means clustering algorithms. IEEE Trans. Pattern Anal. Mach. Intel., 8(2), pp. 248-255.

Kamel, M.S., and Selim, S.Z., 1994. New algorithms for solving the fuzzy clustering problem. Pattern Recognition, 27(3), pp. 421-428.

Richards, J.A., 1993. Remote sensing digital Image Analysis, Springer-Verlag, Berlin.

Zadeh, L.A. 1965. Fuzzy sets. Information and control, 8, pp. 338-353.