Effective organization and visualization of helicopter-based laser scanning data in power line inspection

伴随着电力行业的飞速发展，电网规模也相应壮大起来，架空输电线路传统的运行维护方式需要花费大量人力、物力去获取线下植被净空距离、导线弧垂等数据，但往往精度不高，增加了输电设备检修和输电通道事故防范的难度^[1]。采用直升机机载激光扫描系统对输电线路走廊开展3维量测，能够帮助电网运维部门在最短时间内收集输电线路走廊及设备本体精确的3维信息，为输电线路运行情况评估、危险点智能检测分析与预警等提供决策依据。

放眼国内外，机载激光扫描技术和激光点云后处理技术在电力巡线中得到了广泛的应用。主要集中在利用激光点云对电力线走廊地物进行分类^[2-3]、对走廊内危险点如植被高度的变化检测^[4-5]、电塔和电力线的3维重建^[6-9]、输电线路走廊3维可视化^[10]等方面, 而对于电力巡线直升机激光扫描数据的高效组织却鲜有研究。电力巡线直升机激光扫描系统能够直接获取扫描线上目标表面的3维空间坐标，具有密度高、数据量大的特点。随着飞行轨迹的延长和飞行时间的增加，会产生海量3维点云数据，点云的快速显示对计算机性能要求过高，后处理如简化滤波^[11]、语义分割和特征提取等交互操作受限于数据管理和可视化的性能，花费时间过久，不能满足电力巡检时效性的要求, 因此需要对海量点云数据进行高效组织。国内外学者对于这方面的研究主要关注点在优化点云数据存储结构上。采用一种或多种空间索引结合的方式对点云数据进行分割管理，如利用四叉树对点云数据进行组织和可视化^[12-15]。四叉树是一种常见的空间索引，主要应用于2维的数据管理，难以支持3维的激光点云数据。采用基于八叉树的索引结构对点云数据进行分块调度^[16-24]，在空间上很好地适应了3维点云结构，但由于输电线走廊内地物形状各异，以及水的吸收等因素导致点云分布不均匀，造成八叉树叶节点中数据密度分布的倾斜，使得八叉树构建速度较慢。

针对这些问题，本文中采用并行化的阈值分割算法构建八叉树，对激光点云数据进行分块处理，基于高程差的方法对八叉树叶节点上的点云进行抽稀，并保存在外存中建立点云八叉树的多分辨率细节分层(levels of details，LOD)数据结构, 最后设计了一种基于视点高度变化并结合分页数据库的内外存调度策略实现海量点云3维可视化。该方法能针对电力巡线直升机激光扫描数据分布不均匀的特性，提高八叉树构建速度，实现海量点云的流畅渲染，为直升机点云数据后处理和分析奠定基础。

海量点云的高效渲染显示需要有良好的数据组织结构作为支撑。该算法首先设置八叉树叶节点中的最小点云数量为阈值，用并行计算的方法对点云进行分块处理。接着，对每块点云精简抽稀合并，采用点云外包范围编码方式命名索引，以构建LOD结构。最后，在点云的八叉树LOD结果的基础上，根据视点远近加载不同块的点云，并通过分页数据库保证内存的稳定占用，实现海量点云渲染。流程如图 1所示。

Figure 1.  Flow chart of massive point cloud rendering

八叉树是四叉树在3维空间上的延伸，由于其采用规则的格网剖分，具有较好的可操作性，能满足3维视锥体裁剪算法^[18]。传统的八叉树方法虽然对于精确匹配点的查找性能较高，但树的动态性不好，平衡性较差。尤其是在面对大量不均匀分布的点云数据时，常会出现构建的八叉树深度过高，叶节点中数据不均匀，内存占用率大的情况，且单线程构建八叉树方法执行效率低，因此，作者在传统八叉树的数据索引结构的基础上，通过设置八叉树叶节点中最大点云数量作为八叉树划分的分割阈值，具体算法步骤见下。

算法输入：点云集合、八叉树的最大叶节点个数为N，节点指针为P，八叉树最大深度(树高)为H、点云八叉树外存存储的根目录。

算法输出：点云八叉树外存存储文件。

(1) 输入点云个数为D，初始化构建八叉树的最大深度(树高)H及最大叶节点个数N，并将节点指针指向根节点。设置阈值T为点云个数D/N。

(2) 计算点云的最小外包围盒的X_min，X_max，Y_min，Y_max，Z_min，Z_max，计算X和Y的最小值和最大值的差，取最大的差作为根节点外包正方体的边长。

