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

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

(1.云南省水利水电勘测设计研究院，昆明 650021；2.长江科学院 空间信息技术应用研究所，武汉 430010)



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

吴波涛1，张 煜2，陈文龙2，沈定涛2，魏思奇2

(1.云南省水利水电勘测设计研究院，昆明 650021；2.长江科学院 空间信息技术应用研究所，武汉 430010)

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

LiDAR；红黑树；K-D树；数据结构；数据组织；立方体网格

1 研究背景

LiDAR点云是由海量的激光离散脚点组成的三维点集，每个三维坐标点除了空间坐标外还有与扫描地物相关的额外属性，使得一个扫描区的LiDAR点云数据的信息量一般非常巨大。此外与栅格数据的二维结构不同，LiDAR点云是一种三维的空间数据，即在各个垂直方向上还分布有数量不均的离散点。LiDAR点云这种不同于以往的新特性，无论是在数据存储方式上还是在数据组织管理上都带来了颇具难度的挑战。

以往LiDAR点云数据的存储格式都是由各个LiDAR系统制造商自行决定的，有采用ASCII形式直接提供原始点云数据的，也有提供已经插过值的格网数据的，提供的属性和占用空间也是各不相同，这给LiDAR数据在不同硬件和软件下的共享和处理带来许多不便。为了改变LiDAR数据存储格式不统一的局面，美国摄影测量与遥感协会(American Society for Photogrammetry and Remote Sensing)提出了LiDAR点云数据的存储格式标准——LAS[1]，LAS经过数个版本的发展而趋于成熟，并被各个LiDAR厂商所支持，已经成为LiDAR数据比较常用的存储格式。相比较LiDAR点云物理存储格式的逐渐成熟，LiDAR点云分析处理时的具体组织管理却没有统一而成熟的数据结构方案，常用的分别有插值格网、不规则三角网、八叉树等方式，这些LiDAR数据组织方式有着各自的适用范围和缺点。

本文根据LiDAR点云的数据结构特点，探索一种双层次双类型索引的混合点云数据结构，实现点云数据结构的低冗余和快速空间检索。

2 常用LiDAR点云数据组织方式

LiDAR点云最直观的特点就是数据规模庞大，而且离散点分布不规则，相互之间缺乏空间拓扑关系，这给LiDAR点云的空间搜索和地理分析带来了很大的困难，所以建立高效的数据组织结构对LiDAR点云来说是非常重要的。目前，应用较为广泛的LiDAR点云组织方式主要有：规则格网、不规则三角网、八叉树等。

2.1 规则格网组织方式

规则格网是LiDAR点云组织研究中应用较早的一种数据结构[2-4]。规则格网是将整个LiDAR点云的平面覆盖区域划分为固定大小方格网，每个格网内部都包含若干数目的LiDAR离散点。规则格网的优点是构造简单、快速而且易于编码[5]，但是，当LiDAR点云在各个位置分布不均时，会造成离散点的空间检索效率急剧降低。

2.2 不规则三角网组织方式

使用不规则三角网对LiDAR点云这种不规则的离散点数据集进行组织，能够很大程度上保留离散点的原始形态，不会造成严重的数据结构冗余，所以也有不少的研究者使用不规则三角网来对LiDAR点云进行组织和管理[6-8]。但是三角网的构造复杂，点云的海量数据规模使得三角网的构造相对费时，对于有突出变化的数据集组织效果较差。

2.3 八叉树组织方式

规则格网和不规则三角网都是以平面为基础的数据结构，八叉树则是一种用于描述三维空间的树状数据组织方式[9]。由于LiDAR点云就是一种三维数据，且在八叉树构造中离散点的归属很容易划分，所以使用八叉树来组织LiDAR点云具有很大的优势[10-11]。如果LiDAR点云的分布不均，很容易造成八叉树层次太深，降低LiDAR点云的空间索引效率。

3 LiDAR点云双层次双索引数据结构的建立

从LiDAR点云常用组织方式的分析可以看出，只使用一种数据结构对LiDAR点云进行组织，在构造速度、数据冗余、检索效率等方面难以达到平衡和高效。本文研究将“非空”规则立方体格网和K-D树相结合，采用在不同数据范围下使用相对应的空间数据结构并相互结合的方式建立LiDAR点云的数据管理和组织方式。

