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

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