基于变尺度格网索引与机器学习的行道树靶标点云识别

李秋洁 郑加强 周宏平 陶 冉 束义平

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

0 引言

行道树是城市生态系统和城市景观的重要组成部分，面对当前日益严峻的环境污染问题，行道树对改善城市生态环境[1]、净化空气[2]、调节气候[3]以及涵养水源[4]方面有着重要意义。受温室效应、人为干扰等因素的影响，行道树病虫害日益增多，致使行道树枯萎或死亡，不仅严重影响行道树绿化与美化效果，而且直接影响城市生态环境与居民生活，成为园林绿化精细化管理的制约因素[5]。

由于行道树存在间距较大、树冠大小不同或缺株现象，连续喷雾施药方式使得大量药液流失到地面或飘移挥发到空气中，严重污染城市环境，影响居民生活工作。目前，对靶施药技术已在果园、苗圃病虫害防治中取得成功应用[6-7]。2010年美国农业部农业工程应用技术国家实验室与俄亥俄州立大学合作，研发出基于二维激光雷达(Light detection and ranging，LiDAR)探测的多指变量风送式喷雾机[8-9]，并于2012年形成产品，在美国多个州的果园和苗圃中应用示范推广。该机采用2D LiDAR进行垂直于车辆行驶方向的扇形扫描，利用测量点深度阈值识别靶标，计算靶标实时体积控制喷雾流量，实现变量对靶喷雾。然而，靶标阈值识别法不适用于多地物目标城区环境下的行道树识别，目前鲜见行道树靶标识别相关的研究报道。

3D LiDAR在2个互相垂直方向上扫描测距，以森林资源调查为应用背景，以车载3D LiDAR测量系统为数据采集手段，研究者围绕行道树识别开展了大量研究，已有方法可按点云索引结构分为格网法、体素法及点云法3类。格网法始于机载LiDAR冠层高度模型[10]，将空间区域划分为二维规则格网，根据点云平面坐标建立与格网的对应关系，应用图像分割、轮廓提取、形态学运算等手段定位分割行道树[11-13]。体素法是格网法在三维空间的扩展，将空间划分为体素，通过对体素空间聚类或区域生长提取完整行道树[14-18]。点云法直接对原始或归一化的点云进行操作，为提高检索效率，常采用四叉树、八叉树、k-d树(k-dimensional tree)等结构组织点云[19-21]。格网、体素等均匀空间索引能有效降低点云数据量及数据冗余度，提高邻域检索效率，但难以处理点云密度不均的情况，同时格网/体素尺寸选择与分割精度较难平衡。四叉树、八叉树、k-d树等非均匀空间索引能较好适应数据非均匀分布，保留数据精度，便于点云批量显示、存储，但难以满足数据在线处理需求。

针对行道树连续喷雾施药方式严重污染环境，果园对靶施药技术难以推广至复杂城区环境等问题，本文采用数据冗余度小、易于在线处理的车载2D LiDAR获取城市街道数据，研究行道树靶标识别方法，为对靶施药提供精准喷雾依据。拟建立保留数据精度、提高邻域检索效率、满足在线处理需求的点云索引结构，分析树冠与其他地物目标的差异性，提取树冠特征向量，分析特征分布特性，建立基于机器学习的树冠识别模型，实现行道树靶标的准确识别。

1 行道树靶标识别方法

通过图1所示基于机器学习的树冠点云识别方法识别行道树靶标。对标注好的训练数据进行点云邻域提取，计算特征向量，采用机器学习算法从特征向量集中学习树冠点云分类器。在线识别时，构建先进先出(First in first out，FIFO)缓冲区(f1,f2,…,f2N+1)，中间帧fN+1为待处理帧，其中

(1)

式中δ——点云球域半径，mN——帧数

v——车辆移动速度，m/s

Δt——2D LiDAR扫描周期，s

新一帧数据fnew到来后，按如下规则更新FIFO。

(2)

