Abstract: This paper proposes a globally optimal algorithm for similarity invariant shape matching in a scene. A spanning tree is used to represent the shape and the problem of matching is converted into that of locating this tree in the scene point set. Spatial transformations of individual tree edges are forced to be consistent by minimizing their differences from a global one. The objective function is reduced to a concave quadratic function of edge matching variables with a low rank Hessian matrix, which is then minimized by the branch and bound algorithm with good convergence property. It also presents a novel lower bounding scheme which can be efficiently solved by dynamic programming. Experimental results demonstrate the robustness of the proposed method over state-of-the-art methods, particularly for the challenging tasks where the two point sets only partially overlap.

Key words: global optimization, branch and bound, shape matching, dynamic programming

摘要： 提出一种全局优化算法，用于相似不变地在一场景中匹配一个形状。该算法采用支撑树来表示形状，匹配问题被转化成在目标点集中定位这棵树的问题。通过最小化边的空间变换同一个全局空间变换之间的差别，树的每条边的空间变换被强制是一致的。目标函数归结为一个关于边匹配变量的凹二次函数。该函数具有低秩Hessian矩阵，可以通过分支定界法快速地解出。还提出一种新颖的求下界的方案，它可以通过动态规划高效地解出。实验结果表明，所提算法相比主流算法有更好的鲁棒性，特别对于两点集只有部分重叠的情形。

关键词: 全局优化, 分支定界法, 形状匹配, 动态规划