3.1 LiDAR数据组织方式的概念设计

从大尺度看，LiDAR点云构成了可以目视分辨的地表和各种地物，在一定程度上具有地理的连续性；从小尺度看，LiDAR点云又是一个个离散点，相互之间没有直接的联系(图1)。

图1 点云不同尺度范围Fig.1 Different scales of point cloud

这种大、小尺度上的差异，没有一种数据结构能涵盖解决，只有运用不同类型的数据组织方式能够比较好地解决对应的其中一种尺度的组织问题。本文运用不同类型的数据结构，首先在大尺度的整体范围上，使用“非空”规则立方体格网对LiDAR点云进行初次划分组织，组织方式就是在三维空间里将点云范围用一定的边长划分立体格网，使得若干个立方体组成的格网完整包围点云。由于点云可能存在分布不均的现象，所以会有某些立方体内没有包含LiDAR离散点，这种空立方体将会从格网中排除，即格网是由包含有一定数量离散点的“非空”立方体组成的“非空”规则立方体格网，使用这种非空的立方体格网能够避免数据冗余，同时在邻近搜索时也避免了对于空立方体的检索，每个立方体都有根据其空间位置而赋予的编号，这样对于某个或者某些离散点的空间位置就能快速初步定位。

由于“非空”规则立方体格网构造简单、查询效率高，而且一定程度上避免了空立方体的冗余，所以对于LiDAR点云的初步大尺度组织是比较好的。此时，在每个立方体的内部，由若干数量的LiDAR离散点构成了LiDAR点云的小尺度范围，在这个尺度上，离散点的数量相对不多，利用K-D树对立方体内的离散点进行再组织就形成一颗层次明显的查询树，这样组织内部离散点可以实现LiDAR点的精确快速定位和数据结构上的低冗余，而且由于立方体内部的离散点数量有限且比较均匀，使得内部K-D树的构造费时较少，结构也比较平衡，能够进一步提高空间检索效率。通过这种大范围初次组织、内部小范围再次组织，不同类型数据结构相结合的方式，就形成了LiDAR点云的双层次双索引数据结构(图2)。

图2 双层次双索引数据结构示意图Fig.2 Two-level double-indexing data structure

双层次双索引数据结构将LiDAR点云分为不同层次分别进行组织，然后再综合统一为整体结构。对于数据的空间检索先沿着大尺度定位至立方体网格，接着在立方体内部使用空间树精确定位的路线，根据LiDAR点云的数据特征，利用了不同类型数据结构的优点，从而达到较高效率和有效组织的目标。

3.2 LiDAR数据组织方式的具体实现

LiDAR点云的双层次双索引数据结构的逻辑设计是外围为“非空”规则立方体格网，内层为空间K-D树的2层结构，需要采用特定的物理结构来实现。

外层的“非空”规则立方体格网虽然具有类似普通格网的性质，但是由于“非空”格网的网格排列存在不连续性，所以不能采用连续数组来表达，本文选取红黑树[12]来实现“非空”规则立方体格网的物理结构。红黑树是一种具有自平衡特性的二叉查找树，所谓自平衡指的是在对红黑树进行插入和删除节点的时候，红黑树能调整自身的结构从而确保树结构大致平衡。红黑树的一个关键特性是查找的最长路径总是在最短路径的2倍以下，这个特性确保了红黑树具有极好的查找效率，是目前查找树中性能突出的一种结构[13]。

“非空”规则立方体格网是一种三维结构，确定一个立方体网格需要通过x，y，z3个索引来查找，而红黑树是只能用于1个维度检索的二叉树，所以需要将“非空”规则立方体格网分解为3个维度，每个维度都用1颗红黑树来组织。具体来说，首先以立方体的x索引作为比较值，使用红黑树进行第1层组织，每个节点存储了同一x位置下的立方体构成的yz平面，对每个节点的yz平面以y索引为比较值继续使用红黑树进行第2层组织，此时第2层的红黑树的每个节点就存储了同一y位置下的一列立方体，同样对这一列立方体使用红黑树进行以z索引为查找值的第3层组织，这样使用3层红黑树分别索引3个维度坐标，就构成了“非空”规则立方体格网的整体物理实现结构(图3)。

图3 “非空”规则立方体格网实现结构示意图Fig.3 Implementation of “non-null” regular cube grid structure

在每个立方体内部，则对其所包含的离散点集进行最终层次的组织，由于离散点的数量相对较少，直接采用3个维度的K-D树将这些LiDAR点构造成1颗查询树，建立K-D树时，仍然使用常用的构造方式，即轮流使用x,y,z维度作为划分维度，并按照离散点的编号依次进行划分。至此，立方体格网的内部层次也组织完毕，这样就形成了用于LiDAR点云组织的外围、内层2个层次和格网、查询树2种空间索引的混合数据结构。

LiDAR点云双层次双索引数据结构的具体实现,如图4所示。

图4 双层次双索引数据结构实现Fig.4 Implementation diagram of two-level double-indexing data structure

4 结 论

LiDAR点云的数据量非常庞大，而且激光脚点之间缺乏空间关联信息，对LiDAR点云进行分析处理前必须将点云数据通过一定的方式组织起来。

本文提出建立双层次双索引混合空间索引的方式对LiDAR点云数据进行组织管理，双层次双索引数据结构利用“非空”规则立方体格网和三维K-D树对点云的大、小尺度范围分别进行组织，并统一为整体结构，在物理实现上则采用了红黑树、K-D树等高效的数据结构作为实现基础。通过这种多层划分、多种索引类型混合组织的方式，可摆脱单一类型空间索引应用在LiDAR点云上的索引效率低和结构冗余问题，为LiDAR点云数据组织管理的研究提供一定方向上的启示。

[1]SAMBERG A. An Implementation of the ASPRS LAS Standard[C]∥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[C]∥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,etal. Remote Sensing of Species Mixtures in Conifer Plantations Using LiDAR Height and Intensity Data[J]. 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[J]. Computers and Electronics in Agriculture, 2002, 37(1): 71-95.

[5] PIEGL L A. TILLER W. Algorithm for Finding All k Nearest Neighbors[J]. Computer-Aided Design, 2002, 34(2): 167 - 172.

[6] ZENG Qi-hong,LAI Jia-zhen,XI Xian-hua,etal.Simple Building Reconstruction from LIDAR Point Cloud[C]∥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[J]. International Archives of Photogrammetry and Remote Sensing, 2000, 33(B3/2): 958-964.

[8] ZHANG K, CHEN S C, WHITMAN D,etal. A Progressive Morphological Filter for Removing Nonground Measurements from Airborne LIDAR Data[J]. IEEE Transactions on Geoscience and Remote Sensing, 2003, 41(4): 872-882.

[9] 李清泉,李德仁. 八叉树的三维行程编码[J]. 武汉测绘科技大学学报, 1997,22(2): 102-106.

[10]LINH T H, LAEFER D F. Octree-based, Automatic Building Façade Generation from LiDAR Data[J]. Computer-Aided Design, 2014, 53: 46-61.

[11]WANG M, TSENG Y. LiDAR Data Segmentation and Classification Based on Octree Structure[J]. Parameters, 2004,1:5.

[12]BAYER R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms[J]. Acta Informatica, 1972, 1(4): 290-306.

[13]HANKE S. The Performance of Concurrent Red-black Tree Algorithms[M]. New York: Springer, 1999.

(编辑：王 慰)

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

WU Bo-tao1, ZHANG Yu2, CHEN Wen-long2, SHEN Ding-tao2, Wei Si-qi2

(1.Yunnan Institute of Water & Hydropower Engineering Investigation, Design and Research, Kunming 650021, China; 2.Spatial Information Technology Application Department, Yangtze River Scientific Research Institute, Wuhan 430010, China)

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.

LiDAR; red-black tree; K-D tree; data structure; data organization; regular cube grid

2016-08-20

云南省水利厅水资源费项目(41501558)；云南省水利重大科技项目(CKSK2015852/KJ)

吴波涛(1970-)，男，云南呈贡人，高级工程师，研究方向为工程测量与摄影测量，(电话)13987116160(电子信箱)wbt5190523@126.com。

张 煜(1971-)，男，山东阳谷人，高级工程师，博士，研究方向为摄影测量与遥感，(电话)18986061273(电子信箱)zhangyu_1999@126.com。

10.11988/ckyyb.20160854

2016,33(11):32-35

TP317.4

A

1001-5485(2016)11-0032-04