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