Higher-order Projected Power Iterations for Scalable Multi-Matching
This addresses the challenge of robustly matching multiple objects in real-world settings for vision and graphics applications, offering a scalable solution to a previously computationally limited problem.
The paper tackles the multi-matching problem in vision and graphics by introducing a Higher-order Projected Power Iteration method that efficiently scales to tens of thousands of points, incorporates geometric consistency, and guarantees cycle-consistent matchings, showing superiority over existing methods in experiments.
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.