Research Of Image Segmentation Based On Minimum Spanning Tree

Image processing is widely used in medical images, remote sensing images, fingerprint identification, face detection, geological exploration and other fields. As a critical step in the image processing,image segmentation can provide effective information for image retrieval and image analysis, make it possible to a high level of image processing. Common methods of image segmentation can be summarized as follow: methods based on boundary detection and edge linking, methods based on region, methods based on special theory. In recent years, the combining of graph theory with other methods is becoming a hot spot in the both domestic and foreign research field.This paper describes the image segmentation methods based on graph theory in detail. After the analysis of concepts and theories, an improved Kruskal-Minimum spanning tree algorithm is proposed, which can update the weighted region adjacency graph (WRAG). In this algorithm, recalculating weights of the new region and its adjacent regions must be done after a merging, as well as changing WRAG and sorting edges. The WRAG of improved algorithm is much closer to the characteristics of the original image.The Watershed algorithm is introduced of its concepts, theories and flaws. In order to reduce the number of nodes and edges, this paper proposes a new method, named K ? VWmethod, combining Vincent-Watershed with Kruskal-Minimum spanning tree algorithm. Firstly, presegmentation on the gradient image is completed by the Watershed algorithm, obtaining a large number of small regions. Then calculating the weights and constructing the WRAG. The nodes represent small regions, the edges between nodes represent the relationship between regions. Secondly, with Deepthi Narayan-merging criteria, the modified Kruskal algorithm can obtain better region similarity, by comparing regional differences between the internal and external information of the image own. The K ? VWmethod can not only eliminate the phenomenon of over segmentation, but also reduce the number of edges.By contrast experiments on series of color images, analyzing the advantages of the K - VWmethod. The results show that the proposed method of segmentation has good performance and strong applicability for color images, in which, there are intense contrasting of prospects and backgrounds. Its internal characterstics of regions change slowly and external characterstics of regional edges chage rapidly. To those color images, which containing more noise and details, the segmentation results of K - VWmethod will include redundant reginons and incorrect borderline. It needs further improvement.