Abstract

从城市移动激光扫描 (MLS) 点云中提取单棵树对于许多城市应用都很重要。最近，基于深度学习的城市MLS点云语义分割取得了重大进展，这使得分割树点云成为可能。然而，树段通常在空间上重叠，具有不同的形状和由遮挡引起的不完整性，这使得单个树的提取成为一项具有挑战性的任务。在本文中，我们提出了一种新的自上而下的方法来从城市MLS点云中提取单棵树。首先，应用语义分割深度网络从原始城市 MLS点云中分割树点，然后使用欧几里德距离聚类将分割后的树点进一步分组为一组树簇。接下来，提出了一种逐点方向嵌入深度网络（PDE-net）来预测每个树簇指向树中心的方向向量，以增强实例级树的边界。之后，开发了一种基于方向聚合的策略来检测每个树簇的树中心，并根据检测到的树中心的数量将簇分为单树簇和多树簇。最后，根据我们提出的可访问区域生长算法结合嵌入的逐点方向和检测到的树中心，将单树簇直接提取为单个树，而将多树簇进一步分离为实例级树。使用从不同城市场景收集的四个MLS点云来评估所提出方法的性能。这四个数据集上的准确率、召回率和F-score分别为0.96、0.94和0.95，证明了我们方法的有效性。建议方法的实现可在以下网址获得：https://github.com/HiphonL/IndividualTreeExtraction。

1. Introduction

移动激光扫描(MLS)系统提供了一种有效的手段来获取城市道路的3D点云。从城市MLS点云中提取单棵树具有许多城市应用，例如树木库存、绿化观看率估计、3D街道树建模和城市规划（Lin和Hyyppa，2012；Lu等，2014）。然而，城市MLS点云通常具有场景复杂、数据量大、空间分布不均匀的特点。此外，树木通常在空间上重叠，具有不同的形状和由遮挡引起的不完整性。这些属性对从城市MLS点云中提取单棵树提出了重大挑战。

在过去的几年中，已经进行了许多尝试从点云中提取个体树，大致可以分为两类，即自下而上的方法（Yao and Fan，2013；Yu et al，2014；Huang et al，2014） al, 2015) 和自上而下的方法 (Xu et al, 2018; Zhong et al, 2016; Burt et al, 2018; Ning et al, 2019)。甚至在IQmulus处理竞赛 IQPC’15中也推出了专门的赛道来推动相关研究（Gorte et al, 2015），但是现有的作品大多遵循启发式框架，自动化和智能化水平普遍较低。总体而言，简单的方法很难取得令人满意的结果，而更复杂的方法则缺乏对实际应用的推广。

最近，随着深度学习技术的发展，点云语义分割取得了重大进展（Qi et al, 2017; Hu et al, 2020; Luo et al, 2020a），这使得分割某种类型的目标点成为可能，例如树点，来自原始点云。同时，室内或室外场景点云的实例分割越来越受到关注（Yi等人，2019；Yang等人，2019；Jiang等人，2020），许多相关研究已经在几个方面取得了最先进的水平开放基准。自然，上述这些研究激发了从点云中提取单个树的潜在解决方案。

在本文中，提出了一种基于语义和实例分割从城市MLS点云中提取单棵树的新方法。首先，应用语义分割框架从原始城市MLS点云中分割树点。然后，开发实例级分离工作流，从分割的树点中提取单个树。具体来说，首先使用欧几里得距离聚类方法将分割的树点分组为一组孤立的树簇。然后，提出了一个逐点方向嵌入深度网络，为每个孤立的树簇预测一组指向树中心的方向向量。然后，使用基于方向聚合的策略来检测树中心。最后，提出了一种基于可访问区域增长的方法来提取实例级树。本文的主要创新和贡献可归纳如下：

• 提出了一种基于语义和实例分割的新自上而下框架，以克服从城市MLS点云中提取个体树的挑战性任务。

• 提出了一种逐点方向嵌入深度网络（PDE-net）来预测孤立树簇的方向向量，以增强实例级树的边界。

• 引入了一种基于方向聚合的方法来检测树中心，并开发了一种基于可访问区域增长的方法来将精细的实例级树从多树簇中分离出来。

