面向DEM构建的点云四叉树和R树混合索引研究

doi:10.3969/j.issn.0255-8297.2018.04.008

应用科学学报 ›› 2018, Vol. 36 ›› Issue (4): 644-654.doi: 10.3969/j.issn.0255-8297.2018.04.008

面向DEM构建的点云四叉树和R树混合索引研究

彭宝江^1,2,3, 钟若飞^1,2,3, 孙海丽^1,2,3, 耿雨馨^1,2,3

1. 首都师范大学北京成像技术高精尖创新中心, 北京 100048;
2. 首都师范大学资源环境与旅游学院, 北京 100048;
3. 首都师范大学三维数据获取与应用重点实验室, 北京 100048

收稿日期:2017-01-07 修回日期:2017-05-02 出版日期:2018-07-31 发布日期:2018-07-31
通信作者: 钟若飞,教授,博导,研究方向:车载激光测量,E-mail:40427310@qq.com E-mail:40427310@qq.com
基金资助:
国家自然科学基金（No.41371434）资助

Hybrid Index Method Based on Quad Tree and R-Tree for DEM Reconstruction of Airborne Point Cloud

PENG Bao-jiang^1,2,3, ZHONG Ruo-fei^1,2,3, SUN Hai-li^1,2,3, GENG Yu-xin^1,2,3

1. Beijing Advanced Innovation Center for Imaging Technology, Capital Normal University, Beijing 100048, China;
2. College of Resources Environment and Tourism, Capital Normal University, Beijing 100048, China;
3. Key Lab of 3D Information Acquisition and Application, Capital Normal University, Beijing 100048, China

Received:2017-01-07 Revised:2017-05-02 Online:2018-07-31 Published:2018-07-31

摘要/Abstract

摘要： 机载激光扫描点云数据量大，导致处理点云数据的效率不高.为此，借助四叉树对空间的快速分割和R树的自平衡特性，提出一种基于四叉树和R树混合空间索引的数字高程模型（digital elevation model，DEM）构建方法.首先针对原始点云数据建立外存索引；然后遍历索引以便将符合要求的区域点云分别导入内存，并以形态学滤波法对不同区域内的点云进行同步滤波处理；最后对于分区域处理得到的地面点数据，采用反距离加权内插法得到DEM.实验证明，在确保DEM精度的基础上，应用该索引方法能够极大地提高DEM构建的效率.

关键词: 数字高程模型, 四叉树索引, 混合空间索引, R树索引

Abstract: Airborne laser point cloud features with quick and precise data acquisition, and it is a trend to build digital elevation model by using airborne radar data. However, the huge data volume of airborne laser scanning point cloud leads to low efficiency in processing the point cloud data. This paper proposes a hybrid spatial index method based on quad-tree and R-tree for digital elevation model (DEM) reconstruction, which is inspired by the ability for the fast segmentation of quad-tree and the self-balance of R-tree. First, the original point cloud data are used for constructing an index of external memory. Then the fulfilled regions of point cloud are imported into internal memory after traversing the index, and different regions of point cloud are filtered synchronously by means of morphological filtering method. Finally, the DEM can be constructed by regionally processing the acquired ground point data with the inverse distance weighted interpolation. The experimental result shows that this method can greatly improve the efficiency of data processing in DEM construction.

Key words: hybrid spatial index, R-tree index, digital elevation model (DEM), quad tree index

中图分类号:

P237

彭宝江, 钟若飞, 孙海丽, 耿雨馨. 面向DEM构建的点云四叉树和R树混合索引研究[J]. 应用科学学报, 2018, 36(4): 644-654.

PENG Bao-jiang, ZHONG Ruo-fei, SUN Hai-li, GENG Yu-xin. Hybrid Index Method Based on Quad Tree and R-Tree for DEM Reconstruction of Airborne Point Cloud[J]. Journal of Applied Sciences, 2018, 36(4): 644-654.

参考文献

