A Nearest Neighbor Searches(NNS) Algorithm for Fast Registration of 3D Point Clouds based on GPGPU
- DOI
- 10.2991/isrme-15.2015.446How to use a DOI?
- Keywords
- Registration; ICP; NNS; K-d tree; GPU
- Abstract
For a large set of data points, registration is time-expensive. In order to deal with this problem, we propose an improved Nearest Neighbor Searches(NNS) algorithm for 3D point clouds registration based on Graphic Processing Unit(GPU). In order to maximize the storage of data points in the memory, we minimize the k-d tree element to decrease the consumption of memory. We use left-balanced median sort algorithm to compute root node and partition left and right sub-tree in the process of building k-d tree. During the search process, we use trim optimization to delete the sub-tree branch far away from the query node to avoid a huge amount of invalid computation. We use search stack to store search path, which decrease the computation. Experimental results indicate that an average processing speed for GPU is 15 times faster than that for Central Processing Unit(CPU) when the registration results are appropriate, and the acceleration ratio improves significantly while the number of point clouds increases.
- Copyright
- © 2015, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
Cite this article
TY - CONF AU - Fangfang Wu AU - Fei Wang AU - Peilin Jiang AU - Chen Zhao AU - Jianhua Cheng PY - 2015/04 DA - 2015/04 TI - A Nearest Neighbor Searches(NNS) Algorithm for Fast Registration of 3D Point Clouds based on GPGPU BT - Proceedings of the 2015 International Conference on Intelligent Systems Research and Mechatronics Engineering PB - Atlantis Press SP - 2153 EP - 2158 SN - 1951-6851 UR - https://doi.org/10.2991/isrme-15.2015.446 DO - 10.2991/isrme-15.2015.446 ID - Wu2015/04 ER -