三维点云数据实时管理的Hash map方法

doi:10.11947/j.AGCS.2018.20170619

测绘学报 ›› 2018, Vol. 47 ›› Issue (6): 825-832.doi: 10.11947/j.AGCS.2018.20170619

• 计算机视觉与三维重建 • 上一篇下一篇

三维点云数据实时管理的Hash map方法

郑顺义¹, 何源¹, 徐刚², 王辰¹, 朱锋博¹

1. 武汉大学遥感信息工程学院, 湖北武汉 430079;
2. 立命馆大学理工学部情报学科, 日本滋贺 520072

收稿日期:2017-11-06 修回日期:2018-04-08 出版日期:2018-06-20 发布日期:2018-06-21
通讯作者: 何源 E-mail:yuanhe@whu.edu.cn
作者简介:郑顺义(1973-),男,博士,教授,博士生导师,主要从事数字摄影测量与计算机视觉研究。E-mail:syzheng@whu.edu.cn
基金资助:
国家自然科学基金（41671452；41701532）；中央高校基本科研业务费专项资金（2042016kf0012）；中国博士后科学基金（2017M612510）

Hash Map Method of 3D Point Cloud Data for Real-time Organizing

ZHENG Shunyi¹, HE Yuan¹, XU Gang², WANG Chen¹, ZHU Fengbo¹

1. School of Remote Sensing and Information Engineering, Wuhan University, Wuhan 430079, China;
2. Department of Computer Science & Media Technology, Ritsumeikan University, Shiga 520072, Japan

Received:2017-11-06 Revised:2018-04-08 Online:2018-06-20 Published:2018-06-21
Supported by:
The National Natural Science Foundation of China (Nos.41671452;41701532);The Fundamental Research Funds for the Central Universities (No.2042016kf0012);China Postdoctoral Science Foundation (No.2017M612510)

摘要/Abstract

摘要： 本文基于机器视觉探讨数字摄影测量三维构像下的智能数据处理要素之一：海量点云高效管理技术，提出了一种基于GPU的hash map三维点云数据组织的改进算法，算法可以高效地完成数据的动态插入、更新和索引，而不受数据规模限制。同时，通过传感器位置姿态估计当前活动范围，进行主机与GPU的数据交换，保证了GPU的低内存占用率。在搭载不同等级显卡（GTX960、GTX1050、GTX1060）的计算机设备上试验，本文算法均可以达到60 fps以上的帧率（单帧处理点云数：2.11×10⁵），证明算法满足了三维构像中三维点云数据高效管理的要求。

关键词: 三维点云, 数据组织, 哈希表, 图形处理器, 并行计算

Abstract: In this paper,one of the key elements of intelligent data processing in digital photogrammetry is discussed based on machine vision:efficient management technology of massive point cloud,an improved algorithm for hash mapping 3D data on GPU is proposed.The algorithm can efficiently perform dynamic insertion,update and indexing of data without the limitation of data scale.We applied the algorithm to TSDF (truncated signed distance field) algorithm for point cloud fusion,which can reduce the noise of single frame and the data registration error between different frames in a very efficient way.Currently,most of the data structures of point cloud fusion algorithms are regular or hierarchical grid data structures,so the object bounding boxes should be specified in advance.Moreover,the hierarchical data structure is complex and hard to parallelization.Therefore,the requirements of dynamic scalability,updating and indexing data of real-time 3D reconstruction cannot be satisfied.This paper exploited hash map to manage 3D data.At the same time,the current active region could be estimated with sensor motion to exchange data between host and GPU,keeping low memory utilization of GPU.In the experiments on different levels of graphics cards(GTX960,GTX1050,GTX1060),the algorithm can satisfy the real-time frame rate requirements(60 fps,2.11×10⁵ points per frame),so it meets the requirement of efficient management of 3D point cloud data in three-dimensional imaging.

Key words: 3D point cloud, data organization, hash table, graphics processing unit (GPU), parallel computing

中图分类号:

P234

郑顺义, 何源, 徐刚, 王辰, 朱锋博. 三维点云数据实时管理的Hash map方法[J]. 测绘学报, 2018, 47(6): 825-832.

