We consider the incomplete multi-graph matching problem, which is a
generalization of the NP-hard quadratic assignment problem for matching
multiple finite sets. Multi-graph matching plays a central role in computer
vision, e.g., for matching images or shapes, so that a number of dedicated
optimization techniques have been proposed. While the closely related NP-hard
multi-dimensional assignment problem (MDAP) has been studied for decades in the
operations research community, it only considers complete matchings and has a
different cost structure. We bridge this gap and transfer well-known
approximation algorithms for the MDAP to incomplete multi-graph matching. To
this end, we revisit respective algorithms, adapt them to incomplete
multi-graph matching, and propose their extended and parallelized versions. Our
experimental validation shows that our new method substantially outperforms the
previous state of the art in terms of objective and runtime. Our algorithm
matches, for example, 29 images with more than 500 keypoints each in less than
two minutes, whereas the fastest considered competitor requires at least half
an hour while producing far worse results.

我们研究了不完全多图匹配问题，该问题是配对多个有限集合的 NP 难问题的推广，多图匹配在计算机视觉中起着关键作用，已经提出了许多专门的优化技术。我们填补了这一差距，并将已知的多维分配问题近似算法转化为不完全多图匹配问题。通过实验证明，我们的新方法在目标和运行时间方面显著优于以前的技术水平。我们的算法能够在两分钟内匹配超过 500 个关键点的 29 个图像，而考虑的最快竞争方法至少需要半小时，同时产生了更差的结果。