Multi-level Low-rank Approximation-based Spectral Clustering for image segmentation

Spectral clustering is a well-known graph-theoretic approach of finding natural groupings in a given dataset, and has been broadly used in image segmentation. Nowadays, High-Definition (HD) images are widely used in television broadcasting and movies. Segmenting these high resolution images presents a grand challenge to the current spectral clustering techniques. In this paper, we propose an efficient spectral method, Multi-level Low-rank Approximation-based Spectral Clustering (MLASC), to segment high resolution images. By integrating multi-level low-rank matrix approximations, i.e., the approximations to the affinity matrix and its subspace, as well as those for the Laplacian matrix and the Laplacian subspace, MLASC gains great computational and spacial efficiency. In addition, the proposed fast sampling strategy make it possible to select sufficient data samples in MLASC, leading to accurate approximation and segmentation. From a theoretical perspective, we mathematically prove the correctness of MLASC, and provide detailed analysis on its computational complexity. Through experiments performed on both synthetic and real datasets, we demonstrate the superior performance of MLASC.

► We propose an efficient spectral method to segment high resolution images. ► Our method gains great efficiency by integrating multi-level low-rank approximations. ► The proposed fast sampling strategy leads to accurate approximation and segmentation. ► We provide the mathematical proofs of the theories, and efficiency analysis. ► We empirically demonstrate the superior performance of our method on real data.