Research On Image Segmentation Of The Mean Shift Algorithm Based On Graph Theory

Image segmentation is a basic and critical image processing.So having a good image segmentation is the important foundation in image analysis,image understanding and image recognition.In recent years,the image segmentation technique based on graph theory becomes a new hotspot because of its good characteristics.But with the rapid development of modern electronic devices,the scale of the image pixels rapid growth and the features of the image become complexity increasingly.The computation of a graph segmentation algorithm is so onerous that not suitable for real time image processing.For these deficiencies,this paper proposes a segmentation algorithm based on Ncut and Mean Shift image segmentation algorithm,and it uses Mean Shift for image preprocessing,and then it applys Ncut algorithm for regional clustering.The main contributions of this paper are summarized as follows:(1)Improvement of Mean Shift Algorithm:performing Mean Shift algorithm on idea of integral image,because the complexity of the algorithm is explained by the intensive search of colors samples in the Parzen window to compute the vector oriented toward the mean.By using the idea of integral image,the computational cost to estimate the MS vectors is independent from the size of the Parzen window,decreased the complexity from O(n2)to O(n),which n is the number of pixels.(2)The establishment of regional adjacency graph:in the graph,region adjacent nodes represent the region representative nodes,and in the traditional method it uses random manner or regional average value as representative node.This paper regards mode nodes by Mean Shift algorithm as region adjacent nodes.In this way,it can reduce computing time.(3)Improvement of weight function:this paper improves the weight matrix W and introduces the cosine similarity as the measure of the relationship between the nodes,which makes computing weight function time reduce.In this paper,the proposed image segmentation algorithm is experimented on Berkeley image database.The results show that segmentation quality of this method has a certain improvement compared with some traditional,classical methods,such as Ncut algorithm,Mean Shift algorithm and traditional Ncut segmentation algorithm combined with Mean Shift.