Initial Segmentation And Improved Weight Function Of Image Segmentation Method Based On Graph Theory

Graph theory, as one of important branches of discrete mathematics, has been developing almost three hundred years. It has a relatively complete mathematical theory system, as well as many mature practical algorithms. This kind of method can not only solve the problem from the global, but also has the ability to deal with local data. Therefore, graph method has a broad application prospect in the image processing engineering.In recent years, the image segmentation technology based on graph theory has been developing rapidly and becoming a hot research topic in the field of the international image segmentation. This technology firstly regards the image of pixels (region) as the nodes of a graph, pixels (region) and their neighborhood pixels (region) compose the edges, and then gives the definition of the edge weight, and constructs the weighted undirected graph. Then use the method of graph theory to divide the vertex set into k mutually disjoint subsets. Finally, the image segmentation can be obtained according to relationship between the nodes and pixels (region).This paper firstly summarizes the research status of image segmentation based on graph theory,and introduces three kinds of graph theory algorithms relating with image segmentation—minimum spanning tree algorithm, graphic spectrum segmentation algorithm and max-flow/min-cut algorithm, and gives detailed description of implementing steps of these three algorithms, and their application in image segmentation and the current research hot spot problems.Then, the new image segmentation algorithm combining mean shift with region merging is proposed. This new algorithm firstly use the mean shift algorithm to divide the original image into some regions considered as graph nodes. Then, according to adjacency relations among these regions, the degree of similarity among these regions is defined and undirected graph can be constructed. Furthermore, Kruskal algorithm is used to establish minimum spanning tree to calculate k connected components. And according to the connected component relationships, regions are merged and classified to complete image segmentation. Finally, the segmentation performance of the new algorithm has been tested through comparing the segmentation results of four algorithms. The experimental results show that the segmentation performance of the new algorithm is superior to the other three algorithms.This paper finally discusses and analyses the threshold segmentation method based on the normalized cuts. For its weighted function needs to be artificially given two global parameters, the standard deviation of the local gray values is taken into account. We put forward a new weighted function to improve the original method. At last segmentation performance of the weighted function is tested through a lot of experiments. A large number of comparative experiments results show that:compared to the other three kind of threshold segmentation method, the method of this paper has better segmentation performance, and can retain more image details.