Segmentation of Earth remote sensing images based on agglomerative pixel clustering using the minimum increment of the total squared error as a decision function

Among cluster analysis methods applied to grayscale image segmentation, Arifin's algorithm is particularly notable. This algorithm enables partitioning the original image into a number of clusters ranging from N_max to 1 in linear time, where N_max represents the number of grayscale levels in the original image. Arifin's algorithm incrementally enlarges pixel clusters by combining a "minimum pair" at each iteration within the calculation cycle, characterized by the minimum distance Dist between clusters. The original method calculates Dist by taking the product of interclass and intraclass variances; however, this approach involves cumbersome formulas and lacks a quality assessment for the resulting partitions. This study introduces two modifications to Arifin's algorithm that simplify the calculation of Dist for identifying "minimum pairs" and performing cluster merging sequences, while also enabling evaluation of cluster partition quality. The first modification uses the increment of the total squared error as a distance function for Dist, whereas the second modification employs partial entropy. In the first approach, partition quality is evaluated based on the total squared error or standard deviation, while in the second, it is assessed by the information content. A computer program has been developed to implement the first modification of Arifin's algorithm, incorporating a difference formula to compute partition quality. This program has been tested using standard test images of various sizes, including full-scale aerospace images (three images at 1024×1024 pixels and one at 2050×2050 pixels). The practical significance of the modification, which leverages the increment of the total squared error to create a series of suboptimal piecewise-constant partitions, lies in reducing the number of operations per cycle needed to determine the "minimum pair" among all adjacent clusters, thereby halving processor time.