李秋潔，袁鵬成，劉旭，周宏平

(南京林業(yè)大學機械電子工程學院，南京 210037)

行道樹資源調(diào)查是城市森林資源調(diào)查的重要工作，是開展城市森林生態(tài)研究的前提條件。目前，行道樹資源調(diào)查主要采用人工實測和抽樣調(diào)查等方法，工作量大、效率低下，不能及時準確地反映行道樹動態(tài)變化狀況。移動激光掃描(mobile laser scanning，MLS)測量技術(shù)能夠快速獲取高分辨率、高精度的樹木垂直結(jié)構(gòu)數(shù)據(jù)，改善難度大、周期長的傳統(tǒng)行道樹資源調(diào)查作業(yè)模式，實現(xiàn)大范圍、全面快速地獲取單木尺度的行道樹參數(shù)信息[1-2]。

行道樹點云分割是基于MLS的行道樹參數(shù)提取的首要步驟[3]，目前，主要通過樹干檢測獲取行道樹位置，以樹干為種子點區(qū)域增長分割出完整行道樹[4]。具體過程如下：1)體素化[5]，將空間劃分為立方體素，點云根據(jù)空間坐標歸入相應體素，以體素作為數(shù)據(jù)處理基本單元；2)地面濾除，利用平面擬合等方法濾除地面點云，保留地上目標點云數(shù)據(jù)；3)桿狀物檢測，提取較低高度范圍的點云數(shù)據(jù)進行地面投影，根據(jù)投影面積、形狀、密度分布等特征識別桿狀物；4)桿狀物提取，以桿狀物底部點云數(shù)據(jù)為種子點進行點云分割，提取完整桿狀物；5)行道樹識別，利用點云分布、尺寸等特征濾除路燈、電線桿等桿狀目標，識別行道樹。

Zhong等[6]利用點云法向量進行平面擬合去除地面點。吳賓等[7]和Wu等[8]提取距地面高度1.2～1.4 m的格網(wǎng)進行連通域分析，將大小和緊湊度指數(shù)符合條件的區(qū)域作為樹干，使用三維區(qū)域競爭生長算法提取行道樹候選區(qū)域。張恒等[9]分析行道樹在多層格網(wǎng)中的分布形態(tài)，在空間區(qū)域生長過程中結(jié)合點云投影密度和高程分布等特征有效排除其他地物。楊莎莎[10]根據(jù)高程差從候選區(qū)域中去除車輛、行人、花壇、灌木等低矮地物，根據(jù)水平投影形狀及面積濾除建筑物與路燈。董亞涵等[11]根據(jù)候選區(qū)域投影跨度去除路燈、低矮建筑物、路標及廣告牌，根據(jù)上、下部投影面積比值去除電線桿。

樹干檢測是行道樹定位與分割的核心步驟，已有方法由知識驅(qū)動，人工設計檢測規(guī)則，難以跨越低層點云數(shù)據(jù)到高層地物目標的語義鴻溝，前期無法區(qū)分樹干與其他桿狀目標，需要在桿狀目標提取過程中或結(jié)束后進一步設計識別規(guī)則濾除非行道樹桿狀目標。

本研究將樹干提取分為樹干點云識別與樹干點云分割2個步驟：首先，通過監(jiān)督學習算法從城市街道點云標注數(shù)據(jù)集中自動學習樹干點云與非樹干點云的差異性，獲取高精度樹干點云檢測器；然后，基于樹干點云識別結(jié)果，分割、標識出每一根樹干。行道樹樹干提取流程如圖1所示。

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

1 移動激光掃描系統(tǒng)

本研究采用基于二維激光雷達的MLS系統(tǒng)，如圖2所示。隨著車輛的移動，二維激光雷達不斷返回與車輛移動方向垂直的扇形平面內(nèi)不同角度測量點的距離r及激光反射強度I。與基于三維激光雷達的MLS系統(tǒng)相比，二維激光雷達成本較低，數(shù)據(jù)冗余度小，在林木參數(shù)實時提取、植物三維重建、表型測量等領(lǐng)域[12-15]得到廣泛應用。

圖2 MLS系統(tǒng)數(shù)據(jù)采集方式Fig. 2 Data acquisition mode of MLS system

