Clustering is the task of dividing an input dataset into groups of objects based on their similarity. This process is frequently required in many applications. However, it is computationally expensive when running on traditional CPUs due to the large number of connections and objects the system needs to inspect. In this paper, we investigate the use of NVIDIA graphics processing units and their programming platform CUDA in the acceleration of the Euclidean clustering (EC) process in autonomous driving systems. We propose GPU-accelerated algorithms for the EC problem on point cloud datasets, optimization strategies, and discuss implementation issues of each method. Our experiments show that our solution outperforms the CPU algorithm with speedup rates up to 87X on real-world datasets.

1. [1] K. A. Hawick, A. Leist, and D. P. Playne, “Parallel graph component labelling with GPUs and CUDA,” J. Parallel Computing, Vol.36, Issue 12, pp. 655-678, 2010.
2. [2] Y. Komura, “GPU-based cluster-labeling algorithm without the use of conventional iteration: Application to the Swendsen-Wang multi-cluster spin flip algorithm,” Compu. Phys. Comm., Vol.194, pp. 54-58, 2015.
3. [3] B. Douillard et al., “On the segmentation of 3D LIDAR point clouds,” Proc. of 2011 IEEE Int. Conf. on Robotics and Automation, Shanghai, pp. 2798-2805, 2011.
4. [4] M. Liu, “Efficient segmentation and plane modeling of point-cloud for structured environment by normal clustering and tensor voting,” Proc. of 2014 IEEE Int. Conf. on Robotics and Biomimetics (ROBIO 2014), Bali, pp. 1805-1810, 2014.
5. [5] A. Golovinskiy and T. Funkhouser, “Min-cut based segmentation of point clouds,” Proc. of 2009 IEEE 12th Int. Conf. on Computer Vision Workshops (ICCV Workshops), Kyoto, pp. 39-46, 2009.
6. [6] T. Rabbani, F. A. van den Heuvel, and G. Vosselman, “Segmentation of point clouds using smoothness constraint,” Proc. of Int. Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, p. 36, 2006.
7. [7] I. Bogoslavskyi and C. Stachniss, “Fast range image-based segmentation of sparse 3D laser scans for online operation,” Proc. of 2016 IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), pp. 163-169, 2016.
8. [8] F. Moosmann, O. Pink, and C. Stiller, “Segmentation of 3D lidar data in non-flat urban environments using a local convexity criterion,” Proc. of 2009 IEEE Intelligent Vehicles Symposium, Xi’an, pp. 215-220, 2009.
9. [9] D. Zermas, I. Izzat, and N. Papanikolopoulos, “Fast segmentation of 3D point clouds: A paradigm on LiDAR data for autonomous vehicle applications,” 2017 IEEE Int. Conf. on Robotics and Automation (ICRA), Singapore, pp. 5067-5073, 2017.
10. [10] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise,” Proc. of the 2nd Int. Conf. on Knowledge Discovery and Data Mining (KDD’96), pp. 226-231, 1996.
11. [11] N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, “The R^*-tree: an efficient and robust access method for points and rectangles,” Proc. of the 1990 ACM SIGMOD Int. Conf. on Management of data (SIGMOD ’90), pp. 322-331, 1990.
12. [12] R. B. Rusu, “Semantic 3d object maps for everyday manipulation in human living environments,” Ph.D. thesis, Computer Science Department, Technische Universität München, 2009.
13. [13] J. L. Bentley, “Multidimensional binary search trees used for associative searching,” Commun. ACM, Vol.18, No.9, pp. 509-517, 1975.
14. [14] R. B. Rusu and S. Cousins, “3D is here: Point Cloud Library (PCL),” Proc. of 2011 IEEE Int. Conf. on Robotics and Automation, Shanghai, pp. 1-4, 2011.
15. [15] M. Harris, S. Sengupta, and J. D. Owens, “Parallel prefix sum (scan) with CUDA,” H. Nguyen (Ed.), “GPU Gems 3,” NVIDIA Corporation, 2007.
16. [16] M. Quigley, K. Conley, B. Gerkey, J. Faust, T. Foote, J. Leibs, R. Wheeler, and A. Ng, “ROS: an open-source Robot Operating System,” ICRA Workshop on Open Source Software, Vol.3, pp. 1-5, 2009.