基于地面点去除与密度导向滤波的线路点云树木分割方法与流程

1.本发明涉及计算机视觉技术领域，具体地说，涉及基于地面点去除与密度导向滤波的线路点云树木分割方法。


背景技术：

2.近年来，无人机自主巡检已成为电力系统常用的巡检方式。其中，基于激光雷达点云的树障检测是一项重要任务。输配电线路因植被自然生长，植被与导线距离低于临界值而发生的凝间击穿现象从而导致电网跳闸的故障被称作树障。该类故障极易造成线路停运，甚至电网营运的严重事故，因此对树障预测的研究就有了迫切的现实意义。树障检测中的单木识别是重要一环，但对单木点云的识别与分割研究大部分集中在森林地区，而输配电线路场景的树木识别研究非常稀少。
3.相比于超高压输电线路，配电线路分布更加广泛、高度较低、场景更加复杂、树障发生频率更高。此外，由于相关数据量少、标注困难，因此，对配电电路点云场景的单木识别与分割具有更高难度和更大价值。
4.综上，现有技术存在网络设计复杂、数据标注需求大、效果欠佳等技术问题。鉴于此，我们提出了基于地面点去除与密度导向滤波的线路点云树木分割方法。


技术实现要素：

5.本发明的目的在于提供基于地面点去除与密度导向滤波的线路点云树木分割方法，以解决上述背景技术中提出的问题。
6.为实现上述技术问题的解决，本发明的目的之一在于，提供了基于地面点去除与密度导向滤波的线路点云树木分割方法，包括如下步骤：
7.s1、自适应地面点去除的数据预处理，利用点云场景中地面点与其他点在高程与密度上的差异来实现地面点的分离，具体为：
8.s1.1、首先在水平方向上将点云场景划分为若干个l*l大小的柱pillar，随后将pillar按h大小平均划分高程进行栅格化；其中，l＞＞h；
9.s1.2、统计各栅格内的点云数量作为密度值，用栅格高程均值代表该栅格高程，得到对应的高程-密度统计图；
10.s1.3、细化高程范围，将离散点用多项式函数进行拟合，得到高程与点云密度之间的函数对应关系；
11.s2、基于k-means聚类与密度导向滤波的树木实例提取，具体为：
12.s2.1、首先利用主成分分析法(pca)，计算点云数据在xyz三个维度上的特征值，用于将该点划分为线型点、面型点和散乱点三种形状特征；
13.s2.2、利用距离方法，获取点云中某一点的邻域，使用特征值推导出三种几何特征；并进一步推导该点的形状特征指数；
14.s2.3、树木为典型的非结构化特征，将非结构化点云进行k-means或高斯混合聚
类，实现对树木实例的初步区分；
15.s2.4、遍历初步聚类的所有簇，根据颜色均值和数量筛选，将簇内颜色统计值非绿色以及聚类点云数量不足的簇进行删除；
16.s2.5、采用密度导向滤波进行离群点删除，得到完整的树木实例。
17.作为本技术方案的进一步改进，所述s1.1中，对于同一个pillar，其第i个栅格内点云集合为：
18.si＝(p(x，y，z)|ih≤z＜(i+1)h)
19.其中，si为第i个栅格内点云集合，p(x，y，z)为第i个栅格内任意一点的三维坐标，h为pillar的高程。
20.作为本技术方案的进一步改进，所述s1.3中，将离散点用多项式函数进行拟合的方法包括：
21.待拟合数据为t＝[(h1，n1)，(h2，n2)，...，(hn，nn)]，hi为第i个栅格的高程均值，ni(i＝1，2，...，n)为点云数量，n为同一pillar内的高程栅格数量；设m多项式为：
[0022][0023]
其中，fm为拟合方程，hi是单变量输入，ω0，ω1，ω2，...，ωm是m+1个参数；
[0024]
用最小二乘法衡量预测值与实际值之间的差距，即：
[0025][0026]
其中，l(ω)为目标损失函数；
[0027]
通过对ωj求偏导并令其为0，可得：
[0028][0029][0030]
其中，为偏导函数，k为[0，m]中的任意一个参数；
[0031]
所以要求拟合多项式系数需要求解以下线性方程组：
[0032][0033]
通过将待拟合数据t代入线性方程组，即可求解拟合方程fm。
[0034]
作为本技术方案的进一步改进，所述s1.3中，高程与点云密度之间的函数对应关系中，根据地面点到非地面的过渡区域，点云密度会发生突变，拟合函数梯度最大处(高程
突变点)即为地面点云高程阈值；此时只需求出拟合方程fm的二阶导，令其为0：
[0035][0036]
其中，f
″m为拟合方程fm的二阶导，为二阶导函数，多项式系数在上步中已求出，则可计算出地面点云高程阈值h
′
，通过高程判断来去除地面点。
[0037]
作为本技术方案的进一步改进，所述s2.2中，距离方法的计算过程为：
[0038]
获取点云中某一点p的k邻域；根据输入的点云构建k维树kd-tree，对于空间中某一点p(x，y，z)，利用kd-tree搜索点p的k邻域pi＝{(xi，yi，zi)|i＝1，2，3，...，k}；根据获取的k邻域建立协方差矩阵m：
[0039][0040]
cov(x，y)＝e(x-e(x))e(y-e(y))
[0041]
其中，x，y，z为任意点三维坐标上的随机变量，cov(x，y，z)为协方差矩阵m，cov(x，x)，cov(x，y)，...，cov(z，z)为随机变量两两之间的协方差，e为随机变量的期望；
[0042]
通过svd分解计算协方差矩阵m的特征值λ1＞λ2＞λ3＞0，令使用特征值推导出三种几何特征：
[0043][0044]
其中，μ＝σ1，α
1d
，α
2d
，α
3d
分别表示该点属于线型点、面型点和散乱点三种形状特征的概率；
[0045]
进一步可以推导点p的形状特征指数为：
[0046]dp
＝arg max[α
dd
]，d∈[1，3]
[0047]
其中，d
p
为点p的形状特征指数，α
dd
为点p属于线型点(d＝1)、面型点(d＝2)和散乱点(d＝3)三种形状特征的概率。
[0048]
作为本技术方案的进一步改进，所述s2.3中，采用k-means聚类算法对非结构化点云进行聚类，即根据点云样本间距离，通过预设目标并反复迭代，得到最终的聚类结果；具体方法为：
[0049]
随机确定k个聚类中心(需大于场景中树木实例个数)，根据点云样本到聚类中心的距离，将所有点云样本划分为k类；
[0050]
随后，计算每个聚类的均值作为新的聚类中心，再次划分样本，直至聚类中心不再发生变化，实现对树木实例的初步区分。
[0051]
作为本技术方案的进一步改进，所述k-means聚类算法中，某个样本xi与第k个聚类中心距离的计算式为：
[0052]
dist(xi，k)＝||x
i-k||2[0053]
其中，dist(xi，k)为样本xi与第k，k∈[1，k]个聚类中心之间的距离；
[0054]
遍历所有聚类中心，最小距离所对应的k值，则为该样本所属类别。
[0055]
作为本技术方案的进一步改进，所述s2.4～s2.5中，初步聚类的k个簇中，包含有树木实例与若干非树木实例；通过遍历所有簇，根据颜色均值和数量筛选，将簇内颜色统计值非绿色以及聚类点云数量不足的簇进行删除；
[0056]
剩余簇内除单木点云外，包含较多噪音点与离群点，采用密度导向滤波进行离群点删除，从而得到完整的树木实例；
[0057]
此时，剩余聚类点可划分为典型独立树、长排连续树、稀疏灌木、未完全聚类树四类。
[0058]
作为本技术方案的进一步改进，所述s2.5中，密度导向滤波的算法包括：
[0059]
对同一簇类，按照区域生长算法，划分为r个同心圆；其中，生长半径r＝d/r，d为簇中最远点到簇中心的距离；
[0060]
在每段区域si中，根据密度方向与大小，计算密度分布系数(由密度方向与大小组成)：
[0061][0062][0063]
其中，si为区域内点云集合，xi为区域内的点，x为聚类中心；d
direct_i
(直接的密度分布)、d
dense_i
(稠密的密度分布)这两个值代表密度分布均匀程度，均在0～1之间(分数越高则越均匀)；
[0064]
考虑到未完全分类的情况，需要给靠近聚类中心的区域添加较高的偏置，即其中θ为离群点阈值，λ为调控因子，λ越大则该区域越难划分为离群点；则密度导向滤波为：
[0065][0066][0067]
其中，dgf(si)为深度引导滤波，s
dens_i
为偏置的点云聚类区域。
[0068]
本发明的目的之二在于，提供了一种线路点云树木分隔操作平台装置，包括处理器、存储器以及存储在存储器中并在处理器上运行的计算机程序，处理器用于执行计算机程序时实现上述的基于地面点去除与密度导向滤波的线路点云树木分割方法的步骤。
[0069]
本发明的目的之三在于，提供了一种计算机可读存储介质，所述计算机可读存储介质存储有计算机程序，所述计算机程序被处理器执行时实现上述的基于地面点去除与密度导向滤波的线路点云树木分割方法的步骤。
[0070]
与现有技术相比，本发明的有益效果：
[0071]
1.该基于地面点去除与密度导向滤波的线路点云树木分割方法中，先对点云场景进行自适应的地面点去除预处理，将点云场景进行格栅化并得到格栅的高程与点云密度函数关系，再使用聚类算法结合密度导向滤波的方法进行树木实例提取，可以快速准确地获取各点的形状特征，进而快速区分树木实例结构，可以有效降低非聚类簇和离散点的影响，提高分割及识别精度，降低配电线路巡检中树障的影响；
[0072]
2.该基于地面点去除与密度导向滤波的线路点云树木分割方法中，还可以通过密集采样，在统计图上连接栅格密度值，计算每段折线斜率来近似突变高程点，进而可动态计算地面点高程阈值，对于地面经验阈值未知以及地形变化复杂场景具有较强鲁棒性，可以有效解决现有技术中网络设计复杂、数据标注需求大、效果欠佳的问题。
附图说明
[0073]
图1为本发明中示例性的整体方法流程图；
[0074]
图2为本发明中示例性的点云场景格栅化原理图；
[0075]
图3为本发明中示例性的点云格栅对应的高程-密度统计图；
[0076]
图4为本发明中示例性的设置不同多项式因子m得到不同的拟合效果对比图；
[0077]
图5为本发明中示例性的原始点云场景图；
[0078]
图6为本发明中示例性的线型点、面型点和散乱点三种形状特征示意图；
[0079]
图7为本发明中示例性的近邻点结构性特征筛选效果图；
[0080]
图8为本发明中示例性的非结构化点云聚类效果图；
[0081]
图9为本发明中示例性的聚类中心变化过程原理图；
[0082]
图10为本发明中示例性的聚类得到树木实例效果图；
[0083]
图11为本发明中示例性的典型独立树示意图；
[0084]
图12为本发明中示例性的长排连续树示意图；
[0085]
图13为本发明中示例性的稀疏灌木示意图；
[0086]
图14为本发明中示例性的未完全聚类示意图；
[0087]
图15为本发明中示例性的密度导向滤波中添加较高偏置后的线性图；
[0088]
图16为本发明中示例性的采用密度导向滤波操作的前后效果对比图；
[0089]
图17为本发明中示例性的电子计算机平台装置结构图。
具体实施方式
[0090]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整的描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0091]
实施例1
[0092]
如图1-图16所示，本实施例提供了基于地面点去除与密度导向滤波的线路点云树木分割方法，包括如下步骤。
[0093]
s1、自适应地面点去除的数据预处理：
[0094]
该方法主要利用点云场景中地面点与其他点在高程与密度上的差异来实现地面点的分离，具体为：
[0095]
s1.1、首先在水平方向上将点云场景划分为若干个i*i大小的柱pillar，随后将pillar按h大小平均划分高程进行栅格化；其中，1＞＞h；如图2；
[0096]
对于同一个pillar，其第i个栅格内点云集合为：
[0097]
si＝(p(x，y，z)|ih≤z＜(i+1)h)
[0098]
其中，si为第i个栅格内点云集合，p(x，y，z)为第i个栅格内任意一点的三维坐标，h为pillar的高程。
[0099]
s1.2、统计该栅格内的点云数量ni作为密度值，用栅格高程均值代表该栅格高程，得到对应的高程-密度统计图，如图3所示。
[0100]
s1.3、通过细化高程范围，将离散点用多项式函数进行拟合，可大致得到高程与点云密度之间的函数对应关系；
[0101]
具体地，将离散点用多项式函数进行拟合的方法包括：
[0102]
待拟合数据为t＝[(h1，n1)，(h2，n2)，...，(hn，nn)]，hi为第i个栅格的高程均值，ni(i＝1，2，...，n)为点云数量，n为同一pillar内的高程栅格数量；设m多项式为：
[0103][0104]
其中，fm为拟合方程，hi是单变量输入，ω0，ω1，ω2，...，ωm是m+1个参数；
[0105]
用最小二乘法衡量预测值与实际值之间的差距，即：
[0106][0107]
其中，l(ω)为目标损失函数；
[0108]
通过对ωj求偏导并令其为0，可得：
[0109][0110][0111]
其中，为偏导函数，k为[0，m]中的任意一个参数；
[0112]
所以要求拟合多项式系数需要求解以下线性方程组：
[0113][0114]
通过将待拟合数据t代入线性方程组，即可求解拟合方程fm。
[0115]
其中，设置不同的多项式因子m可得到不同的拟合效果，如图4所示；为平衡拟合精度与计算效率之间的关系，该系数可优选设置为5。
[0116]
进一步地，高程与点云密度之间的函数对应关系中，根据地面点到非地面的过渡区域，点云密度会发生突变，拟合函数梯度最大处(高程突变点)即为地面点云高程阈值；此时只需求出拟合方程fm的二阶导，令其为0：
[0117][0118]
其中，f
″m为拟合方程fm的二阶导，为二阶导函数，多项式系数在上步中已求出，则可计算出地面点云高程阈值h
′
，通过高程判断来去除地面点。
[0119]
此外，该方法也通过密集采样，在统计图上连接栅格密度值，计算每段折线斜率来近似突变高程点。该方法可动态计算地面点高程阈值，对于地面经验阈值未知以及地形变化复杂场景具有较强鲁棒性。
[0120]
s2、基于k-means聚类与密度导向滤波的树木实例提取，以图5的原始点云场景为例，具体为：
[0121]
s2.1、首先利用主成分分析法(pca)，计算点云数据在xyz三个维度上的特征值，用于将该点划分为线型点、面型点和散乱点三种形状特征，如图6。
[0122]
s2.2、利用距离方法，获取点云中某一点的邻域，使用特征值推导出三种几何特征；并进一步推导该点的形状特征指数；
[0123]
具体地，距离方法的计算过程为：
[0124]
获取点云中某一点p的k邻域；根据输入的点云构建k维树kd-tree，对于空间中某一点p(x，y，z)，利用kd-tree搜索点p的k邻域pi＝{(xi，yi，zi)|i＝1，2，3，...，k}；根据获取的k邻域建立协方差矩阵m：
[0125][0126]
cov(x，y)＝e(x-e(x))e(y-e(y))
[0127]
其中，x，y，z为任意点三维坐标上的随机变量，cov(x，y，z)为协方差矩阵m，cov(x，x)，cov(x，y)，...，cov(z，z)为随机变量两两之间的协方差，e为随机变量的期望；
[0128]
通过svd分解计算协方差矩阵m的特征值λ1＞λ2＞λ3＞0，令使用特征值推导出三种几何特征：
[0129][0130]
其中，μ＝σ1，α
1d
，α
2d
，α
3d
分别表示该点属于线型点、面型点和散乱点三种形状特征的概率；
[0131]
进一步可以推导点p的形状特征指数为：
[0132]dp
＝arg max[α
dd
]，d∈[1，3]
[0133]
其中，d
p
为点p的形状特征指数，α
dd
为点p属于线型点(d＝1)、面型点(d＝2)和散乱点(d＝3)三种形状特征的概率。
[0134]
s2.3、树木为典型的非结构化特征，将其用绿色点云表示，线性特征点用红色表示，可得到如图7所示的分割结果；随后将非结构化点云进行k-means或高斯混合聚类，实现对树木实例的初步区分，效果如图8所示；
[0135]
具体地，k-means算法是一种典型的聚类方法，根据点云样本间距离，通过预设目
标并反复迭代，得到最终的聚类结果；具体方法为：
[0136]
随机确定k个聚类中心(需大于场景中树木实例个数)，根据点云样本到聚类中心的距离，将所有点云样本划分为k类；
[0137]
随后，计算每个聚类的均值作为新的聚类中心，再次划分样本，直至聚类中心不再发生变化，实现对树木实例的初步区分。其迭代过程变化如图9所示。
[0138]
其中，某个样本xi与第k个聚类中心距离的计算式为：
[0139]
dist(xi，k)＝||x
i-k||2[0140]
其中，dist(xi，k)为样本xi与第k，k∈[1，k]个聚类中心之间的距离；
[0141]
遍历所有聚类中心，最小距离所对应的k值，则为该样本所属类别；
[0142]
最终，所有非结构化点云聚类成k簇，且包含带有不同噪音的单木实例，效果如图10。
[0143]
s2.4、初步聚类的k个簇中，包含有树木实例与若干非树木实例；遍历所有簇，根据颜色均值和数量筛选，将簇内颜色统计值非绿色以及聚类点云数量不足的簇进行删除；
[0144]
s2.5、剩余簇内除单木点云外，包含较多噪音点与离群点，采用密度导向滤波进行离群点删除；剩余聚类点可划分为典型独立树、长排连续树、稀疏灌木、未完全聚类树四类，如图11-图14所示；采用密度导向滤波可将聚类中的离群点筛除，可得到完整的树木实例。
[0145]
具体地，密度导向滤波的算法包括：
[0146]
对同一簇类，按照区域生长算法，划分为r个同心圆；其中，生长半径r＝d/r，d为簇中最远点到簇中心的距离；
[0147]
在每段区域si中，根据密度方向与大小，计算密度分布系数(由密度方向与大小组成)：
[0148][0149][0150]
其中，si为区域内点云集合，xi为区域内的点，x为聚类中心；d
direct_i
(直接的密度分布)、d
dense_i
(稠密的密度分布)这两个值代表密度分布均匀程度，均在0～1之间(分数越高则越均匀)；
[0151]
考虑到未完全分类的情况，需要给靠近聚类中心的区域添加较高的偏置，即其中θ为离群点阈值，λ为调控因子，λ越大则该区域越难划分为离群点；则密度导向滤波为：
[0152][0153][0154]
其中，dgf(si)为深度引导滤波，s
dens_i
为偏置的点云聚类区域，如图15所示。
[0155]
进而，滤波前后的树木实例对比如图16所示。
[0156]
如图17所示，本实施例还提供了一种线路点云树木分隔操作平台装置，该装置包括处理器、存储器以及存储在存储器中并在处理器上运行的计算机程序。
[0157]
处理器包括一个或一个以上处理核心，处理器通过总线与存储器相连，存储器用于存储程序指令，处理器执行存储器中的程序指令时实现上述的基于地面点去除与密度导向滤波的线路点云树木分割方法的步骤。
[0158]
可选的，存储器可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，如静态随时存取存储器(sram)，电可擦除可编程只读存储器(eeprom)，可擦除可编程只读存储器(eprom)，可编程只读存储器(prom)，只读存储器(rom)，磁存储器，快闪存储器，磁盘或光盘。
[0159]
此外，本发明还提供一种计算机可读存储介质，计算机可读存储介质存储有计算机程序，计算机程序被处理器执行时实现上述的基于地面点去除与密度导向滤波的线路点云树木分割方法的步骤。
[0160]
可选的，本发明还提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得计算机执行上述各方面基于地面点去除与密度导向滤波的线路点云树木分割方法的步骤。
[0161]
本领域普通技术人员可以理解，实现上述实施例的全部或部分步骤的过程可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，程序可以存储于计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0162]
以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的仅为本发明的优选例，并不用来限制本发明，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。

