More Web Proxy on the site http://driver.im/

Article

Segmentation via graph-spectral methods and riemannian geometry

Author:

Antonio Robles-KellyAuthors Info & Claims

CAIP'05: Proceedings of the 11th international conference on Computer Analysis of Images and Patterns

Pages 661 - 668

https://doi.org/10.1007/11556121_81

Published: 05 September 2005 Publication History

Abstract

In this paper, we describe the use of graph-spectral techniques and their relationship to Riemannian geometry for the purposes of segmentation and grouping. We pose the problem of segmenting a set of tokens as that of partitioning the set of nodes in a graph whose edge weights are given by the geodesic distances between points in a manifold. To do this, we commence by explaining the relationship between the graph Laplacian, the incidence mapping of the graph and a Gram matrix of scalar products. This treatment permits the recovery of the embedding coordinates in a closed form and opens up the possibility of improving the segmentation results by modifying the metric of the space in which the manifold is defined. With the set of embedding coordinates at hand, we find the partition of the embedding space which maximises both, the inter-cluster distance and the intra-cluster affinity. The utility of the method for purposes of grouping is illustrated on a set of shape silhouettes.

References

[1]

M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Neural Information Processing Systems, number 14, pages 634-640, 2002.

[2]

I. Borg and P. Groenen. Modern Multidimensional Scaling, Theory and Applications. Springer Series in Statistics. Springer, 1997.

[3]

I. Chavel. Riemannian Geometry: A Modern Introduction. Cambridge University Press, 1995.

[4]

M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czech Math. Journal, (25):619-633, 1975.

[5]

J. C. Gower. Some distance properties of latent root and vector methods used in multivariate analysis. Biometrika, 53:325-328, 1966.

[6]

J. Ham, D. D. Lee, S. Mika, and B. Scholkopf. A kernel view of the dimensionality reduction of manifolds. In In Proc. Int. Conf. Machine Learning, page 369-376, 2004.

Digital Library

[7]

B. Luo, A. Robles-Kelly, A. Torsello, R. C. Wilson, and E. R. Hancock. A probabilistic framework for graph clustering. In EEE International Conference on Computer Vision and Pattern Recognition, pages I:912-919, 2001.

[8]

P. Perona and W. T. Freeman. Factorization approach to grouping. In Proc. ECCV, pages 655-670, 1998.

Digital Library

[9]

S. T. Roweis and L. K. Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290:2323-2326, 2000.

[10]

S. Sarkar and K. L. Boyer. Quantitative measures of change based on feature organization: Eigenvalues and eigenvectors. Computer Vision and Image Understanding, 71(1):110-136, 1998.

Digital Library

[11]

G. L. Scott and H. C. Longuet-Higgins. Feature grouping by relocalisation of eigenvectors of the proximity matrix. In British Machine Vision Conference, pages 103-108, 1990.

[12]

J. Shi and J. Malik. Normalized cuts and image segmentations. In Proc. of the IEEE Conf. on Comp. Vision and Pattern Recognition, pages 731-737, 1997.

Digital Library

[13]

J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500):2319-2323, 2000.

[14]

W. S. Torgerson. Multidimensional scaling I: Theory and method. Psychometrika, 17:401-419, 1952.

[15]

G. Young and A. S. Householder. Discussion of a set of points in terms of their mutual distances. Psychometrika, 3:19-22, 1938.

Cited By

DuJinwei DBuZhan BYiTao Y(2021)A Graph Embedding Method Based on Opinion DynamicsProceedings of the 2021 4th International Conference on Artificial Intelligence and Pattern Recognition10.1145/3488933.3488975(687-697)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1145/3488933.3488975
Lombaert HGrady LPennec XAyache NCheriet F(2012)Spectral Demons --- Image Registration via Global Spectral CorrespondenceProceedings, Part II, of the 12th European Conference on Computer Vision --- ECCV 2012 - Volume 757310.5555/2964398.2964402(30-44)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.5555/2964398.2964402
Nguyen QRobles-Kelly AZhou J(2009)A graph-based feature combination approach to object trackingProceedings of the 9th Asian conference on Computer Vision - Volume Part II10.1007/978-3-642-12304-7_22(224-235)Online publication date: 23-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-12304-7_22

Index Terms

Segmentation via graph-spectral methods and riemannian geometry
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis

Index terms have been assigned to the content through auto-classification.

Recommendations

Point pattern matching via spectral geometry
SSPR'06/SPR'06: Proceedings of the 2006 joint IAPR international conference on Structural, Syntactic, and Statistical Pattern Recognition

In this paper, we describe the use of Riemannian geometry, and in particular the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. Using the properties of Jacobi ...
Automatic Diagnosis of Brain Magnetic Resonance Images based on Riemannian Geometry

Automated brain tumor detection and segmentation, from medical images, is one of the most challenging. The authors present, in this paper, an automatic diagnosis of brain magnetic resonance image. The goal is to prepare the image of the human brain to ...
Riemannian Manifold Learning

Recently, manifold learning has been widely exploited in pattern recognition, data analysis, and machine learning. This paper presents a novel framework, called Riemannian manifold learning (RML), based on the assumption that the input high-dimensional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CAIP'05: Proceedings of the 11th international conference on Computer Analysis of Images and Patterns

September 2005

864 pages

ISBN:3540289690

Editors:
André Gagalowicz
INRIA-Rocquencourt, Domaine de Voluceau, Le Chesnay, France
,
Wilfried Philips
Ghent University, Gent, Belgium

Sponsors

DGA: DGA
Ghent University - Faculty of Engineering and Architecture: Ghent University - Faculty of Engineering and Architecture
INRIA: Institut Natl de Recherche en Info et en Automatique
IEEE Section France: IEEE Section France

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

DuJinwei DBuZhan BYiTao Y(2021)A Graph Embedding Method Based on Opinion DynamicsProceedings of the 2021 4th International Conference on Artificial Intelligence and Pattern Recognition10.1145/3488933.3488975(687-697)Online publication date: 24-Sep-2021
https://dl.acm.org/doi/10.1145/3488933.3488975
Lombaert HGrady LPennec XAyache NCheriet F(2012)Spectral Demons --- Image Registration via Global Spectral CorrespondenceProceedings, Part II, of the 12th European Conference on Computer Vision --- ECCV 2012 - Volume 757310.5555/2964398.2964402(30-44)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.5555/2964398.2964402
Nguyen QRobles-Kelly AZhou J(2009)A graph-based feature combination approach to object trackingProceedings of the 9th Asian conference on Computer Vision - Volume Part II10.1007/978-3-642-12304-7_22(224-235)Online publication date: 23-Sep-2009
https://dl.acm.org/doi/10.1007/978-3-642-12304-7_22

View Options

View options

Media

Figures

Other

Tables

View Table of Contents