Open AccessThe article suggests a method of image segmentation into simply connected domains based on color. Pixels from an original image are represented as points in five-dimensional space which includes three color and two spatial coordinates. The points are normalized in order to eliminate distinguished characteristics. The set of points is compared with a weighted complete graph. The points of five-dimensional space are vertexes in the graph. Euclidian distance between the points is used as weights of the edges in the graph. To solve the task of clustering, a minimum spanning tree of the graph is built. For clustering, the tree is separated into sub-trees by removing some edges. Each sub-tree is a simply connected domain on the original image. In order to improve algorithm speed and reduce memory usage a greedy algorithm is used to build this minimum spanning tree for the graph. Edges to be removed are searched on the graph representing the length of an added edge versus a sequence number of its adding to the tree in the greedy algorithm. The desired edges are detected as maximums on the graphic. This search is based on assumption that transition to an adjacent cluster leads to connection of longer edge in comparison with edges within a cluster. Segmentation into clusters is iterative. At each step the bigger clusters are divided into smaller ones. It means that hierarchy of clusters can be built. A computer experiment was carried out using different images.
The suggested method has no disadvantages of the most common method of k-means and allows dividing domains with different colors but the same intensity. Therewith there is no need to specify a number of clusters. Instead, it is necessary to choose a segmentation depth then a number of clusters will be automatically defined. The suggested method has no disadvantages of detection of image edges either. It is sufficient to find one point of image edge to separate two domains.
A distinctive feature of the suggested method is natural building of cluster hierarchy, which allows choosing a level of details. This feature makes the method applicable for algorithms of preliminary image processing for further pattern recognition or searching details on an image.