[1] Gobbetti E, Marton F M. Layered point clouds:a simple and efficient multiresolution structure for distributing and rendering gigantic point-sampled models[J]. Computers & Graphics, 2004, 28(6):815-826.
[2] Nebiker S, Bleisch S, Christen M. Rich point clouds in virtual globes-a new paradigm in city modeling?[J]. Computers Environment & Urban Systems, 2010, 34(6):508-517.
[3] Maune D F. Digital elevation model technologies and applications:the DEM users manual[M]. 2nd ed. Bethes (Md.):American Society for photogrammetry and Remote Sensing, 2007:23-25.
[4] 龚俊,柯胜男,朱庆,钟若飞. 一种八叉树和三维R树集成的激光点云数据管理方法[J]. 测绘学报,2012, 41(4):597-604. Gong J, Ke S N, Zhu Q, Zhong R F. An efficient management method for point cloud data based on octree and 3D R-tree[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(4):597-604. (in Chinese)
[5] 李晓红. 一种LiDAR点云生成格网DEM的快速算法[J]. 测绘通报,2012(12):44-46. Li X H. A Fast algorithm of LiDAR point clouds to generate grid DEM[J]. Bulletin of Surveying and Mapping, 2012(12):44-46. (in Chinese)
[6] 张齐勇,岑敏仪,杭芬,付仁俊. 基于LiDAR点云数据索引的DEM快速提取[J]. 测绘科学,2010, 35(3):69-70. Zhang Q Y, Cen M Y, Hang F, Fu R J. Quickly extracting DEM for LiDAR data based on spatial data index[J]. Science of Surveying and Mapping, 2010, 35(3):69-70. (in Chinese)
[7] Ma H, Wang Z. Distributed data organization and parallel data retrieval methods for huge laser scanner point clouds[J]. Computers & Geosciences, 2011, 37(2):193-201.
[8] 张蕊,李广云,王力,李明磊. 基于HDFS的海量激光点云数据分块存储方法研究[J]. 测绘通报,2014(3):21-24. Zhang R, Li G Y, Wang L, Li M L. Research on partition storage method of mass laser points cloud data based on HDFS[J]. Bulletin of Surveying and Mapping, 2014(3):21-24. (in Chinese)
[9] Jian X, Xiao X, Cheng F H, Zhi Z Z, Zhao H W, Deng Z Z. A hadoop-based algorithm of generating DEM grid from point cloud data[J]. ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2015, XL-7/W3(7):1209-1214.
[10] 李鹏程, 王慧, 刘志青, 闸旋. 一种从机载LiDAR点云数据获取DEM的方法[J]. 测绘通报, 2012(5):59-62. Li P C, Wang H, Liu Z Q, Zha X. A method of deriving DEM from airborne LiDAR points cloud data[J]. Bulletin of Surveying and Mapping, 2012(5):59-62. (in Chinese)
[11] 吴芳,张宗贵,郭兆成,安志宏,于坤,李婷. 基于机载LiDAR点云滤波的矿区DEM构建方法[J]. 国土资源遥感,2015, 27(1):62-67. Wu F, Zhang Z G, Guo Z C, An Z H, Yu K, Li T. Method of deriving DEM in the mining area based on filtering of airborne LiDAR data[J]. Remote Sensing for Land and Resources, 2015, 27(1):62-67. (in Chinese)
[12] Gong J, Zhu Q, Zhong R F, Zhang Y T, Xie X. An efficient point cloud management method based on a 3D R-tree[J]. Photogrammetric Engineering & Remote Sensing, 2012, 74(4):373-381.
[13] 李清泉,李德仁. 八叉树的三维行程编码[J]. 武汉大学学报(信息科学版),1997, 22(2):102-106. Li Q Q, Li D R. Three-dimensional run-ecoding (3DRE) for octree[J]. Journal of Wuhan Technical University of Surveying and Mapping, 1997, 22(2):102-106. (in Chinese)
[14] 杨建思,刘华,林鹏. 基于KD树的点云数据自适应屏幕精度高效显示方法[J]. 测绘通报,2014(7):18-22. Yang J S, Liu H, Lin P. A high efficient display method based on KD tree index for point-cloud data[J]. Application Research of Computers, 2014(7):18-22. (in Chinese)
[15] Wang S W, Armstrong M P. A quadtree approach to domain decomposition for spatial interpolation in grid computing environments[J]. Parallel Computing, 2003, 29:1481-1504.
[16] 龚俊,柯胜男,鲍曙明. 一种全新的R树节点选择算法[J]. 计算机应用研究,2008, 25(10):2946-2948. Gong J, Ke S N, Bao S M. Brand-new node-choosing algorithm of R-tree spatial index[J]. Application Research of Computers, 2008, 25(10):2946-2948. (in Chinese)
[17] Vosselman G. Slope based filtering of laser altimetry data[J]. International Archives of Photogrammetry and Remote Sensing, 1999, 54(2/3):138 n1471.
[18] 张熠斌,隋立春,曲佳,柳艳. 基于数学形态学算法的机载LiDAR点云数据快速滤波[J]. 测绘通报,2009(5):16-18. Zhang Y B, Sui L C, Qu J, Liu Y. Fast filtering of airborne LiDAR point cloud data based on mathematical morphology[J]. Bulletin of Surveying and Mapping, 2009(5):16-18. (in Chinese)
[19] Liu X Y. Airborne LiDAR for DEM generation:some critical issues[J]. Progress in Physical Geography, 2008, 32(1):31-49.
[20] 于彩霞,董箭,李改肖,陈惠荣,王沫. 基于LiDAR点云的高精度DEM构建方法[J]. 地理空间信息,2015(3):22-24. Yu C X, Dong J, Li G X, Chen H R, Wang M. Research on high precision DEM construction method based on LiDAR[J]. Geospatial Information, 2015(3):22-24. (in Chinese)

面向DEM构建的点云四叉树和R树混合索引研究

Hybrid Index Method Based on Quad Tree and R-Tree for DEM Reconstruction of Airborne Point Cloud

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	张春森, 张会, 郭丙轩, 杜神斌, 张月莹. 顾及相机响应函数的无人机影像匀光匀色[J]. 应用科学学报, 2019, 37(6): 783-794.
[2]	杨惠雯, 方俊永, 赵冬. 基于改进分离阈值法的农作物遥感精细分类特征选择[J]. 应用科学学报, 2019, 37(1): 51-63.
[3]	马飞虎, 姜珊珊, 孙翠羽. PSInSAR在铅山县矿区地表沉降监测中的应用[J]. 应用科学学报, 2018, 36(6): 969-977.
[4]	莫悠, 钟若飞, 张振鑫. 移动与定点扫描结合的室内点云数据获取方法[J]. 应用科学学报, 2018, 36(5): 756-764.
[5]	巫兆聪, 项伟, 李俊, 杨志. 基于满足度评估的遥感应用需求聚类算法[J]. 应用科学学报, 2018, 36(4): 635-643.
[6]	张莎莎, 王树根. 数字正射影像镶嵌的质量评价方法[J]. 应用科学学报, 2018, 36(3): 461-470.
[7]	巫兆聪, 刘培, 巫远. 一种多光谱遥感应用需求综合方法[J]. 应用科学学报, 2017, 35(5): 658-666.
[8]	刘亚文, 覃苏舜. 点云数据稀疏区域建筑物立面重建方法[J]. 应用科学学报, 2017, 35(2): 217-225.
[9]	黄俊杰, 谭波, 陈孝明, 陈江平, 阮羚, 冯莞舒, 熊宇. 用Apriori关联规则挖掘算法发现湖北电网雷击灾害的时空分布规律[J]. 应用科学学报, 2017, 35(1): 31-41.
[10]	樊敬敬, 张华, 郝明. 面向对象的机载LiDAR数据建筑物提取[J]. 应用科学学报, 2016, 34(1): 84-94.
[11]	李爱霞, 管海燕, 钟良, 于永涛. 基于张量投票的道路表面裂缝检测[J]. 应用科学学报, 2015, 33(5): 541-549.
[12]	孙振兴1,2,3，钟若飞1,2,3. 一种用于全景影像的测量方案[J]. 应用科学学报, 2015, 33(4): 399-406.
[13]	巫兆聪，徐卓知，杨帆. 遥感卫星应用需求满足度的模糊评估[J]. 应用科学学报, 2015, 33(3): 299-308.
[14]	贾永红1,2，吕臻1，周明婷1. 资源三号卫星影像超分辨率重建[J]. 应用科学学报, 2015, 33(3): 309-316.
[15]	巫兆聪1，杨帆1，王楠1，巫远1，朱卓娃2. 不同类型遥感传感器对地覆盖区域仿真与计算[J]. 应用科学学报, 2015, 33(1): 1-8.