A Polyhedral Annexation Algorithm for Aligning Partially Overlapping Point Sets

Abstract

Point set registration aims to find a spatial transformation that best aligns two point sets. Algorithms which can handle partial overlap and are invariant to the corresponding transformations are particularly desirable. To this end, we first reduce the objective of the robust point matching (RPM) algorithm to a function of a low dimensional variable. The resulting function is nevertheless only concave over a finite region including the feasible region, which prohibits the use of the popular branch-and-bound (BnB) algorithm. To address this issue, we propose to use the polyhedral annexation (PA) algorithm for optimization, which enjoys the merit of only operating within the concavity region of the objective function. The proposed algorithm does not need regularization on transformation and thus is invariant to the corresponding transformation. It is also approximately globally optimal and thus is guaranteed to be robust. Moreover, its most computationally expensive subroutine is a linear assignment problem which can be efficiently solved. Experimental results demonstrate better robustness of the proposed method over the state-of-the-art algorithms. Our method’s matching error is on average 44% (resp. 65%) lower than that of Go-ICP in 2D (resp. 3D) synthesized tests. It is also efficient when the number of transformation parameters is small.

Keywords

• Point set registration
• branch-and-bound
• concave optimization
• polyhedral annexation