Title: A Concave Optimization Algorithm for Matching Partially Overlapping Point Sets,
Abstract: Point matching refers to the process of finding spatial transformation and
correspondences between two sets of points. In this paper, we focus on the case
that there is only partial overlap between two point sets. Following the
approach of the robust point matching method, we model point matching as a
mixed linear assignment-least square problem and show that after eliminating
the transformation variable, the resulting problem of minimization with respect
to point correspondence is a concave optimization problem. Furthermore, this
problem has the property that the objective function can be converted into a
form with few nonlinear terms via a linear transformation. Based on these
properties, we employ the branch-and-bound (BnB) algorithm to optimize the
resulting problem where the dimension of the search space is small. To further
improve efficiency of the BnB algorithm where computation of the lower bound is
the bottleneck, we propose a new lower bounding scheme which has a
k-cardinality linear assignment formulation and can be efficiently solved.
Experimental results show that the proposed algorithm outperforms
state-of-the-art methods in terms of robustness to disturbances and point
matching accuracy.