(3) 如果八叉树深度不大于H-1，将空间等分为8个子节点，将外包范围赋值给P[i](i=0~7)，进入步骤(4)；如果八叉树深度等于H，则停止划分，进入步骤(5)。

(4) 遍历8个子节点，创建新的文件夹，并采用压缩编码算法命名子节点编号i，保存节点的外包围盒信息，回到步骤(3)。

(5) 根据指针关系遍历每个叶节点的父节点，计算其包含的点云总数为n。

(6) 如果n>T，可以继续分割产生叶节点及新的文件夹，否则将父节点的范围赋值给叶节点。

(7) 将每个叶子节点中的点云数据以二进制的形式保存在叶节点文件夹中。

(8) 退出算法。

具体算法的流程如图 2所示。在点云文件的外存存储结构中，第1层点云根目录的文件夹名称看起来像是乱码，但实质是将点云集合的基本坐标信息、外包范围信息等属性转换成Json文件，并对文件进行哈希压缩，形成字符串。分割后的点云文件以二进制格式存储在最后一层级文件夹中，以.ocd为后缀名。为了节省八叉树构建时间，采用并行化的方法，对整个工程点云进行分割，在消息传递接口(message passing interface, MPI)环境下运行，每个进程处理一部分点云。

Figure 2.  Partition and external organization of point cloud octree based on threshold segmentation

LOD技术在解决大规模3维场景中渲染效率的问题上提供了很好的思路，即根据物体模型的节点在显示环境中所处的位置和重要度，决定物体渲染的资源分配，降低非重要物体的面数和细节度，从而获得高效率的渲染运算，在3维仿真领域中得到了广泛应用。电力巡线直升机激光扫描数据主要关注输电线走廊内的特征地物，如杆塔、导线、线下植被等，而激光点云数据多在平坦区域造成冗余。为了使细节层次模型在每一层级上尽可能保留特征地物信息，并精简其它非重要的信息，考虑数据点的高程与邻近数据点的高程区域高程平均值的相关关系来判断某个数据点的保留与否。在前面构建八叉树索引的基础上，针对电力巡线直升机激光扫描数据的特性，采用改进的数据密度精简(data density reduction，DDR)抽稀算法，在使用搜索半径及高差阈值作为传统DDR算法的参量基础上，联合特征地物经验高程差作为限制条件，以叶结点的点云为起点，采用广度优先遍历的顺序由下向上逐层抽稀，得到点云的八叉树多分辨率LOD数据，并保存在上一节中所述的文件组织结构下，如图 3所示。

Figure 3.  LOD construction by data extraction method based on height difference

算法描述见下。

算法输入：八叉树点云结构。

算法输出：各层级的多分辨率点云数据。

(1) 将外存八叉树结构读取到内存链表中，设置搜索半径R及高差阈值ΔH；并根据经验值设置特征地物高H。

(2) 遍历八叉树叶节点链表结构为V, 如果链表的末结点是八叉树结构的叶子结点，进入步骤(3), 否则指针+1仍进入步骤(2)。

(3) 在叶子节点中，以外包中心点为圆心，在搜索半径为R的区域内统计点高程的平均值h，若指定点的高程值与该平均值的差Δh小于指定的高差阈值ΔH，则剔除该点。

(4) 将抽稀后的点云保存在该层级八叉树目录下，如果文件已经存在，则对点云进行合并操作。

(5) 遍历其余7个叶子节点，转到步骤(3), 否则转入步骤(2)。

输电线路走廊往往长达上百甚至上千公里，电力巡线直升机激光扫描点云数量常达到亿级。如此大规模3维场景绘制渲染的效率直接影响了3维可视化的效果。

3维场景渲染过程简单来讲分为3个阶段：更新交互阶段，即负责场景对象的运动和交互事件响应等；筛选阶段，即负责对场景中的对象进行筛选裁剪，将不会被用户看到或是没必要被用户看到的物体剔除；绘制阶段，即将所有待绘制目标数据送入渲染管线。由此可见，为了提高3维场景绘制渲染，可以在场景筛选阶段改善。

基于前面构建的八叉树存储结构，采用视锥体筛选的方法，以深度优先遍历点云八叉树结构，将每个节点的外包与视锥进行比较，剔除视锥之外的节点。保证了场景中只有视锥体范围内(近平面、远平面、上平面、下平面、左平面、右平面构成的六面梯形椎体)的一小部分节点是可见的，因而加速了场景的绘制速度，如图 4所示。

