Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Synchronisation of partial multi-matchings via non-negative factorisations

Bernard, Florian ; Thunberg, Johan LU ; Goncalves, Jorge and Theobalt, Christian (2019) In Pattern Recognition 92. p.146-155
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... (More)
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.

(Less)
Please use this url to cite or link to this publication:
author
; ; and
publishing date
type
Contribution to journal
publication status
published
subject
in
Pattern Recognition
volume
92
pages
10 pages
publisher
Elsevier
external identifiers
  • scopus:85063620765
ISSN
0031-3203
DOI
10.1016/j.patcog.2019.03.021
language
Unknown
LU publication?
no
id
4dfa5601-3544-42be-92e1-6b9451e1730c
date added to LUP
2024-09-05 14:05:12
date last changed
2024-09-16 18:06:43
@article{4dfa5601-3544-42be-92e1-6b9451e1730c,
  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.<br/><br/>}},
  author       = {{Bernard, Florian and Thunberg, Johan and Goncalves, Jorge and Theobalt, Christian}},
  issn         = {{0031-3203}},
  language     = {{und}},
  pages        = {{146--155}},
  publisher    = {{Elsevier}},
  series       = {{Pattern Recognition}},
  title        = {{Synchronisation of partial multi-matchings via non-negative factorisations}},
  url          = {{http://dx.doi.org/10.1016/j.patcog.2019.03.021}},
  doi          = {{10.1016/j.patcog.2019.03.021}},
  volume       = {{92}},
  year         = {{2019}},
}