An Adaptive Clustering Algorithm for Image Segmentation

The problem of segmenting images of objects with smooth surfaces is considered. The algorithm we present is a generalization of the K-means clustering algorithm to include spatial constraints and to account for local intensity variations in the image. Spatial constraints are included by the use of a Gibbs random field model. Local intensity variations are accounted for in an iterative procedure involving averaging over a sliding window whose size decreases as the algorithm pro-gresses. Results with an eight-neighbor Gibbs random field model applied to pictures of industrial objects, buildings, aerial photographs, optical characters, and faces, show that the algorithm performs better than the A-means algorithm and its nonadaptive extensions that incorporate spatial constraints by the use of Gibbs random fields. A hierarchical implementation is also presented and results in better performance and faster speed of execution. The segmented images are caricatures of the originals which preserve the most significant features, while removing unimportant details. They can be used in image recognition and as crude representations of the image. The caricatures are easy to display or print using a few grey levels and can be coded very efficiently. In particular, segmentation of faces results in binary sketches which preserve the main characteristics of the face, so that it is easily recognizable.