Study Of Image Segmentation Methods Based On Multiscale Fast Spectral Clustering

Image segmentation is a important step between image processing and image analysis and has received more and more attention in recent years.Spectral clustering method is a popular image segmentation method in recent years.Because it is not restricted by the shape of the sample space,and can be clustered in any sample space.However,there are at least two problems waiting to be solved.The first problem is the computational complexity of constructing similarity matrix is proportion to O(n2).The second one is the computa-tional complexity of directing computing the eigen-decomposition of the Laplacian matrix.The expensive computational cost brought by the Spectral clustering method restricts the application of traditional spectral clustering methods in practice.In this paper,the image segmentation algorithm based on spectral clustering is mainly studied from the aspect of im?proving the efficiency of spectral clustering method.We do the following works to further improve the spectral clustering algorithm:Firstly,aiming at the problem of low efficiency of spectral clustering method in im-age segmentation,we propose the Multi-scale Fast Spectral Clustering algorithm(MFSC).Firstly,the image is pre-segmented by quadtree decomposition algorithm to obtain "super-pixel".These "superpixels" are used as the basic unit of segmentation,and the similarity matrix based on superpixel is constructed,and then the tree shape is obtained by quadtree decomposition.The data structure transforms the feature decomposition problem of large-scale matrix in spectral clustering into a plurality of smaller feature decomposition problems at different scales.Where the complexity of the MFSC algorithm is reduced to O(n log n),and n is the number of pixels of the image,reaching a linear level.The experimental results show that the MFSC effectively improves the efficiency of the spectral clustering algorithm and achieves better segmentation results.Secondly,although the multi-scale spectral clustering algorithm based on quadtree de-composition has achieved good results in the field of image segmentation.However,the quadtree decomposition algorithm still has many limitations.At the same time,the scale parameters required to construct the similarity matrix also greatly affect the segmentation result of the spectral clustering method.To this end,this paper proposes a Multi-scale Fast Spectral Clustering based on K-d tree algorithm.The improved K-d tree algorithm is more flexible and has a wider application than the quadtree decomposition algorithm.In addi-tion,the algorithm uses local scale adaptive set-scale scale parameters in the construction of similarity matrix to solve the problem of manual setting of scale parameters.Through the verification on the artificial dataset,UCI dataset and image dataset,the new algorithm can achieve higher execution efficiency while better clustering effect.Thirdly,in order to facilitate the research of the proposed clustering algorithm,this pa-per designs a set of spectral clustering algorithm analysis application system based on Qt platform and C++and Matlab.The system integrates the proposed algorithm and a vari-ety of current mainstream spectral clustering algorithms,which can intuitively analyze and compare the differences between segmentation results and operational efficiency of differ-ent spectral clustering algorithms according to user requirements.Research has provided convenience.