• 已经进行了广泛的实验和分析，以证明我们提出的方法的有效性。

本文的其余部分安排如下：第2节介绍了基于深度学习的点云单树提取、点云语义和实例分割的最新进展。第3节详细介绍了我们提出的方法。第4节介绍了实验和分析。最后，讨论和结论分别在第5节和第6节中介绍。

2. Related work

从点云中提取单个树是一个重要的话题。在本节中，我们首先回顾一些现有的个体树提取方法，然后简要介绍基于深度学习的语义和实例分割，这启发了我们提出的方法。

2.1. Individual tree extraction from point clouds

个体树提取涉及将点云分割成代表个体树的点段。在自下而上的方法中，原始点云首先被分割成点段或目标实例。然后，通过对树结构的固定假设将它们进一步组装成完整的树，或者使用机器学习方法将它们分类为树。例如，Yao和Fan(2013)提出将原始城市MLS点云划分为地面点和非地面点，然后将非地面点分割成与目标实例对应的各种点段。接下来，使用局部形状描述符将点段进一步分类为单个树。 Yu et 等人(2014)首先使用基于块的高程过滤方法从城市MLS点云中去除地面点。然后，使用欧几里得距离聚类将非地面点分组为一组聚类。之后，使用基于体素的归一化切割（Ncut）分割方法来分离包含多个实例的集群。最后，开发了一种基于模板匹配的策略来提取单个树。一般来说，自下而上的方法过度依赖人工特征分析，导致自动化程度较低。同时，固定树结构的假设限制了它们的泛化能力。

在自顶向下的方法中，第一步是提取树点。通常，应用二元分类器将原始点云分为树点和非树点。然后，将树点分组为孤立的簇，其中包含多棵树的簇进一步分离为单个树。例如，Zhong等人(2016)提出了一种用于地面激光扫描(TLS)和MLS点云的个体树提取框架，包括基于连通性的空间聚类、基于茎的初始分割和重叠冠层的精细分割。 Xu et al(2018)首先利用高程直方图中的峰值检测，从城市机载激光扫描（ALS）和MLS点云中去除地面点。然后，使用支持向量机提取结合形状特征的树点。接下来，将树点直接分割成超体素，并使用多尺度非重叠滑动窗口检测树顶超体素。最后，将非树梢超体素分配给最近的树梢超体素，以实现个体树木的提取。Burt等人(2018)开发了一种开源软件Treeseg，用于从大型陆地激光扫描(TLS)点提取个体树森林云。Treeseg的内置方法包括基于对茎的检测，从更大面积的TLS点云中识别单个树，将茎提取到第一个分支的位置，并通过连接提取与每个提取的茎相关联的树冠测试。此外，需要手动分割来细化冠边界。这些自上而下的方法显示出一些性能优势，但是，它们在更复杂的多树重叠情况下经常失败，并且不能准确地确定树冠的边界。而且，它们通常对数据质量有严格的要求，例如点密度和树段的完整性。

总体而言，这些方法主要基于启发式，自动化程度普遍较低。此外，现有的多树聚类分离策略，即最近邻分配和Ncut的变体，要么在提取边界时不准确，要么对超参数设置敏感。因此，迫切需要一种自动且鲁棒的方法来从点云中提取单个树。

2.2. Semantic and instance segmentation of point clouds

点云语义分割的目标是将给定的点云分割成几个具有不同语义含义的子集。最近，深度学习已经成为点云语义分割领域的主导方法，大致可以分为三类：基于投影的（Lawin等人，2017年；Boulch等人，2017年）、基于体素化（Huang和You，2016年；Tchapmi等人，2017年）和基于点的方法（Qi等人，2017年；Wang等人，2019b；托马斯等人，2019）。基于投影的方法首先将原始点云投影到多视图合成图像中。然后，采用基于全卷积神经网络（FCN）的多流框架对合成图像进行逐像素语义预测。点云的最终语义分割是通过将合成图像的语义预测重新投影到离散点上来实现的。基于体素化的方法首先将原始点云划分为规则体素网格，然后使用3D卷积神经网络进行语义分割。在基于点的方法中，PointNet(Qi等人, 2017)是直接在无序点云上使用深度学习的先驱。但是，PointNet无法捕获局部上下文特征，这严重限制了语义分割的性能。为了解决这个问题，已经提出了许多改进的工作，例如基于图的策略（Wang等人，2019b；Luo等人，2020a）和基于点卷积的方法（Thomas等人，2019；Wu等人，2019）。事实上，基于深度学习的点云语义分割取得了重大进展，使得从原始点云中提取特定类型的对象点变得更加容易。因此，对于自顶向下的个体树提取，这些语义分割方法为从原始点云中提取树点提供了一种有效的解决方案。

