基于變尺度格網索引與機器學習的行道樹靶標點云識別

李秋潔 鄭加強 周宏平 陶 冉 束義平

(南京林業大學機械電子工程學院， 南京 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.