300.

[Cover] [Contents] [Index]

Page 69

2.3.1.1 The basic algorithm

The basic migrating means clustering algorithm, often called the ISODATA algorithm (Ball and Hall, 1967), has been widely used for automatic image segmentation for many years. In the remote sensing field, ISODATA is the most generally used method of unsupervised pattern recognition. This algorithm is implemented by recursively migrating a set of cluster means (centres) using a ‘closest distance to mean’ approach until the locations of the cluster means are unchanged, or until the change from one iteration to the next is less than some predefined threshold. Change may also be defined in terms of the number of pixels moving from one cluster to another between iterations, or by the value of a measure of cluster compactness, such as the sum of squares of the deviations of each pixel from the centre of its cluster, summed for all classes.

The user of the ISODATA algorithm must estimate the initial number of clusters, say n, present in the data. The algorithm initially determines the location of n cluster means within the feature space, either by generating random feature vectors, or by selecting n pixels at random from the available data, or by using a predefined set of feature vectors. Each pixel is then associated with its nearest cluster centre. ‘Nearest’ is defined either by the Euclidean or Mahalanobis distance measure. At the next stage, the location of each cluster mean is recalculated based on the set of pixels allocated to that centre. The process is repeated until the change between iterations becomes less than a user-specified threshold. Figure 2.5 illustrates the process.

The calculation of the distance between a pixel and a cluster centre normally uses the Euclidean measure D_E represented by:

Figure 2.5 Algorithm for migrating mean clustering process.

[Cover] [Contents] [Index]