建立MLS坐標系統(tǒng)，求取點云三維空間坐標，如圖3所示。x軸為車輛移動方向，y軸為深度方向，z軸垂直地面向上。MLS測量數(shù)據(jù)可以用測量點幀序號i和幀內(nè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坐標系統(tǒng)Fig. 3 Coordinate system of MLS

后續(xù)處理的點云數(shù)據(jù)擁有5個屬性值，包括三維空間坐標[x(i,j),y(i,j),z(i,j)]、測量點的距離r(i,j)及激光反射強度I(i,j)。

2 行道樹樹干提取

2.1 鄰域查找

為計算點云局部特征，需首先查詢點云鄰域。對于離散、非結(jié)構(gòu)化的點云數(shù)據(jù)，主要采用體素、八叉樹、k-d樹等方法索引點云數(shù)據(jù)，由于本研究采用的MLS系統(tǒng)直接生成結(jié)構(gòu)化點云數(shù)據(jù)，可省去建立索引的時間和空間開銷。

假設第i幀第j個測量點為P，采用兩步法[16]計算以P為球心，δ為半徑的球域。首先，求取P球域的幀序號及幀內(nèi)編號范圍，根據(jù)車輛速度和二維激光雷達掃描周期可計算幀間分辨率(Δi)，即車輛行駛方向上相鄰幀測量點的最小距離：

Δi=vΔt

(2)

根據(jù)測量距離和弧度分辨率可計算幀內(nèi)分辨率(Δj)，即二維激光雷達掃描方向上相鄰測量點的最小距離：

Δj=r(i,j)Δα

(3)

式中：Δα為二維激光雷達弧度分辨率。假設P球域的幀序號范圍為[i-δi,i+δi]，幀內(nèi)序號范圍為[j-δj,j+δj]，根據(jù)球域半徑和幀間、幀內(nèi)分辨率計算δi、δj：

(4)

2.2 特征提取

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

圖4 MLS點云數(shù)據(jù)非均勻性Fig. 4 Non-uniformity of MLS point cloud data

2.3 樹干點云檢測器訓練

Boosting系列算法是一類提高弱學習算法性能的強學習算法，與支持向量機、神經(jīng)網(wǎng)絡等算法相比，具有參數(shù)少、低泛化誤差、容易實現(xiàn)等優(yōu)勢，在模式識別的各個領(lǐng)域取得成功應用[19-20]。本研究采用Discrete AdaBoost[21]訓練樹干檢測器。

fort=1 toT：

(1)學習弱分類器：ft=L(S,Dt)；

(2)計算分類錯誤率：et=∑m,ft(xm)≠cmDt(m)；

(4)更新樣本權(quán)重：

(5)

式中，γt=0.5-et?？芍?，Discrete AdaBoost的訓練誤差隨迭代次數(shù)指數(shù)下降，只要弱學習算法優(yōu)于隨機猜想，算法可通過足夠多次迭代達到任意精度。

與其他機器學習算法相比，Boosting的優(yōu)勢如下：1)采用集成(ensemble)機制降低了算法復雜度，提高了算法效率；2)無需知道弱學習算法的任何先驗知識，只需其性能比隨機猜測稍好即可，弱學習算法可以是神經(jīng)網(wǎng)絡、SVM、決策樹、k-近鄰分類器、經(jīng)驗規(guī)則等各種機器學習算法；3)訓練過程采用線性規(guī)劃(linear programming)方法，算法簡單，容易工程實現(xiàn)；4)確定弱學習算法后，除迭代次數(shù)，無需調(diào)節(jié)任何參數(shù)。

2.4 樹干幀分割

對樹干檢測結(jié)果進行幀投影，得到每幀的樹干點數(shù)，之后通過檢測樹干起始幀定位樹干。

1)若某幀樹干點個數(shù)大于一定閾值Ntrunk，則識別為樹干幀：

(6)

式中：Lmin為樹干最小長度；rmin為樹干測量點最小距離。

2)若樹干幀與當前樹干起始幀的間距大于一定閾值Dtrunk，則識別為新的樹干起始幀：

(7)

式中，Dmin為兩棵樹干的最小距離。最后，將各個樹干點聚類到最鄰近樹干起始幀，分割提取出各個樹干的點云數(shù)據(jù)。

3 結(jié)果與分析

3.1 城市街道數(shù)據(jù)采集

