基于移动激光扫描的行道树树干提取

李秋洁，袁鹏成，刘旭，周宏平

(南京林业大学机械电子工程学院，南京 210037)

行道树资源调查是城市森林资源调查的重要工作，是开展城市森林生态研究的前提条件。目前，行道树资源调查主要采用人工实测和抽样调查等方法，工作量大、效率低下，不能及时准确地反映行道树动态变化状况。移动激光扫描(mobile laser scanning，MLS)测量技术能够快速获取高分辨率、高精度的树木垂直结构数据，改善难度大、周期长的传统行道树资源调查作业模式，实现大范围、全面快速地获取单木尺度的行道树参数信息[1-2]。

行道树点云分割是基于MLS的行道树参数提取的首要步骤[3]，目前，主要通过树干检测获取行道树位置，以树干为种子点区域增长分割出完整行道树[4]。具体过程如下：1)体素化[5]，将空间划分为立方体素，点云根据空间坐标归入相应体素，以体素作为数据处理基本单元；2)地面滤除，利用平面拟合等方法滤除地面点云，保留地上目标点云数据；3)杆状物检测，提取较低高度范围的点云数据进行地面投影，根据投影面积、形状、密度分布等特征识别杆状物；4)杆状物提取，以杆状物底部点云数据为种子点进行点云分割，提取完整杆状物；5)行道树识别，利用点云分布、尺寸等特征滤除路灯、电线杆等杆状目标，识别行道树。

Zhong等[6]利用点云法向量进行平面拟合去除地面点。吴宾等[7]和Wu等[8]提取距地面高度1.2～1.4 m的格网进行连通域分析，将大小和紧凑度指数符合条件的区域作为树干，使用三维区域竞争生长算法提取行道树候选区域。张恒等[9]分析行道树在多层格网中的分布形态，在空间区域生长过程中结合点云投影密度和高程分布等特征有效排除其他地物。杨莎莎[10]根据高程差从候选区域中去除车辆、行人、花坛、灌木等低矮地物，根据水平投影形状及面积滤除建筑物与路灯。董亚涵等[11]根据候选区域投影跨度去除路灯、低矮建筑物、路标及广告牌，根据上、下部投影面积比值去除电线杆。

树干检测是行道树定位与分割的核心步骤，已有方法由知识驱动，人工设计检测规则，难以跨越低层点云数据到高层地物目标的语义鸿沟，前期无法区分树干与其他杆状目标，需要在杆状目标提取过程中或结束后进一步设计识别规则滤除非行道树杆状目标。

本研究将树干提取分为树干点云识别与树干点云分割2个步骤：首先，通过监督学习算法从城市街道点云标注数据集中自动学习树干点云与非树干点云的差异性，获取高精度树干点云检测器；然后，基于树干点云识别结果，分割、标识出每一根树干。行道树树干提取流程如图1所示。

图1 行道树树干提取流程Fig. 1 Trunk extraction progress of street tree

1 移动激光扫描系统

本研究采用基于二维激光雷达的MLS系统，如图2所示。随着车辆的移动，二维激光雷达不断返回与车辆移动方向垂直的扇形平面内不同角度测量点的距离r及激光反射强度I。与基于三维激光雷达的MLS系统相比，二维激光雷达成本较低，数据冗余度小，在林木参数实时提取、植物三维重建、表型测量等领域[12-15]得到广泛应用。

图2 MLS系统数据采集方式Fig. 2 Data acquisition mode of MLS system

建立MLS坐标系统，求取点云三维空间坐标，如图3所示。x轴为车辆移动方向，y轴为深度方向，z轴垂直地面向上。MLS测量数据可以用测量点帧序号i和帧内编号j进行索引，第i帧第j个测量点的三维空间坐标为：

(1)

式中：v为车速，假设车辆匀速行驶；Δt为二维激光雷达扫描周期；r(i,j)为第i帧第j个测量点的距离；θ(j)为每帧第j个测量点的扫描角度；x(i,j)、y(i,j)和z(i,j)分别为第i帧第j个测量点的x、y、z坐标。

图3 MLS坐标系统Fig. 3 Coordinate system of MLS

后续处理的点云数据拥有5个属性值，包括三维空间坐标[x(i,j),y(i,j),z(i,j)]、测量点的距离r(i,j)及激光反射强度I(i,j)。

2 行道树树干提取

2.1 邻域查找

为计算点云局部特征，需首先查询点云邻域。对于离散、非结构化的点云数据，主要采用体素、八叉树、k-d树等方法索引点云数据，由于本研究采用的MLS系统直接生成结构化点云数据，可省去建立索引的时间和空间开销。

假设第i帧第j个测量点为P，采用两步法[16]计算以P为球心，δ为半径的球域。首先，求取P球域的帧序号及帧内编号范围，根据车辆速度和二维激光雷达扫描周期可计算帧间分辨率(Δi)，即车辆行驶方向上相邻帧测量点的最小距离：

