Details
| Original language | English |
|---|---|
| Title of host publication | Energy Minimization Methods in Computer Vision and Pattern Recognition - 10th International Conference,EMMCVPR 2015, Proceedings |
| Publisher | Springer Verlag |
| Pages | 450-463 |
| Number of pages | 14 |
| ISBN (electronic) | 9783319146119 |
| Publication status | Published - 2015 |
| Event | 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015 - Hong Kong, China Duration: 13 Jan 2015 → 16 Jan 2015 |
Publication series
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 8932 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
Abstract
Spectral graph clustering is among the most popular algorithms for unsupervised segmentation. Applications include problems such as speech separation, segmenting motions or objects in video sequences and community detection in social media. It is based on the computation of a few eigenvectors of a matrix defining the connections between the graph nodes. In many real world applications, not all edge weights can be defined. In video sequences, for instance, not all 3d-points of the observed objects are visible in all the images. Relations between graph nodes representing he 3d-points cannot be defined if these never co-occur in the same images. It is common practice to simply assign an affinity of zero to such edges. In this article, we present a formal proof that this procedure decreases the separation between two clusters. An upper bound is derived on the second smallest eigenvalue of the Laplacian matrix.Furthermore, an algorithm to infer missing edges is proposed and results on synthetic and real image data are presented.
ASJC Scopus subject areas
- Mathematics(all)
- Theoretical Computer Science
- Computer Science(all)
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
Energy Minimization Methods in Computer Vision and Pattern Recognition - 10th International Conference,EMMCVPR 2015, Proceedings. Springer Verlag, 2015. p. 450-463 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8932).
Research output: Chapter in book/report/conference proceeding › Conference contribution › Research › peer review
}
TY - GEN
T1 - Randomly walking can get you lost
T2 - 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition, EMMCVPR 2015
AU - Ackermann, Hanno
AU - Scheuermann, Björn
AU - Chin, Tat Jun
AU - Rosenhahn, Bodo
PY - 2015
Y1 - 2015
N2 - Spectral graph clustering is among the most popular algorithms for unsupervised segmentation. Applications include problems such as speech separation, segmenting motions or objects in video sequences and community detection in social media. It is based on the computation of a few eigenvectors of a matrix defining the connections between the graph nodes. In many real world applications, not all edge weights can be defined. In video sequences, for instance, not all 3d-points of the observed objects are visible in all the images. Relations between graph nodes representing he 3d-points cannot be defined if these never co-occur in the same images. It is common practice to simply assign an affinity of zero to such edges. In this article, we present a formal proof that this procedure decreases the separation between two clusters. An upper bound is derived on the second smallest eigenvalue of the Laplacian matrix.Furthermore, an algorithm to infer missing edges is proposed and results on synthetic and real image data are presented.
AB - Spectral graph clustering is among the most popular algorithms for unsupervised segmentation. Applications include problems such as speech separation, segmenting motions or objects in video sequences and community detection in social media. It is based on the computation of a few eigenvectors of a matrix defining the connections between the graph nodes. In many real world applications, not all edge weights can be defined. In video sequences, for instance, not all 3d-points of the observed objects are visible in all the images. Relations between graph nodes representing he 3d-points cannot be defined if these never co-occur in the same images. It is common practice to simply assign an affinity of zero to such edges. In this article, we present a formal proof that this procedure decreases the separation between two clusters. An upper bound is derived on the second smallest eigenvalue of the Laplacian matrix.Furthermore, an algorithm to infer missing edges is proposed and results on synthetic and real image data are presented.
UR - http://www.scopus.com/inward/record.url?scp=84921875841&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-14612-6_33
DO - 10.1007/978-3-319-14612-6_33
M3 - Conference contribution
AN - SCOPUS:84921875841
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 450
EP - 463
BT - Energy Minimization Methods in Computer Vision and Pattern Recognition - 10th International Conference,EMMCVPR 2015, Proceedings
PB - Springer Verlag
Y2 - 13 January 2015 through 16 January 2015
ER -