試驗采用日本Hokuyo公司生產(chǎn)的UTM-30LX型2D LiDAR。該款LiDAR采用波長905 nm的紅外線，通過電機擺動獲取不同角度的測量值，測量距離0.1～30 m，測量精度±30 mm，掃描范圍270°，角度分辨率0.25°，掃描周期25 ms。每次掃描獲取1幀數(shù)據(jù)，包含1 081個不同角度的距離和激光反射強度，分別用4字節(jié)、2字節(jié)表示。

1. 數(shù)據(jù)采集計算機；2. 2D LiDAR；3. 小車供電模塊； 4. 主動輪；5. 小車控制器；6. 遙控器。圖5 MLS系統(tǒng)Fig. 5 MLS system

試驗采用遙控MLS測量系統(tǒng)(圖5)，以包含2個主動輪、18個從動輪的履帶底盤小車作為移動平臺，以STM32F103ZET6作為小車控制器，通過測速編碼器獲得小車速度，根據(jù)比例-微分-積分(proportion-integral-differential，PID)算法控制主動輪轉(zhuǎn)速，實現(xiàn)小車行駛方向和速度的精確控制。

數(shù)據(jù)采集地點為南京林業(yè)大學校園內(nèi)長度50 m的路段，包含建筑物、行道樹、行人、車道、人行道、路牙、路燈、草皮等地物目標，如圖6所示。采用MLS系統(tǒng)對街道進行單側(cè)掃描，2D LiDAR掃描角度范圍為-135°～135°，車輛速度0.2 m/s，采集時長250 s，獲取10 000幀數(shù)據(jù)，包含10 810 000個點云數(shù)據(jù)。

圖6 數(shù)據(jù)采集地點Fig. 6 Data collection area

為獲取帶標注的點云數(shù)據(jù)，采用MATLAB編程，利用長方體框選的方法為點云數(shù)據(jù)添加類別標簽，形成標注文件。由于y軸負半軸街道信息采集不全，僅處理y≥0的點云數(shù)據(jù)。標注后的數(shù)據(jù)集描述如表2所示，部分標注點云數(shù)據(jù)如圖7所示。

表2 數(shù)據(jù)集描述Table 2 Description of data set

圖7 部分標注點云數(shù)據(jù)Fig. 7 Some labelled point cloud data

3.2 樹干點云識別

3.2.1 球域半徑選擇

球域半徑不宜過小，應大于MLS系統(tǒng)測量分辨率；同時，球域半徑也不宜過大，否則無法表征點云局部特性。根據(jù)式(2)計算系統(tǒng)幀間分辨率為0.005 m，選取數(shù)據(jù)集最遠測量點距離rmax=17.204 m，根據(jù)式(3)計算幀內(nèi)分辨率為0.075 m。因此，δ需不小于0.075 m。為選取合適的球域半徑，令δ在0.10～0.40 m時以0.05 m為間隔取值，開展試驗。

3.2.2 單個特征鑒別力分析

為評估單個特征對樹干點云識別的貢獻，分析其在Bayes決策下的錯誤率。Bayes決策是使錯誤率最小的分類決策規(guī)則，具體如下：

如果P(c=1|x)>P(c=-1|x)，則判定為樹干，否則判定為非樹干。

式中：x為點云特征；P(c=1|x)為樹干的后驗概率；P(c=-1|x)為非樹干的后驗概率。假設樹干和非樹干的先驗概率相等，根據(jù)Bayes公式，可得到Bayes決策的等價形式：

如果p(x|c=1)>p(x|c=-1)，則判定為樹干，否則判定為非樹干。

式中：p(x|c=1)為樹干的類條件概率密度；p(x|c=-1)為非樹干的類條件概率密度。

利用樹干及非樹干的單個特征直方圖估計其類條件概率密度，獲取Bayes錯誤率近似值。首先采用最大、最小歸一化方法將特征變換到[0,1]范圍內(nèi)；然后以0.05為間隔計算樹干和樹冠的直方圖分布，則Bayes錯誤率近似為：

(8)

式中：h1(i)為直方圖第i個區(qū)間范圍的樹干點個數(shù)；h-1(i)為直方圖第i個區(qū)間范圍的非樹干點個數(shù)。