图 1. 我们提出的从城市MLS点云中提取单棵树的框架概述。第2部分和第3部分在第3.1节中介绍，第4部分在第3.2节中描述，第5部分在第3.3节中详细介绍。

点云的实例分割旨在将原始点云分离为实例级目标点集。现有的研究可以分为两类：基于proposal的方法（Yi等人, 2019; Yang等人, 2019）和proposal-free的方法（Wang等人, 2018; Liu and Furukawa, 2019; Wang等人, 2019a）。基于proposal的方法通常将实例分割转化为两个子问题，即3D目标检测和实例mask预测，而proposal-free的方法主要侧重于学习实例感知特征表示并将实例分离制定为一个聚类过程总体而言，基于proposal的方法通过对proposal区域的预测获得了更高的目标性结果，但由于冗余proposal的预测，它们通常在计算上很昂贵。proposal-free方法的计算效率更高，但其结果的目标性通常较低，因为它们没有明确地检测目标边界。此外，这些研究主要集中在室内场景点云上。通常，室内物体之间的实例边界更容易区分。例如，两把椅子的边界非常接近，仍然可以清楚地区分。然而，在室外城市MLS点云中，相邻树之间的边界往往是模糊的，这使得这些实例分割方法难以推广到单棵树提取的任务。尽管如此，实例分割方法确实为MLS点云的实例级树分离提供了灵感。

3. The proposed approach

基于最近点云语义分割方法的成功，并受到点云实例分割新兴发展的启发，我们提出了一种新的自顶向下方法，基于语义分割和实例级分离，从城市MLS中提取单个树点云。在本节中，我们分三个部分阐述所提出的方法，即树点分割和逐点方向嵌入、基于方向聚合的树中心检测和基于可访问区域生长的实例级树分离。我们提出的框架的概述如图1所示。

图 2. 逐点方向嵌入网络(PDE-net)的示意图。(a)是输入孤立树簇。(b)是PDE-net的主干框架。©是输出的逐点方向。(d)和(e)在侧视图中显示预测的逐点方向。(f)和(g)是顶视图中的逐点方向。请注意，输出点方向的数量等于输入点的数量。另请注意，我们仅在©中显示部分逐点方向，以便清楚地说明。

图 3.体素化和体素遍历的图示。 (a)是树簇的体素化示例。(b)和©是快速体素遍历以跟踪逐点方向射线的示例。

3.1. Tree point segmentation and pointwise direction embedding

在城市MLS点云中对树点进行语义标记的主要障碍是真实场景的复杂性。最近，深度学习在点云领域取得了突破，特别是在分类、语义分割和目标检测任务方面。这允许在语义分割的帮助下从城市MLS点云中准确分割树点。因此，在本文中，首先应用现有的语义分割框架将原始城市MLS点云分为树点和非树点。然后，利用聚类距离阈值为$d_c$的欧几里得距离聚类方法将树点进一步分组为一组簇。然后，将这些簇作为后续部分的基本处理单元。为实现单棵树的提取，需要将包含多棵具有空间重叠的树的簇（称为多树簇）进一步分离为实例级树，而仅覆盖一棵树的簇（即单树簇）为直接识别为个体树。

通常，多树簇的特点是重叠情况严重，实例边界模糊，这使得单个树的精细提取变得复杂。受深度霍夫投票模型 (VoteNet) (Qi等人, 2019) 的启发，我们提出了一个逐点方向嵌入网络(PDE-net)以增强实例级树边界的可区分性，如图2所示。与VoteNet不同回归偏移以投票目标中心，PDE-net预测指向输入树簇的相应树中心的逐点方向向量。在具体实现中，给定一个由N个点和3维空间坐标$(x,y,z)$组成的树簇（见图2(a)），记为 P = { P n ∣ i = 1 , … , N } ⊆ R 3 \mathrm{P}=\left\{\mathrm{P}_n \mid i=1, \ldots, N\right\} \subseteq \mathbb{R}^3 P={Pn​∣i=1,…,N}⊆R3是一种语义分割类网络，用作主干框架来提取输入点云的$N\times f$维特征。然而，与语义分割任务不同，最终的MLP层被定义为对应于方向向量的3维输出，而不是语义类的数量。最后，根据输入的N个点预测N个方向向量，逐点方向嵌入的例子如图2（c）所示。根据图2(d)-(g)所示的比较，可以看出方向嵌入有助于区分实例级树点的边界。请注意，图2(e)显示了YOZ平面上的点方向和z轴之间的角度，而图2(g)显示了XOY平面上的点方向和x轴之间的角度。为了优化PDE-net，基于误差松弛的方向损失(${\mathcal{L}}_{\text{ESD }}$)定义如下:

$${\mathcal{L}}_{\mathrm{ESD}}=\frac{1}{C}\sum _{c=1}^c\frac{1}{N_c}\sum _{i=1}^{N_c}{\left[{\sigma }_{et}-v_i^{pre}\cdot v_i^{gt}\right]}_{†}(1)$$
其中，$C$是树簇中的树的数量，$N_c$是每棵树的点数，$v^{\text{pre }}$是预测方向向量，${\nu }^{\mathrm{gt}}$是方向向量的ground truth，即$v_i^{gt}={\mathrm{P}}_i^{(c)}-{\mathrm{TC}}_b$。${\mathrm{P}}_i^{(c)}$是第$c$个实例级树的第$i$个点。${\mathrm{TC}}_c$是第$c$个树中心，它被定义为第$c$个实例级树的3D边界框的中心位置。请注意，在计算方向损耗之前，$v^{\text{pre }}$ 和 $v^{gt}$应通过L2归一化。为了清楚起见，我们将$v^{pre}\cdot v^{gt}$定义为角度项(AT)。事实上，当PDE-net用硬指向树中心的错误进行训练时，预测会被严格要求指向准确的中心点，这实际上是非常困难的，容易导致过拟合。此外，我们通过实验发现，邻近实例边界的点的预测方向通常是不稳定的，而其他点的预测方向更准确和稳定。同时，与实例边界相邻的点通常所占比例较小，这导致相应的误差往往被其他点的误差所掩盖。为了使PDE-net更加关注实例边界附近点的方向嵌入，引入了一个误差容限项${\sigma }_{et}$来放松对PDE-net的约束，任何大于该容限的角度项都被抑制到${\sigma }_{et}$。在等式(1)中，$[x{]}_{†}=\max (0,x)$，它表示铰链，意味着ATs大于${\sigma }_{et}$的点不会被进一步优化，而ATs小于σet的点将受到更多关注。PDE-net的详细训练过程可以在第4.2节中找到。

3.2. Tree center detection based on pointwise direction aggregation

在之前的工作中（Zhong et al, 2016; Xu et al, 2018; Itakura and Hosoi, 2018; Burt et al, 2018），通常通过检测树冠的局部最高点来确定树丛中覆盖的树木数量（即树顶点）或通过识别一定高度内的茎。这些方法需要高质量的数据，适用于简单的树木场景。事实上，这些策略对于城市MLS点云通常不够稳健。例如，树木可能被栅栏遮挡，导致点云中缺少茎，或者不均匀的树冠形状导致树的多个局部树冠最高点。因此，在本文中，我们提出了一种基于逐点方向聚合的树中心（TC）检测方法。检测到的树中心可用于将树簇分类为单树簇或多树簇。包含多个树中心的树簇被认为是多树簇，进一步分离成实例级树，而只包含一个树中心的树簇被认为是单树簇，直接提取为单棵树。此外，检测到的树中心将为后续的多树簇分离操作提供服务，这将在3.3节中描述。

