3D Multi-Layered Normal Distribution Transform for Fast and Long Range Scan Matching

Simultaneously Localization and Mapping (SLAM) problem requires a sophisticated scan matching algorithm, in which two consecutive point clouds belonging to highly correlated scene are registered by finding the rigid body transformation parameters when an initial relative pose estimate is available. A well-known scan matching method is the Iterative Closest Point (ICP) algorithm, and the basis of the algorithm is the minimization of an error function that takes point correspondences into account. Another 3D scan matching method called Normal Distribution Transform (NDT) has several advantages over ICP such as the surface representation capability, accuracy, and data storage. On the other hand, the performance of the NDT is directly related to the size of the cell, and there is no proved way of choosing an optimum cell size. In this paper, a novel method called Multi-Layered Normal Distribution Transform (ML-NDT) using various cell sizes in a structured manner is introduced. In this structure a number of layers are used, where each layer contains different but regular cell sizes. In the conventional NDT, the score function is chosen as Gaussian probability function which is minimized iteratively by Newton optimization method. However, the ML-NDT score function is described as the Mahalanobis distance function, and in addition to Newton optimization method, Levenberg–Marquardt algorithm is also adapted to the proposed method for this score function. The performance of the proposed method is compared to the original NDT, and the effects of the optimization methods are discussed. Moreover, an important issue in a scan matching algorithms is the subsampling strategy since the point cloud contains huge amount of data which has a non-uniform distribution. Therefore, the application of a sampling strategy is a must for fast and robust scan matching. In the performance analysis, two sampling strategies are investigated which are random sampling and grid based sampling. The method is successfully applied to experimentally obtained datasets, and the results show that ML-NDT with grid based sampling provides a fast and long range scan matching capability.