Markerless point cloud registration with keypoint-based 4-points congruent sets

Abstract. This paper addresses the registration of LiDAR point clouds. More specifically, we present an automatic method for markerless registration of two such point clouds given in arbitrary local scan coordinates – i.e. without simplifying assumptions such as a common up-vector. Clearly, the critical step of the registration is to find a coarse initial alignment, to be refined with established local methods for fine registration, such as ICP or least-squares surface matching. The proposed approach builds on the 4-Points Congruent Sets (4PCS) algorithm (Aiger et al., 2008), a popular registration tool in computer graphics, and extends it to better deal with the specific challenges of LiDAR data. The main limitations of the original 4PCS method in that context are (i) that it does not cope well with strongly varying point densities, such as they routinely occur in laser scans due to the constant angular sampling from different viewpoints; and (ii) that to remain efficient, huge LiDAR point clouds must be down-sampled so heavily that approximate point-to-point correspondence can no longer be guaranteed. To overcome these drawbacks we propose not to apply 4PCS to the original point cloud (respectively, a randomly or regularly subsampled version of it), but rather to represent the point clouds with sets of distinctive 3D keypoints, and run (a slightly modified) 4PCS on the keypoint sets. The resulting combination, termed Keypoint-based 4-Points Congruent Sets (K-4PCS), proves to be very reliable: with suitable parameter settings, tests in indoor as well as outdoor environments yield 100% success rates.