基于PDE-net的逐点方向，一种直观的方法是利用逐点方向的空间聚集特性来检测树中心。这里，树中心是为单个树点云定义的3D边界框的中心位置。具体来说，首先将树簇划分为$S_v$大小的网格体素，如图3(a)所示。然后，引入了一种快速体素遍历算法（Amanatides et al, 1987）来跟踪每个点的方向射线。一个例子如图3(b)和©所示。之后，计算通过每个体素的方向射线的数量。理论上，由于预测的逐点方向指向树中心，每条方向射线的遍历体素将包括在某个树中心的体素，并且穿过树中心体素的方向射线的数量应该是局部最大值。但是，实际预测的逐点方向不可避免地会存在误差，这意味着预测的逐点方向可能无法完美地聚合到 3D空间中的某个点。因此，当直接使用3D体素空间中的局部最大值进行检测时，可能会遗漏一些树中心。为了缓解这个问题，开发了一种两步基于局部最大值的树中心检测方法，即首先检测树中心在XOY平面上的位置（步骤1），然后确定树中心的高度（第2步）。在步骤1中，沿z轴对穿过体素的方向射线的数量求和，如图4(a)所示。之后，一个3×3大小的2D局部最大值滤波器（见粉色图4（b）中的网格）用于遍历XOY平面以检测树中心的水平位置，表示为${\mathrm{TC}}_{xoy}$（见图4（b））。在步骤2中，每个${\mathrm{TC}}_{xoy}$的高度由相应水平位置沿z轴的局部最大值确定。值得注意的是，对于多树簇，在步骤1中可能会检测到一些错误的${\mathrm{TC}}_{xoy}$。主要原因是多树簇的某些点方向可能在树中心范围之外相互重合，这也可能导致到XOY平面中的局部最大值，如图 4（b）中的粉红色圆圈所示。幸运的是，导致false ${\mathrm{TC}}_{xoy}$的方向射线的数量通常远少于真正的${\mathrm{TC}}_{xoy}\mathrm{s}$。因此，引入了方向射线数量的阈值$N_d$来细化树中心。检测到的树中心的示例如图 4（c）中的红点所示。最后，将只包含一个树中心的树簇直接提取为单独的树，无需任何其他处理步骤，而具有多个树中心的树簇将被送入后续操作进行实例级树分离。

图 4.树中心检测示意图。(a)穿过体素的方向光线的数量沿z轴求和。(b)在XOY平面上检测树中心的水平位置。©检测到的树中心（红点）示例。（有关此图例中颜色参考的解释，请读者参考本文的网络版本。）

3.3. Instance-level tree separation using accessible region growing

单个树提取最具挑战性的任务是空间重叠树点的实例级分离。然而，上述的逐点方向嵌入和树中心检测使得区分实例级树的边界和确定多树簇中包含的树的数量成为可能。为此，我们引入了一种简单而有效的算法，该算法基于可访问区域增长来分离实例级树，算法1中对此进行了详细说明。

算法 1. 可访问区域增长算法。 $K$是树中心的数量；$N$是多树簇中的点数；${\overrightarrow{\mathrm{D}}}_{(k,n)}$是第$n$个树点指向第$k$个树中心的方向；$\alpha$是${\overrightarrow{\mathrm{D}}}_{(k,n)}$与嵌入方向${\overrightarrow{\mathrm{D}}}_n$之间的角度。

