The Image Spectrum Segmentation Based On Graph Theory

Segmentation is one of the most difficult and important steps in digital image processing. Segmentation accuracy determines the eventual success or failure of computerized analysis procedures. For this reason,image segmentation has been widely investigated for more than 40 years,and hundreds of algorithms have been presented in the literature. Although those algorithms are to some extent successful,image segmentation is still far from been solved.In this paper, the research of the Normalized Cut criterion is on the study of many related literatures, then we proposed an improved image spectrum segmentation technology which is based on graph theory.The usually Normalized Cut theory use the pixels in the pictures as the nodes to create the weighted undirected liaison graph.Then create a N×N dim's weighted matrix according to the weighted undirected liaison graph.The time complexity of the algorithm will become verry big if the graph is very big, In order to overcome this problem, this paper proposes an image segmentation method based on NCut criterion and image 2-d's histogram.The main theory of this method is that,first,according to the two-dim histogram of the image,we make use of the K-Means clustering analysis method to presegment the graph,and then, use the outcome of the image presegmentation,small and continuous area,as nodes of the weighted undirected liaison graph.The dimension of the weighted matrix,according to the weighted undirected liaison graph,will far from N×N ,that is to say,this method decrease the complexity of the algorithm. At the end of this paper,we give out the simulation realization of the algorithm and the outcome of the experiment.