Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors

David Knossow 1 Avinash Sharma 1 Diana Mateus 1 Radu Horaud 1
1 PERCEPTION - Interpretation and Modelling of Images and Videos
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
Abstract : In this paper we propose an inexact spectral matching algorithm that embeds large graphs on a low-dimensional isometric space spanned by a set of eigenvectors of the graph Laplacian. Given two sets of eigenvectors that correspond to the smallest non-null eigenvalues of the Laplacian matrices of two graphs, we project each graph onto its eigenenvectors. We estimate the histograms of these one-dimensional graph projections (eigenvector histograms) and we show that these histograms are well suited for selecting a subset of significant eigenvectors, for ordering them, for solving the sign-ambiguity of eigenvector computation, and for aligning two embeddings. This results in an inexact graph matching solution that can be improved using a rigid point registration algorithm. We apply the proposed methodology to match surfaces represented by meshes.
Type de document :
Communication dans un congrès
Andrea Torsello and Francisco Escolano and Luc Brun. 7th International Workshop on Graph-Based Representations in Pattern Recognition, May 2009, Venice, Italy. Springer, 5534, pp.144-153, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-02124-4_15〉
Liste complète des métadonnées


https://hal.inria.fr/inria-00446989
Contributeur : Radu Horaud <>
Soumis le : mercredi 13 janvier 2010 - 22:17:04
Dernière modification le : jeudi 11 janvier 2018 - 01:48:44
Document(s) archivé(s) le : jeudi 18 octobre 2012 - 12:25:44

Fichiers

KnossowSharmaMateusHoraud-GbR....
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Knossow, Avinash Sharma, Diana Mateus, Radu Horaud. Inexact Matching of Large and Sparse Graphs Using Laplacian Eigenvectors. Andrea Torsello and Francisco Escolano and Luc Brun. 7th International Workshop on Graph-Based Representations in Pattern Recognition, May 2009, Venice, Italy. Springer, 5534, pp.144-153, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-02124-4_15〉. 〈inria-00446989〉

Partager

Métriques

Consultations de la notice

887

Téléchargements de fichiers

1921