ZHENG Shunyi, HE Yuan, XU Gang, WANG Chen, ZHU Fengbo. Hash Map Method of 3D Point Cloud Data for Real-time Organizing[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(6): 825-832.

参考文献

[1] 郑顺义, 周漾, 黄荣永, 等. 馆藏文物三维测量与重建方法研究[J]. 测绘科学, 2014, 39(7):76-79. ZHENG Shunyi, ZHOU Yang, HUANG Rongyong, et al. A Method of 3D Measurement and Reconstruction for Cultural Relics in Museums[J]. Science of Surveying and Mapping, 2014, 39(7):76-79.
[2] 翟瑞芳, 张剑清. 基于激光扫描仪的点云模型的自动拼接[J]. 地理空间信息, 2004, 2(6):37-39. ZHAI Ruifang, ZHANG Jianqing. Automatic Registration of Point Clouds Based on Laser Scanner[J]. Geospatial Information, 2004, 2(6):37-39.
[3] RUSINKIEWICZ S, HALL-HOLT O, LEVOY M. Real-time 3D Model Acquisition[J]. ACM Transactions on Graphics (TOG), 2002, 21(3):438-446.
[4] ROSSIGNAC J, BORREL P. Multi-resolution 3D Approximations for Rendering Complex Scenes[C]//FALCIDIENO B, KUNⅡ T L. Modeling in Computer Graphics. Berlin, Heidelberg:Springer, 1993:455-465.
[5] CURLESS B, LEVOY M. A Volumetric Method for Building Complex Models from Range Images[C]//Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques.[S.l.]:ACM, 1996:303-312.
[6] NEWCOMBE R A, IZADI S, HILLIGES O, et al. Kinect-Fusion:Real-time Dense Surface Mapping and Tracking[C]//Proceedings of the 10th IEEE International Symposium on Mixed and Augmented Reality. Basel, Switzerland:IEEE, 2011:127-136.
[7] IZADI S, KIM D, HILLIGES O, et al. KinectFusion:Real-time 3D Reconstruction and Interaction Using a Moving Depth Camera[C]//Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology. Santa Barbara, California:ACM, 2011:559-568.
[8] 谭歆. KinectFusion三维重建的再优化[D]. 杭州:浙江大学, 2015. TAN Xin. Global Optimization for 3D Reconstruction Based on KinectFusion[D]. Hangzhou:Zhejiang University, 2015.
[9] WHELAN T, MCDONALD J, KAESS M, et al. Kintinuous:Spatially Extended Kinectfusion[R]. Cambridge:MIT, 2012.
[10] WHELAN T, JOHANNSSON H, KAESS M, et al. Robust Real-time Visual Odometry for Dense RGB-D Mapping[C]//Proceedings of 2013 IEEE International Conference on Robotics and Automation. Karlsruhe, Germany:IEEE, 2013:5724-5731.
[11] ROTH H, VONA M. Moving Volume KinectFusion[C]//Proceedings of the British Machine Vision Conference. Boston, MA:BMVA Press, 2012:1-11.
[12] ZENG Ming, ZHAO Fukai, ZHENG Jiaxiang, et al. Octree-based Fusion for Realtime 3D Reconstruction[J]. Graphical Models, 2013, 75(3):126-136.
[13] ZENG Ming, ZHAO Fukai, ZHENG Jiaxiang, et al. A Memory-efficient Kinectfusion Using Octree[M]//Proceedings of the 1st International Conference on Computational Visual Media. Beijing, China:Springer, 2012:234-241.
[14] CHEN Jiawen, BAUTEMBACH D, IZADI S. Scalable Real-time Volumetric Surface Reconstruction[J]. ACM Transactions on Graphics (TOG), 2013, 32(4):113.
[15] KÄMPE V, SINTORN E, ASSARSSON U. High Resolution Sparse Voxel Dags[J]. ACM Transactions on Graphics (TOG), 2013, 32(4):101.
[16] NIEβNER M, ZOLLHÖFER M, IZADI S, et al. Real-time 3D Reconstruction at Scale Using Voxel Hashing[J]. ACM Transactions on Graphics (TOG), 2013, 32(6):169.
[17] KLINGENSMITH M, DRYANOVSKI I, SRINIVASA S, et al. Chisel:Real Time Large Scale 3D Reconstruction Onboard a Mobile Device Using Spatially-Hashed Signed Distance Fields[C]//Proceedings of Robotics:Science and Systems. Rome, Italy:[s.n.], 2015:4.
[18] TESCHNER M, HEIDELBERGER B, MVLLER M, et al. Optimized Spatial Hashing for Collision Detection of Deformable Objects[C]//Proceedings of the 8th Workshop on Vision, Modeling, and Visualization. Munich, Germany:AKA, 2003:47-54.
[19] RIVEST R. The MD5 Message-digest Algorithm[R]. Request for Comments 1321 Cambridge:MIT Laboratory for Computer Science and RSA Data Security, Inc, 1992.
[20] TUBIC D, HÉBERT P, LAURENDEAU D. A Volumetric Approach for Interactive 3D Modeling[J]. Computer Vision and Image Understanding, 2003, 92(1):56-77.
[21] TUBIC' D, HÉBERT P, LAURENDEAU D. 3D Surface Modeling from Curves[J]. Image and Vision Computing, 2004, 22(9):719-734.
[22] WERNER D, AL-HAMADI A, WERNER P. Truncated Signed Distance Function:Experiments on Voxel Size[C]//Proceedings of the 11th International Conference Image Analysis and Recognition. Cham:Springer, 2014:357-364.
[23] 王攀. 基于Out-of-Core的海量数据等值面绘制技术研究与实现[D]. 长沙:国防科学技术大学, 2008. WANG Pan. Research on Isosurface Extraction of Large Scale Datasets With Out-of-core Method[D]. Changsha:National University of Defense Technology, 2008.
[24] DESCHÊNES J D, HÉBERT P, LAMBERT P, et al. Multiresolution Interactive Modeling with Efficient Visualization[C]//Proceedings of the 5th International Conference on 3-D Digital Imaging and Modeling. Ottawa, Ontario, Canada:IEEE, 2005:39-46.
[25] ZWICKER M, PFISTER H, VAN BAAR J, et al. Surface splatting[C]//Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques. Los Angeles:ACM, 2001:371-378.
[26] LORENSEN W E, CLINE H E. Marching Cubes:A High Resolution 3D Surface Construction Algorithm[J]. ACM SIGGRAPH Computer Graphics, 1987, 21(4):163-169.

三维点云数据实时管理的Hash map方法

Hash Map Method of 3D Point Cloud Data for Real-time Organizing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	朱庆, 冯斌, 李茂粟, 陈媚特, 徐肇文, 谢潇, 张叶廷, 刘铭崴, 黄志勤, 冯义从. 面向动态关联数据的高效稀疏图索引方法[J]. 测绘学报, 2020, 49(6): 681-691.
[2]	邓非, 颜青松, 肖腾. 多视密集匹配并行传播GPU-PatchMatch算法[J]. 测绘学报, 2020, 49(2): 181-190.
[3]	梁伟, 徐新禹, 李建成, 朱广彬. 联合EGM2008模型重力异常和GOCE观测数据构建超高阶地球重力场模型SGG-UGM-1[J]. 测绘学报, 2018, 47(4): 425-434.
[4]	郑茂腾, 周顺平, 熊小东, 朱俊峰. GPU并行区域网平差[J]. 测绘学报, 2017, 46(9): 1193-1201.
[5]	崔阳, 吕志平, 李林阳, 陈正生, 孙大双, 邝英才. GNSS大网双差模型并行快速解算方法[J]. 测绘学报, 2017, 46(7): 848-856.
[6]	宋树华, 董芳, 万元嵬, 赵金玲, 李世忠, 席福彪, 陈恺, 张乐, 陈东. 几种地球剖分网格分析与初探[J]. 测绘学报, 2016, 45(S1): 48-55.
[7]	谢传节, 龙舟, 马益杭, 由志杰. 多边形间空间关系查询的异构多核架构并行算法[J]. 测绘学报, 2016, 45(1): 119-126.
[8]	崔阳吕志平. 多核环境下的GNSS数据并行处理研究[J]. , 2013, 42(5): 661-667.
[9]	沈婕. MPI环境下等高线简化并行计算适宜性研究[J]. , 2013, 42(4): 0-0.
[10]	邹贤才,李建成,汪海洪,徐新禹. 基于OpenMP的并行计算在卫星重力数据处理中的应用[J]. 测绘学报, 2010, 39(6): 636-641.
[11]	肖汉,张祖勋. 基于GPGPU的并行影像匹配算法[J]. 测绘学报, 2010, 39(1): 0-82.
[12]	周杨;徐青;康宁;张勇. 月面形貌的3维可视化算法 [J]. 测绘学报, 2009, 38(6): 0-481.