Scan Registration using NDT and Point Cloud Clustering

Date:30 Oct, 2015

Scan Registration using NDT and Point Cloud Clustering

The Normal Distributions Transform (NDT) algorithm is a promising method for scan registration, however many issues with the NDT approach exist, including a poor convergence basin, discontinuities in the NDT cost function, and unreliable pose estimation in sparse, outdoor environments. This research propses methods to overcome the shortcomings of the NDT algorithm, in both 2D and 3D scenarios. To improve the convergence basin of NDT for 2D scan registration, the Multi-Scale k-Means NDT (MSKM-NDT) algorithm is proposed, which divides a 2D point cloud using k-means clustering and performs the scan registration optimization over multiple scales of clustering. The k-means clustering approach generates fewer Gaussian distributions when compared to the standard NDT algorithm, allowing for evaluation of the cost function across all Gaussian clusters, which guarantees convergence of the algorithm. As k-means clustering does not scale well to 3D, the Segmented Greedy Cluster NDT (SGC-NDT) method is proposed as an alternative approach to improve and guarantee convergence using 3D point clouds that contain points corresponding to the ground of the environment. The SGC-NDT algorithm segments the ground points using a Gaussian Process (GP) regression model and performs clustering of the non ground points using a greedy method. A region-growing clustering algorithm extracts natural features in the environment and generates Gaussian clusters to be used within the NDT framework for scan registration.


Das A, Waslander SL. Scan Registration using Segmented Region Growing NDT. International Journal of Robotics Research. 2014.

Das A, Servos J, Waslander SL. 3D Scan Registration Using the Normal Distributions Transform with Ground Segmentation and Point Cloud Clustering. In 2013 IEEE International Conference on Robotics and Automation. Karlsruhe, Germany; 2013.

Das A, Waslander SL. Scan Registration with Multi-Scale K-Means Normal Distributions Transform. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems. Villamoura, Portugal; 2012.