A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching
A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching
复制标题
DOI：
10.1109/cvpr.2017.747
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
P. Swoboda;C. Rother;Hassan Abu Alhaija;Dagmar Kainmüller;Bogdan Savchynskyy
中科院分区：
文献类型：
--
作者：
P. Swoboda;C. Rother;Hassan Abu Alhaija;Dagmar Kainmüller;Bogdan Savchynskyy
我们研究二次分配问题，在计算机视觉中也称为图匹配。这个问题的两个主要解决方案优化了拉格朗日分解算法，并使用次梯度和对偶上升（也称为消息传递）更新。我们进一步探索这个方向，并提出了几个额外的拉格朗日松弛的图匹配问题的沿着与相应的算法，这都是基于一个共同的双上升框架。我们广泛的实证评估提供了一些理论见解，并提出了一个新的国家的最先进的任何时候所考虑的问题求解器。我们对最先进技术的改进在一个新的数据集上特别明显，该数据集具有大规模稀疏问题实例，每个实例包含超过500个图形节点。
We study the quadratic assignment problem, in computer vision also known as graph matching. Two leading solvers for this problem optimize the Lagrange decomposition duals with sub-gradient and dual ascent (also known as message passing) updates. We explore this direction further and propose several additional Lagrangean relaxations of the graph matching problem along with corresponding algorithms, which are all based on a common dual ascent framework. Our extensive empirical evaluation gives several theoretical insights and suggests a new state-of-the-art anytime solver for the considered problem. Our improvement over state-of-the-art is particularly visible on a new dataset with large-scale sparse problem instances containing more than 500 graph nodes each.