Detecting Changes and Finding Collisions in 3D Point Clouds

Data Structures and Algorithms for Post-Processing Large Datasets

Johannes Schauer Marin Rodrigues <>

Informatics VII: Robotics and Telematics, Julius-Maximilians-University, Am Hubland, Würzburg 97074, Germany


Affordable prices for 3D laser range finders and mature software solutions for registering multiple point clouds in a common coordinate system paved the way for new areas of application for 3D point clouds. Nowadays we see 3D laser scanners being used not only by digital surveying experts but also by law enforcement officials, construction workers or archaeologists. Whether the purpose is digitizing factory production lines, preserving historic sites as digital heritage or recording environments for gaming or virtual reality applications -- it is hard to imagine a scenario in which the final point cloud must also contain the points of "moving" objects like factory workers, pedestrians, cars or flocks of birds. For most post-processing tasks, moving objects are undesirable not least because moving objects will appear in scans multiple times or are distorted due to their motion relative to the scanner rotation.

The main contributions of this work are two postprocessing steps for already registered 3D point clouds. The first method is a new change detection approach based on a voxel grid which allows partitioning the input points into static and dynamic points using explicit change detection and subsequently remove the latter for a "cleaned" point cloud. The second method uses this cleaned point cloud as input for detecting collisions between points of the environment point cloud and a point cloud of a model that is moved through the scene.

Our approach on explicit change detection is compared to the state of the art using multiple datasets including the popular KITTI dataset. We show how our solution achieves similar or better F1-scores than an existing solution while at the same time being faster.

To detect collisions we do not produce a mesh but approximate the raw point cloud data by spheres or cylindrical volumes. We show how our data structures allow efficient nearest neighbor queries that make our CPU-only approach comparable to a massively-parallel algorithm running on a GPU. The utilized algorithms and data structures are discussed in detail. All our software is freely available for download under the terms of the GNU General Public license. Most of the datasets used in this thesis are freely available as well. We provide shell scripts that allow one to directly reproduce the quantitative results shown in this thesis for easy verification of our findings.


Full pdf: thesis.pdf (R markdown source:

Presentation slides: presentation.pdf (Libre Office source: presentation.odp)


Schauer Marin Rodrigues, J. (2020). Detecting Changes and Finding Collisions in 3D Point Clouds - Data Structures and Algorithms for Post-Processing Large Datasets. Schriftenreihe Würzburger Forschungsberichte in Robotik und Telematik, Band 20.

DOI: 10.25972/OPUS-21428
ISSN: 1868-7474 (online)
ISSN: 1868-7466 (print)
ISBN: 978-3-945459-32-4 (online)

Related work