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

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³) (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.