An Efficient Globally Optimal Algorithm for Asymmetric Point Matching
An Efficient Globally Optimal Algorithm for Asymmetric Point Matching
复制标题
DOI：
10.1109/tpami.2016.2603988
复制
发表时间：
2017-07
影响因子：
23.6
通讯作者：
W. Lian;Lei Zhang;Ming-Hsuan Yang
中科院分区：
文献类型：
--
作者：
W. Lian;Lei Zhang;Ming-Hsuan Yang
虽然鲁棒点匹配算法已被证明是有效的非刚性配准，有几个问题，采用确定性退火优化技术。首先，它不是全局最优的，需要对空间变换进行正则化以获得良好的匹配结果。其次，它倾向于对齐两个点集的质心。为了解决这些问题，我们提出了一个全局最优的算法的鲁棒点匹配问题的情况下，每个模型点有一个场景集的副本。通过消除变换变量，我们表明，原来的匹配问题减少到凹二次分配问题的目标函数具有低秩Hessian矩阵。这有助于使用大规模全局优化技术。我们提出了一种改进的正常矩形分支定界算法来解决由此产生的问题，多个矩形同时细分，以增加收缩的机会，包含全局最优解的矩形。此外，我们提出了一个有效的下界计划，它具有线性分配制定，可以有效地解决。在合成和真实的数据集上进行的大量实验表明，该算法在对离群值的鲁棒性、匹配准确度和运行时间方面优于现有方法。
Although the robust point matching algorithm has been demonstrated to be effective for non-rigid registration, there are several issues with the adopted deterministic annealing optimization technique. First, it is not globally optimal and regularization on the spatial transformation is needed for good matching results. Second, it tends to align the mass centers of two point sets. To address these issues, we propose a globally optimal algorithm for the robust point matching problem in the case that each model point has a counterpart in scene set. By eliminating the transformation variables, we show that the original matching problem is reduced to a concave quadratic assignment problem where the objective function has a low rank Hessian matrix. This facilitates the use of large scale global optimization techniques. We propose a modified normal rectangular branch-and-bound algorithm to solve the resulting problem where multiple rectangles are simultaneously subdivided to increase the chance of shrinking the rectangle containing the global optimal solution. In addition, we present an efficient lower bounding scheme which has a linear assignment formulation and can be efficiently solved. Extensive experiments on synthetic and real datasets demonstrate the proposed algorithm performs favorably against the state-of-the-art methods in terms of robustness to outliers, matching accuracy, and run-time.