基于改进四叉树结构的LAS数据空间索引建立方法

陶维重 徐 莹 杨 阳 刘 扬

（1.黑龙江地理信息工程院，黑龙江 哈尔滨 150081；2.北京师范大学地理科学学部，北京 100000）

0.引言

LAS文件是由美国摄影测量与遥感协会ASPRS（American Society for Photogrammetry and Remote Sensing）提出的用于保存激光点云数据的文件格式，被广泛使用在三维激光扫描、激光点云可视化、海量激光点云存储等。根据ASPRS对LAS文件结构的描述可知，LAS文件本身并不存在空间索引，这使得对LAS文件直接进行空间查询和空间分析等相关操作带来了不便。目前的做法是将LAS数据导入到第三方软件中再对激光点云数据建立空间索引，空间查询和分析等相关操作则由第三方软件提供接口来完成[1]。这种方式无法摆脱第三方软件本身的束缚，并且这些软件大多都不会公开空间索引算法，对激光点云分析的底层算法构建带来了麻烦，需要自己建立LAS数据空间索引的方法来解决以上问题。

四叉树空间索引结构是常见的地理数据空间索引的结构，四叉树结构简单易于实现，本文根据ASPRS对LAS文件的说明对其进行解析，结合空间索引建立方法和激光点云数据特点，分析传统四叉树结构针对该类型数据建立空间索引的一些缺陷，对四叉树结构进行改进，利用改进后的结构建立LAS激光点云数据的空间索引。

1 LAS数据读取方式介绍

1.1 LAS数据结构解析

根据ASPRS对LAS格式的说明，以目前较为通用的LAS1.3为例，LAS文件主要包含三个部分：公共文件头区、变长记录区、点集记录区[2]。

公共文件头区（Public header block）：该区域包含了该LAS文件的概要信息，如,版本号、总点数、范围信息、偏移量、变长记录区长度等信息。

变长记录区（Variable length records）：该区域被用于提高LAS数据的可扩展性，使LAS数据的存储方式更加灵活。

点集记录区（Point data records）：包含了点的空间位置和属性信息，如，XYZ、回波次数、回波强度等。

LAS本身不存在空间索引存储部分，只是单纯的点集数据，如果想进行空间查询类操作，需要开发者根据文件说明提取对应信息建立，通过解析LAS文件以上的信息，可以对LAS文件存储的激光点云数据规模进行预分析，得到建立空间索引所需要的相关数据。

1.2 开源LAS文件解析库LIBLAS

ASPRS对于LAS文件各个分区存储的长度均有说明，开发者可以根据文档对LAS文件进行定长读取，也可以使用LIBLAS开源库对LAS文件进行读取。LIBLAS是一个用于读写LAS文件开源C/C++库，从LAS1.0开始便在点云开发者网站上被评为最优秀的激光点云读写开源库，并且随着LAS数据的不断迭代而更新，在读写LAS数据上，被用于各种激光点云处理软件当中。基于LIBLAS对LAS文件优秀的兼容性，可以轻松得到LAS文件保存的激光点云数据相关信息，通过建立Reader对象，读取LAS文件中的公共文件头区建立Header对象，获取点云的概要信息，通过Reader中的ReadNextPoint方法移动指针对激光点云数据进行查找操作，从而实现读取激光点云数据的目的。后文中的所有算法中的关于激光点云读取部分的均是由LIBLAS实现。

2 基于改进四叉树的空间索引

2.1 传统的四叉树空间索引结构

四叉树索引是Tayeb在1998年提出的一种树状结构的数据索引[3]，其原理是将一块矩形区域四等分成四个子区域，每个子区域再次四等分，自顶向下递归操作，直到每个子区域包含的元素数量小于或等于规定的容量为止。四叉树具有明显的空间特性，根据四叉树的空间特性，可以利用其制作空间索引[4]，其原理结构（如图1所示）:

图1 四叉树结构原理

假设矩形区域内存在编号为1至9的地理数据，将区域等分为四个子区域ABCD，其中，B区域又四等分四个子区域，则地理数据索引的存储结构为（如图1所示），地理数据索引被存储在ACDxyzt子节点上，B节点作为父节点（子节点的上一级）不保存地理数据。这种存储方式方便，在数据量不大时空间查询的效率较高。但由于其是由顶向下依次划分的结构，在数据量逐渐增大时，树的层次结构也会随之加深，查询效率会受到影响[5]，此时需要重新调整单一节点的最大元素数量从而减少深度，保证查询效率。同时，如果地理数据分布不均匀，某些子节点的深度将非常深，而一些子节点的深度则很浅，不利于组织数据，使得四叉树索引的重心结构发生严重偏斜，尤其是针对数据量在千万级甚至亿级的激光点云数据上，这种传统的四叉树结构显然会影响空间索引的效率，所以需要对传统四叉树结构和构建方式进行优化，以便解决上述问题。

2.2 改进的四叉树空间索引结构

