O(N) implicit subspace embedding for unsupervised multi-scale image segmentation

Hongbo Zhou, Qiang Cheng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

3 Scopus citations


Subspace embedding is a powerful tool for extracting salient information from matrix, and it has numerous applications in image processing. However, its applicability has been severely limited by the computational complexity of O(N 3 ) (N is the number of the points) which usually arises in explicitly evaluating the eigenvalues and eigenvectors. In this paper, we propose an implicit subspace embedding method which avoids explicitly evaluating the eigenvectors. Also, we show that this method can be seamlessly incorporated into the unsupervised multi-scale image segmentation framework and the resulted algorithm has a running time of genuine O(N). Moreover, we can explicitly determine the number of iterations for the algorithm by estimating the desired size of the subspace, which also controls the amount of information we want to extract for this unsupervised learning. We performed extensive experiments to verify the validity and effectiveness of our method, and we conclude that it only requires less than 120 seconds (CPU 3.2G and memory 16G) to cut a 1000*1000 color image and orders of magnitude faster than original multi-scale image segmentation with explicit spectral decomposition while maintaining the same or a better segmentation quality.

Original languageEnglish
Title of host publication2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011
PublisherIEEE Computer Society
Number of pages7
ISBN (Print)9781457703942
StatePublished - 2011

Publication series

NameProceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition
ISSN (Print)1063-6919


Dive into the research topics of 'O(N) implicit subspace embedding for unsupervised multi-scale image segmentation'. Together they form a unique fingerprint.

Cite this