Study Of Image Segmentation Methods Based On Spectral Clustering

At present,Cluster analysis is one of the very active research focuses in the international field of Data Mining and Machine Learning.It is an effective means for people to understand and reveal the intrinsic links between things.As an efficient means of data analysis,it has been widely used in many fields,e.g.,data compressing,image processing,computer vision,speech recognition,document clustering,outlier detection,etc.And as a novel clustering algorithm,spectral clustering algorithm has many advantages over traditional clustering algorithms.Spectral clustering algorithm is simple,easy to implement,fall into global optimal solution,and it can analysis data of any shapes and so on.Building on the basis of affinity matrix,traditional spectral clustering algorithm need construct the laplacian matrix and compute its eigenvalues and the corresponding eigenvectors,and then according to some rules it will select one or more eigenvectors to analyze the data.However,three are at least two difficulties waiting to be solved.The first is how to set the Gaussian kernel scale parameter required by constructing the affinity matrix.The second is the computational complexity of directing computing the eigenvalues decomposing(EVD)is proportional to O(n3).The two difficulties severely limit the practical application of the traditional spectral clustering algorithm.Thus,designing a new spectral clustering algorithm without the requirement of artificial setting scale parameter and with lower computational complexity plays a very important significance on theoretical study and practical application.If using cosine method instead of Gaussian kernel,then we need not set the scale parameter artificially.The former studies show that sampling technique is an effective way of lowering the computational complexity of spectral clustering algorithm.However,the approximation error is big and the samples can not accurately capture the cluster geometry structures.We do the following works to further improve the spectral clustering algorithm.(1)Aim to the problem of image segmentation by spectral clustering ensemble,spectral clustering ensemble algorithm based on similarity matrix(SCESM)algorithm is designed in this paper.Algebraic transformation is used in SCESM algorithm to approximately obtain the eigenvalue in the process of spectral decomposition which can greatly reduces the computational complexity of spectral clustering ensemble algorithm.In order to apply SCESM to large image processing,an image segmentation method using Mean shift algorithm and the MSSCESM algorithm(MSSCESM)is designed in this thesis.MSSCESM pre-segments the large image by using the Mean shift algorithm and introduces the thought of spectral clustering ensemble to perform the pre-segmented regions resulting in the good input of the SCESM algorithm.The experimental results show that MSSCESM can obtain better segmentation quality than that of some other commonly used algorithms and MSCESM is effective.(2)The studies show that like the sampling technique,the low-rank approximation method can also be well used to solve the difficulty of the high computational complexity of EVD.What's more,the approximation error of the low-rank approximation method is lower than the sampling technique.Thus,a new spectral clustering algorithm named as spectral clustering using the low-rank approximation method is proposed in this paper by combining the low-rank approximation method into the traditional spectral clustering algorithm.Experiments show that new algorithm is fast and can gain good quality while effectively reduce the approximation error.(3)Though both the sampling technique and the low-rank approximation method can largely lower the computational complexity of the EVD,they involve sampling technique.As is known to us that no matter how the samples or representatives are chosen randomly or by using a more expensive selection,it may not completely represent the whole dataset and may not correctly capture the cluster geometry structures.Thus,some other methods of finding the approximation embedding are needed without involving the sampling technique.A new spectral clustering algorithm named as spectral clustering using the commute time is proposed in this paper by combining the commute time into the traditional spectral clustering algorithm.Experiments show that new algorithm is fast and can gain good quality.