A Flexible Tensor Block Coordinate Ascent Scheme for Hypergraph Matching
This work addresses the problem of improving matching accuracy in computer vision for applications like image alignment, though it appears incremental as it builds on existing hypergraph matching methods.
The paper tackles the hypergraph matching problem for image correspondence by proposing a tensor block coordinate ascent framework with monotonic ascent guarantees, and shows that the new algorithms outperform previous work in matching scores and accuracy, especially in challenging settings with high outliers and noise.
The estimation of correspondences between two images resp. point sets is a core problem in computer vision. One way to formulate the problem is graph matching leading to the quadratic assignment problem which is NP-hard. Several so called second order methods have been proposed to solve this problem. In recent years hypergraph matching leading to a third order problem became popular as it allows for better integration of geometric information. For most of these third order algorithms no theoretical guarantees are known. In this paper we propose a general framework for tensor block coordinate ascent methods for hypergraph matching. We propose two algorithms which both come along with the guarantee of monotonic ascent in the matching score on the set of discrete assignment matrices. In the experiments we show that our new algorithms outperform previous work both in terms of achieving better matching scores and matching accuracy. This holds in particular for very challenging settings where one has a high number of outliers and other forms of noise.