对中间帧fN+1逐点处理，提取邻域计算特征向量，采用树冠点云分类器识别树冠点云，提供喷雾处方图。

图1 基于机器学习的树冠点云识别方法流程图Fig.1 Flow chart of crown point cloud recognition based on machine learning

1.1 点云采集

车载2D LiDAR点云数据采集系统测量垂直于车辆移动方向的扇形扫描区域距离信息，每次扫描返回1帧数据，包含不同角度的测量点距离。建立点云坐标系，x轴为车辆移动方向，y轴为深度方向，z轴垂直地面向上，如图2所示，求取点云坐标为

(3)

式中t——测量时间

r——测量点距离

θ——测量点角度

图2 车载2D LiDAR点云数据采集系统Fig.2 Vehicle-borne 2D LiDAR point cloud data acquisition system

1.2 点云索引建立

构建图3所示变尺度格网索引，格网单元与测量点一一对应。i为测量点帧序号，j为测量点帧内编号。为计算格网实际尺寸，引入尺度因子

(4)

式中 Δα——2D LiDAR弧度分辨率

sx——车辆运动方向尺度因子

sr——2D LiDAR扫描方向尺度因子

图3 变尺度格网Fig.3 Variable-scale grid

1.3 点云邻域提取

点云特征计算需要连同三维邻域内其他点一起统计分析，因此需考虑邻域形状和大小。由于树冠点云杂乱分布，无法表达为线、面、柱等基本几何元素，故采用三维球形邻域提取点云特征。

假设P0的格网坐标为(i0,j0)，为快速求取以P0为中心、δ为半径的球形邻域U(P0,δ)，构建其与二维格网邻域R(P0,δ)的映射关系，确定球形邻域的格网搜索范围，实现邻域点快速查找，如图4所示。

图4 球形邻域与格网邻域的映射关系Fig.4 Mapping relationship between spherical neighborhood and grid neighborhood

求取球域U(P0,δ)的步骤为：

(1)求取球域U(P0,δ)与激光扫描光束的切面，得到圆形格网邻域，为便于计算，可进一步简化为矩形格网邻域

(5)

(2)在格网邻域R(P0,δ)中搜索符合球域定义的点。

(6)

1.4 特征定义

定义描述树冠一致性、树冠与建筑物、路灯、电线杆、标志牌等地物目标差异性的11个特征。

(1)高程特征

包括球域高程均值μz、高程方差δz及高程范围Δz=zmax-zmin。此类特征可排除地面、低矮灌木植被及较高的建筑物。

(2)深度特征

包括球域深度均值μy、深度方差δy及深度范围Δy=ymax-ymin。此类特征可排除电线杆、建筑物等垂直分布的地物。

(3)密度特征

不同类型的物体点云密度不同，树冠点云密度比电线杆等杆状物高，比地面和建筑物低。定义密度d为球域内点数。

(4)协方差矩阵特征

计算球域内点云三维坐标的协方差矩阵，从中提取全方差o、线性a1D、平面性a2D、球度性a3D4个几何特征[18, 22-24]，与建筑物、路灯、电线杆、标志牌等具有规则几何形状的人造地物目标相比，树冠点云具有较高的各项异性，较低的线性、平面性、球度性。

(7)

式中λ1、λ2、λ3——点云协方差矩阵特征值

1.5 点云分类器学习

不同特征的鉴别力存在差异，对树冠点云识别的贡献不同，采用机器学习算法融合11个特征x=(μz,δz,Δz,μy,δy,Δy,d,o,a1D,a2D,a3D)，训练树冠点云分类器。支持向量机(Support vector machine,SVM)求取最小化结构风险的线性分类器，与最小化经验风险的学习方法相比，具有泛化性能强的优点[25]。

将距离分类器最近的样本称为支持向量，支持向量到分类器的距离称为间隔(margin)，SVM以最大化间隔为目标，求取最优分类器，如图5所示。待分类样本类别为

(8)

式中x——待识别点云特征向量

