Sequential image segmentation based on minimum spanning tree representation

Image segmentation is a very important stage in various image processing applications. Segmentation of pixels of an image and clustering of data are closely related to each other. For many graph-based data-clustering methods and many graph-based image-segmentation methods, minimum spanning tree (MST)-based approaches play a crucial role because of their ease of operation and low computational complexity. In this paper, we improve a successful data-clustering algorithm that uses Prim's sequential representation of MST, for the purpose of image segmentation. The algorithm runs by scanning the complete MST structure of the entire image, such that it finds, and then cuts, inconsistent edges among a constantly changing juxtaposed edge string whose elements are obtained from the MST at a specific length. In our method, the length of the string not only determines the edges to compare, but also helps to remove the small, undesired cluster particles. We also develop a new predicate for the cutting criterion. The criterion takes into account several local and global features that differ from image to image. We test our algorithm on a database that consists of real images. The results show that the proposed method can compete with the most popular image segmentation algorithms in terms of low execution time.