Image Segmentation Algorithm Based On Graph Theory

Image segmentation based on graph theory is a newly developed image segmentation technique in recent years. This thesis introduces and illustrates a general framework to integrate the areas of image segmentation and graph-cut theory. The image is mapped into a weighted undirected graph and the pixels are considered as vertexes and the similarity between the visual properties (e.g. gray-level intensity, color or texture) at each pair of neighboring pixels is assigned as the respective edge weight. Therefore the image segmentation can be obtained by cutting the graph with a minimum cut criteria.In this paper, a survey on this image segmentation technique is given and the performances of three basic graph partition algorithms (minimum cut, normalized cut and isoperimetric segmentation algorithm) are introduced and compared. Based on the isoperimetric graph partitioning method, we propose several practical segmentation algorithms. The first is the iterative two-way cut method which can segment an image into pieces with particular characteristics each other by iteration. The second is simultaneous K-way cut method which divides the image into K parts synchronously. The last is an interactive method separating objects of interest from the background by the user's input specifying the object of interest manually.In order to increase the speed of the interactive segmentation, we introduce a multi-scale method for the computation of graph partition that is motivated by the well-known multi-resolution signal processing theory and the pyramid structure. We perform a number of numerical experiments to show that this multi-scale computation method can reduce the running time of the segmentation algorithm, as well as can produce nearly the same segmentation result as the conventional graph cuts method, especially when the object to be extracted is small compared to the whole image.