Research Of Image Segmentation Algorithm Based On Graph Theory

Image segmentation is used to divide an image into different areas based on its characteristic,and extract the targets of interest.It is the precondition of image recognition and tracking,this technology has been widely used in military,medical,intelligent transportation,pedestrian detection,product testing,sports,remote sensing and machine vision,etc.The graphs in the graph theory are the research object of image segmentation based on graph theory,and the related theoretical knowledge was used to perform segmentation of images.Because images and graphs in graph theory have an obvious contrast,it can make full use of related theoretical knowledge in graph theory to manipulate images and reduce the error caused by the image discretization,and achieve the accurate segmentation results.This dissertation focuses on the characteristics and applications of image segmentation based on graph theory.The relevant theoretical knowledge in the g raph of graph theory is used to segment the image accurately and efficiently,which plays an important role in image analysis and processing.The main tasks are as follows:1.The image segmentation problem is described as a minimization problem of computing image features by minimizing the Ginzburg-Landau function.The image is transformed into a weighted undirected graph using the characteristics of the graph,and the graph model is constructed.Then,the eigenvalues and the corresponding eigenvectors of the similarity matrix are obtained.Next,the image gray histogram is used to statistic related information,the original image is hierarchically clustered to obtain the cluster center,and the cluster center is used as the initial clustering center of the fuzzy C-means algorithm.Finally,the constructed graph model is clustered segmentation by fuzzy C-means.This algorithm does not need to set the number of clusters in advance,and the global clustering center is searched automatically by hierarchical clustering.It improves the segmentation speed effectively after the introduction of graph theory.2.With the increasing size of the image,direct pixel-based segmentation method is difficult to balance computational efficiency.For this problem,the nearest n eighbor graph is introduced based on the region adjacency graph to optimize the global search.The SLIC super pixel algorithm is used to segment the image into small regions,and the adjacency data table of the region adjacency graph(RAG)and nearest neig hbor graph(NNG)are used to describe the relationship between regions,then calculate the value of the dissimilarity function between each area will be merged and all its neighboring areas,and finally merge the regions with the smallest dissimilarity val ues.This method can extract the local features and obtain the redundant information of the image.It solves the problem of global optimal solution,and can merge the most similar regions better,reduces the complexity of the combined calculation and improves the accuracy of region merging.3.Spectral clustering algorithm maps the original images to a weighted undirected graph.Based on the degree of samples similarity,this algorithm enables them to cluster in arbitrary shape and converge to the global opt imal.However,this algorithm needs to calculate the similarity matrix of the sample during the clustering process,and the Laplacian matrix corresponding to the similarity matrix should be decomposed by features,the computing efficiency is low.To solve this problem,a uniform sampling method is used to perform preliminary sampling on the image.By minimizing the error of the Nystr?m extension method,the error between the sampling point and the pixel point is minimized through iterative calculation,and the final sampling point is obtained,then calculating the eigenvalues and the corresponding eigenvectors to construct a similarity matrix,the Nystr?m spectral clustering is used to segment the image.The algorithm has a capability of small computation and strong global optimization.4.The high computational complexity limits the application of spectral clustering algorithm in image segmentation,and the choice of sample information in image segmentation of spectral clustering is a key factor in the segmen tation accuracy.For gray image segmentation,based on image feature information and the scale change,the similarity relationship between pixels on different scales is used to calculate the minimum error between the similarity matrix and the sparse matrix on the edges and regions,and the feature information is extracted to create sparseness similarity matrix,then,spectral clustering is used to segment image.The algorithm reduces the computational complexity of spectral clustering image segmentation,sa ves memory space,improves the accuracy of image segmentation,and it has strong robustness to noise.