IEEE Trans Pattern Anal Mach Intell. 2017 Jul;39(7):1281-1293. doi: 10.1109/TPAMI.2016.2603988. Epub 2016 Aug 29.
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.
尽管稳健点匹配算法已被证明对于非刚性配准是有效的，但所采用的确定性退火优化技术存在几个问题。首先，它不是全局最优的，需要对空间变换进行正则化以获得良好的匹配结果。其次，它倾向于对齐两个点集的质心。为了解决这些问题，我们提出了一种全局最优算法，用于在每个模型点在场景集中都有对应点的情况下解决稳健点匹配问题。通过消除变换变量，我们表明原始匹配问题被简化为具有低秩 Hessian 矩阵的凹二次分配问题。这便于使用大规模全局优化技术。我们提出了一种修改后的标准矩形分支定界算法来解决由此产生的问题，其中同时细分多个矩形以增加包含全局最优解的矩形缩小的机会。此外，我们提出了一种有效的下界方案，具有线性分配公式，可以有效地求解。在合成和真实数据集上的广泛实验表明，与最先进的方法相比，该算法在抗离群值、匹配精度和运行时间方面表现良好。
