-
使用三维激光扫描技术获得地铁隧道的高密度、高精度的表面几何信息是目前地铁测量领域获取数据的新手段。利用隧道点云数据可以进行隧道的形变分析、竣工测量、病害检测等工作。但是，隧道点云数据量巨大，传统的数据管理方法已成为海量隧道点云后期数据处理的一大瓶颈，建立合理高效的隧道点云管理机制是进行隧道点云后续处理的前提[1]。目前，国内外学者针对空间数据的管理方法进行了大量的研究工作，其中，广泛应用的管理策略主要有格网索引[2]、四叉树索引[3]、八叉树索引[4]、KD树索引[5]、R树及其变种树索引[6-10]等。海量点云的空间形态千差万别，数据量巨大，单纯地使用一种索引模型往往难以进行高效管理，为了充分发挥不同索引的优势，多数学者将重心放在了两种及以上索引的混合索引模型的研究。文献[11]提出一种八叉树和三维R树集成的空间索引方法——3DOR树，该方法利用八叉树的收敛性创建R树叶节点，避免逐点插入费时过程，同时利用R树的高度平衡性来保证数据的检索效率。针对海量的空间分布不均匀的点云数据，该方法利用八叉树算法将点云划分完成后，叶节点数量庞大，虽然使用R树管理叶节点能保证索引结构的平衡性，但R树的高度将很大，R树中间节点的矩形重叠将变得严重，查询效率急剧下降。文献[12]提出了一种基于红黑树与KD树的点云数据管理方法，根据点云的数据结构特点，利用红黑树与KD树建立一种“非空”规则立方体格网和KD树相结合的双层次数据结构，用于点云的组织管理。由于红黑树和KD树都是二叉树，针对数据量巨大的点云，该方法构建的二叉树高度较大，索引效率较低。文献[13]提出了一种全局KD树与局部八叉树相结合的混合空间索引结构——KD-OcTree，该方法在全局使用KD树重构点云之间的邻域关系，在其叶子节点再构造二级索引结构——局部八叉树。该模型能一定程度地提高点云的邻域查询效率，但对于海量的条带状的空间点云数据，其上层的KD树深度较大，不利于点云的可视化。
现阶段海量点云索引研究主要存在以下两个问题：①单一索引难以适应海量空间分布复杂的数据，而混合索引适用性有限，难以满足多种空间分布、多密度的点云数据的管理需求[14]。②多层次、多分辨率模型的组织方法难以适应点云的密度变化。到目前为止，还没有学者针对地铁隧道点云这种特殊空间分布的点云提出专门的管理方法。本文针对目前海量点云管理方法存在的问题，结合地铁隧道点云的空间分布特点，提出了一种R树与格网混合的索引模型，实现了地铁隧道海量点云的管理。
HTML
-
地铁隧道距离较长，隧道的宽度约为5 m，平面位置变化较大，高程变化相对较小，点云空间分布特点明显，点主要集中在隧道壁的曲面上，隧道中间部分没有点分布。虽然地铁隧道点云覆盖了较大空间范围，但实际上点云主要分布在细条带状区域，点云在空间中分布不均匀。扫描仪在获取隧道点云时，架设在隧道的内部，因此扫描中心距离隧道壁的距离很近，因此，获取的隧道壁的点云密度极大，并且距离扫描仪越近的位置扫描点密度越大，越远的地方扫描点密度越小。地铁隧道点云的空间分布特点总结如下：
1) 点云平面位置变化较大，高程变化较小。
2) 点云在平面上呈细条带状分布，点分布在横向的柱面上。
3) 扫描点密度较大，密度分布不均匀。
-
空间格网可以很好地适应数据的空间分布，并且单个网格覆盖的空间范围较小，其内部的点云密度较为均匀，便于进行局部的管理。本文首先根据点云的平面覆盖范围建立平面格网，每个网格为固定边长Lg(本文设置网格边长为4 m)的正方形，如图 1所示。然后将点云中的所有点分配到格网中，分配完成后，删除没有点云数据的网格。
Figure 1. Dividing Point Cloud into Grids
-
隧道点云在空间中的分布规律比较明显，点云格网化分块后，每个网格内部的点云空间形态基本类似，主要由空间中不连续的两个曲面点云组合而成，大致如图 2所示。由于隧道点云密度分布不均匀，局部点密度较大，因此，部分网格内部点数量较大，不利于后期调度与处理。因此，本文在单个网格点云空间形态的基础上对每个网格内的点云建立局部索引进行管理。
Figure 2. Spatial Segmentation of Point Cloud in One Grid
常用的管理局部点云的索引有KD树、四叉树、八叉树等比较简单高效的索引模型。由于部分网格点密度极大，其内部点数量依然较大，而KD树索引不适用于管理数据量较大的点云，因此，针对单个网格点云的空间分布特点，本文采用八叉树与四叉树组合的索引策略，即使用八叉树算法对点云进行一次划分，然后使用四叉树算法对八叉树叶节点递归划分，直至叶节点内的点个数不超过Nm(本文设定的Nm值为50 000)。从图 2可以看出，利用八叉树划分网格点云可以将点云在三维空间中较为均匀地划分为8个部分。划分完成后，每一块点云集中在一个片状的空间不闭合的曲面上，如果采用八叉树算法继续划分，则每次划分会出现空节点或者个别节点中的点个数极少而不再继续划分的情况，这样会降低树的平衡性。而采用四叉树算法在平面上对节点进行划分可以使点云划分得更均匀，树的平衡性更好，索引的效率更高。为了比较两种方法的效果，本文选择密度不同的3个网格点云，分别使用八叉树算法和四叉树与八叉树混合的算法进行划分，并统计了相关指标，如表 1所示。从表 1中可以看出，混合算法与八叉树算法消耗的时间差别不大，并且树的深度也基本一致，但是混合算法构建的索引节点数目更少，平衡性更好，效率更高。
点个数 节点个数 层数 索引耗时/ms 八叉树|混合方法 八叉树|混合方法 八叉树|混合方法 4 886 326 390|271 4|5 755|789 8 031 506 616|407 5|5 1 658|1 444 15 168 507 1 252|807 5|5 2 912|3 260 Table 1. Statistics of Key Criterias of Different Indexes
-
每个网格局部索引建立完成后，整个点云由多个局部索引共同管理。如果隧道较长，则网格数量较多，而格网索引缺少层次，不利于LOD结构的构建，因此，需要将所有的网格管理起来。由于隧道点云在空间中呈条带状分布，因此，非空网格在空间中同样呈条带状分布，空间分布不均匀但有规律，如果使用传统树模型管理网格，则树的深度较大，并且平衡性较差，索引的效率较低。而R树具有适应空间数据的分布特性及高度平衡性，因此，本文采用R树对网格进行管理。
传统R树存在一个缺点，即兄弟节点对应的空间区域存在重叠，那么进行查询时存在多路径问题，影响查询效率。为了提高R树的构建效率，同时减少R树节点空间区域的重叠，Leutenegger等[15]提出了一种名为STR(sort-tile-recursive)的Packed R-trees算法，该算法是一种自下而上的静态R树的构建方法，简单高效，适合管理空间中分布比较规则的实体。不同行、列的网格在空间中没有任何重叠，本文利用这一特点，借鉴STR算法的切片组织思想，提出了一种网格R树的构建方法，该方法构建的R树的最大特点是同一层的R树节点的空间区域没有任何重叠，同时还具有传统R树的高度平衡性，查询效率优于传统R树。
具体实现方法如下：
1) 判断隧道点云的大致走向，判断依据为整个点云的外包围矩形较长的边在哪个坐标轴方向上，以X轴(Y轴)走向为例，如图 3所示。
Figure 3. R Tree Structure of All Grids
2) 将同一列(行)的所有网格组织为一个切片，作为第一层R树的一个节点，如图 3所示的红色矩形。
3) 设置R树节点的子节点个数值N(本文设为4)。
4) 在X(Y)方向上，将新的一层节点中每N个节点合为一组作为R树上一层的一个节点，最后剩余不足N个的节点也合为一个节点。
5) 计算新的一层R树节点个数Nn, 如果Nn≥N, 则重复4)、5)，否则，算法退出。
经过上述5个步骤，所有的网格被组织为一个多层的R树结构。
1.1. 地铁隧道点云空间分布特点
1.2. 地铁隧道点云格网划分
1.3. 单个网格点云细分
1.4. 自下而上的点云格网R树组织
-
合理的LOD结构是海量点云可视化与处理不可缺少的部分，点云LOD的构建过程可以看作是索引结构中父节点对子节点数据进行抽稀的过程。隧道点云密度分布不均匀，对于划分后的网格点云，部分网格点密度较大，而部分密度较小。为了获得高质量流畅的点云渲染效果，本文采用了一种基于网格面积的自下而上的LOD构建方法，具体方法如下。
1) 隧道点云索引建立完成后，可以获得初始格网节点所在的层Dg、整个点云的点个数Na和网格的个数Gn。
2) 设置索引结构的根节点存储的点个数Nr(本文设置为5 000个点)以及相邻两层采样间隔Sl，Sl的计算方法如下：
式中，ceil表示向上取整函数；Da表示均匀分割时索引结构的层数；Nm为单个网格划分时的叶节点最大点个数；Ln表示均匀分割时索引结构的叶节点个数。
3) 计算格网层采样总点数Ng：
4) 遍历所有网格，根据每个网格的最小外包围矩形顶点坐标计算每个网格的面积Si以及所有网格的面积之和Ss：
式中，n为网格个数；Xmaxi、Xmini、Ymaxi、Ymini为第i个网格的外包围矩形顶点坐标。
5) 计算每个网格的采样间隔Gi：
式中，Ni为第i个网格中的点个数。
按照计算得到的每个网格的采样间隔对每个网格的子节点进行抽稀，抽稀完成后，每个网格内采样得到的点个数与其面积成正比，与点密度无关。由于单个网格的点云密度比较均匀，因此，对于在索引结构中深度大于Dg的节点可采用等间隔采样的方式创建LOD(levels of detail)节点，采样间隔为Sl。同样的，采样后的所有网格的点云密度基本一致，因此，对深度小于Dg的节点同样采用等间隔采样的方法创建LOD节点，采样间隔同样为Sl，如图 4所示。
Figure 4. Process of Building LOD
-
隧道点云数据量巨大，通常管理一个区间的隧道点云的索引有上万个节点，文献[16]提出采用多文件的方式存储海量点云，多文件的存储方式会将整个点云数据分散存储到成千上万个文件中，整个点云数据会被存储在硬盘中不连续的区域内。动态调度时，会有成千上万次打开和关闭文件的操作，同时，由于点云数据存储的不连续性，从硬盘读取不同节点的数据时也会花费大量的硬盘寻道时间，严重影响动态调度的效率。因此，为了提高动态调度的效率，本文采用文献[11]提出的单文件存储点云数据的方法，将所有节点数据按照索引结构遍历的顺序保存到同一个文件中。图 5是点云场景渲染时，每一帧遍历节点的顺序，层数小于等于格网层的节点采用广度优先的遍历顺序，大于格网层的采用深度优先的遍历顺序，按照该顺序将所有节点数据保存到同一个文件中，并记录每个节点数据的相对起始地址Ar和偏移量F。渲染点云时，当视点较远时，视口覆盖范围较大，此时只需要加载上层节点经过抽稀的点云数据，广度优先遍历可以快速获取大范围的上层节点，当视点较近时，视口覆盖的范围较小，深度优先遍历可以快速获取局部小范围的节点。两种遍历顺序相结合可以提高点云的动态调度效率。
Figure 5. Traverse Sequence of Index Structure
-
为了验证本文提出的混合索引模型对海量地铁隧道点云数据管理的有效性，选取了武汉某地铁线路中的3段地铁隧道点云数据，记为数据1、数据2、数据3。数据1为一段大约280 m长的隧道点云数据，是通过隧道扫描小车获取的点云数据，点密度较为均匀，点个数为210 988 370，约占4.71 GB存储空间。数据2为一段大约500 m长的隧道点云数据，点个数为583 652 640，约占13.00 GB存储空间。数据3为一段大约1 500 m长的隧道点云数据，点个数为1 592 713 804，约占35.51 GB存储空间。数据2和数据3都是通过隧道内架设扫描仪获取的点云数据，点密度不均匀，离扫描仪较近的位置点云密度极大，远的地方较为稀疏，其中数据2的隧道宽度较窄，局部点密度最大。本文基于Visual Studio2013开发平台使用C++语言编程实现了索引结构，主要功能包括索引的建立、多分辨率层次LOD的建立、点云的动态调度可视化以及基本的交互。程序的运行平台为Windows10 64位系统，计算机硬件基本配置为IntelCore i5-4210 2.9 GHz，内存为8 GB，硬盘容量为750 GB，显卡为NVIDIA GTX960 m，2 GB。本实验采用独立显卡进行渲染加速，渲染帧数较高。
采用本文提出的点云管理方法对3组实验数据构建索引，并进行渲染。点云LOD的渲染效果如图 6所示，由于篇幅所限，这里主要展示数据1和数据3的渲染效果，数据2和数据3效果基本一致，差别主要在于隧道长度不同。
Figure 6. Efficacy of the LOD
渲染过程中，从不同的视角对不同密度区域的点云进行浏览，浏览过程中统计了空间索引的几个重要指标，统计结果如表 2所示。
点云数据 点个数 数据大小/GB 构建索引耗时/min 渲染消耗最大显存/MB 最小帧率/fps 数据1 210 988 370 4.71 5.9 238.9 60.0 数据2 583 652 640 13.00 17.7 371.2 49.2 数据3 1 592 713 804 35.51 45.7 347.1 51.9 Table 2. Statistics of Key Criterias of Index
从表 2可以看出，随着点云数据量的增大，构建索引花费的时间也在变大，但是渲染时消耗的显存并没有明显的增大。并且，整个渲染过程帧率都保持在40 fps以上，流畅度较高。数据2点云密度最大，渲染点云时，局部加载的点最多，消耗的显存最多，最小帧率也最小。从表 2可以得出，点云密度对渲染时消耗的计算机的资源有较大的影响，而隧道的长度影响较小。
本文将提出的管理方法与传统八叉树索引方法及QR树混合索引方法[17]进行了对比。将实验的3份数据使用3种索引模型进行管理，并统计了索引的相关指标，如表 3所示(其中方法1代表本文方法，方法2代表八叉树索引方法，方法3代表QR树混合索引方法)。其中，八叉树方法划分的停止条件为每个节点的点个数不超过50 000，与本文提出的方法停止条件一致。为了方便比较，实验设置QR树混合索引方法中的四叉树叶节点的外包围矩形边长不超过4 m，与本文方法设置的网格大小一致，然后使用八叉树算法对单个网格中的点云进行空间划分，划分停止的条件同样是叶节点中点个数不超过50 000，然后使用R树管理八叉树的叶节点。
点云数据 构建索引耗时/min 节点个数 选点耗时/ms 邻域查询耗时/ms 方法1|方法2|方法3 方法1|方法2|方法3 方法1|方法2|方法3 方法1|方法2|方法3 数据1 5.9|25.2|19.6 10 129|13 449|14 917 24|424|1 010 16|149|123 数据2 17.7|70.6|38.6 31 587|36 932|48 373 67|795|1 176 37|206|150 数据3 45.7|241.6|133.8 85 256|153 204|135 245 116|1 109|1 336 46|326|176 Table 3. Statistics of Key Criterias of Three Different Management Method
八叉树方法和QR树混合索引方法采用的点云的存储方式为多文件存储方式，即每个节点的点云存储在单独的文件中，创建LOD节点时，采用均匀采样的方式对子节点进行采样，采样间隔与本文计算出的采样间隔一致。表 3中每一个数据的选点耗时是在指该数据中不同密度的位置鼠标选择20个点，统计选择这20个点的平均耗时，而邻域查询耗时是指查询选择的每一个点的最邻近点所耗时间的平均值。通过对比可以得出，多文件八叉树的构建花费了大量的时间，远大于本文提出的方法和文献[17]方法。这主要是由于本文方法和文献[17]方法只需要读取一次点云数据便可将所有点云分配到小范围的网格中，而八叉树算法则需要多次读取划分点云，这大大增加了构建时间。同时，多文件的存储方式频繁的读取和保存文件也增加了大量的处理时间，因此文献[17]方法的构建索引耗时要多于本文方法。由于本文提出的方法构建的索引平衡性更好，因此，整个索引的节点个数小于八叉树和QR树的节点个数，并且本文的点云数据存储在硬盘的连续区域中，系统可以更快地读取节点的点云数据到内存中进行判断，因此，本文提出的方法在选点和邻域查询效率上有较大的优势。
本文还将索引的构建效率和渲染效果同Leica Cyclone软件和Pointools软件进行了对比，如表 4所示。本文取数据2的渲染效果进行了比较，如图 7所示。由于Cyclone和Pointools都是商业软件，因此无法测试其效率上限。从表 4可以看出，随着点云数据量的增大，两款商业软件构建索引的时间迅速增加，而本文的构建时间基本上与数据量成正比，效率优于两款软件。点云渲染时，Cyclone软件消耗的最大显存最小，点云渲染流畅度较高，但是存在点云加载不均匀的现象，如图 7(a)所示。而Pointools软件消耗的最大显存随着点云数据量的增大而增大，而且存在局部点云显示不全的现象，如图 7(b)所示，数据量较小时，Pointools软件有很高的渲染流畅度，而较大时，则出现了卡顿的现象。本文采用的方法渲染时消耗的最大显存基本是稳定的，与隧道长度无关，虽然消耗了较多的显存，但在可接受的范围内，局部显示点较为均匀，可视化效果较好，渲染流畅。在数据加载效率方面，Cyclone软件和本文采用的方法均有较高的数据加载速度，动态显示时，数据调度速度较快，当数据量较大时，Pointools软件出现数据加载缓慢的现象。在隧道点云的管理和可视化方面，本文方法与两款商业软件相比具有一定的优势。
Figure 7. Rendering Effects Comparison of Different Softwares
点云数据 点个数 构建索引耗时/min 渲染消耗最大显存/MB 本文方法|Cyclone|Pointools 本文方法|Cyclone|Pointools 数据1 210 988 370 5.9|7.3|3.4 238.9|187|160 数据2 583 652 640 17.7|21.3|20.1 371.2|220|330 数据3 1 592 713 804 45.7|98.6|96.5 347.1|203|370 Table 4. Statistics of Key Criterias of Three Different Softwares
-
本文针对海量地铁隧道点云数据的管理问题进行了研究。首先分析了地铁隧道点云的空间分布及点密度分布特点，提出了一种R树与格网混合的索引模型，并设计了基于节点面积的LOD结构回溯构建方法。为了提高点云动态调度的效率，本文采用了高效的隧道点云单文件的存储方式。实验证明，本文提出的隧道点云管理方法能有效支持海量的地铁隧道点云数据的可视化、交互以及调度处理等过程。
DownLoad:
