基于红黑树与K-D树的LiDAR数据组织管理

吴波涛; 张 煜; 陈文龙; 沈定涛; 魏思奇

doi:10.11988/ckyyb.20160854

PDF(1330 KB)

raybet体育在线院报 ›› 2016, Vol. 33 ›› Issue (11) : 32-35. DOI: 10.11988/ckyyb.20160854

遥感技术应用

基于红黑树与K-D树的LiDAR数据组织管理

吴波涛¹,张煜²,陈文龙²,沈定涛²,魏思奇²

作者信息 +

Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree

WU Bo-tao¹ , ZHANG Yu² , CHEN Wen-long², SHEN Ding-tao², Wei Si-qi²

Author information +

文章历史 +

摘要

LiDAR点云是由海量的激光离散脚点组成的三维点集,在平面以及垂直方向上均分布有数量不均的离散点。LiDAR点云离散点相互之间缺乏空间拓扑关系,所以建立适当的数据组织结构对LiDAR点云进行组织是对LiDAR点云进行处理的基础。根据LiDAR点云的数据结构特点,利用红黑树与K-D树建立一种“非空”规则立方体格网和K-D树相结合的双层次数据结构,用于LiDAR点云的组织管理,从而降低结构冗余和提高索引效率。

Abstract

LiDAR point cloud is a 3D point set composed of massive discrete laser dots which exist in both plane and vertical directions. Because of lacking space topological relations among the discrete dots of LiDAR point cloud, it is important to establish an appropriate data structure for LiDAR point cloud as the foundation of LiDAR processing. According to the structural characteristics of LiDAR point cloud data, a two-level data structure with “non-null” regular cube grid and K-D tree is established for the organization and management LiDAR point cloud using red-black tree and K-D tree to build. The structure could reduce the structural redundancy and improve indexing efficiency.

导出引用

吴波涛,张煜,陈文龙,沈定涛,魏思奇. 基于红黑树与K-D树的LiDAR数据组织管理[J]. raybet体育在线院报. 2016, 33(11): 32-35 https://doi.org/10.11988/ckyyb.20160854

WU Bo-tao,ZHANG Yu,CHEN Wen-long, SHEN Ding-tao, Wei Si-qi. Data Organization and Management of LiDAR Based onRed-black Tree and K-D Tree[J]. Journal of Changjiang River Scientific Research Institute. 2016, 33(11): 32-35 https://doi.org/10.11988/ckyyb.20160854

中图分类号： TP317.4

参考文献

[1]SAMBERG A. An Implementation of the ASPRS LAS Standard∥Proceedings of the ISPRS Workshop on Laser Scanning and SilviLaser. Espoo, Finland. September 12-14, 2007: 363-372.
[2]CHARANIYA A P,MANDUCHI R,LODHA S K.Supervised Parametric Classification of Aerial LiDAR Data∥Proceedings of the 2004 Conference on Computer Vision and Pattern Recognition Workshop (CVPRW04) Volume 3. IEEE Computer Society Washington, DC, USA, 2004: 30.
[3]DONOGHUE N M, WATT P J, NICHOLAS J, et al. Remote Sensing of Species Mixtures in Conifer Plantations Using LiDAR Height and Intensity Data. Remote Sensing of Environment, 2007, 110(4): 509-522.
[4]POPESCU S C, WYNNE R H, NELSON R F. Estimating Plot-level Tree Heights with LiDAR: Local Filtering with a Canopy-height Based Variable Window Size. Computers and Electronics in Agriculture, 2002, 37(1): 71-95.
[5]PIEGL L A. TILLER W. Algorithm for Finding All k Nearest Neighbors. Computer-Aided Design, 2002, 34(2): 167 - 172.
[6]ZENG Qi-hong,LAI Jia-zhen,XI Xian-hua,et al.Simple Building Reconstruction from LIDAR Point Cloud∥Proceedings of the 2008 International Conference on Audio, Language and Image Processing. IEEE. Shanghai, China, July 7-9, 2008:1040-1044.
[7]WANG Z, SCHENK T. Building Extraction and Reconstruction from LiDAR Data. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B3/2): 958-964.
[8]ZHANG K, CHEN S C, WHITMAN D, et al. A Progressive Morphological Filter for Removing Nonground Measurements from Airborne LIDAR Data. IEEE Transactions on Geoscience and Remote Sensing, 2003, 41(4): 872-882.
[9]李清泉,李德仁. 八叉树的三维行程编码. 武汉测绘科技大学学报, 1997,22(2): 102-106.
[10]LINH T H, LAEFER D F. Octree-based, Automatic Building Faade Generation from LiDAR Data. Computer-Aided Design, 2014, 53: 46-61.
[11]WANG M, TSENG Y. LiDAR Data Segmentation and Classification Based on Octree Structure. Parameters, 2004,1:5.
[12]BAYER R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms. Acta Informatica, 1972, 1(4): 290-306.
[13]HANKE S. The Performance of Concurrent Red-black Tree Algorithms. New York: Springer, 1999.