Research Of Image Segmentation And Parallelization Based On Graph Theory

Image segmentation plays an important role in digital image processing and computer vision. Image Segmentation based on graph theory is a prevalent research topic in recently international image segmentation area. Its basic idea is to mapping an image to the weighted undirected graph, in which the pixels are mapped to vertices and the vision information such as gray or distances are mapped to weight of edges. Then a function is constructed based on a specific segmentation of graph. The minimum value of such energy function could supply an optimal segmentation of original image. Besides, it has highly flexibility and could supply a unified method to tackle with the information such as color, texture and noise and can be applied to any digital image.Min-max cut algorithm fully reflects the optimal segmentation criteria of spectral segmentation based on graph theory, namely the similarity of vertices in one sub-graph is maximum, the similarity of vertices in different sub-graphs is minimum.It turns the NP-hard problem into the question to finding the solutions of the characteristic equations, the prefect answer can be achieved by math method, but this method exist a complex problem in solving large-scale matrices’eigenvector, moreover, with the image size increasing, the computation size is increasing, the algorithm’s application efficiency would be lowered.Making the similarity matrix reflect the relationship between vertices realistically, when building the edges, there is no longer simple to build the edges based on eight neighborhood, and the vertice connects with other vertices within the central radius r. The similarity is calculated using Gaussian function characterized by gray and distance between the vertices.In order to reduce the number of nodes and edges, this paper proposes a new method, combining Vincent-Watershed with Min-max cut algorithm. Firstly, pre-segmentation on the image is completed by the Watershed algorithm, obtaining a large number of small regions.Then calculating the weights and constructing the graph:nodes represent small regions, the edges between nodes represent the relationship between regions. Secondly, using Min-max cut to merge these small regions and segment the image. It can not only eliminate the phenomenon of over segmentation, but also reduce the number of edges.In order to make the segmentation of Min-max cut algorithm faster, the page propose CUDA GPU-based platforms to accelerate it. According to GPU is suitable for high density and simple logic computing, it is feasible to accelerate the Min-max cut algorithm.Based on the implementation steps of Min-max cut algorithm, the page analysis parallelism of each step analysis, and designs the Min-max cut algorithm based on GPU. The page achieves the GPU accelerating solving the eigenvalues of a tridiagonal matrix and the K-means clustering. Experimental results show that the speedup is1.5based on GPU,and concluded that the block matrix calculation of mass is the way to raise the speedup of Min-max cut based on GPU.