The three-dimensional (3D) normal distributions transform (NDT) is a popular scan registration method for 3D point cloud datasets. It has been widely used in sensor-based localization and mapping applications. However, the NDT cannot entirely utilize the computing power of modern many-core processors, such as graphics processing units (GPUs), because of the NDT’s linear nature. In this study, we investigated the use of NVIDIA’s GPUs and their programming platform called compute unified device architecture (CUDA) to accelerate the NDT algorithm. We proposed a design and implementation of our GPU-accelerated 3D NDT (GPU NDT). Our methods can achieve a speedup rate of up to 34 times, compared with the NDT implemented in the point cloud library (PCL).

1. [1] P. Biber and W. Strasser, “The normal distributions transform: a new approach to laser scan matching,” Proc. of the 2003 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS 2003), Vol.3, pp. 2743-2748, 2003. https://doi.org/10.1109/IROS.2003.1249285
2. [2] M. Magnusson, A. Lilienthal, and T. Duckett, “Scan Registration for Autonomous Mining Vehicles Using 3D-NDT,” J. of Field Robotics, Vol.24, No.10, pp. 803-827, 2007. https://doi.org/10.1002/rob.20204
3. [3] M. Magnusson, “The Three-Dimensional Normal-Distributions Transform – an Efficient Representation for Registration Surface Analysis, and Loop Detection,” Ph.D. thesis, Örebro University, 2009.
4. [4] E. Takeuchi and T. Tsubouchi, “A 3-D Scan Matching using Improved 3-D Normal Distributions Transform for Mobile Robotic Mapping,” 2006 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 3068-3073, 2006. https://doi.org/10.1109/IROS.2006.282246
5. [5] T. Stoyanov, M. Magnusson, H. Andreasson, and A. J. Lilienthal, “Fast and accurate scan registration through minimization of the distance between compact 3D NDT representations,” The Int. J. of Robotics Research, Vol.31, No.12, pp. 1377-1393, 2012. https://doi.org/10.1177/0278364912460895
6. [6] R. B. Rusu and S. Cousins, “3D is here: Point Cloud Library (PCL),” 2011 IEEE Int. Conf. on Robotics and Automation, pp. 1-4, 2011.
7. [7] M. Muja and D. Lowe, “Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration,” Proc. of the 4th Int. Conf. on Computer Vision Theory and Applications (VISAPP 2009), Vol.1, pp. 331-340, 2009.
8. [8] M. Magnusson, A. Nuchter, C. Lorken, A. J. Lilienthal, and J. Hertzberg, “Evaluation of 3D registration reliability and speed – A comparison of ICP and NDT,” 2009 IEEE Int. Conf. on Robotics and Automation, pp. 3907-3912, 2009. https://doi.org/10.1109/ROBOT.2009.5152538
9. [9] T. Stoyanov, M. Magnusson, H. Almqvist, and A. J. Lilienthal, “On the accuracy of the 3D Normal Distributions Transform as a tool for spatial representation,” 2011 IEEE Int. Conf. on Robotics and Automation, pp. 4080-4085, 2011. https://doi.org/10.1109/ICRA.2011.5979584
10. [10] T. Kaminade, T. Takubo, Y. Mae, and T. Arai, “The generation of environmental map based on a NDT grid mapping – Proposal of convergence calculation corresponding to high resolution grid –,” 2008 IEEE Int. Conf. on Robotics and Automation, pp. 1874-1879, 2008.
11. [11] J. W. Kim and B. H. Lee, “Robust and fast 3-D scan registration using normal distributions transform with supervoxel segmentation,” Robotica, Vol.34, No.7, pp. 1630-1658, 2016. https://doi.org/10.1017/S0263574714002483
12. [12] M. Magnusson, N. Vaskevicius, T. Stoyanov, K. Pathak, and A. Birk, “Beyond points: Evaluating recent 3D scan-matching algorithms,” 2015 IEEE Int. Conf. on Robotics and Automation (ICRA), pp. 3631-3637, 2015. https://doi.org/10.1109/ICRA.2015.7139703
13. [13] K. W. Jang, W. J. Jeong, and Y. Kang, “Development of a GPU-Accelerated NDT Localization Algorithm for GNSS-Denied Urban Areas,” Sensors, Vol.22, No.5, Article No.1913, 2022. https://doi.org/10.3390/s22051913
14. [14] M. Harris, S. Sengupta, and J. D. Owens, “Parallel Prefix Sum (Scan) with CUDA,” H. Nguyen (Ed.), “GPU Gems 3,” pp. 851-876, Addison Wesley, 2007.
15. [15] S. Kato, E. Takeuchi, Y. Ishiguro, Y. Ninomiya, K. Takeda, and T. Hamada, “An Open Approach to Autonomous Vehicles,” IEEE Micro, Vol.35, No.6, pp. 60-68, 2015. https://doi.org/10.1109/MM.2015.133
16. [16] M. Quigley, B. Gerkey, K. Conley, J. Faust, T. Foote, J. Leibs, E. Berger, R. Wheeler, and A. Ng, “ROS: an open-source Robot Operating System,” ICRA Workshop on Open Source Software, 2009.
17. [17] J. Sturm, N. Engelhard, F. Endres, W. Burgard, and D. Cremers, “A benchmark for the evaluation of RGB-D SLAM systems,” 2012 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, pp. 573-580, 2012. https://doi.org/10.1109/IROS.2012.6385773
18. [18] D. Prokhorov, D. Zhukov, O. Barinova, K. Anton, and A. Vorontsova, “Measuring robustness of Visual SLAM,” 2019 16th Int. Conf. on Machine Vision Applications (MVA), pp. 1-6, 2019. https://doi.org/10.23919/MVA.2019.8758020
19. [19] B. K. P. Horn, H. M. Hilden, and S. Negahdaripour, “Closed-Form Solution of Absolute Orientation using Orthonormal Matrices,” J. of the Optical Society of America A, Vol.5, No.7, pp. 1127-1135, 1988. https://doi.org/10.1364/JOSAA.5.001127
20. [20] A. Carballo et al., “Characterization of Multiple 3D LiDARs for Localization and Mapping Performance using the NDT Algorithm,” 2021 IEEE Intelligent Vehicles Symp. Workshops (IV Workshops), pp. 327-334, 2021. https://doi.org/10.1109/IVWorkshops54471.2021.9669244
21. [21] A. Carballo, S. Seiya, J. Lambert, H. Darweesh, P. Narksri, L. Y. Morales, N. Akai, E. Takeuchi, and K. Takeda, “End-to-End Autonomous Mobile Robot Navigation with Model-Based System Support,” J. Robot. Mechatron., Vol.30, No.4, pp. 563-583, 2018.