根据LAS文件的说明，在LAS文件的公共文件头区，可以得到文件中的激光点云数据概要信息。包括总点数量、范围信息，可以预估出整个LAS文件中的激光点云分布情况。而且在采集激光点云数据时，往往是采用均匀打点的方式，整个区域内的激光点云密集程度是相对一致的。根据这种特性，假设有一个深度为L的满四叉树（每个父节点都有四个子节点区域），其最深节点是由多个长为k宽为m的矩形区域的容器组成的，该容器用来存储激光点云的唯一标识ID，设LAS文件中最大最 小XY坐标为（MaxX，MaxY）、（MinX，MinY），则有关系：

这里所有的变量都是已知的，调整k和m的值，可以依此直接建立四叉树的最深一层，以最深层向上依次建立父节点容器，父节点容器存储子节点容器的索引，根据实际需要，可以继续向上建立父节点，这样便建立了一套可以控制深度的改进四叉树。

这种改进四叉树与传统四叉树本质区别在于：传统四叉树是由最上层的根节点向下生成的，而改进四叉树是优先构建好一个满四叉树的最深层，依次向上建立父节点，在向上建立父节点过程中，可以根据实际需要设定深度，不需要构建到最顶层，以便达到自由控制深度的目的。

遍历LAS文件中的点数据，每个点数据均有XYZ坐标及遍历时的指针位置，将三维的激光点云向二维平面投影，计算投影坐标XY，根据XY值计算该点数据所在的容器位置，假设存储位置为（IndexX，IndexY），则有以下关系：

此时找到了容器的位置，将点的标识ID存入容器中，这样便构成了改进四叉树最深层结构，为了节约内存，只有容器中有元素时，才在内存中划定一块区域用于存储，若容器元素数量为0，则该容器设置为NULL。

最深层构建完毕后，根据四叉树结构反推上一级容器结构，临近上层的容器长为2k，宽为2m，L2层级就是由L1层级推算而来（如图2所示），四个区域分别存储了其各自子节点容器的索引值，这样L1层与L2层便建立起关系。以这种方式向上继续构建父节点，可以构造任意深度的改进四叉树，该四叉树深度可控，同时，可根据数据量大小和数据分布情况调整容器大小，以便达到最佳的空间查询效率，不会存在传统四叉树深度过深、重心偏斜的情况，同时在组织数据时更加合理，使后续的空间分析功能更加高效易用。

图2 改进四叉树结构

3.空间查询的实现

以最常见的多边形查询为例，假设存在图2中的激光点云数据，对其进行多边形查询操作，其流程（如图3所示）：

图3 改进四叉树结构空间查询流程

（1）首先判断多边形的最大最小XY值，可以简单计算出该多边形区域的空间范围W；

（2）从改进四叉树最深层向上遍历，假设L层级中单个容器的空间范围为W（L），确保W（L）＜W＜W（L＋1），根据四叉树的结构特点，在L＋2层级必有一个容器完全包含W范围，根据最大最小XY值可以计算出该容器的索引；

（3）拿到该容器后，找到该容器的子节点上的所有容器，根据最大最小XY值判断哪些容器是完全包含的，这些容器下的最深节点处的容器中的点索引所指向的点将完全被包含在矩形框内部。而不完全包含的容器，则继续向下遍历，逐层判断，直到最深层，判断单点XY是否处于最大最小XY之间，如果是，归于结果集合，如果不是则舍去。

当模拟点击查询或最近距离R时，假设有一输入点，其坐标（X0，Y0），想找到离其最近的点数据来模拟点击查询或最近距离R范围内查询，其步骤（如图4所示）：

图4 改进四叉树结构模拟点击查询流程

该查询方式是针对改进四叉树结构中的数据索引进行查询，再由数据索引找到对应点。由于改进四叉树索引的查询本质上是将空间位置查询转化为数组索引的查询，速度是十分快的，理论上性能很强，在实际应用中也验证了这一点。改进四叉树空间索引使得LAS数据进行高效空间查询操作得到了可能。

4.结束语

空间索引是高效空间查询的必要组成部分，空间索引的结构决定了空间查询的效率。本文针对LAS激光点云数据文件格式特点，对传统四叉树结构空间索引进行改进，不借助任何第三方软件建立了一套适用于LAS激光点云数据的空间索引，在激光点云处理软件中具有很大意义，具有高效的空间索引结构意味着更多复杂算法的实现，从而丰富软件功能，提高了软件的可用性。传统的LAS处理软件旨在针对LAS数据整体进行操作，例如，滤波、分类等，空间索引的加入使得LAS数据的分析由整体变为局部，可以针对特定区域进行分析，甚至是建立拓扑分析等操作，使得海量激光点云数据的分析达到更高的层次。在黑龙江省基础测绘项目中，针对LAS处理过程中遇到的空间查询类问题均采用该方式进行操作，效率高、效果好，突破了第三方软件的限制。然而，该改进四叉树空间索引目前只是建立了改进四叉树空间索引模型，并没有对其中的细节进行优化，如，编码方式、数据压缩方式、最小单个容器最优范围选取等，可见该改进四叉树仍然具有优化空间，下一步将针对上面提出的细节进行优化，提升空间索引的效率，以提升软件在实际应用时的性能。