xi——支持向量

ci——支持向量类别

αi——支持向量权重

n——支持向量个数

b——分类器偏置

图5 间隔最大化分类器Fig.5 Margin maximization classifier

通过引入非线性核函数K(·)，SVM可以解决非线性分类问题，此时待分类样本类别为

(9)

式中K(xi,x)——x、xi非线性映射后的内积运算函数

树冠点云的特征直方图呈正态分布，如图6所示，因此，采用高斯径向基核函数将样本映射到高维空间分类。

(10)

式中σ——核宽

图6 树冠点云特征分布直方图Fig.6 Feature distribution histagrams of crown point cloud

2 实验

实验采用日本Hokuyo公司生产的UTM-30LX型2D LiDAR，如图7所示。扫描范围270°，角度分辨率0.25°，扫描周期25 ms。实验程序采用Matlab 2014b软件开发，实现点云标注、特征提取、分类器训练及树冠点云识别。

图7 UTM-30LX型2D LiDAR实物图及工作方式Fig.7 Diagram of 2D LiDAR UTM-30LX and work condition

2.1 点云样本集

图8为南京林业大学校园内采集的点云样本，包含树木、建筑、停车棚、自行车、路灯、灌木、行人等地物目标。

图8 点云样本Fig.8 Point cloud sample

图9 点云标注过程Fig.9 Point cloud annotation process

建立标注文件记录点云类别信息，标注步骤如下：

(1)输入点云文件及标注文件路径，若标注文件不存在，则新建标注文件，否则，读入标注文件，继续标注。

(2)显示xz平面点云视图，输入点云x轴坐标范围，进行x轴分割，如图9a所示。

(3)显示yz平面点云视图，输入点云y、z轴坐标范围，进行yz平面分割。图9b中，用大矩形框分割出树冠，用2个小矩形框排除框内的非树冠点云。

(4)将已分割的点云区域标注为树冠或非树冠，显示标注信息，如图9c所示，标注未完成则转至步骤(1)。图9d是样本的标注结果。

点云样本集包含树冠点云201 456个，非树冠点云137 484个，从中随机抽取5%的点云用于训练，剩余95%点云用于测试。

2.2 树冠识别结果

球域半径δ在0.1～0.8 m范围内以0.1 m间隔变化时，分类器在训练集和测试集上的错误率、检出率及虚警率如表1所示。从表中可看出，分类器性能受球域半径影响较小，分类器泛化性能较好，测试集分类错误率小于0.8%，检出率大于99.4%，虚警率小于0.9%。

表1 不同球域半径的分类结果Tab.1 Classification result of different sphere radiuses

2.3 特征鉴别力分析

为评估各个特征对树冠识别的贡献，对单个特征的分类性能进行测试，表2为δ=0.1 m时，采用高斯径向基核函数SVM学习的单特征分类器的分类结果，所有特征的测试集分类错误率均小于32.5%，即对树冠识别有所贡献。其中，分类错误率最低的4个特征依次是高程均值μz、深度均值μy、高程范围Δz和高程方差δz，前2个特征的分类错误率小于3%，表明这些特征具有较强的鉴别性，对分类的贡献较大。

表2 不同特征在测试集上的分类结果Tab.2 Classification result of different features

以格网索引结构显示点云数据，图10给出了单个特征在测试集上的分类结果。高程均值μz能排除低高程的地物目标，高程方差δz与高程范围Δz能过滤水平地面。深度均值μy能排除较近及较远的地物目标，但无法过滤与树冠位于同一深度范围的树干，深度方差δy与深度范围Δy能过滤树干等具有垂直分布特性的地物目标，但漏检较多。密度特征d能排除点云密集分布的地物目标，漏检较少。协方差矩阵特征o、a1D、a2D、a3D对地面、树干、停车棚等结构性较强的地物目标起到一定的过滤作用，但除线性特征a1D以外，其他3个特征漏检较多。

