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/).

Download article (PDF)

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  -