Δi=vΔt

(2)

根据测量距离和弧度分辨率可计算帧内分辨率(Δj)，即二维激光雷达扫描方向上相邻测量点的最小距离：

Δj=r(i,j)Δα

(3)

式中：Δα为二维激光雷达弧度分辨率。假设P球域的帧序号范围为[i-δi,i+δi]，帧内序号范围为[j-δj,j+δj]，根据球域半径和帧间、帧内分辨率计算δi、δj：

(4)

2.2 特征提取

表1 点云局部特征Table 1 Local features of point cloud

图4 MLS点云数据非均匀性Fig. 4 Non-uniformity of MLS point cloud data

2.3 树干点云检测器训练

Boosting系列算法是一类提高弱学习算法性能的强学习算法，与支持向量机、神经网络等算法相比，具有参数少、低泛化误差、容易实现等优势，在模式识别的各个领域取得成功应用[19-20]。本研究采用Discrete AdaBoost[21]训练树干检测器。

fort=1 toT：

(1)学习弱分类器：ft=L(S,Dt)；

(2)计算分类错误率：et=∑m,ft(xm)≠cmDt(m)；

(4)更新样本权重：

(5)

式中，γt=0.5-et。可知，Discrete AdaBoost的训练误差随迭代次数指数下降，只要弱学习算法优于随机猜想，算法可通过足够多次迭代达到任意精度。

与其他机器学习算法相比，Boosting的优势如下：1)采用集成(ensemble)机制降低了算法复杂度，提高了算法效率；2)无需知道弱学习算法的任何先验知识，只需其性能比随机猜测稍好即可，弱学习算法可以是神经网络、SVM、决策树、k-近邻分类器、经验规则等各种机器学习算法；3)训练过程采用线性规划(linear programming)方法，算法简单，容易工程实现；4)确定弱学习算法后，除迭代次数，无需调节任何参数。

2.4 树干帧分割

对树干检测结果进行帧投影，得到每帧的树干点数，之后通过检测树干起始帧定位树干。

1)若某帧树干点个数大于一定阈值Ntrunk，则识别为树干帧：

(6)

式中：Lmin为树干最小长度；rmin为树干测量点最小距离。

2)若树干帧与当前树干起始帧的间距大于一定阈值Dtrunk，则识别为新的树干起始帧：

(7)

式中，Dmin为两棵树干的最小距离。最后，将各个树干点聚类到最邻近树干起始帧，分割提取出各个树干的点云数据。

3 结果与分析

3.1 城市街道数据采集

试验采用日本Hokuyo公司生产的UTM-30LX型2D LiDAR。该款LiDAR采用波长905 nm的红外线，通过电机摆动获取不同角度的测量值，测量距离0.1～30 m，测量精度±30 mm，扫描范围270°，角度分辨率0.25°，扫描周期25 ms。每次扫描获取1帧数据，包含1 081个不同角度的距离和激光反射强度，分别用4字节、2字节表示。

1. 数据采集计算机；2. 2D LiDAR；3. 小车供电模块； 4. 主动轮；5. 小车控制器；6. 遥控器。图5 MLS系统Fig. 5 MLS system

试验采用遥控MLS测量系统(图5)，以包含2个主动轮、18个从动轮的履带底盘小车作为移动平台，以STM32F103ZET6作为小车控制器，通过测速编码器获得小车速度，根据比例-微分-积分(proportion-integral-differential，PID)算法控制主动轮转速，实现小车行驶方向和速度的精确控制。

数据采集地点为南京林业大学校园内长度50 m的路段，包含建筑物、行道树、行人、车道、人行道、路牙、路灯、草皮等地物目标，如图6所示。采用MLS系统对街道进行单侧扫描，2D LiDAR扫描角度范围为-135°～135°，车辆速度0.2 m/s，采集时长250 s，获取10 000帧数据，包含10 810 000个点云数据。

图6 数据采集地点Fig. 6 Data collection area

为获取带标注的点云数据，采用MATLAB编程，利用长方体框选的方法为点云数据添加类别标签，形成标注文件。由于y轴负半轴街道信息采集不全，仅处理y≥0的点云数据。标注后的数据集描述如表2所示，部分标注点云数据如图7所示。

表2 数据集描述Table 2 Description of data set

图7 部分标注点云数据Fig. 7 Some labelled point cloud data

3.2 树干点云识别

3.2.1 球域半径选择

球域半径不宜过小，应大于MLS系统测量分辨率；同时，球域半径也不宜过大，否则无法表征点云局部特性。根据式(2)计算系统帧间分辨率为0.005 m，选取数据集最远测量点距离rmax=17.204 m，根据式(3)计算帧内分辨率为0.075 m。因此，δ需不小于0.075 m。为选取合适的球域半径，令δ在0.10～0.40 m时以0.05 m为间隔取值，开展试验。

