Title :
A flexible tensor block coordinate ascent scheme for hypergraph matching
Author :
Quynh Nguyen Ngoc;Antoine Gautier;Matthias Hein
Author_Institution :
Max Planck Institute for Informatics, Saarbrü
fDate :
6/1/2015 12:00:00 AM
Abstract :
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.
Keywords :
"Tensile stress","Optimization","Noise","Approximation algorithms","Symmetric matrices","Computer vision","Accuracy"
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2015 IEEE Conference on
Electronic_ISBN :
1063-6919
DOI :
10.1109/CVPR.2015.7299164