综上所述，各个特征在树冠识别中所起的作用不同，通过SVM能有效融合这些特征，提高分类性能。

图10 单个特征的分类结果Fig.10 Classification results of single feature

3 结论

(1)应用车载2D LiDAR获取道路高精度点云数据，建立变尺度格网点云索引，保留数据精度的同时提高点云球域搜索效率，实现点云在线处理。

(2)提取高程、深度、密度及协方差矩阵等特征，构建11维特征向量，采用基于高斯径向基核函数的支持向量机算法融合特征，学习树冠点云分类器。

(3)实验结果表明，本文方法能实现行道树靶标精准识别，测试集分类错误率小于0.8%，检出率大于99.4%，虚警率小于0.9%。

(4)鉴别力最强的4个特征从高到低依次是高程均值、深度均值、高程范围和高程方差，前2个特征的测试集分类错误率小于3%。

1 JANG H S, LEE S C, JEON J Y, et al. Evaluation of road traffic noise abatement by vegetation treatment in a 1∶10 urban scale model[J]. Journal of the Acoustical Society of America, 2015, 138(6): 3884-3895.

2 GROMKE C, RUCK B. Influence of trees on the dispersion of pollutants in an urban street canyon-experimental investigation of the flow and concentration field[J]. Atmospheric Environment, 2007, 41(16): 3287-3302.

3 GILLNER S, VOGT J, THARANG A, et al. Role of street trees in mitigating effects of heat and drought at highly sealed urban sites[J]. Landscape & Urban Planning, 2015, 143: 33-42.

4 BERLAND A, HOPTON M E. Comparing street tree assemblages and associated stormwater benefits among communities in metropolitan Cincinnati, Ohio, USA[J]. Urban Forestry & Urban Greening, 2014, 13(4): 734-741.

5 逄凯惠. 绿化带大树主要病虫害调查分析[J]. 防护林科技, 2016(8): 34-35.

PANG Kaihui. Analysis on major diseases and pests for the trees of green belt[J]. Protection Forest Science and Technology, 2016(8): 34-35.(in Chinese)

6 邱白晶, 闫润, 马靖, 等. 变量喷雾技术研究进展分析[J/OL]. 农业机械学报, 2015, 46(3): 59-72. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?file_no=20150309&flag=1&journal_id=jcsam.DOI：10.6041/j.issn.1000-1298.2015.03.009.

