In this paper we address the problem of simultaneously matching multiple graphs imposing cyclic or transitive consistency among the correspondences. This is obtained through a synchronization process that projects doubly-stochastic matrices onto a consistent set. We overcome the lack of group structure of the Birkhoff polytope, i.e., the space of doubly-stochastic matrices, by making use the Birkhoff-Von Neumann theorem stating that any doubly-stochastic matrix can be seen as the expectation of a distribution over the permutation matrices, and then cast the synchronization problem as one over the underlying permutations. This allows us to transform any graph-matching algorithm working on the Birkhoff polytope into a multi-graph matching algorithm. We evaluate the performance of two classic graph matching algorithms in their synchronized and un-synchronized versions with a state-of-the-art multi-graph matching approach, showing that synchronization can yield better and more robust matches.
|Data di pubblicazione:||2017|
|Titolo:||Synchronization over the Birkhoff polytope for multi-graph matching|
|Rivista:||LECTURE NOTES IN COMPUTER SCIENCE|
|Titolo del libro:||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-319-58961-9_24|
|Appare nelle tipologie:||4.1 Articolo in Atti di convegno|