GPU-Accelerated 3D Normal Distributions Transform
*Graduate School of Informatics, Nagoya University
Furo-cho, Chikusa-ku, Nagoya 464-8603, Japan
**MAP IV, Inc.
711 National Innovation Complex, Nagoya University, Furo-cho, Nagoya, Aichi 464-0814, Japan
***Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo
7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan
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).
-  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
-  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
-  M. Magnusson, “The Three-Dimensional Normal-Distributions Transform – an Efficient Representation for Registration Surface Analysis, and Loop Detection,” Ph.D. thesis, Örebro University, 2009.
-  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
-  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
-  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.
-  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.
-  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
-  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
-  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.
-  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
-  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
-  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
-  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.
-  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
-  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.
-  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
-  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
-  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
-  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
-  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.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.