Research Of Image Segmentation Algorithms Based On Graph Theory

Image segmentation is a technology and process that segments the image into regions with different characteristics. It has different names in different areas. It is a key technology in the image processing and also a problem. It can extract the meaningful parts of the image and it is the foundation of further recognition, analysis and understanding of the image.Up to now, there are lots of image segmentation methods, but still not a method for all kinds of images. The implementation of image segmentation can be divided into three stages: image preprocessing stage, the core algorithm stage, and the post-processing stage. Clustering optimization based on graph theory can trace back to the 1960s, and the image processing and analysis based on graph theory can trace back to the 1980s. The main research in this thesis is the image segmentation methods based on graph theory. The main work in this thesis is as follows:①First, the status of the image segmentation and the status of the image segmentation based on graph theory is introduced. And several concepts of the graph and the graph cut algorithms that appeared during the past two decade are simply introduced. The relationship between graph cut and image segmentation is described.②An segmentation algorithm FWTI (First Watershed Then Isoperimetric) based on Watershed and Isoperimetric is proposed. FWTI is an algorithm that combined watershed algorithm and Isoperimetric Algorithm, it first uses watershed algorithm to segment the image, and then construct graph using the regions produced by watershed algorithm as nodes, and then further segmenting is done by using isoperimetric algorithm among the regions. The ground nodes in FWTI algorithm are selected automatically, and this algorithm is an automatic technology. The experiment results show that FWTI algorithm not only help to overcome the over-segmentation problem of watershed algorithm but also improve the segmentation speed compared to the original isoperimetric algorithm.③An Isoperimetric segmentation algorithm combined with block structure is proposed. This algorithm first constructs blocks for the image and then uses the blocks as nodes to construct graph, and then uses the Isoperimetric algorithm to segment the image. For automatic segmentation can't accurately segment the target area from the image, in this thesis the foreground regions is labeled by selecting the ground nodes artificially, and the segmentation of the target areas can be done by semi-automatic method. The experiment results show that the use of block structure can reduce the number of the nodes and the edges in the graph, so this algorithm can improve the segmentation speed compared to the original isoperimetric algorithm.