Synchronization Over the Birkhoff Polytope for Multi-graph Matching

摘要

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.