基于DBSCAN算法的树木分割与应用

尤 磊,邹 畅,宋新宇

(信阳师范大学 a.计算机与信息技术学院; b.河南省物联网与智能安防工程研究中心; c.数学与统计学院, 河南 信阳 464000)

0 引言

快速、准确地提取森林资源信息,对实现森林的科学管理等林业生产与研究工作非常重要。地面三维激光雷达(Terrestrial Laser Scanning,TLS)是一种应用前景广阔的主动遥感技术,其通过生成毫米级精度的三维激光以获取森林的空间属性信息[1]。其自动化程度高,可快速获取大面积且高精度的物体表面三维点云,已有很多研究尝试将其应用于林业资源调查[2]。

单株树木是森林的基本组成部分,提取单株树木信息是获取森林资源信息的基础。树木分割是将林分点云分割为多个部分,每个部分是一株树木的点云。精确树木分割是TLS应用于林分与森林资源调查的关键环节之一。从林分点云中提取树木点云最初多采用光学图形处理方法实现[3]。VEGA等[4]在对林分点云归一化的基础上,在不同尺度上进行分割,并从中动态选择最佳顶点集,然后使用选择的一组顶点生成树木点云。HAMRAZ等[5]提出一种多层林分的树木分割方法,该方法将点云分层到树冠层,使用基于数字表面模型的树木分割方法,分割得到每层内的各个树冠。HUA等[6]提出一种Shadow-cut的树木分割方法,其基于点云几何特征分离树的区域,将点云投影至图像,通过图像分割完成树木分割。王鑫运等[7]对不同分辨率的冠层高度模型进行先开后闭的形态学滤波处理,采用反距离插值算法和图像增强算法,提高树冠内部像素与树冠间像素的对比度,最后利用局部最大值法在冠层高度模型中搜索树顶以实现树木分割。DERSCH等[8]提出基于自动树干检测的图切聚类方法分割树木,其在待划分簇中定位树干位置,再通过分层分类程序识别垂直线以自动检测树干。WANG等[9]提出一种使用小型机载激光雷达数据树木分割的多阈值分割方法,其在使用数字表面模型对每一层进行多阈值分割的基础上,通过合并准则跨分层组合树段以分割树木。WANG等[10]以车载激光雷达获取的城市点云为输入,提出一种结合语义和实例分割的深度学习框架以提取树木点云。

上述方法使用不同的技术提取单株树木点云以实现树木分割,并在各自应用场景中取得较好效果,然而依然存在树木欠分割或过分割[11]的现象。同时由于不同林分的郁闭度不同,现有方法难以适用不同郁闭度下的树木分割,特别是基于深度学习与图像分割的方法。基于此,本文提出一种基于密度的抗噪空间聚类(Density-based spatial clustering of applications with noise, DBSCAN)的树木分割算法,该方法根据点云密度识别同一层中不同的树木,在郁闭度中等的林分中取得较好效果。

1 算法介绍

以TLS获取的林分点云为数据,首先采用渐进加密三角网滤波算法,将点云分为地面点云和非地面点云;接着将非地面点云进行归一化处理;然后使用高斯滤波对归一化后的点云去噪;在对点云垂直分段的基础上,逐层使用DBSCAN算法进行聚类;通过聚类个数区分树干段所在区域并获取树干段点云的簇,根据簇中心点之间的距离匹配树木树干段点云,直至所有簇匹配完毕;最后使用RANSAC算法将树干段点云进行直线拟合,搜索距离直线最近的点以完成树木分割。算法流程图如图1所示。

图1 算法流程图

1.1 数据来源

试验样地位于辽宁省清原县大孤家林场,选择郁闭度不同的9个样地(郁闭度是森林中乔木树冠在阳光直射下在地面的总投影面积(冠幅)与此林地(林分)总面积的比值,它是反映林分密度的指标),每个样地长30 m、宽30 m,9个样地中共有树高8～25 m不等的树木738株。

采用FARO X330地面三维激光扫描仪分别对样地进行扫描,以获取每个样地的样地点云。在样地扫描过程中,分别在样地的4个顶点、4条边界的中心点及样地的中心点作为扫描站点,即一个样地扫描9站。使用FARO Scene软件对9站扫描的点云配准得到样地点云。

1.2 预处理

1.2.1 点云归一化

使用LiDAR360[12]软件中的渐进加密三角网滤波算法,将林分点云分为地面点云和非地面点云。为消除地面起伏对树木提取的影响,计算非地面点云中所有点的最小正方体,并对非地面点云进行归一化。

1.2.2 点云去噪

由于高斯滤波[13]利用高斯函数经傅里叶变换后仍具有高斯函数的特性,可较好保持样地原貌,因此本文使用高斯滤波对点云进行去噪处理,以删除大部分明显的噪声点。使用KD-Tree搜索每个点云的k个邻域点,k值越大,处理效果越好,取k=80,使邻域的权重满足高斯分布以删除高频噪声点。样地点云使用高斯滤波去噪的效果如图2所示,其中图2a为地面三维激光扫描仪获取的点云图,图2b为将点云删除地面点云并进行高斯滤波后的点云图。

图2 样地点云使用高斯滤波去噪的效果图

1.3 垂直分段

采用垂直分段的方法处理整个样地的点云,即在垂直方向上将点云按照一定高度进行分段。垂直分段高度过大会导致树木分割不精确,过小会导致计算量过大。本文中分段高度设置为0.15 m。

1.4 DBSCAN算法

对每一层垂直分段后的点云进行DBSCAN聚类:计算垂直分段内每一个点与其他点的欧式距离。当该点邻域半径(Eps)范围内的点的数量(包括该点)等于或大于最小包含点数(MinPts),那么将该点定义为核心点,该点邻域半径Eps范围内的圆即为它的邻域,邻域内包含边界点和其他核心点,两个核心点之间距离小于Eps是密度相连的,它们构成相交圆的范围内的所有点为同一簇。找到所有密度相连的核心点以及其邻域范围的点,即为一个聚类簇。对每一层垂直分段后的所有点重复上述过程,最终得到DBSCAN算法的密度聚类结果。

根据垂直分段后DBSCAN聚类生成的簇个数可以发现,在树冠区域,树冠间的相互重叠导致树冠段形成的聚类簇通常是多棵树的树冠点云融合在一起的点云簇,无法作为树木分割的依据;而在树干段区域,由于树木树干间的距离导致每株树木的树干与其他树木的树干距离较远而形成不同的聚类簇,可以作为树木分割的依据。

1.5 计算簇的中心点

根据聚类的个数区分树冠段点云的垂直分段和树干段点云的垂直分段。图3为树干段点云的部分聚类簇,通过簇的形状可以发现,这些簇是树木树干段的一部分。

图3 树干段点云的部分聚类簇

此处簇的位置为簇中心点所在的位置。对于任一簇的点云Q={ai|i=1,…,m},点ai的坐标为(ai,x,ai,y,ai,z),Q的中心点c的坐标为(cx,cy,cz),则有以下公式:

(1)

(2)

(3)

1.6 匹配树干段点云

从树干最底层的垂直分段簇开始,计算该层所有簇与上一层树干段点云垂直分段的所有簇的距离,当该层簇与上一层簇之间的距离最小且小于垂直分段高度时,则认为这两个簇属于同一树干。重复此步骤直至计算所有树干段点云垂直分段的簇,此时可得到树干大部分的树干段点云。图4为匹配树干段点云的过程,其中,灰色点云为已匹配的树干段点云,蓝色点云为即将匹配的簇。

(a)匹配开始 (b)匹配结束

1.7 树干段点云拟合直线

使用RANSAC算法将树干段点云进行直线拟合,以树木平均胸径作为误差阈值,对断面点云采用CF(Circle Fitting)[14]方法拟合圆以得到直径值。将满足直线模型构建的点称为内点,t为内点数量在树干段点云中所占的比例。设置迭代次数为m次,m值为树干段点云包含点数量,这样可以保证置信度P最接近1并能拟合出一条包含最多内点的直线,则有以下公式:

P=1-(1-t2)m。

(4)

图5为树干段点云,其中,红色点云为满足直线模型构建的内点。

图5 RANSAN算法拟合直线

将所有获取的树干段点云进行直线拟合,并将直线作为该树木的中轴。计算并比较非地面点云中非树干段点云与每条中轴的距离,点与其距离最近的中轴属于同一株树木,从而完成树木分割。

2 实验结果与分析

2.1 评价指标

基于DBSCAN算法的树木分割效果评价包括识别率R、召回率r、精确率p以及调和值F[15],分别如式(5)—式(8)所示。

R=n/N,

(5)

r=TP/(TP+FN),

(6)

p=TP/(TP+FP),

(7)

F=2rp/(r+p),

(8)

式中:N表示样地实际的树木数;n表示算法分割的树木数;TP表示正确分割的树木数;FN表示漏检的树木数;FP表示过检的树木数。

识别率R可反映样地中树木的检测成功率,数值越接近1,检测出的样地树木比值越高;召回率r表示正确分割树木占样地实际树木的比值,数值越接近1,表明正确分割的树木越多,分割效果越好;精确率p表示算法分割出的树木为正确分割的比值,数值越接近1表明算法分割越准确;调和值F则是从整体上评估分割的优劣,数值越接近1表示整体效果越佳。

2.2 对比算法

