{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T12:37:56Z","timestamp":1755693476280,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T00:00:00Z","timestamp":1742515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"JST, CREST","award":["JPMJCR22M2"],"award-info":[{"award-number":["JPMJCR22M2"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62306059"],"award-info":[{"award-number":["62306059"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2025,3,31]]},"abstract":"<jats:p>The Iterative Closest Points (ICP) algorithm is the most widely used method for estimating rigid transformation in 3D point cloud registration. However, the ICP relies on repeatedly performing computationally intensive nearest neighbor searches (NNS) within 3D space. This dependency becomes a significant bottleneck when processing large datasets, thereby hindering the practical deployment of point cloud technologies in real-world applications. To address this issue, we propose two approximate nearest neighbor search (ANNS) acceleration strategies for efficient improvement of the processing speed of the NNS. Our strategies first voxelize target cloud points and then fill voxels in the 3D coordinate space around the source point cloud in two different ways, which can convert the global nearest neighbor search to a local search. Both the proposed methods are suited to be parallelized on GPUs with a low computational load. Extensive experiments show that our methods significantly accelerate NNS processing while maintaining high accuracy, outperforming most of the currently known approaches.<\/jats:p>","DOI":"10.1145\/3716875","type":"journal-article","created":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T16:09:29Z","timestamp":1739203769000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Accelerating Nearest Neighbor Search in 3D Point Cloud Registration on GPUs"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4447-0480","authenticated-orcid":false,"given":"Qiong","family":"Chang","sequence":"first","affiliation":[{"name":"School of Computing, Institute of Science Tokyo, Meguro-ku, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6557-7175","authenticated-orcid":false,"given":"Weimin","family":"Wang","sequence":"additional","affiliation":[{"name":"International School of Information Science and Engineering, Dalian University of Technology, Dalian, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3038-7678","authenticated-orcid":false,"given":"Jun","family":"Miyazaki","sequence":"additional","affiliation":[{"name":"Computer Science, Institute of Science Tokyo, Meguro-ku, Japan"}]}],"member":"320","published-online":{"date-parts":[[2025,3,21]]},"reference":[{"key":"e_1_3_1_2_2","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201919)","author":"Aoki Yasuhiro","year":"2019","unstructured":"Yasuhiro Aoki, Hunter Goforth, Rangaprasad Arun Srivatsan, and Simon Lucey. 2019. PointNetLK: Robust & efficient point cloud registration using PointNet. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201919)."},{"key":"e_1_3_1_3_2","first-page":"15859","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201921)","author":"Bai Xuyang","year":"2021","unstructured":"Xuyang Bai, Zixin Luo, Lei Zhou, Hongkai Chen, Lei Li, Zeyu Hu, Hongbo Fu, and Chiew-Lan Tai. 2021. PointDSC: Robust point cloud registration using deep spatial consistency. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201921). 15859\u201315869."},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/3DUI.2014.6798870"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2023.03.004"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA56546.2023.10070940"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1991.132043"},{"key":"e_1_3_1_10_2","first-page":"2514","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201920)","author":"Choy Christopher","year":"2020","unstructured":"Christopher Choy, Wei Dong, and Vladlen Koltun. 2020. Deep global registration. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201920). 2514\u20132523."},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.2312\/VG\/VG-PBG08\/025-031"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.9"},{"key":"e_1_3_1_13_2","unstructured":"EPFL Computer Graphics and Geometry Laboratory. 2012. EPFL statue model repository. Retrieved from https:\/\/lgg.epfl.ch\/statuesdataset.php"},{"key":"e_1_3_1_14_2","first-page":"428","article-title":"Exploiting hardware utilization and adaptive dataflow for efficient sparse convolution in 3D point clouds","volume":"5","author":"Hong Ke","year":"2023","unstructured":"Ke Hong, Zhongming Yu, Guohao Dai, Xinhao Yang, Yaoxiu Lian, Ningyi Xu, and Yu Wang. 2023. Exploiting hardware utilization and adaptive dataflow for efficient sparse convolution in 3D point clouds. Proc. Mach. Learn. Syst. 5 (2023), 428\u2013441.","journal-title":"Proc. Mach. Learn. Syst."},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3113043"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9560835"},{"key":"e_1_3_1_17_2","first-page":"15994","volume-title":"Proceedings of the IEEE\/CVF International Conference on Computer Vision (ICCV\u201921)","author":"Lee Junha","year":"2021","unstructured":"Junha Lee, Seungwook Kim, Minsu Cho, and Jaesik Park. 2021. Deep Hough voting for robust global registration. In Proceedings of the IEEE\/CVF International Conference on Computer Vision (ICCV\u201921). 15994\u201316003."},{"key":"e_1_3_1_18_2","doi-asserted-by":"crossref","unstructured":"Xiang Li et\u00a0al. 2024. An optimized GPU implementation for GIST descriptor. ACM Transactions on Architecture and Code Optimization 21 4 (2024) 1\u201324.","DOI":"10.1145\/3689339"},{"key":"e_1_3_1_19_2","first-page":"12","volume-title":"Proceedings of the IEEE\/CVF International Conference on Computer Vision (ICCV\u201919)","author":"Lu Weixin","year":"2019","unstructured":"Weixin Lu, Guowei Wan, Yao Zhou, Xiangyu Fu, Pengfei Yuan, and Shiyu Song. 2019. DeepVCP: An end-to-end deep neural network for point cloud registration. In Proceedings of the IEEE\/CVF International Conference on Computer Vision (ICCV\u201919). 12\u201321."},{"issue":"2","key":"e_1_3_1_20_2","first-page":"63","article-title":"Efficient point cloud pre-processing using the point cloud library","volume":"10","author":"Miknis Marius","year":"2016","unstructured":"Marius Miknis, Ross Davies, Peter Plassmann, and Andrew Ware. 2016. Efficient point cloud pre-processing using the point cloud library. Int. J. Image Process. 10, 2 (2016), 63.","journal-title":"Int. J. Image Process."},{"key":"e_1_3_1_21_2","doi-asserted-by":"crossref","unstructured":"Shinya Miura Qiong Chang and Jun Miyazaki. 2024. k-way in-place merge by CPU-GPU cooperative processing. In 2024 IEEE 35th International Conference on Application-specific Systems Architectures and Processors (ASAP). 152\u2013160.","DOI":"10.1109\/ASAP61560.2024.00039"},{"key":"e_1_3_1_22_2","doi-asserted-by":"crossref","unstructured":"Matteo Munaro Radu B. Rusu and Emanuele Menegatti. 2016. 3D robot perception with point cloud library. Robotics and Autonomous Systems 78 (2016) 97\u201399.","DOI":"10.1016\/j.robot.2015.12.008"},{"key":"e_1_3_1_23_2","first-page":"3407","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201918)","author":"Pavlov Artem L.","year":"2018","unstructured":"Artem L. Pavlov, Grigory W. V. Ovchinnikov, Dmitry Yu Derbyshev, Dzmitry Tsetserukou, and Ivan V. Oseledets. 2018. AA-ICP: Iterative closest point with Anderson acceleration. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201918). IEEE, 3407\u20133412."},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00024"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-013-9327-2"},{"key":"e_1_3_1_26_2","first-page":"11143","volume-title":"Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201922)","author":"Qin Zheng","year":"2022","unstructured":"Zheng Qin, Hao Yu, Changjian Wang, Yulan Guo, Yuxing Peng, and Kai Xu. 2022. Geometric transformer for fast and robust point cloud registration. In Proceedings of the IEEE\/CVF Conference on Computer Vision and Pattern Recognition (CVPR\u201922). 11143\u201311152."},{"key":"e_1_3_1_27_2","first-page":"194","volume-title":"Computer Vision Systems","author":"Qiu Deyuan","year":"2009","unstructured":"Deyuan Qiu, Stefan May, and Andreas N\u00fcchter. 2009. GPU-accelerated nearest neighbor search for 3D registration. In Computer Vision Systems, Mario Fritz, Bernt Schiele, and Justus H. Piater (Eds.). Springer Berlin, 194\u2013203."},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323037"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/IM.2001.924423"},{"key":"e_1_3_1_30_2","first-page":"1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201911)","author":"Rusu Radu Bogdan","year":"2011","unstructured":"Radu Bogdan Rusu and Steve Cousins. 2011. 3D is here: Point cloud library (PCL). In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA\u201911). IEEE, 1\u20134."},{"key":"e_1_3_1_31_2","article-title":"PCRNet: Point cloud registration network using PointNet encoding","author":"Sarode Vinit","year":"2019","unstructured":"Vinit Sarode, Xueqian Li, Hunter Goforth, Yasuhiro Aoki, Rangaprasad Arun Srivatsan, Simon Lucey, and Howie Choset. 2019. PCRNet: Point cloud registration network using PointNet encoding. arXiv preprint arXiv:1908.07906 (2019).","journal-title":"arXiv preprint arXiv:1908.07906"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","unstructured":"Aleksandr Segal Dirk Haehnel and Sebastian Thrun. 2009. Generalized-ICP. In Robotics: Science and Systems 2 4 (2009) 435.","DOI":"10.15607\/RSS.2009.V.021"},{"key":"e_1_3_1_33_2","unstructured":"Chhavi Sharma. 2019. Project4-CUDA-ICP. Retrieved from https:\/\/github.com\/chhavisharma\/Project4-CUDA-ICP"},{"key":"e_1_3_1_34_2","volume-title":"Proceedings of the International Conference on Intelligent Robot Systems (IROS\u201912)","author":"Sturm J.","year":"2012","unstructured":"J. Sturm, N. Engelhard, F. Endres, W. Burgard, and D. Cremers. 2012. A benchmark for the evaluation of RGB-D SLAM systems. In Proceedings of the International Conference on Intelligent Robot Systems (IROS\u201912)."},{"key":"e_1_3_1_35_2","first-page":"68","volume-title":"Proceedings of the 31st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP\u201923)","author":"Sugiura Keisuke","year":"2023","unstructured":"Keisuke Sugiura and Hiroki Matsutani. 2023. An efficient accelerator for deep learning-based point cloud registration on FPGAs. In Proceedings of the 31st Euromicro International Conference on Parallel, Distributed and Network-Based Processing (PDP\u201923). IEEE, 68\u201375."},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2020.3013758"},{"key":"e_1_3_1_37_2","first-page":"302","article-title":"TorchSparse: Efficient point cloud inference engine","volume":"4","author":"Tang Haotian","year":"2022","unstructured":"Haotian Tang, Zhijian Liu, Xiuyu Li, Yujun Lin, and Song Han. 2022. TorchSparse: Efficient point cloud inference engine. Proc. Mach. Learn. Syst. 4 (2022), 302\u2013315.","journal-title":"Proc. Mach. Learn. Syst."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/192161.192241"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP49357.2023.10095859"},{"key":"e_1_3_1_40_2","first-page":"1","volume-title":"Proceedings of the IEEE Intelligent Vehicles Symposium (IV\u201923)","author":"Wang Xiao","year":"2023","unstructured":"Xiao Wang, Xiaodong Deng, Yingxiang Li, Shitao Chen, Longjun Liu, and Nanning Zheng. 2023. Design hybrid computing architecture for accelerating point cloud registration. In Proceedings of the IEEE Intelligent Vehicles Symposium (IV\u201923). IEEE, 1\u20137."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2019.00362"},{"key":"e_1_3_1_42_2","first-page":"2027","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201916)","author":"Wieschollek Patrick","year":"2016","unstructured":"Patrick Wieschollek, Oliver Wang, Alexander Sorkine-Hornung, and Hendrik Lensch. 2016. Efficient large-scale approximate nearest neighbor search on the GPU. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201916). 2027\u20132035."},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMM.2023.3283881"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSVT.2023.3237328"},{"key":"e_1_3_1_45_2","first-page":"1912","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201915)","author":"Wu Zhirong","year":"2015","unstructured":"Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 2015. 3D ShapeNets: A deep representation for volumetric shapes. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR\u201915). 1912\u20131920."},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2021.3054619"},{"key":"e_1_3_1_47_2","first-page":"1033","volume-title":"Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE\u201920)","author":"Zhao Weijie","year":"2020","unstructured":"Weijie Zhao, Shulong Tan, and Ping Li. 2020. SONG: Approximate nearest neighbor search on GPU. In Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE\u201920). IEEE, 1033\u20131044."},{"key":"e_1_3_1_48_2","doi-asserted-by":"crossref","first-page":"766","DOI":"10.1007\/978-3-319-46475-6_47","volume-title":"Computer Vision\u2013ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II 14","author":"Zhou Qian-Yi","year":"2016","unstructured":"Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. 2016. Fast global registration. In Computer Vision\u2013ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part II 14. Springer, 766\u2013782."},{"key":"e_1_3_1_49_2","article-title":"Open3D: A modern library for 3D data processing","author":"Zhou Qian-Yi","year":"2018","unstructured":"Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun. 2018. Open3D: A modern library for 3D data processing. arXiv preprint arXiv:1801.09847 (2018).","journal-title":"arXiv preprint arXiv:1801.09847"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716875","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3716875","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:19:16Z","timestamp":1750295956000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3716875"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,21]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3716875"],"URL":"https:\/\/doi.org\/10.1145\/3716875","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2025,3,21]]},"assertion":[{"value":"2024-07-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}