Keypoint-based 4-Points Congruent Sets – Automated marker-less registration of laser scans

Abstract

We propose a method to automatically register two point clouds acquired with a terrestrial laser scanner without placing any markers in the scene. What makes this task challenging are the strongly varying point densities caused by the line-of-sight measurement principle, and the huge amount of data. The first property leads to low point densities in potential overlap areas with scans taken from different viewpoints while the latter calls for highly efficient methods in terms of runtime and memory requirements.

A crucial yet largely unsolved step is the initial coarse alignment of two scans without any simplifying assumptions, that is, point clouds are given in arbitrary local coordinates and no knowledge about their relative orientation is available. Once coarse alignment has been solved, scans can easily be fine-registered with standard methods like least-squares surface or Iterative Closest Point matching. In order to drastically thin out the original point clouds while retaining characteristic features, we resort to extracting 3D keypoints. Such clouds of keypoints, which can be viewed as a sparse but nevertheless discriminative representation of the original scans, are then used as input to a very efficient matching method originally developed in computer graphics, called 4-Points Congruent Sets (4PCS) algorithm. We adapt the 4PCS matching approach to better suit the characteristics of laser scans.

The resulting Keypoint-based 4-Points Congruent Sets (K-4PCS) method is extensively evaluated on challenging indoor and outdoor scans. Beyond the evaluation on real terrestrial laser scans, we also perform experiments with simulated indoor scenes, paying particular attention to the sensitivity of the approach with respect to highly symmetric scenes.

Introduction

Airborne, mobile, and static terrestrial laser scanners are standard devices to acquire 3D data for a wide range of applications. In this work we deal with LiDAR point clouds of static terrestrial laser scanners (TLS) that are commonly used in surveying, archeology, manufacturing, etc. Typically, multiple scans from different viewpoints are needed to fully cover large outdoor objects or complex indoor facilities in full detail. A prerequisite for any further processing of such data, like semantic classification or complete 3D reconstruction, is the relative orientation of all scans. The registration puts all scans into a common coordinate frame, thus assembling the scanned object of interest from the individual scans.

The industry standard at present is to place artificial markers in the scene during the measurement campaign. Corresponding markers (or targets) that are visible in at least two scans are then extracted either manually or automatically (e.g., Akca, 2003, Franaszek et al., 2009) to determine the relative orientation of the scans. This procedure is rather time-consuming, markers must remain stable during the measurement campaign and they should be distributed in such a way that no ill-defined geometric constellations arise. In addition, they inevitably occlude small parts of the scene and they usually have to be removed during post-processing because they are not acceptable in the final product. To circumvent artificial markers altogether, quite some effort has been spent on finding fully automated marker-less methods for LiDAR point cloud registration. In contrast to point clouds computed via dense matching of images, the scale is inherently known in LiDAR point clouds, since the sensor directly measures distances. Therefore, registration of LiDAR point clouds can be solved with a rigid-body transformation with six degrees of freedom. Typically, such transformation parameters are estimated in a two-step procedure: An initial coarse registration roughly aligns scans with a precision that avoids the following fine registration to get stuck in a local minimum. It turns out that the first step (coarse registration) is much harder than the second (fine registration).

Various solutions for fine registration of scans exist. The most common approach today certainly is the Iterative Closest Point (ICP) algorithm introduced in the seminal works of Besl and McKay, 1992, Chen and Medioni, 1992, Zhang, 1994, and since then refined in different ways (e.g., Bergevin et al., 1996, Bae and Lichti, 2004, Minguez et al., 2006, Censi, 2008). The basic principle of ICP is to minimize the Euclidean distances between nearby points. ICP solves this problem iteratively, by first establishing point-to-point correspondences, and second estimating the transformation parameters. After applying the transformation to all points, point correspondences are sought again and a new, refined set of transformation parameters is estimated. This procedure is then repeated until convergence.

A general property of all such methods is that they involve a non-convex objective function which is optimized locally. Clearly, fine registration without a sufficiently precise coarse alignment is therefore prone to get stuck in local minima. More precisely, if raw scans are not well aligned initially, a sufficiently precise transformation into a common reference frame can hardly be found because the convergence basin of the non-convex objective function is too small. Please refer to Pottmann et al., 2006, Bae, 2009 for comprehensive investigations on the convergence properties of such techniques. An idea that naturally comes into mind is thus to first coarsely align both raw scans so that this initial, rough solution is inside the ICP convergence basin. ICP then takes over and accomplishes fine-registration.

Here, we follow this line of thought and propose a fully automated, marker-less, coarse registration approach, where the coarsely aligned point clouds serve as input to standard ICP. What makes this task challenging are (i) the huge amount of data (millions of points), which calls for computationally efficient techniques, (ii) the typically large baselines between adjacent scanning viewpoints (to limit time and costs in the field) and (iii) the quadratic decrease of the point density with distance from the scanner (due to the angular sampling of scanning LiDAR devices). The latter causes different point densities on the same surfaces in different scans. As we will see later on in this paper, this property calls for custom-designed processing steps: standard approaches from computer vision or computer graphics cannot be applied directly because they usually assume approximately even point distributions within and between different scans.

In this paper we adapt the 4-Points Congruent Sets (4PCS) approach for coarse registration, proposed by Aiger et al. (2008), to the aforementioned challenges. To keep registration computationally tractable we downsample raw scans and represent them with a sparse cloud of 3D keypoints. We test two different kinds of keypoints, the 3D Difference-of-Gaussians (DoG) detector and the 3D Harris corner detector. The first relies on LiDAR intensities, whereas the second fires at distinct geometrical structures. In contrast to heavily downsampling point clouds at random, less aggressive downsampling followed by keypoint extraction better preserves salient features of the scene and thus offers better repeatability across scans. We call the combined method, which utilizes 3D keypoints as input to a (slightly modified) 4PCS algorithm Keypoint based 4-Points Congruent Sets (K-4PCS). We plan to release the test data and the source code of the proposed method – integrated in the open-source Point Cloud Library (PCL, Rusu and Cousins, 2011) – after publication.