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

doi:10.3969/j.issn.0255-8297.2018.04.008

Abstract

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

CLC Number:

P237

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.

References

[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)

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	ZHANG Chunsen, ZHANG Hui, GUO Bingxuan, DU Shenbin, ZHANG Yueying. Dodging Method Based on Camera Response Functions for UAV Image [J]. Journal of Applied Sciences, 2019, 37(6): 783-794.
[2]	YANG Hui-wen, FANG Jun-yong, ZHAO Dong. Feature Selection in Precise Crop Classification Using Remote Sensing Data Based on Improved SEaTH Algorithm [J]. Journal of Applied Sciences, 2019, 37(1): 51-63.
[3]	MA Fei-hu, JIANG Shan-shan, SUN Cui-yu. Application of PSInSAR in Monitoring Land Subsidence in Yanshan Mining Area [J]. Journal of Applied Sciences, 2018, 36(6): 969-977.
[4]	MO You, ZHONG Ruo-fei, ZHANG Zhen-xin. Acquisition of Indoor Laser Point Clouds Based on Mobile and Terrestrial Scanning [J]. Journal of Applied Sciences, 2018, 36(5): 756-764.
[5]	WU Zhao-cong, XIANG Wei, LI Jun, YANG Zhi. Clustering Algorithm for Remote Sensing Application Requirements Based on Satisfaction Evaluation [J]. Journal of Applied Sciences, 2018, 36(4): 635-643.
[6]	ZHANG Sha-sha, WANG Shu-gen. Quality Evaluation Method for the Results of Digital Orthophoto Mosaic [J]. Journal of Applied Sciences, 2018, 36(3): 461-470.
[7]	WU Zhao-cong, LIU Pei, WU Yuan. Synthesis of Requirements in Applications of Multi-spectral Remote Sensing [J]. Journal of Applied Sciences, 2017, 35(5): 658-666.
[8]	LIU Ya-wen, QIN Su-shun. Building Facade Reconstruction on Sparse LiDAR Data Region [J]. Journal of Applied Sciences, 2017, 35(2): 217-225.
[9]	HUANG Jun-jie, TAN Bo, CHEN Xiao-ming, CHEN Jiang-ping, RUAN Ling, FENG Wan-shu, XIONG Yu. Spatiotemporal Distribution of Lightning Disasters of Power Lines in Hubei Province Using Data Mining Based on Apriori Association Rules [J]. Journal of Applied Sciences, 2017, 35(1): 31-41.
[10]	FAN Jing-jing, ZHANG Hua, HAO Ming. Object-Based Building Extraction from Airborne LiDAR Data [J]. Journal of Applied Sciences, 2016, 34(1): 84-94.
[11]	LI Ai-xia, GUAN Hai-yan, ZHONG Liang, YU Yong-tao. Tensor Voting Based Pavement Crack Extraction [J]. Journal of Applied Sciences, 2015, 33(5): 541-549.
[12]	SUN Zhen-xing1,2,3, ZHONG Ruo-fei1,2. Measurement Scheme for Panoramic Images [J]. Journal of Applied Sciences, 2015, 33(4): 399-406.
[13]	WU Zhao-cong, XU Zhuo-zhi, YANG Fan. Fuzzy Evaluation of Application Satisfaction for Remote Sensing Satellite [J]. Journal of Applied Sciences, 2015, 33(3): 299-308.
[14]	JIA Yong-hong1,2, Lü Zhen1, ZHOU Ming-ting1. Super Resolution Reconstruction of ZY-3 Satellite Images [J]. Journal of Applied Sciences, 2015, 33(3): 309-316.
[15]	WU Zhao-cong1, YANG Fan1, WANG Nan1, WU Yuan1, ZHU Zhuo-wa2. Coverage Area in Different Types of Remote Sensors:Simulation and Calculation [J]. Journal of Applied Sciences, 2015, 33(1): 1-8.