不同球域半徑下單個特征的Bayes錯誤率及最小錯誤率(表中加粗數(shù)據(jù))如表3所示。從表3中可看出：1)球域半徑對單個特征鑒別力有所影響；2)特征的最優(yōu)球域半徑各不相同，如強度均值在δ=0.10 m時鑒別力最強，而線性特征在δ=0.40 m時鑒別力最強；3)所有球域半徑下鑒別力最強的3個特征均為高程方差、強度范圍以及強度方差。

表3 不同球域半徑下單個特征的Bayes錯誤率Table 3 Bayes error of single feature in different sphere radiuses

3.2.3 多個特征樹干點云識別

樹干檢測器訓練時，采用分類決策樹作為弱學習算法，迭代次數(shù)T=300。從點云數(shù)據(jù)集中隨機抽取5%用于訓練，其余95%用于測試。用查準率(precision)和查全率(recall)評估樹干點云檢測器性能：

(9)

測試集上不同球域半徑下的樹干點云識別結(jié)果見表4。對于所有球域半徑，測試集查準率均高于93%，查全率均高于94%，表明Boosting算法通過強學習顯著提高了單個特征的分類性能。

表4 不同球域半徑下的樹干點云識別結(jié)果Table 4 Point cloud recognition results of trunk in different sphere radiuses

為盡可能識別所有樹干點云，球域半徑選取δ=0.25 m，此時樹干點云查全率最高。經(jīng)統(tǒng)計共有556個漏檢點與212個虛警點，虛警點包括169個樹冠點、1個人行道點和42個草皮點。樹干點云識別結(jié)果見圖8，可以看出，虛警和漏檢主要集中在樹干首末兩端，分析原因如下：樹干與樹冠、草皮交界處的點云可能產(chǎn)生錯誤標注；此部分點云的球域與樹冠、草皮重合度高，不易識別。

圖8 樹干點云識別結(jié)果(δ=0.25 m)Fig. 8 Point cloud recognition result of trunk (δ=0.25 m)

δ=0.25 m時，Boosting與SVM、神經(jīng)網(wǎng)絡的比較結(jié)果見表5。其中，神經(jīng)網(wǎng)絡對類別不平衡最為敏感，為最小化整體錯誤率，將所有樹干樣本都識別為非樹干樣本。SVM能獲得較高的查準率，但查全率低于Boosting，表明有更多的樹干點被誤識別為非樹干點。

表5 不同學習算法的樹干點云識別結(jié)果Table 5 Point cloud recognition results of trunk using different learning algorithms %

3.3 樹干點云分割

以橫軸為測量點幀序號i，縱軸為測量點幀內(nèi)編號j，得到樹干點云標注和識別二值圖像，如圖9所示。為便于觀察，僅截取標注/識別為樹干的點云數(shù)據(jù)。從圖9中可看出，由于車道不平坦且存在減速帶等障礙物，會導致部分幀樹干缺失。

圖9 樹干點云識別二值圖Fig. 9 Binary images of trunk point cloud recognition

為進行樹干分割，首先統(tǒng)計各幀樹干點個數(shù)，如圖10所示，樹干所在幀有明顯的波峰；然后檢測樹干起始幀，將樹干點歸類到最近的樹干起始幀，分割出各個樹干的點云數(shù)據(jù)，如圖11所示。

圖10 各幀樹干點個數(shù)Fig. 10 Number of trunk point cloud in each frame

圖11 樹干點云分割結(jié)果Fig. 11 Segmentation result of trunk point cloud

4 結(jié) 論

1)從點云球域提取深度、高程、維度、密度、強度等14個特征，基于標注數(shù)據(jù)集，采用Boosting算法學習樹干點云檢測器。試驗結(jié)果表明，上述方法能實現(xiàn)行道樹樹干精準識別，濾除路燈、行人、鐵樁等桿狀地物點云。

2)分析不同球域半徑下的特征鑒別力，各個特征的最優(yōu)球域半徑各不相同，鑒別力最強的3個特征是高程方差、強度范圍及強度方差。通過特征融合，樹干點云檢測器能顯著提高單個特征的分類性能。

3)通過樹干起始幀可檢測定位樹干，通過樹干點云聚類可提取出每一根樹干。

后續(xù)研究將改進MLS測量系統(tǒng)，提高點云精度，同時結(jié)合樹冠點云識別方法提取完整行道樹點云。