Automatic registration of partially overlapping terrestrial laser scanner point clouds

This project homepage summarizes the results of the research done at the Institute of Geodesy and Photogrammetry on the topic of Automated Registration of Terrestrial Laser Scanner (TLS) Point Clouds. In addition to some information about the different approaches and the respective papers, source codes and test data sets are here provided.

Enlarged view: Example image for automatic registration of partially overlapping terrestrial laser scanner point clouds
Example of a pairwise registration of laser scans.

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.

Plane-based registration workflow
Plane-based registration workflow
Enlarged view: Matched (virtual) tiepoints
Matched (virtual) tiepoints
Enlarged view: Extracted planes in 2D representation (top) and in 3D space (bottom)
Extracted planes in 2D representation (top) and in 3D space (bottom)

Keypoint-based Registration via 4-Points Congruent Sets

external page Keypoint-based 4-Points Congruent Sets – Automated marker-less Registration of Laser Scans
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.

Enlarged view: Workflow for pairwise K-4PCS registration
Workflow for pairwise K-4PCS registration
Enlarged view: Basic Idea of 4-Points Congruent Sets matching
Basic Idea of 4-Points Congruent Sets matching
Enlarged view: 3D keypoint extraction
3D keypoint extraction

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 page Point Cloud Library (PCL) within the scope of this project.
A sample program together with the necessary datasets can be found Download here (ZIP, 259.5 MB).

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 Download here (ZIP, 10 KB). 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 page Globally Consistent Registration of Terrestrial Laser Scans via Graph Optimization
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.

Enlarged view: Workflow of global scan registration
Workflow of global scan registration
Enlarged view: Global consistent alignment via graph optimiziation
Global consistent alignment via graph optimiziation

Source code and sample program

The source code of the proposed method can be found Download here (ZIP, 14 KB). The method requires parts of the open-source external page Point Cloud Library (PCL). The algorithm itself is written in PCL style (templated, header-only), but is not part of the main trunk of the library and have to be added manually to a project. It additionally requires the open-source library external page OpenGM. A sample program of how to use the method together with the required datasets is provided Download here (ZIP, 323.6 MB).

In the following, all datasets which have been used for testing the method - including the groundtruth (pairwise transformation matrices) - are provided:

  • Download Office (ZIP, 293.7 MB): An indoor dataset with 5 scans of a typical office room. All scans overlap each other sufficiently for matching (fully connected scan graph)
  • Download Arch (ZIP, 873 MB): Typical dataset to acuqire data of an object of interest (here: Roman arch). 5 Scans are placed around the arch. The scans are acquired with rather low overlap (30-40%) and feature vegetation and artifacts (moving people).
  • Download Trees (ZIP, 1.2 GB): 6 scans acquired in a forest with large amount of underwood and medium overlap. The dataset is a rather extreme case of scanning, but shows the great potential of the proposed method.
  • Download Courtyard (ZIP, 1.2 GB): The data set consists of 8 scans acquired in the courtyard of an ancient tomb. Because of the low vertical variation, lack of vertical objects within the scans, the dataset represents projects for the generation of DTMs out of laser scans.
  • Download Facade (ZIP, 1.4 GB): 8 scans to model an urban scene with focus on a sepcific facade. The scans have rather large overlap and feature large amount of artifacts cause by moving cars and people.
  • Facility: Due to legal restrictions, the data of the facility dataset can not be provided.