-
随着经济快速发展，对电力的供应和保障提出了越来越搞的要求，因此电力巡检也变得越来越重要。而线路走廊穿越的地理环境较为复杂，传统的运维手段面临着量测不准确、低效等诸多问题[1]。由于LiDAR数据具有较高的定位和测距精度，相比于传统的测绘手段，激光雷达技术（LiDAR）能够自动、快速获取高精度地面三维信息，并在电力、测绘、海洋以及环保等领域得到了广泛的应用[2]。在电力应用的中通过LiDAR获取到高精度DEM数据能够为选线决策、电力巡检等应用提供数据支撑；同时高精度的DEM数据也是电力自动化、智能化巡检应用中重要基础数据。
一般来说，通过机载LiDAR设备获取的数据中除了包含地面点外还包含大量建筑、植被冠层等非地面点信息。这些非地面点的存在严重影响了DEM提取的精度。
针对激光点云地面点提取的问题国内外众多学者对此进行了研究并发展了一系列地面地提取与滤波的方法，主要包括：以不规则三角网为基础的地面点提取算法[3]，以数学形态学为基础的滤波算法[4-5]，以激光点云扫描线坡度为基础的地面点提取算法[6]以及基于点云聚类和分割的地面点提取和非地面点滤除算法[7]。在各类算法中基于不规则三角网的算法具有更好的适应性，然而基于不规则三角网的算法提取结果受初始地面点和阈值影响很大，因此在三角网的基础上有学者提出了渐进三角网的地面点提取方法[8-9]，通过逐步插入和网格调整的方式，有效的避免了初始三角网构建后网格不调整导致的提取误差。然而虽然渐进三角网的方法能够取得较好的效果，但是由于此方法需要判断每一个点所在的三角网且在插入数据点过程中需要对网格进行调整，计算效率低，耗时长。
针对基于渐进三角网的地面提取效率低下的问题，本文在渐进三角网的算法基础上结合kd-tree和K近邻搜索算法提出了基于伪渐进三角网的地面点提取算法，在保证提取精度的条件下极大地提高了地面点提取的效率。
HTML
-
基于渐进三角网的地面点提取算法是在基于不规则三角网算法的基础上结合渐进三角网算法进行的改进。相比于基于不规则三角网的地面点提取方法，基于渐进三角网的算法在进行地面点提取的过程中能够根据提取地面点的结果对地面三角网的重新调整，从而解决了基于不规则三角网算法中静态构网导致地面点提取的累积误差。
基于渐进三角网的地面点提取主要流程如下：（1）地面种子点提取；（2）根据提取到的地面种子点构建初始三角网（TIN）；（3）根据初始三角网进行地面点提取以及渐进三角网的构建。
-
如表1所示基于渐进三角网的地面点提取流程分为：（1）地面种子点提取；（2）根据提取到的地面种子点构建初始三角网；（3）根据初始三角网进行地面点提取和渐进三角网的构建。相比于其他数据集，电力巡线过程中获取到的数据集有其特点，因此采用的提取过程存在一些区别，分析在电力巡线过程中基于渐进三角网的地面点提取算法主要过程：
总数/万个 本文方法提取数目/个 渐进三角网算法提取数目/个 相同点数目/个 相同点比例/% 51 143 261 141 329 142 423 99.42 114 340 531 339 952 337 341 99.06 332 1 325 753 1 330 465 1 322 452 99.75 2 105 6 634 451 6 693 531 6 606 532 99.57 Table 1.
Comparisons of ground point extraction results -
在电力应用中一般是沿输电线路获取点云数据，因此数据会呈现出条带状如图1所示：
Figure 1. Patrol point cloud distribution
如果采用传统的方法进行网格划分方式会存在大量不包含任何激光点的冗余网格，或网格中包含数据较少从而造成提取误差。为了减小由不规则条带状线路造成的计算误差，本文采用沿线路方向进行网格划分的方法提高关键地面点提取的精度，如图2所示：
Figure 2. Grid generation along point cloud distribution direction
一般来说为了消除建筑表面对地面关键点的影响，选取的网格尺寸需要大于建筑物尺寸，但是网格选取过大又会导致山顶部分点云被滤除从而造成误差。因此一般来说选取与最大单体建筑相同的大小的网格来进行地面点提取，提取得到的地面点点云剖面如图3所示：
Figure 3. Side view extraction from ground mesh points
图3为网格点提取的侧视图，图4为网格点提取正视图，从图3中可以看出通过提取网格最低点的方式能够很好的提取地面种子点。
Figure 4. Front view extraction from ground mesh points
-
在提取网格点的基础上构建不规则三角网如图5所示：
Figure 5. Ground points triangulation construction
图5为基于提取地面点构建的地面三角网的局部区域。一般来说三角网的构建都采用Delaunay三角剖分的方式进行构建[10]，Delaunay三角剖分的两个主要原则为：（1）空心圆准则，构成的三角形的外接圆中不包含第四个点；（2）最大化最小角准则，在满足条件的三角网中选取最小角最大的三角网构建方式。
Delaunay三角剖分的实现方式主要分为逐点插入法、三角网生长法和分治法三种[11]。虽然采用分治法具有较高的效率，然而在电力巡线的应用中由于点云数据量巨大，且构建的三角网需要持续调整因此选择逐点插入的方法对提取的地面种子点进行三角剖分。
-
基于渐进三角网的构建方法如图6所示：
Figure 6. Ground point extraction from progressive triangulation
基于渐进三角网的地面点提取流程图图6所示，其中图6(a)为地面点三角网局部放大展示；如图6(b)所示P点为待判断点，计算P点落在哪个三角网中，假设待判断三角形为三角形ABC，则判断点在三角网中的方法为：
(（1）) 由于ABC能构成三角形则空间中任意向量能够由向量
((2)) ((3)) ((4)) 则根据式(1)~(4)可以判断点P所在的三角形，若P处于点ABC构成的三角形中，则判断点P到三角形ABC所构成的面的距离以及点P到三角形ABC所三个顶点与面ABC构成夹角的最小值。
P点到面ABC的距离为：
((5)) 则P点到ABC的夹角为：
((6)) 式中：d为P到面ABC的距离。
-
基于渐进三角网的地面点提取算法充分考虑地形的连续性，在此基础上通过构建渐进三角网实现地面点的提取，针对地形连续的表面具有较好的效果，然而基于渐进三角网的地面点提取算法在每个点的插入过程都需要对全局三角网进行搜索和网格调整，计算复杂度随着点云数据量的增加成指数增加，在电力巡线过程中的海量点云数据效率较低。另外基于渐进三角网的地面点不仅需要存储点云数据还要存储点云所构成的三角网索引需要较大的存储空间。
1.1 基于渐进三角网地面点提取算法原理
1.2 基于渐进三角网地面点提取算法
1.2.1 地面种子点提取
1.2.2 不规则三角网构建
1.2.3 渐进三角网的构建
1.3 基于渐进三角网地面点提取算法问题
-
在基于渐进三角网的算法中首先需要构建三角网，在构建三角网的基础上判断待确定点所在的网格，然后针对所在判断待定点到所在三角网构成平面的距离和角度确定待判断点是否属于地面点。
如图7所示，如果采用渐进三角网的待定点判断方式则P点属于三角形ACD，实际上根据地理学第一定律，P点的特征应该同与其相近的ABC点更加类似。则我们假设待定点的判断不应该以构建三角网的三角形来判断，而是以与其最可能存在的面来判断。因此应该选择与其最近邻的ABC三点构成的面来进行判断。
Figure 7. Point judgment based on imitation progressive encryption TIN method
基于以上假本文针对渐进三角网存在的问题提出了一种基于渐进伪三角网算法的地面点提取方法。该方法主要分为同样分为三个步骤：（1）基于局部区域最低点的地面点种子点提取；（2）通过局部最低地面种子点构建kd-tree；（3）通过K近邻算法寻找最近邻的三个点构成的平面，采用公式(5)和公式(6)计算待定点到选定平面的距离和角度判断是否需要将待定点添加到点集中。
-
与基于渐进三角网的地面点提取算法相比，基于渐进伪三角网的地面点提取算法也首先要进行地面种子点的提取，在此技术上由于基于地面伪三角网算法不要进行三角网的构建，因此将数据以kd-tree的形式进行构建，其算法的主要过程为：
-
实际上点云是在空间上是三维点数据，但是在提取过程中高程信息作为我们关注的信息需要在计算中使用，在计算近邻的过程中只需要考虑二维平面坐标，因此构建kd-tree的过程也只需要利用X-Y二维坐标信息。
kd-tree是一种空间分割方式，其主要特点为将包含在空间的数据按照一定判断方式和层次进行二等分的划分如图8所示：
Figure 8. Kd-tree spatial point set partition
图8(a)为点集空间划分示例，图8(b)为模拟数据进行kd-tree划分的实例，二维kd-tree空间划分过程为：首先根据X坐标将点集划分为大于
-
此步骤包含三个过程分别为:（1）待插入点的K近邻点的查找；（2）距离角度计算；（3）kd-tree的更新。
图9为kd-tree的K近邻查找过程，其查找过程为回溯的过程，其中红色星号点为待查找的点。首先根据待查找点的位置判断其所在区域的分界点，在此基础想计算以待查找点为中心，待查找点与分界点为半径的圆是否与其他区域相切，如果相切则计算其他区域中是否有更近邻的点依次进行查找，则回溯过程就是根据最近邻点回溯得到K近邻的点。
Figure 9. K-nearest search of kd-tree
相比于判断待定点所在的三角形，采用kd-tree的数据组织形式进行K近邻查找，能够极大的提高算法的处理效率。另外相比于基于渐进三角网的算法每次网格点的插入都需要对网格进行调整，而重新调整网格计算复杂度较高，而kd-tree可以构建为平衡二叉树的模式，在此模式下进行数据插入的计算复杂度为
2.1 改进的渐进伪三角网的地面点提取原理
2.2 改进的基于渐进伪三角网的地面点提取算法
2.2.1 地面种子点构建kd-tree
2.2.2 渐进伪三角网的构建
-
通过渐进三角网算法地面点提取结果见图10：
Figure 10. Extraction of ground points from progressive triangulation
图10(a)通过渐进三角网提取结果，图10(b)为提取结果局部放大展示效果，从图10中可以直观的查看提取效果，从图中可以看出通过渐进三角网的地面点提取方法有效的剔除了房屋以及植被点，能够很好的提取出地面点。比较地面点提取前后的提取结果如图11所示：
Figure 11. Comparison of extraction results with original point clouds
图11(a)原始影像，图11(b)为植被点剔除的结果，从图11中可以看出通过渐进三角网的滤波算法基本上能够滤除非地面的植被点和建筑点云，但是在滤波过程中部分地面点也被滤除造成了漏提取的现象。
通过改进的伪渐进三角网提取算法提取效果如图12所示：
Figure 12. Comparison of the article results with original point clouds
图12(a)为原始点云数据，图12(b)为基于伪渐进三角网算法地面点提取的结果，图12(c)为基于渐进三角网算法地面点提取结果，图12(b)、(c)采用同样的阈值。从图上可以看出基于伪三角网的地面点提取算法与基于三角网的地面点提取算法提取结果具有很高的一致性，都能够很好的剔除非地面的植被点和建筑点云。
为了进一步比较本文提出方法与基于渐进三角网算法提取结果的差异，本文分别针对不同点云数据量的数据集采用此两种算法进行提取，提取结果如表1所示：
表1为本文提出的基于伪渐进三角网的地面点提取算法和与基于渐进三角网的提取算法的比较，从结果的比较中可以看出本文算法提取的地面点结果与基于渐进三角网的算法提取的结果具有很强的相似性，提取出相同的地面点的比例达到99%以上，从提取结果可以看出本文的方法在地面点的提取精度上与基于渐进三角网的方法具有较高的一致性。比较两种算法的计算效率：
表2为本文提出的方法与基于渐进三角网算法提取不同数据量大小的数据集的地面点的计算耗时，计算机硬件配置如下所示：
总数/万个 本文方法耗时/s 渐进三角网算耗时/s 51 2.31 4.31 114 5.43 11.4 332 54.54 154.43 2 105 357.34 1 034.34 Table 2.
Time spend with different dataset 1）CPU：Inte(R)Core(TM)i7-3517U@1.9GHz。
2）内存大小：8 GB。
3）开发语言：C++。
4）操作系统：Linux Ubuntu 18.4。
可以看出在数据量较小的情况下本文提出的方法与基于渐进三角网的算法耗时并无太大区别，随着数据集增大，相比于基于渐进三角网的地面点提取算法，本文提出的方法能够极大的缩短计算时间提高地面点提取效率。
3.1 实验与分析
-
本文提出的方法假设点是否为地面点的判断应该以其所最近邻的三个地面点为基础，通过构建平衡kd-tree算法提高K近邻点的搜索效率，同时构建平衡kd-tree提高了数据点的插入效率，相比于基于渐进三角网的地面点提取算法，本文所提出的基于伪渐进三角网的算法由于避免了判断处于哪个三角形。另外避免了由于插入点引起的三角网构建的调整，极大的提高了计算效率。
相比于基于渐进三角网的算法，本文提出的基于伪渐进三角网的算法能够在保证地面点提取精度的情况下更加高效的提取地面点，在针对电力巡线等数据量巨大且需要快速数据处理的应用中更加适用。
DownLoad:
