一种顾及体元邻域关系的行道树提取方法

徐嘉淼，刘如飞，魏晓东，柴永宁

(1.山东科技大学 测绘科学与工程学院，山东 青岛 266590；2.青岛秀山移动测量有限公司，山东 青岛 266590)

0 引言

道路两侧的行道树是城市建设管理中的重要组成部分，其在景观功能、生态功能和意向功能等方面起着积极的作用[1]。因此，行道树信息的自动化快速提取是智慧城市建设中不可或缺的环节。车载移动测量作为测绘领域内一种前沿的测量技术，可以在高速运动状态下迅速获取道路两侧地物的高精度三维信息，对城市行道树信息化管理意义重大。

针对车载LiDAR点云行道树目标自动化提取，国内外学者已经展开了广泛的研究。一些方法对城市典型地物(行道树、路面、建筑物等)统一进行分类与提取，从而间接提取出行道树点云；另一些方法则单独对行道树点云进行提取。上述方法可以分为4类。①扫描线法。这类方法主要对树干点云在每条扫描线上的分布特征进行分析，可以快速简单地自动化提取出树干点云[2]。但是杂乱无章的树冠点云无法通过扫描线直接反映出几何形态，不利于树冠点云的进一步提取，适用性不强。②语义模型法。直接将离散的点云分割成独立的点云块，以行道树的几何特征为约束建立相应的语义模型，从点云块中分类出行道树目标[3-4]。这类方法可以直接对原始点云进行处理，但是在点云分割与聚类过程中容易受周围邻近地物影响，且计算量偏大。③点云投影法。将点云投影至平面内并建立二维格网，统计格网内点云的密度和高差等信息，从而对行道树点云进行提取；或者生成规则的点云特征图像，然后借助于图像处理算法来提取出行道树点云[5-6]。这类方法采用了降维的思想，减少了数据量，提高数据处理效率，但是在点云投影和生成规则图像过程中，存在精度损失，且格网尺寸选择对最终提取结果有影响。④体元法。将行道树实体分割成一系列非空体元，既保留了行道树的三维信息，也方便对其局部细节进行展示和分析，充分利用了行道树的整体特征，减少数据冗余，提高计算效率[7-8]。Wu等[9]提出了一种基于分层体元点密度的行道树提取方法，实现单株行道树的完整提取，仅考虑单一的体元密度特征无法有效区分人造杆目标与行道树树干；Yang等[10]基于多尺度超体素进行区域聚类分割，根据先验知识设定各类目标对象几何特征分类阈值，实现多类目标层次化提取，实验结果表明，该算法适用于复杂城市环境下的行道树点云提取；Ordonez等[11]将点云进行三维空间体元简化，对单个体元进行二维平面分析，利用杆状地物的孤立性识别出目标数据，并分组、立体还原，最后根据支持向量机算法分离出行道树目标；Kang等[12]建立规则体元索引，通过分析杆状地物的孤立性与竖直连续性特征，采用自适应半径的平面圆模型和垂直区域生长算法对杆状地物体元进行检测与分割，建立多类杆目标语义规则，进一步区分树干、路灯与电线杆；罗海峰等[13]将体元与深度学习相结合，对地物点云建立八叉树体元索引，归一化分割重叠点云获得独立目标对象，基于多个方向生成目标对象的体元化全局特征，输入深度置信网络(deep belief networks，DBN)进行训练，实现行道树点云的提取。

上述算法无法对体元内点云进行细致的形态与属性分析，并且没有充分挖掘体元之间的邻域关系。此外，当行道树与其他地物距离太近，特别是路灯穿插在树冠中时，极易造成误分类。针对以上不足，本文提出了一种以体元为研究对象且顾及自身空间邻域关系的行道树点云自动提取算法，在城市部件采集、大规模园林普查等方面具有重要意义。

1 行道树点云提取算法

行道树广泛种植于道路两侧或分车带内，其自身结构复杂且常与其他地物混合，一定程度上造成了提取困难。以体元为研究对象且顾及自身空间邻域关系的行道树点云自动提取算法主要包括数据预处理、树干提取、树冠提取3个步骤，如图1所示。

图1 行道树自动化提取流程图

1.1 原始点云预处理

首先对原始点云数据进行双边滤波去噪和高程归一化处理，然后采用文献[14]中方法滤除地面点，保留非地面点，减少了数据量，提高数据处理效率。

车载移动测量记录了激光点云的反射强度、三维坐标等信息。结合点云自身的三维坐标与体元尺寸参数实现三维虚拟规则格网的创建，方便对点云进行快速索引和邻域搜索。假设体元在三轴方向上的尺寸分别为dx、dy、dz，存在点云P(Xp，Yp，Zp)落入对应的体元Voxel内，则Voxel的行号row、列号col、层号layer的计算方法如式(1)所示。

(1)

1.2 体元特征计算与邻域分析

点云曲率是衡量地物表面平坦程度的重要特征。灌木和树冠点云呈散乱团状，树干点云呈规则圆柱状，导致前者的曲率大于后者，在体元内部表现为点云平均曲率的差异。点云回波反射强度是衡量地物表面反射率的重要特征。人造杆目标表面涂抹了特殊的反光材料且十分光滑，树干表皮粗糙，导致前者的回波反射强度大于后者，在体元内部表现为点云平均回波反射强度的差异。

为提高树干点云分类与识别的准确性，本文选择了体元的曲率与回波反射强度特征，结合树干几何形态，充分挖掘体元空间邻域关系，最终建立了表1所示的体元空间邻域关系描述规则。

表1 体元空间邻域分析

SVI和SVc表示种子体元的平均反射强度值和平均曲率值；VI和Vc表示非种子体元的平均反射强度值和平均曲率值；OL和RL表示第L层体元模板内点云拟合平面圆的圆心和半径；Shape和Direction表示点云集合的形状系数和主方向。

1.3 树干与树冠点云提取

1)体元水平邻域一致性。行道树周围存在的人造杆目标(主要是路灯与交通标志牌)与灌木是行道树点云提取过程中的主要干扰因素。人造杆与树干点云之间的回波反射强度存在差异；同理，灌木与树干点云之间的曲率存在差异。以体元的平均回波反射强度与平均曲率特征为约束，结合表1中的体元水平邻域内特征描述，在同层格网内进行体元水平邻域分析，可有效滤除人造杆目标与灌木体元。具体步骤如下。

①在距离地面1.2～1.4 m的那层格网内随机选择一个非空体元作为种子体元SV。

②若SV的平均回波反射强度与平均曲率特征同时满足阈值条件，则将其标记属性为Treek；反之，标记属性为False，并重新选择种子体元，直到满足阈值条件为止。

③如图2所示，以种子体元SV为中心创建5×5体元模板，搜索模板内其他非空体元V，计算二者的平均回波反射强度与平均曲率特征在二维欧式空间下的距离Distance，根据距离远近判断体元相似度。若满足相似度阈值条件，则将体元V标记属性Treek；反之，标记属性为False。

图2 体元水平邻域一致性分析

④在同层格网内未被标记任何属性的非空体元集合中重新选择种子体元SV，并重复步骤②、步骤③，直到不存在未被标记属性的非空体元为止。

2)体元竖直邻域一致性。行道树包括树干和树冠2个部分，可利用体元的竖直邻域一致性来确定第一分枝点所在位置。树干点云在竖直方向上连续分布，因此，在相邻的2层网格中一定存在具有相同行列号的非空体元，将多层格网叠加处理，使得树干在各层格网中的竖直邻域关系得以体现。

对三维格网逐层进行体元水平邻域分析，最终保留一定数量的5×5体元模板。搜索存在相同行列号体元的体元模板并进行聚类，则聚类体元内点云集合为疑似树干点云。某层聚类体元内点云如图3所示，利用随机抽样一致算法(random sample consensus，RANSAC)进行平面圆拟合，计算圆心O与半径R，同时利用主成分分析法(principle components analysis，PCA)计算点云集合的形状系数Shape与主方向Direction。利用表1中的体元竖直邻域特征描述对疑似树干点云作进一步判断，判断条件如式(2)所示。

图3 体元竖直邻域一致性分析

|OL-OL+1|

(2)

树干呈竖直圆柱状，即相邻2层聚类体元内点云的拟合圆圆心坐标偏移量与半径之差同时小于阈值，且点云集合的形状系数为1(线状)，主方向近似平行于Z轴，据此提取行道树树干点云。

3)分层点云投影面积计算。经过上述体元邻域分析之后，可滤除大部分路灯与交通标志牌噪点，但是树干与灯杆外形接近，且后者长期暴露在户外，难免会发生损坏老化，其表面反射率不达标，无法通过体元平均回波反射强度和平均曲率特征进行滤除，造成个别路灯灯杆被误分类为树干。根据树冠与路灯的形态差异，设计了一种分层点云投影面积判别法来进一步区分出行道树与路灯，同时提取完整的树冠点云，实现测区内行道树的单体化输出。

在原始三维格网索引下，从第一分枝点开始，自下而上逐层聚类搜索疑似树冠点云。实际道路环境中很多树木树冠相连，且个别路灯穿插在树冠中，在聚类搜索时需逐层设置约束半径，防止树冠点云过度生长。算法以树干点云重心坐标为圆心，根据垂直于行驶方向的道路内侧点云计算当前分层的约束半径。

在数据采集过程中，道路外侧的树冠点云必然存在缺失，为提高分层点云投影面积计算的准确性，采用文献[15]算法引入树冠点云方位残缺率，加权计算各分层点云投影面积值。

4)树冠点云判别。行道树树冠点云的外形近似于“卵形”，若沿竖直方向等距切分，可分解为一个圆锥与若干圆台模型。如图4所示，树冠点云被等距切分为19个冠层，按照上文所述方法计算各冠层点云投影面积，对19个面积值进行3次样条插值，获得光滑曲线。当冠层序号layer=7时，投影面积S取得最大值，投影面积曲线在宏观上满足先单调递增后单调递减的变化趋势，于是建立冠层点云投影面积理论模型，如式(3)所示。

图4 单个树冠分层点云投影面积曲线

Si-1Si>Si+1

(3)

式中：Si表示第i个冠层点云投影面积。

随机选取了10棵行道树样本，对其树冠点云进行分层，分别计算各冠层内点云投影面积S，并绘制投影面积曲线(图5)。不难发现，虽然不同行道树的树冠体积存在较大差异，但自下而上各冠层点云投影面积总体上呈先递增后递减的变化趋势，仍然满足式(3)的投影面积理论模型。

图5 10棵行道树树冠分层点云投影面积曲线

如图6所示，路灯贯穿树冠，且下部灯杆被误分类为树干。这类路灯的上部聚类点云包含树冠与灯头，分层计算聚类点云投影面积并绘制投影面积曲线(图6)。从图6中可知，在第10冠层(layer=10)处点云的投影面积S取得最大值；当layer<10时，冠层点云的S值单调递增，与理论模型相符；当layer>10时，S值理论上单调递减，但是受上部灯杆与路灯灯臂影响，导致局部冠层点云(layer=13、14、15)投影面积反而增大；当layer>20时，仅存在灯头点云，多个相邻冠层点云的S值近似相等，曲线趋于平缓。故存在一定数量的分层点云投影面积不符合理论模型。

图6 树冠与路灯分层点云投影面积曲线

结合树冠分层点云投影面积理论模型来对疑似树冠点云进行判别，进一步剔除被误分类为树干的路灯。为量化树冠点云的判别指标，引入道格拉斯-普克算法[16]提取投影面积曲线轮廓特征点，根据特征点计算树冠判别值δ。

道格拉斯-普克算法作为一种全局的曲线化简算法，能在一定程度上保持化简后曲线的整体形态。对图4树冠分层点云投影面积曲线使用道格拉斯-普克算法进行化简，结果如图7(a)所示，最终保留7个特征点，且曲线在特征点3处取得最大值。依次计算相邻特征点i和i+1之间的连续斜率ki，同时记录2点之间所包含的若干冠层(如特征点4、5之间包含了第10、11、12冠层，连线斜率为k4)。在树冠分层点云投影面积理论模型约束下，特征点1、2、3位于单调递增区间内，故相邻特征点连线斜率ki>0(i=1，2)；特征点4、5、6、7位于单调递减区间内，故相邻特征点连线斜率ki<0(i=3，4，5，6)。且相邻多个冠层点云投影面积变化明显，斜率绝对值不小于阈值Kmin。

同理，图7(b)为图6中投影面积曲线的化简结果，保留了9个特征点，曲线在特征点5处取得最大值。位于单调递减区间内的特征点6、7的连线斜率k6>0；特征点8、9的连线过于平缓，其斜率k8的绝对值小于阈值Kmin。显然，上述2组相邻特征点内的冠层点云投影面积与理论模型相悖。

图7 道格拉斯-普克算法曲线简化

一次迭代完成之后，统计满足斜率条件的相邻特征点之间的冠层数量，用于计算树冠判别值δ(满足理论模型的冠层数量与冠层总数之比)。若δ>80%，则认为当前聚类点云为树冠，否则作为伪树冠剔除。

2 实验

2.1 实验数据与参数设置

为验证算法的有效性，采用车载移动测量系统所采集的2组实际路段点云进行实验，数据点位精度优于3 cm。如图8(a)所示，道路Ⅰ全长约0.547 km，为双向4车道，地形平坦，道路两侧的行道树主要为白蜡树，数据共有10 811 215个点。如图8(b)所示，道路Ⅱ全长0.835 km，为双向2车道，地形起伏较大，道路两侧的行道树主要为法国梧桐，数据共有16 280 769个点。2条道路均存在低矮绿化，主要的杆目标有行道树、路灯和交通标志牌。

图8 实验数据

根据城市行道树种植规范，道路两侧的行道树规格接近，且树干位于所在区域地面1.3 m处，为林业部门定义胸径的高度[17]。经过实地量测，道路Ⅰ的白蜡树树干平均胸径为25 cm，道路Ⅱ的法国梧桐树干平均胸径为38 cm。以行道树树干的平均胸径作为体元的划分尺度，树干点云提取过程中需人工设定的参数见表2。对于树冠点云的提取，分层点云投影面积曲线，经过道格拉斯-普克算法简化后，保留若干特征点，需人工设定相邻特征点连线斜率绝对值的最小阈值Kmin。若Kmin设置过大，则无法判别树冠点云；设置过小，则无法有效去除被误分类为树干的人造杆目标。经过大量样本实验，确定Kmin的取值为0.6。

2.2 结果与讨论

本文利用C++实现上述算法，设置好参数对原始点云进实验，2条道路上的行道树点云提取结果分别如图9和图10所示。图中树干点云被统一赋成红色，树冠点云按照行道树ID号随机赋色。道路两侧的行道树被准确提取，不受周围人造杆目标和灌木的影响。

图9 道路Ⅰ提取结果

图10 道路Ⅱ提取结果

图11(a)和图11(b)分别是图9中区域A和区域B的局部放大图，将提取得到的行道树目标与原始点云叠加显示。路灯、监控探头、交通标志牌和行道树这4类杆目标相互交错且周围存在大量低矮灌木，一定程度上对行道树目标的提取造成了困难。算法依据体元的平均回波反射强度与平均曲率特征进行空间邻域分析，可以准确提取树干点云，不受邻近地物噪点的干扰。

图11 行道树提取结果与原始点云叠加

图12为图10中区域A的局部放大图，树木之间距离较近，部分树冠相连。算法以道路内侧点云为参考，逐层计算冠幅半径Rmin，然后以Rmin为聚类生长约束条件，逐层提取树冠点云。根据最后提取结果可以看出，树冠分割效果较好。

图12 相连行道树提取结果

树干是行道树的重要组成部分，本文算法首先提取树干，然后从树干顶端向上聚类获取树冠点云。图13(a)为图10中区域B的原始点云，路灯贯穿树冠。图13(b)为树干提取结果，其中，路灯的下部灯杆因表面老化导致反射率不达标，从而被误分类为树干。算法建立了树冠分层点云投影面积理论模型，搜索疑似树冠点云，并逐层计算投影面积，在理论模型约束下计算树冠判别阈值。最终提取结果如图13(c)所示，有效滤除了被误分类为树干的灯杆。

图13 树冠点云判别

但2组实验数据中仍然存在一些错误提取及遗漏的情况。个别树木距离扫描仪较远且受到车辆遮挡，树干点云缺失，不满足杆状地物特征，无法通过体元邻域分析进行识别。此外，个别树冠的枝叶过于稀疏，其外形不符合常规树冠的“卵形”，无法使用冠层投影面积变化理论模型对其进行判别。可见，点云数据的完整程度与密度直接影响整体的提取效果。对原始数据和实验结果进行了统计分析，根据式(4)评价行道树点云提取的准确率与召回率。

(4)

式中：TP为正确提取的数量；FN未被提取的数量；FP为错误提取的数量。

统计结果如表3所示，算法对2组数据中行道树目标提取的准确率分别达到94.77%和92.61%，召回率分别达到91.78%和89.13%。将本文算法和同样采用体元法的文献[9]进行了对比。编程实现文献[9]算法，再次对2组实验数据进行处理，对比分析正确率与召回率。如表4所示，本文方法对行道树提取的正确率与召回率均有提高。由于部分人造杆目标穿插在树冠中，文献[9]直接对非空体元聚类会将其误分类为树木，降低正确率。行道树底部存在大量低矮灌木，与树干距离较近的上部灌木噪点会破坏树干的形态，造成漏提，降低召回率。

表3 行道树提取结果定量分析

表4 方法对比

3 结束语

针对车载激光扫描数据，本文提出了一种顾及体元邻域关系的行道树提取方法。首先建立规则格网索引，然后以树干几何特征为基础，结合点云的回波反射强度与曲率属性，充分挖掘体元的空间邻域关系，成功提取出树干点云。在此基础上，建立树冠分层点云投影面积理论模型，聚类搜索疑似树冠点云并分层计算投影面积，将计算结果与理论模型进行比较，通过设定分类阈值来识别树冠，同时滤除被误分类为树干的灯杆，最终实现行道树点云的自动化提取。实验结果表明，本文算法可以避免邻近地物噪点影响，准确提取复杂城市道路环境下的行道树点云，提取结果的正确率和召回率分别达到了93.41%和90.12%，具有较强的适应性与稳健性。在后续的研究中，可尝试引入新的体元特征，以增强行道树提取的稳健性。此外，也可以根据树冠分层点云投影面积进行精细化建模，用于行道树种类的识别。