  In many applications, we need algorithms which can align partially
overlapping point sets and are invariant to the corresponding transformations.
In this work, a method possessing such properties is realized by minimizing the
objective of the robust point matching (RPM) algorithm. We first show that the
RPM objective is a cubic polynomial. We then utilize the convex envelopes of
trilinear and bilinear monomials to derive its lower bound function. The
resulting lower bound problem has the merit that it can be efficiently solved
via linear assignment and low dimensional convex quadratic programming. We next
develop a branch-and-bound (BnB) algorithm which only branches over the
transformation variables and runs efficiently. Experimental results
demonstrated better robustness of the proposed method against non-rigid
deformation, positional noise and outliers in case that outliers are not mixed
with inliers when compared with the state-of-the-art approaches. They also
showed that it has competitive efficiency and scales well with problem size.