我们提出的算法的核心步骤包括使用逐点方向以及检测到的树中心生成可访问区域，并使用基于体素的区域生长将实例级树与生成的可访问区域分离。给定具有逐点方向集PD和树中心集TC的多树聚类点集MTC，对于第k个树中心${\mathrm{TC}}_k$，首先生成对应的可访问区域。具体来说，首先估计MTC中每个点${\mathrm{P}}_n$指向${\mathrm{TC}}_k$的临时方向${\overrightarrow{\mathrm{D}}}_{(k,n)}$，即${\overrightarrow{\mathrm{D}}}_{(k,n)}={\mathrm{TC}}_k-{\mathrm{P}}_n$，然后${\overrightarrow{\mathrm{D}}}_{(k,n)}$并进一步计算嵌入方向${\overrightarrow{\mathrm{D}}}_n$。 MTC中角度$\alpha$小于给定阈值${\theta }_{\mathrm{ARe}}$的那些点被认为是可访问区域。一个详细的例子如图5所示。对于第2个树中心（即${\mathrm{TC}}_2$），${\mathrm{P}}_1$的预测逐点方向（即${\overrightarrow{\mathrm{D}}}_1$）指向${\mathrm{TC}}_1$，而临时方向${\overrightarrow{\mathrm{D}}}_{2,1}$指向${\mathrm{TC}}_2$。在这种情况下，角度α达到大于θARe的值。因此，P1被视为不可访问区域。相反，${\mathrm{P}}_2$和${\mathrm{P}}_4$的角度α小于${\theta }_{\mathrm{ARe}}$，因此${\mathrm{P}}_2$和${\mathrm{P}}_4$被认为是可访问区域。遍历树簇的所有点后，生成${\mathrm{TC}}_2$的最终可访问区域（即图5中的红点）。值得注意的是，原则上，那些靠近边界的不可访问点的角度$\alpha$更大，这便于区分实例级树的精细边界。之后，将${\mathrm{TC}}_2$设置为种子，生成的可访问区域以及该种子同时划分为网格体素。然后，引入了基于体素的区域生长，以将第二个实例级树与生成的可访问区域分开。最后遍历所有树中心，重复上述步骤，实现输入MTC的所有实例级树的分离。实例级树分离的逐步过程如图6所示。

图 5. 计算第二个树中心(${\mathrm{TC}}_2$)的可达区域的例子。红点是${\mathrm{TC}}_2$生成的可达区域。(对于该图图例中颜色的解释，读者可以参考本文的网络版本。)

图 6. 实例级树分离过程的一个例子。

5. Discussion

我们的比较结果表明，以前的单个树分割方法，即基于VNcut和基于NNA的方法，不能感知精细的树边界，并导致边界处的分割错误。相比之下，我们提出的方法在提取精细树边界方面表现明显更好，因为我们引入了基于逐点方向嵌入的实例级树边界增强。此外，在先前的方法中，用于对树簇中的树的数量进行计数的基于树干或基于树梢的检测方法需要高质量的数据，并且过度依赖于固定树结构的假设。在我们的方法中，我们建议使用树中心检测来计算树簇中的树的数量，这不仅消除了对高质量数据的要求，而且还适用于不完整的树点云，因为不完整的树点云仍然具有中心。理论上，精确的逐点方向嵌入和树中心位置完全可以实现对单棵树的精细提取。然而，我们的测试表明，逐点方向嵌入的误差相对较小，而树中心预测在某些极端情况下可能会有较大的误差。因此，在本文的实验结果中，实例级树的边界处仍然存在一些分离误差。此外，树中心检测过程仍然涉及经验阈值，即阈值Nd，这将限制所提出方法的推广能力。因此，在我们未来的工作中，我们将致力于提高检测到的树中心的精确度，并使我们的方法在更极端的情况下更加鲁棒。同时，我们将致力于将提出的单棵树提取方法集成到一个端到端的框架中，以使其应用更加方便。

6. Conclusions

本文提出了一种新的自顶向下的方法，结合语义和实例分割从城市MLS点云中提取单棵树。我们首先使用现有的语义分割深度网络从原始城市MLS点云中分割树点，然后使用欧几里德距离聚类将树点进一步分组为一组树簇。接下来，我们提出了一个逐点方向嵌入网络来预测每个树簇指向树中心的方向向量，以增强实例级树的边界。之后，我们提出了一种基于方向聚合的策略来检测每个树簇的树中心，并根据检测到的树中心的数量将簇分为单树簇和多树簇。然后，基于我们提出的可达区域生长算法，单树聚类被直接提取为单个树，而多树聚类被进一步分离为实例级树。最后，大量的实验和分析表明，我们的方法是一个有效的解决方案，为个别树木提取从城市的MLS点云。总之，我们相信我们的贡献为从城市MLS点云中提取单棵树的深度学习应用提供了新的见解。

原文链接:https://www.sciencedirect.com/science/article/abs/pii/S0924271621000654

References