Figure 4.  Frustum culling method

3维场景的每一帧渲染是单线程操作。如果在大规模3维场景中进行漫游浏览，每一帧的变化带来的是地形、遥感影像、点云数据的变化，如果只在裁剪阶段对节点进行判断处理，对于计算机的CPU和内存来说是巨大的消耗。因此，本文中借鉴网络海量数据库搜索方法，采用分页数据库的方式，在更新交互阶段，开辟另一线程，对“一段时间之内始终不在当前页面上的场景子树”移除出内存，并将“新载入到当前页面”的场景子树加入渲染，即分页数据库。其中的“页面”是指视锥体范围, 如图 5所示。

Figure 5.  The internal and external storage scheduling strategy combining the view port change and the page database

具体步骤见下。

(1) 首先为多分辨率点云结构中的每一节点设置视点可视范围，通过PagedLOD节点挂载到渲染树中。启用场景筛选(Cull)。

(2) 在场景筛选过程中，遍历PagedLOD中的数据，根据视点远近加载相应节点，将其保存到“数据请求列表”。

(3) 分页数据库开启数据处理线程。首先删除“已弃用队列”中的对象，并从“数据请求列表”中获取新的请求。

(4) 若线程获取到新的数据请求，则将其送入“等待合并列表”，线程让出控制权。

(5) 场景的每次更新遍历所有PagedLOD节点，将一段时间内没有进入用户视野的节点送入“已弃用队列”，并将“等待合并列表”中的数据送入当前场景渲染树中。

根据视点高度作为搜索条件，将符合条件的结果在“页面”上显示，合理的内外存调度策略使得内存占用率能保持在一个较稳定的区间，保证渲染的效率。

本文中的点云数据来源于直升机电力巡线航拍的机载激光雷达点云数据，并以las文件格式组织。点的数据组成包括3维坐标信息(经度、纬度和高程值)和其它信息(回波数、分类号等)。实验区段为某±800kV特高压直流输电线路衡阳段，路径长度约5.4km，走廊占地面积约45km²。从中截取一部分区域，共有15813380个点，文件大小为422MB。计算机为普通笔记本电脑，配置为Core i5 2.4GHz、8GB内存、256GB硬盘，软件方面为Windows10 64位操作系统，VS2010编译环境，OSG3维渲染引擎。

设置不同的八叉树最大叶子节点个数和树高，八叉树建树耗时如表 1所示。由表 1可以看出，基于阈值分割的八叉树构建方较传统八叉树构建方法具有更快的速度，叶子节点中点云分布的平衡性较高，节省了存储空间。在叶子数量和深度适中时，基于阈值分割的八叉树构建方法具有较明显的优势，随着八叉树叶子节点个数增大，树高增加，两种方法在构树耗时上相近。

在此基础上，采用MPI并行化编程模型可以再一次提升构树速度，如图 6所示。3条曲线分别表示不同进程数，横坐标为构建八叉树的最大叶节点个数N，纵坐标为八叉树构建耗时t。比较MPI环境下，单进程、四进程和八进程的执行速度，可以看到, 基于并行计算的方法，随着开辟的进程数增加，八叉树构建速度可以得到很好的提高。

Figure 6.  Excution time under different processors

以数字高程模型和高分辨率遥感影像构建的输电线路走廊3维地理环境为基础，加载电力巡线直升机激光点云数据，可以一次性载入并流畅显示。帧数在25左右。海量点云3维可视化如图 7所示。

Figure 7.  3-D visualization of mass point cloud

为了高效处理大范围海量的电力巡线直升机激光扫描数据，其中的一个关键就是空间索引结构。传统的空间索引方法(如R树、KD树等)在解决不均匀分布数据组织时表现不佳。本文中使用基于阈值分割的八叉树构建方法，通过实验证明，此方法对于存在数据倾斜现象的大范围海量的空间数据，尤其是机载激光点云数据有较好的表现。除了对八叉树划分方法进行改进，基于MPI框架采用并行化的方法，也可以显著提高八叉树建树速度。

基于八叉树点云划分结构，通过改进的高差剔除法逐层精简抽稀点云，构建点云多分辨率LOD模型，在准确反映大范围地形起伏的前提下，保留了输电线路走廊特征地物的点云细节信息，配合视点变化和分页数据库的内外存调度策略，实现了海量电力巡线直升机激光扫描数据的流畅显示。