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. (c) 2012 Elsevier B.V. All rights reserved.