Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Hippi: Higher-order projected power iterations for scalable multi-matching

Bernard, Florian ; Thunberg, Johan LU ; Swoboda, Paul and Theobalt, Christian (2019) 2019 IEEE/CVF International Conference on Computer Vision (ICCV) p.10284-10293
Abstract
The matching of multiple objects (e.g. shapes or images) is a fundamental problem in vision and graphics. In order to robustly handle ambiguities, noise and repetitive patterns in challenging real-world settings, it is essential to take geometric consistency between points into account. Computationally, the multi-matching problem is difficult. It can be phrased as simultaneously solving multiple (NP-hard) quadratic assignment problems (QAPs) that are coupled via cycle-consistency constraints. The main limitations of existing multi-matching methods are that they either ignore geometric consistency and thus have limited robustness, or they are restricted to small-scale problems due to their (relatively) high computational cost. We address... (More)
The matching of multiple objects (e.g. shapes or images) is a fundamental problem in vision and graphics. In order to robustly handle ambiguities, noise and repetitive patterns in challenging real-world settings, it is essential to take geometric consistency between points into account. Computationally, the multi-matching problem is difficult. It can be phrased as simultaneously solving multiple (NP-hard) quadratic assignment problems (QAPs) that are coupled via cycle-consistency constraints. The main limitations of existing multi-matching methods are that they either ignore geometric consistency and thus have limited robustness, or they are restricted to small-scale problems due to their (relatively) high computational cost. We address these shortcomings by introducing a Higher-order Projected Power Iteration method, which is (i) efficient and scales to tens of thousands of points, (ii) straightforward to implement, (iii) able to incorporate geometric consistency, (iv) guarantees cycle-consistent multi-matchings, and (iv) comes with theoretical convergence guarantees. Experimentally we show that our approach is superior to existing methods. (Less)
Please use this url to cite or link to this publication:
author
; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2019 IEEE/CVF International Conference on Computer Vision (ICCV)
pages
10 pages
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
conference name
2019 IEEE/CVF International Conference on Computer Vision (ICCV)
conference location
Seoul, Korea, Republic of
conference dates
2019-10-27 - 2019-11-02
external identifiers
  • scopus:85081928419
ISBN
978-1-7281-4803-8
DOI
10.1109/ICCV.2019.01038
language
English
LU publication?
no
id
7786b3c7-b9c9-4499-859c-2d53d1241843
date added to LUP
2024-09-05 14:00:28
date last changed
2024-09-16 18:00:25
@inproceedings{7786b3c7-b9c9-4499-859c-2d53d1241843,
  abstract     = {{The matching of multiple objects (e.g. shapes or images) is a fundamental problem in vision and graphics. In order to robustly handle ambiguities, noise and repetitive patterns in challenging real-world settings, it is essential to take geometric consistency between points into account. Computationally, the multi-matching problem is difficult. It can be phrased as simultaneously solving multiple (NP-hard) quadratic assignment problems (QAPs) that are coupled via cycle-consistency constraints. The main limitations of existing multi-matching methods are that they either ignore geometric consistency and thus have limited robustness, or they are restricted to small-scale problems due to their (relatively) high computational cost. We address these shortcomings by introducing a Higher-order Projected Power Iteration method, which is (i) efficient and scales to tens of thousands of points, (ii) straightforward to implement, (iii) able to incorporate geometric consistency, (iv) guarantees cycle-consistent multi-matchings, and (iv) comes with theoretical convergence guarantees. Experimentally we show that our approach is superior to existing methods.}},
  author       = {{Bernard, Florian and Thunberg, Johan and Swoboda, Paul and Theobalt, Christian}},
  booktitle    = {{2019 IEEE/CVF International Conference on Computer Vision (ICCV)}},
  isbn         = {{978-1-7281-4803-8}},
  language     = {{eng}},
  pages        = {{10284--10293}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  title        = {{Hippi: Higher-order projected power iterations for scalable multi-matching}},
  url          = {{http://dx.doi.org/10.1109/ICCV.2019.01038}},
  doi          = {{10.1109/ICCV.2019.01038}},
  year         = {{2019}},
}