Synchronisation of Partial Multi-Matchings via Non-negative Factorisations

  • 2018-03-16 17:17:05
  • Florian Bernard, Johan Thunberg, Jorge Goncalves, Christian Theobalt
  • 11

Abstract

In this work we study permutation synchronisation for the challenging case ofpartial permutations, which plays an important role for the problem of matchingmultiple objects (e.g. images or shapes). The term synchronisation refers tothe property that the set of pairwise matchings is cycle-consistent, i.e. inthe full matching case all compositions of pairwise matchings over cycles mustbe equal to the identity. Motivated by clustering and matrix factorisationperspectives of cycle-consistency, we derive an algorithm to tackle thepermutation synchronisation problem based on non-negative factorisations. Inorder to deal with the inherent non-convexity of the permutationsynchronisation problem, we use an initialisation procedure based on a novelrotation scheme applied to the solution of the spectral relaxation. Moreover,this rotation scheme facilitates a convenient Euclidean projection to obtain abinary solution after solving our relaxed problem. In contrast tostate-of-the-art methods, our approach is guaranteed to producecycle-consistent results. We experimentally demonstrate the efficacy of ourmethod and show that it achieves better results compared to existing methods.

 

Quick Read (beta)

loading the full paper ...