3.2.2 单个特征鉴别力分析

为评估单个特征对树干点云识别的贡献，分析其在Bayes决策下的错误率。Bayes决策是使错误率最小的分类决策规则，具体如下：

如果P(c=1|x)>P(c=-1|x)，则判定为树干，否则判定为非树干。

式中：x为点云特征；P(c=1|x)为树干的后验概率；P(c=-1|x)为非树干的后验概率。假设树干和非树干的先验概率相等，根据Bayes公式，可得到Bayes决策的等价形式：

如果p(x|c=1)>p(x|c=-1)，则判定为树干，否则判定为非树干。

式中：p(x|c=1)为树干的类条件概率密度；p(x|c=-1)为非树干的类条件概率密度。

利用树干及非树干的单个特征直方图估计其类条件概率密度，获取Bayes错误率近似值。首先采用最大、最小归一化方法将特征变换到[0,1]范围内；然后以0.05为间隔计算树干和树冠的直方图分布，则Bayes错误率近似为：

(8)

式中：h1(i)为直方图第i个区间范围的树干点个数；h-1(i)为直方图第i个区间范围的非树干点个数。

不同球域半径下单个特征的Bayes错误率及最小错误率(表中加粗数据)如表3所示。从表3中可看出：1)球域半径对单个特征鉴别力有所影响；2)特征的最优球域半径各不相同，如强度均值在δ=0.10 m时鉴别力最强，而线性特征在δ=0.40 m时鉴别力最强；3)所有球域半径下鉴别力最强的3个特征均为高程方差、强度范围以及强度方差。

表3 不同球域半径下单个特征的Bayes错误率Table 3 Bayes error of single feature in different sphere radiuses

3.2.3 多个特征树干点云识别

树干检测器训练时，采用分类决策树作为弱学习算法，迭代次数T=300。从点云数据集中随机抽取5%用于训练，其余95%用于测试。用查准率(precision)和查全率(recall)评估树干点云检测器性能：

(9)

测试集上不同球域半径下的树干点云识别结果见表4。对于所有球域半径，测试集查准率均高于93%，查全率均高于94%，表明Boosting算法通过强学习显著提高了单个特征的分类性能。

表4 不同球域半径下的树干点云识别结果Table 4 Point cloud recognition results of trunk in different sphere radiuses

为尽可能识别所有树干点云，球域半径选取δ=0.25 m，此时树干点云查全率最高。经统计共有556个漏检点与212个虚警点，虚警点包括169个树冠点、1个人行道点和42个草皮点。树干点云识别结果见图8，可以看出，虚警和漏检主要集中在树干首末两端，分析原因如下：树干与树冠、草皮交界处的点云可能产生错误标注；此部分点云的球域与树冠、草皮重合度高，不易识别。

图8 树干点云识别结果(δ=0.25 m)Fig. 8 Point cloud recognition result of trunk (δ=0.25 m)

δ=0.25 m时，Boosting与SVM、神经网络的比较结果见表5。其中，神经网络对类别不平衡最为敏感，为最小化整体错误率，将所有树干样本都识别为非树干样本。SVM能获得较高的查准率，但查全率低于Boosting，表明有更多的树干点被误识别为非树干点。

表5 不同学习算法的树干点云识别结果Table 5 Point cloud recognition results of trunk using different learning algorithms %

3.3 树干点云分割

以横轴为测量点帧序号i，纵轴为测量点帧内编号j，得到树干点云标注和识别二值图像，如图9所示。为便于观察，仅截取标注/识别为树干的点云数据。从图9中可看出，由于车道不平坦且存在减速带等障碍物，会导致部分帧树干缺失。

图9 树干点云识别二值图Fig. 9 Binary images of trunk point cloud recognition

为进行树干分割，首先统计各帧树干点个数，如图10所示，树干所在帧有明显的波峰；然后检测树干起始帧，将树干点归类到最近的树干起始帧，分割出各个树干的点云数据，如图11所示。

图10 各帧树干点个数Fig. 10 Number of trunk point cloud in each frame

图11 树干点云分割结果Fig. 11 Segmentation result of trunk point cloud

4 结 论

1)从点云球域提取深度、高程、维度、密度、强度等14个特征，基于标注数据集，采用Boosting算法学习树干点云检测器。试验结果表明，上述方法能实现行道树树干精准识别，滤除路灯、行人、铁桩等杆状地物点云。

2)分析不同球域半径下的特征鉴别力，各个特征的最优球域半径各不相同，鉴别力最强的3个特征是高程方差、强度范围及强度方差。通过特征融合，树干点云检测器能显著提高单个特征的分类性能。

3)通过树干起始帧可检测定位树干，通过树干点云聚类可提取出每一根树干。

后续研究将改进MLS测量系统，提高点云精度，同时结合树冠点云识别方法提取完整行道树点云。