An Efficient Multilinear Optimization Framework for Hypergraph Matching
This work provides an incremental improvement in efficiency for hypergraph matching, which is used for correspondence problems in computer vision.
The paper tackles the NP-hard hypergraph matching problem in computer vision by proposing a third-order optimization scheme that avoids a previous lifting step, achieving the same guarantees and performance as the fourth-order method but with a two-fold speed improvement, and introduces a homotopy method for further performance gains.
Hypergraph matching has recently become a popular approach for solving correspondence problems in computer vision as it allows to integrate higher-order geometric information. Hypergraph matching can be formulated as a third-order optimization problem subject to the assignment constraints which turns out to be NP-hard. In recent work, we have proposed an algorithm for hypergraph matching which first lifts the third-order problem to a fourth-order problem and then solves the fourth-order problem via optimization of the corresponding multilinear form. This leads to a tensor block coordinate ascent scheme which has the guarantee of providing monotonic ascent in the original matching score function and leads to state-of-the-art performance both in terms of achieved matching score and accuracy. In this paper we show that the lifting step to a fourth-order problem can be avoided yielding a third-order scheme with the same guarantees and performance but being two times faster. Moreover, we introduce a homotopy type method which further improves the performance.