Automatic registration of partially overlapping terrestrial laser scanner point clouds

Plane-based Point Cloud Registration

Automatic Registration of Terrestrial Laser Scanner Point Clouds using Natural Planar Surfaces
Pascal Willy Theiler, Konrad Schindler
ISPRS Annals, 22nd ISPRS Congress, Melbourne, Australia, 2012

Abstract: Terrestrial laser scanners have become a standard piece of surveying equipment, used in diverse fields like geomatics, manufacturing and medicine. However, the processing of today’s large point clouds is time-consuming, cumbersome and not automated enough. A basic step of post-processing is the registration of scans from different viewpoints. At present this is still done using artificial targets or tiepoints, mostly by manual clicking. The aim of this registration step is a coarse alignment, which can then be improved with the existing algorithm for fine registration. The focus of this paper is to provide such a coarse registration in a fully automatic fashion, and without placing any target objects in the scene. The basic idea is to use virtual tiepoints generated by intersecting planar surfaces in the scene. Such planes are detected in the data with RANSAC and optimally fitted using least squares estimation. Due to the huge amount of recorded points, planes can be determined very accurately, resulting in well-defined tiepoints. Given two sets of potential tiepoints recovered in two different scans, registration is performed by searching for the assignment which preserves the geometric configuration of the largest possible subset of all tiepoints. Since exhaustive search over all possible assignments is intractable even for moderate numbers of points, the search is guided by matching individual pairs of tiepoints with the help of a novel descriptor based on the properties of a point’s parent planes. xperiments show that the proposed method is able to successfully coarse register TLS point clouds without the need for artificial targets.

Keypoint-based Registration via 4-Points Congruent Sets

external pageKeypoint-based 4-Points Congruent Sets – Automated marker-less Registration of Laser Scanscall_made
Pascal Willy Theiler, Jan Dirk Wegner, Konrad Schindler
ISPRS Journal of Photogrammetry and Remote Sensing, Volume 96, 2014

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.

Source code and sample program:

The source code of the Keypoint-based 4-Points Congruent Sets as well as the stand-alone 4-Points Congruent Sets matching method has been made available in the open-source external pagePoint Cloud Librarycall_made (PCL) within the scope of this project.
A sample program together with the necessary datasets can be found Downloadhere (ZIP, 259.5 MB)vertical_align_bottom.

Note, the standard voxel grid filter of PCL fails due to overflowing integers if large point clouds and small voxel sizes are involved. To avoid this error, we have developed an extended filter strategy which uses an octree structure - filtering is then carried out in all octree leaves seperately. The implementations of this method can be found Downloadhere (ZIP, 10 KB)vertical_align_bottom. They are written in PCL style (templated, header-only), but are not part of the main trunk of the library and have to be added manually to a project.

Other publications regarding K-4PCS:

Fast registration of laser scans with 4-points congruent sets – what works and what doesn’t
Pascal Willy Theiler, Jan Dirk Wegner, Konrad Schindler
Photogrammetric Computer Vision (PCV), ISPRS Technical Commission III Midterm Symposium, Zurich, Switzerland, 2014

Markerless point cloud registration with keypoint-based 4-points congruent sets
Pascal Willy Theiler, Jan Dirk Wegner, Konrad Schindler
ISPRS Workshop on Laser Scanning, Antalya, Turkey, 2013

Globally Consistent Registration of Multiple Point Clouds

external pageGlobally Consistent Registration of Terrestrial Laser Scans via Graph Optimizationcall_made
Pascal Willy Theiler, Jan Dirk Wegner, Konrad Schindler
ISPRS Journal of Photogrammetry and Remote Sensing, Volume 109, 2015

Abstract: In this paper we present a framework for the automatic registration of multiple terrestrial laser scans. The proposed method can handle arbitrary point clouds with reasonable pairwise overlap, without knowledge about their initial orientation and without the need for artificial markers or other specific objects. The framework is divided into a coarse and a fine registration part, which each start with pairwise registration and then enforce consistent global alignment across all scans. While we put forward a complete, functional registration system, the novel contribution of the paper lies in the coarse global alignment step. Merging multiple scans into a consistent network creates loops along which the relative transformations must add up. We pose the task of finding a global alignment as picking the best candidates from a set of putative pairwise registrations, such that they satisfy the loop constraints. This yields a discrete optimization problem that can be solved efficiently with modern combinatorial methods. Having found a coarse global alignment in this way, the framework proceeds by pairwise refinement with standard ICP, followed by global refinement to evenly spread the residual errors. The framework was tested on six challenging, real-world datasets. The discrete global alignment step effectively detects, removes and corrects failures of the pairwise registration procedure, finally producing a globally consistent coarse scan network which can be used as initial guess for the highly non-convex refinement. Our overall system reaches success rates close to 100% at acceptable runtimes <1 h, even in challenging conditions such as scanning in the forest.