将本文算法与以LiDAR360软件中实现的基于距离判别的树木分割算法[16]进行比较。基于距离判别的树木分割算法的核心思想是将点云进行归一化,以局部最大值为种子点,即树木的顶点,分别根据点与不同种子点间的距离完成树木分割。

2.3 结果与分析

两种算法的树木分割效果如图6所示(左侧为本文算法,右侧为基于距离判别的树木分割算法)。从图6可以直观看出,本文算法对郁闭度高的林区具有一定的树木分割能力,而在传统算法中,这类树木往往被漏检或错误分割。

图6 两种方法的树木分割效果图

表1与表2分别是两种算法的实验结果,可以看出,本文算法提取的树木数量为691株,相应的识别率平均值为0.92;基于距离判别的树木分割算法提取的树木数量为627株,相应的识别率平均值为0.84。两种算法F值的平均值分别为0.91和0.86,说明两种树木分割算法的整体效果较好。其中,本文算法的r平均值为0.88,p平均值为0.94,表明本文算法的欠分割与过分割现象均较少,即通过树干点云获取树木位置具有较高的精确度。同时,基于距离判别的树木分割算法分割的树木多为正确分割(p的平均值为0.94),而r的平均值为0.79,说明树木的漏检造成较多的错误分割。

表1 DBSCAN算法在不同样地的实验结果

表2 基于距离判别的树木分割算法在不同样地的实验结果

2.4 提取树木的点云完整度评价

现有树木分割算法的评价指标多从树木分割的数量来进行描述,对于某一株树木而言,分割质量难以体现。由于无法准确获取每棵树木完整的点云数据,通过人工分割的树木点云作为原始的树木点云数据,以本文算法提出的树木点云为提取数据,计算提取树木的点云完整度。图7是树木点云完整度示意图,其中蓝色点为欠分割点,红色点为算法正确分割点。从图7可以看出本文算法的正确分割率超过75%,不容易导致树木过分割,提取树木的点云完整度较高。

图7 树木点云完整度示意图

3 讨论

采取DBSCAN算法对森林样地点云进行树木分割,并与基于距离判别的树木分割算法进行比较。本文算法将点云在垂直方向上分段,分别获取树冠段点云和树干段点云,能够应用于树木的中下层探测与识别;DBSCAN算法是基于密度的一种聚类算法,其可自动确定簇的数量而不受噪声点的干扰,且能处理任意形状和大小的簇。因此,根据不同郁闭度样地树木的形态结构特征,可以发挥DBSCAN的优势,从而提高样地的树木分割精度。

基于DBSCAN算法的树木分割算法应用在研究区样地中能取得很好的效果(F=0.91),且算法提取的树木绝大多数为正确分割。其主要原因在于垂直分段后的聚类中心,通过计算不同分段的各个聚类中心点坐标,可以很容易确定出同一树干点云的位置,再根据树干点云的位置划分。然而,在郁闭度较高的样地中,中下层点云密度过高,DBSCAN算法聚类很难到达理想的效果,存在漏分割现象,从而影响树木分割的精度。基于距离判别的树木分割算法的F值为0.86,原因是该算法在郁闭度较高的样地时,根据冠层高度无法精确判断种子点。通过两种算法的实验结果对比,可以看出本文算法具有较好的适应性。

已有研究根据不同的树种采取不同的方法进行树木分割。例如,LI等[16]利用树木之间相对位置识别了混交针叶林型样地86%的树木,其中94%为正确分割;李平昊等[17]对阔叶复杂林型采用基于距离的算法进行树木分割,F值为0.83;白少博[18]采用区域生长算法和Hough变换分割针叶林和阔叶林,其中,针叶林样地分割正确率为87%,阔叶林样地为86.8%,然而当研究区为高郁闭度原始森林时,算法的分割精度普遍很低。因此,对比其他研究者采用类似分割算法的研究成果,本文得到的树木分割精度较高。

4 结束语

以地面激光扫描仪获取的样地点云为数据,提出基于DBSCAN算法的树木分割算法。对9种不同郁闭度的样地开展树木分割试验,并对分割精度以及完整度进行评价,具体结论如下:

1)通过DBSCAN算法处理不同郁闭度样地可以发现,该算法可有效划分疏林和郁闭度为中度的样地,对于郁闭度较高的样地虽然有一定的树木分割能力,但是无法从分层聚类中精准确定树干点云位置,存在漏分现象,划分方法有待改进。

2)使用召回率、精确率、调和值以及识别率分别评价本文算法和基于距离判别的树木分割算法的分割效果,结果显示,本文算法具有较好的分割精度。

3)引入树木点云完整度,将算法分割出的树木点云与人工分割的树木点云数据对比,结果表明,本文算法提取的树木点云具有较好的树木点云完整度。

综上所述,本文算法可实现以地面激光雷达获取样地点云的树木有效分割。