Synchronisation of partial multi-matchings via non-negative factorisations. (August 2019)

• Record Type: Journal Article
• Authors: Bernard, Florian; Thunberg, Johan; Goncalves, Jorge; Theobalt, Christian
• Is Part Of: Pattern recognition. Volume 92(2019:Aug.)
• Page Start: 146
• Page End: 155
• Publication Date: 2019-08
• Subjects: Partial permutation synchronisation -- Multi-matching -- Spectral decomposition -- Non-negative matrix factorisation; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2019.03.021
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Partial permutation synchronisation is relevant for multi-matching problems. We derive an improved algorithm based on non-negative factorisations. A novel initialisation procedure for the non-convex problem is presented. We introduce a new projection approach to obtain a binary solution. The approach achieves superior results that are guaranteed to be cycle-consistent. Abstract: In this work we study permutation synchronisation for the challenging case of partial permutations, which plays an important role for the problem of matching multiple objects (e.g. images or shapes). The term synchronisation refers to the property that the set of pairwise matchings is cycle-consistent, i.e. in the full matching case all compositions of pairwise matchings over cycles must be equal to the identity. Motivated by clustering and matrix factorisation perspectives of cycle-consistency, we derive an algorithm to tackle the permutation synchronisation problem based on non-negative factorisations. In order to deal with the inherent non-convexity of the permutation synchronisation problem, we use an initialisation procedure based on a novel rotation scheme applied to the solution of the spectral relaxation. Moreover, this rotation scheme facilitates a convenient Euclidean projection to obtain a binary solution after solving our relaxed problem. In contrast to state-of-the-art methods, our approach is guaranteed to produce cycle-consistent results. We experimentally demonstrate the efficacy of our method and show that it achieves better results compared to existing methods.