Abstract: Spectral clustering based on the similarity while the structure of similarity matrix is complex in image segmentation. The calculation of spectral clustering can be very time-consuming, especially in the process of Eigen-decomposition for Laplacian matrix. Sparse matrix could obtain the approximate solution of the similarity matrix by sing a small amount of sample information, thus, reducing the computational complexity effectively. An image segmentation algorithm based on the sparse matrix is proposed. First, error analysis of the spectral clustering is carried out in different scales. Then, a novel sampling method is presented. The sample information is used to create a sparse matrix, which can be used to substitute the similarity matrix. Typical experiment results and theoretical analysis show that the proposed algorithm can effectively reduce the complexity in calculating spectral clustering and improve the accuracy and robustness of the segmentation.

Key words: information processing technology, computer application, image segmentation, spectral clustering, sparse matrix, K-means