Go-ICP: A Globally Optimal Solution to 3D ICP Point-Set Registration

The Iterative Closest Point (ICP) algorithm is one of the most widely usedmethods for point-set registration. However, being based on local iterativeoptimization, ICP is known to be susceptible to local minima. Its performancecritically relies on the quality of the initialization and only localoptimality is guaranteed. This paper presents the first globally optimalalgorithm, named Go-ICP, for Euclidean (rigid) registration of two 3Dpoint-sets under the L2 error metric defined in ICP. The Go-ICP method is basedon a branch-and-bound (BnB) scheme that searches the entire 3D motion spaceSE(3). By exploiting the special structure of SE(3) geometry, we derive novelupper and lower bounds for the registration error function. Local ICP isintegrated into the BnB scheme, which speeds up the new method whileguaranteeing global optimality. We also discuss extensions, addressing theissue of outlier robustness. The evaluation demonstrates that the proposedmethod is able to produce reliable registration results regardless of theinitialization. Go-ICP can be applied in scenarios where an optimal solution isdesirable or where a good initialization is not always available.