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

Hongbo Zhou, Qiang Cheng

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

Abstract

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
Pages2209-2215
Number of pages7
ISBN (Print)9781457703942
DOIs
StatePublished - 1 Jan 2011

Publication series

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

Fingerprint

Image segmentation
Eigenvalues and eigenfunctions
Unsupervised learning
Program processors
Computational complexity
Image processing
Color
Decomposition
Data storage equipment
Experiments

Cite this

Zhou, H., & Cheng, Q. (2011). O(N) implicit subspace embedding for unsupervised multi-scale image segmentation. In 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011 (pp. 2209-2215). [5995606] (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition). IEEE Computer Society. https://doi.org/10.1109/CVPR.2011.5995606
Zhou, Hongbo ; Cheng, Qiang. / O(N) implicit subspace embedding for unsupervised multi-scale image segmentation. 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011. IEEE Computer Society, 2011. pp. 2209-2215 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition).
@inproceedings{9e01246d751148a987b43814b874f792,
title = "O(N) implicit subspace embedding for unsupervised multi-scale image segmentation",
abstract = "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.",
author = "Hongbo Zhou and Qiang Cheng",
year = "2011",
month = "1",
day = "1",
doi = "10.1109/CVPR.2011.5995606",
language = "English",
isbn = "9781457703942",
series = "Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition",
publisher = "IEEE Computer Society",
pages = "2209--2215",
booktitle = "2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011",

}

Zhou, H & Cheng, Q 2011, O(N) implicit subspace embedding for unsupervised multi-scale image segmentation. in 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011., 5995606, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, IEEE Computer Society, pp. 2209-2215. https://doi.org/10.1109/CVPR.2011.5995606

O(N) implicit subspace embedding for unsupervised multi-scale image segmentation. / Zhou, Hongbo; Cheng, Qiang.

2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011. IEEE Computer Society, 2011. p. 2209-2215 5995606 (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition).

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

TY - GEN

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

AU - Zhou, Hongbo

AU - Cheng, Qiang

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80052879605&partnerID=8YFLogxK

U2 - 10.1109/CVPR.2011.5995606

DO - 10.1109/CVPR.2011.5995606

M3 - Conference contribution

SN - 9781457703942

T3 - Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition

SP - 2209

EP - 2215

BT - 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011

PB - IEEE Computer Society

ER -

Zhou H, Cheng Q. O(N) implicit subspace embedding for unsupervised multi-scale image segmentation. In 2011 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011. IEEE Computer Society. 2011. p. 2209-2215. 5995606. (Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition). https://doi.org/10.1109/CVPR.2011.5995606