Spectral Clustering And Dictionary Learning Based Image Segmentation

Spectral Clustering Algorithm has been widely used in many fields for its simple implement, no relevant with dimension and could converged to the global optimal solution. However, Spectral Clustering Algorithm requires computing the principal eigenvectors of a n x n similarity matrix(n is the number of examples), which become a bottleneck for spectral clustering when applied in large scale datasets. In this paper, we research the fast spectral clustering algorithm that takes image segmentation as the application background. The main contributions can be summarized as follows:(1) A novel algorithm called Dictionary Learning Sampling Nystrom Spectral Clustering (DNSC) algorithm is proposed, in which, the dictionary learning algorithm is introduced to select the typical sample sets without any prior knowledge. The experiment results show that DNC algorithm gets a better accuracy rate compared with the Random Nystrom Spectral Clustering (RNSC) algorithm.(2) A Double Dictionary Learning Sampling Nystrom Spectral Clustering (DDNSC) algorithm is proposed. Bases on the Nystrom approximation framework, it introduces image can be divided into two parts of edge and regional. And we can select sampling points from edge-points and regional-points which replaces the original random sampling mechanism to select a sample subset. This select method preserves more image information as possible while approximating the rest points to reduce the amount of computation. The experiment results show that, compared with RNSC algorithm and k-means Nystrom Spectral Clustering (KNSC) algorithm, DDNSC algorithm is more stable and could get a better segmentation result with the same computation complexity.(3) We propose a method based spectral clustering and discriminative dictionary based image segmentation method. We use Nystrom Spectral Clustering labeled the subset labels to direct all the other examples to get a final segmentation result. Then we introduce Discriminative Dictionary Learning and use it complete image segmentation. The experiment results show that algorithm could get a better segmentation result.This paper was supported bythe National Natural Science Foundation of China(Nos.60702062,60970067,61003198), the Fundamental Research Funds for the Central Universities (No.(JY10000902001, JY10000902038), the Provincial Natural Science Foundation of Shaanxi of China(No.2009JQ8016), the China Postdoctoral Science Foundation funded project (No.20090460093).