Center for Remote Imaging, Sensing and Processing
The National University of Singapore
Blk S17, Lower Kent Ridge Road, 119260, Singapore
Tel: (65)8744322, Fax: (65)7757717
Keywords: Multi-temporal SAR images, InSAR coherence image, Classification, Fuzzy c-mean clustering, Possibility c-mean clustering, Simulated annealing, Adaptive neighborhood model
A classification algorithm for multi-temporal SAR images and InSAR coherence images is developed. This is done by minimizing an energy function which is defined by the sum of (1) the difference between the pixel value and the cluster center (mean value of a class) and (2) the difference between the pixel label (class) and its neighborhood. The global minimization of the energy function of the whole image is achieved by a simulated annealing approach. The cluster centers for different classes are calculated using fuzzy c-mean and possibility c-mean algorithms or determined manually from the image values. In order to preserve the details of the original images, a neighborhood structure with a 5*1 window is used to calculate the energy function, whose orientation is determined by the local homogeneity (e.g. the variance of the pixel values within the window) of the original images. This algorithm is used to classify three ERS-2 SAR images over the Mekong delta region, Vietnam. By comparing visually the color composite SAR images and the classified image, it is shown that the classification result is reasonable. Moreover, this algorithm is also used to classify an InSAR coherence image acquired from two JERS SAR images over south Sumatra, Indonesia. The classified InSAR coherence image delineates the bare land and forest clearly, since the coherence of bare land is larger than that of forest.
Multi-temporal ERS-1/2 synthetic aperture radar (SAR) images show not only the radar backscattering properties of objects within one image but also the time evolution of radar backscattering. Interferometric SAR (InSAR) images generated from two repeat-pass single-complex SAR images give coherence properties of radar backscattering between the two SAR images. The information contained in multi-temporal SAR images and InSAR coherence images has been used successfully to monitor forest cover and rice fields (Liew, et. al, 1998). Classification of objects is an important step in many applications. This is carried out by (1) determining the cluster statistical characteristics of different classes, e. g., the mean value of classes; (2) classifying every pixel according to the clustering result and other conditions, for example, smooth homogeneous regions and at the same time preservation of the fine structural details. It often happens for SAR images that mixed-up classes occur within a homogeneous region due to noise. The preservation of fine structures is often required when utilizing SAR data for cartography, urban planning, and analysis of agricultural sites, especially, detecting roads.
In this paper we apply fuzzy c-mean (FCM) and possibility c-mean (PCM) clustering algorithms to cluster images (Cherkassky and Mulier, 1998; Wong and Posner, 1993). The results of these two algorithms are compared. Then, we use a classification algorithm which is based on the adaptive neighborhood model (Garzelli, 1999) and the simulated annealing technique (Hegarat-Mascle and Vidal-Madjar, 1996), to obtain smooth homogeneous regions but preserve fine structures.
The goal of clustering is to partition an image set into a small number of groups or representative clusters. The fuzzy c-mean clustering algorithm seeks to find fuzzy partitioning by minimizing the following loss function:
where xi denotes the data vector (i=1, . . . ,n), n the total number of pixels, cj the center of a fuzzy cluster (j=1, . . . ,m), m the number of fuzzy clusters assumed to be known, µj(xi) the fuzzy membership of xi to cluster j. The parameter b>1 is a fixed value specified a priori. Typically b is chosen around 2. The necessary conditions for an optimal solution are
Performing differentiation and applying the constraint
Here dji denotes the Euclidean distance between the data vector and the cluster center.
The system of nonlinear equations can be solved by an iterative process, which is known as the FCM algorithm
1) Set number of clusters m and parameter b
2) Initialize cluster centers cj
Update membership values µ j(xi) via (4) using current estimates of cj and update cluster centers cj via (5) using current estimates of µ j(xi) until the membership values stabilize;
In FCM algorithm the noise and outliers in the data set create many spurious local minima and distort the solution that corresponds to the global minimum. Thus, a possibility c-mean (PCM) clustering algorithm was proposed by adding a term to the loss function
where nj denotes suitable positive numbers. Similar to the FCM algorithm the optimal solution can be achieved by iteration, using
This is done by alternating between the estimation of the cluster membership values (for the given values of cluster centers) and the estimation of the cluster centers (for the given membership values).
3. Classification Algorithm
Once the cluster centers have been estimated, the whole image set is classified by assigning labels to every pixel. The label, l=1, . . . m, is an integer value and represents classes. If the classification is carried out according to only the condition that the Euclidean distance between the data vector and the cluster center reaches a minimum, some regions appear somewhat mottled, with isolated pixels of one class embedded within larger regions of another class, i.e., mixed-up classes. Generally, one expects neighboring pixels to belong to the same class unless there is a true border between regions. Thus, we assume the field of labels is a Markov Random Field (MRF): the probability of a pixel to be labeled k knowing the labels of all other pixels in the image is equal to the probability of a pixel to be labeled k knowing the labels of its neighbors. The classification is realized by minimizing an energy function. It consists of its own energy U1 and energy U2 related to its neighborhood N. For each pixel, i, U1 and U2 are defined as
where ß is a weighting factor ( ß³0) and d is the Kroeneker symbol:
and N represents the neighborhood structure. Usually, the number of pixels within a neighborhood structure is predefined. The shape, in contrast, is not fixed, but is adapted to data. Here, the neighborhood structure is a 5*1 window with different orientations (shown in Fig. 1). One of the neighborhood structures is selected on which the variance of the data has the minimum value. Thus, by using the adaptive windows we take into account the local homogeneity and improve the detail preservation.
A classification is optimal if the global energy E over the whole image
is minimum. Global minimization is achieved by a simulated annealing approach.
Fig. 1 Neighborhood structures for classification algorithm
4. Simulated Annealing Algorithm
The concept of simulated annealing (SA) is based on an analogy between the thermodynamic behavior of solids and large combinatorial optimization. The basic procedure involves a cooling procedure, in which a þ temperature þ parameter starts out high and is gradually lowered until the system is þ frozen þ (in a state of minimal energy). In the simulated annealing algorithm, not only are state changes accepted which decrease energy, but also some state changes are accepted which increase energy with a defined probability. However, the lower the temperature, the less likely is any significant energy increase.
Simulated Annealing algorithm is implemented as follows
1) Choose initial temperature T0, assign the class label to every pixels randomly
For each pixel, change randomly its label from class i to class j,
Compute DUij=Ei-Ej and accept the change,
when DUij 0, or, with a probability exp (-DUij/T), when DUij>0,