QIU Baijing, YAN Run, MA Jing, et al. Research progress analysis of variable rate sprayer technology[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(3): 59-72.(in Chinese)

7 李瀚哲, 翟长远, 张波, 等. 果园喷雾靶标探测技术现状分析[J]. 农机化研究, 2016, 38(2): 1-5.

LI Hanzhe, ZHAI Changyuan, ZHANG Bo, et al. Status analysis of orchard spray target detection technology[J]. Journal of Agricultural Mechanization Research, 2016, 38(2): 1-5.(in Chinese)

8 CHEN Y, OZKAN H E, ZHU H, et al. Spray deposition inside tree canopies from a newly developed variable-rate air-assisted sprayer[J]. Transactions of the ASABE, 2013, 56(6): 1263-1272.

9 LIU H, ZHU H, SHEN Y, et al. Development of digital flow control system for multi-channel variable-rate sprayers[J]. Transactions of the ASABE, 2014, 57(1): 273-281.

10 李增元, 刘清旺, 庞勇. 激光雷达森林参数反演研究进展[J]. 遥感学报, 2016, 20(5): 1138-1150.

LI Zengyuan, LIU Qingwang, PANG Yong. Review on forest parameters inversion using LiDAR[J]. Journal of Remote Sensing, 2016, 20(5): 1138-1150.(in Chinese)

11 杨必胜, 魏征, 李清泉, 等. 面向车载激光扫描点云快速分类的点云特征图像生成方法[J]. 测绘学报, 2010, 39(5): 540-545.

YANG Bisheng, WEI Zheng, LI Qingquan, et al. A classification-oriented method of feature image generation for vehicle-borne laser scanning point clouds[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(5): 540-545.(in Chinese)

12 杨莎莎, 李永强, 李框宇, 等. 基于车载LiDAR数据的单株树提取[J]. 测绘工程, 2014, 23(8): 23-27.

YANG Shasha, LI Yongqiang, LI Kuangyu, et al. Tree extraction from vehicle-borne LiDAR data[J]. Engineering of Surveying and Mapping, 2014, 23(8): 23-27.(in Chinese)

13 ZHONG R, WEI J, SU W, et al. A method for extracting trees from vehicle-borne laser scanning data[J]. Mathematical & Computer Modelling, 2013, 58(3-4): 727-736.

14 WU B, YU B, YUE W. A voxel-based method for automated identification and morphological parameters estimation of individual street trees from mobile laser scanning data[J]. Remote Sensing, 2013, 5(2): 584-611．

15 张恒, 许君一, 刘如飞, 等. 一种基于改进区域增长的行道树点云提取方法[J]. 测绘科学技术学报, 2015, 32(2): 178-182.

ZHANG Heng, XU Junyi, LIU Rufei, et al. An extraction method of trees in vehicle-borne laser point cloud based on the improved region growing method[J]. Journal of Geomatics Science and Technology, 2015, 32(2): 178-182.(in Chinese)

16 YUE G, LIU R, ZHANG H, et al. A method for extracting street trees from mobile LiDAR point clouds[J]. Open Cybernetics & Systemics Journal, 2015, 9(1): 204-209.

17 VAUGHN N R, MOSKAL L M, TURNBLOM E C. Tree species detection accuracies using discrete point lidar and airborne waveform LiDAR[J]. Remote Sensing, 2012,4(2): 377-403.

18 董震, 杨必胜. 车载激光扫描数据中多类目标的层次化提取方法[J]. 测绘学报, 2015, 44(9): 980-987.

DONG Zhen, YANG Bisheng. Hierarchical extraction of multiple objects from mobile laser scanning data[J]. Acta Geodaetica et Cartographica Sinica, 2015, 44(9): 980-987.(in Chinese)

19 YOKOYAMA H, DATE H, KANAI S, et al. Detection and classification of pole-like objects from mobile laser scanning data of urban environments[J]. International Journal of CAD/CAM, 2013, 13(1): 1-10.

20 LIANG X L, LITKEY P, HYYPPA J, et al. Automatic stem mapping using single-scan terrestrial laser scanning[J]. IEEE Transactions on Geoscience and Remote Sensing, 2012, 50(2): 661-670.

21 李海亭, 肖建华, 李艳红, 等. 机器学习在车载激光点云分类中的应用研究[J]. 华东师范大学学报:自然科学版, 2015, 49(3): 460-464.

LI Haiting, XIAO Jianhua, LI Yanhong, et al. Application of machine learning in the vehicle-borne laser point cloud extraction[J]. Journal of Central China Normal University: Natural Science, 2015, 49(3): 460-464.(in Chinese)

22 郭波, 黄先锋, 张帆, 等. 顾及空间上下文关系的JointBoost点云分类及特征降维[J]. 测绘学报, 2013, 42(5):715-721.

GUO Bo, HUANG Xianfeng, ZHANG Fan, et al. Points cloud classification using JointBoost combined with contextual information for feature reduction[J]. Acta Geodaetica et Cartographica Sinica, 2013, 42(5):715-721.(in Chinese)

23 DEMANTKE J, MALLET C, DAVID N, et al. Dimensionality based scale selection in 3D LiDAR point clouds[J]. ISPRS-International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2012, 3812(5):97-102.

24 MARTIN R, BERNHARD H, MARKUS H, et al. Object-based point cloud analysis of full-waveform airborne laser scanning data for urban vegetation classification[J]. Sensors, 2008, 8(8):4505-4528.

25 VAPNIK V. The nature of statistical learning theory[M]. New York: Springer-Verlag, 1995.