技术特征：
1.基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，包括如下步骤：s1、自适应地面点去除的数据预处理，利用点云场景中地面点与其他点在高程与密度上的差异来实现地面点的分离，具体为：s1.1、首先在水平方向上将点云场景划分为若干个l*l大小的柱pillar，随后将pillar按h大小平均划分高程进行栅格化；s1.2、统计各栅格内的点云数量作为密度值，用栅格高程均值代表该栅格高程，得到对应的高程-密度统计图；s1.3、细化高程范围，将离散点用多项式函数进行拟合，得到高程与点云密度之间的函数对应关系；s2、基于k-means聚类与密度导向滤波的树木实例提取，具体为：s2.1、首先利用主成分分析法，计算点云数据在xyz三个维度上的特征值，用于将该点划分为线型点、面型点和散乱点三种形状特征；s2.2、利用距离方法，获取点云中某一点的邻域，使用特征值推导出三种几何特征；并进一步推导该点的形状特征指数；s2.3、树木为典型的非结构化特征，将非结构化点云进行k-means或高斯混合聚类，实现对树木实例的初步区分；s2.4、遍历初步聚类的所有簇，根据颜色均值和数量筛选，将簇内颜色统计值非绿色以及聚类点云数量不足的簇进行删除；s2.5、采用密度导向滤波进行离群点删除，得到完整的树木实例。2.根据权利要求1所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s1.1中，对于同一个pillar，其第i个栅格内点云集合为：s
i
＝(p(x，y，z)|ih≤z＜(i+1)h)其中，s
i
为第i个栅格内点云集合，p(x，y，z)为第i个栅格内任意一点的三维坐标，h为pillar的高程。3.根据权利要求2所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s1.3中，将离散点用多项式函数进行拟合的方法包括：待拟合数据为t＝[(h1，n1)，(h2，n2)，...，(h
n
，n
n
)]，h
i
为第i个栅格的高程均值，n
i
(i＝1，2，...，n)为点云数量，n为同一pillar内的高程栅格数量；设m多项式为：其中，f
m
为拟合方程，h
i
是单变量输入，ω0，ω1，ω2，...，ω
m
是m+1个参数；用最小二乘法衡量预测值与实际值之间的差距，即：其中，l(ω)为目标损失函数；通过对ω
j
求偏导并令其为0，可得：
其中，为偏导函数，k为[0，m]中的任意一个参数；所以要求拟合多项式系数需要求解以下线性方程组：通过将待拟合数据t代入线性方程组，即可求解拟合方程f
m
。4.根据权利要求3所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s1.3中，高程与点云密度之间的函数对应关系中，根据地面点到非地面的过渡区域，点云密度会发生突变，拟合函数梯度最大处即为地面点云高程阈值；此时只需求出拟合方程f
m
的二阶导，令其为0：其中，f
m
″
为拟合方程f
m
的二阶导，为二阶导函数，多项式系数在上步中已求出，则可计算出地面点云高程阈值h
′
，通过高程判断来去除地面点。5.根据权利要求1所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s2.2中，距离方法的计算过程为：获取点云中某一点p的k邻域；根据输入的点云构建k维树kd-tree，对于空间中某一点p(x，y，z)，利用kd-tree搜索点p的k邻域p
i
＝{(x
i
，y
i
，z
i
)|i＝1，2，3，...，k}；根据获取的k邻域建立协方差矩阵m：cov(x，y)＝e(x-e(x))e(y-e(y))其中，x，y，z为任意点三维坐标上的随机变量，cov(x，y，z)为协方差矩阵m，cov(x，x)，cov(x，y)，...，cov(z，z)为随机变量两两之间的协方差，e为随机变量的期望；通过svd分解计算协方差矩阵m的特征值λ1＞λ2＞λ3＞0，令使用特征值推导出三种几何特征：
其中，μ＝σ1，α
1d
，α
2d
，α
3d
分别表示该点属于线型点、面型点和散乱点三种形状特征的概率；进一步可以推导点p的形状特征指数为：d
p
＝argmax[α
dd
]，d∈[1，3]其中，d
p
为点p的形状特征指数，α
dd
为点p属于线型点、面型点和散乱点三种形状特征的概率。6.根据权利要求5所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s2.3中，采用k-means聚类算法对非结构化点云进行聚类，即根据点云样本间距离，通过预设目标并反复迭代，得到最终的聚类结果；具体方法为：随机确定k个聚类中心，根据点云样本到聚类中心的距离，将所有点云样本划分为k类；随后，计算每个聚类的均值作为新的聚类中心，再次划分样本，直至聚类中心不再发生变化，实现对树木实例的初步区分。7.根据权利要求6所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述k-means聚类算法中，某个样本x
i
与第k个聚类中心距离的计算式为：dist(x
i
，k)＝||x
i-k||2其中，dist(x
i
，k)为样本x
i
与第k，k∈[1，k]个聚类中心之间的距离；遍历所有聚类中心，最小距离所对应的k值，则为该样本所属类别。8.根据权利要求7所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s2.4～s2.5中，初步聚类的k个簇中，包含有树木实例与若干非树木实例；通过遍历所有簇，根据颜色均值和数量筛选，将簇内颜色统计值非绿色以及聚类点云数量不足的簇进行删除；剩余簇内除单木点云外，包含较多噪音点与离群点，采用密度导向滤波进行离群点删除，从而得到完整的树木实例；此时，剩余聚类点可划分为典型独立树、长排连续树、稀疏灌木、未完全聚类树四类。9.根据权利要求8所述的基于地面点去除与密度导向滤波的线路点云树木分割方法，其特征在于，所述s2.5中，密度导向滤波的算法包括：对同一簇类，按照区域生长算法，划分为r个同心圆；其中，生长半径r＝d/r，d为簇中最远点到簇中心的距离；在每段区域s
i
中，根据密度方向与大小，计算密度分布系数：中，根据密度方向与大小，计算密度分布系数：其中，s
i
为区域内点云集合，x
i
为区域内的点，x为聚类中心；d
direct_i
、d
dense_i
这两个值代表密度分布均匀程度，均在0～1之间；考虑到未完全分类的情况，需要给靠近聚类中心的区域添加较高的偏置，即其中θ为离群点阈值，λ为调控因子，λ越大则该区域越难划分为离群点；则密度导向滤波为：
其中，dgf(s
i
)为深度引导滤波，s
dens_i
为偏置的点云聚类区域。

技术总结
本发明涉及计算机视觉技术领域，具体为基于地面点去除与密度导向滤波的线路点云树木分割方法。自适应地面点去除：首先将点云场景进行栅格化，得到高程与点云密度之间的函数对应关系；基于K-Means聚类与密度导向滤波的树木实例提取：计算点云数据在xyz三个维度上的特征值，推导出三种几何特征及点的形状特征指数，将非结构化点云进行聚类；将簇内颜色统计值非绿色、聚类点云数量不足的簇及离群点进行删除。本发明设计可以快速准确地获取各点的形状特征，进而快速区分树木实例结构，有效降低非聚类簇和离散点的影响，提高分割及识别精度，降低配电线路巡检中树障的影响；且对于地面经验阈值未知以及地形变化复杂场景具有较强鲁棒性。强鲁棒性。强鲁棒性。


技术研发人员：何明蔚 朱晓红 徐跃琴 单潇 杨紫棋 范云方 李涛 李琼慧 宋雅君 何周艳 徐丽琼
受保护的技术使用者：云南电网有限责任公司曲靖供电局
技术研发日：2023.03.31
技术公布日：2023/7/31