基于自適應(yīng)差分進化算法擬合圓的樹干胸徑測量方法

胡春華 李萍萍 金成磊 朱 樂

(1.南京林業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院， 南京 210037； 2.南京林業(yè)大學(xué)生物與環(huán)境學(xué)院， 南京 210037)

0 引言

林業(yè)生產(chǎn)中，森林資源調(diào)查與數(shù)據(jù)采集是一個重要環(huán)節(jié)。樹木胸徑是立木測定的最基本因子之一。測量樹木胸徑可以了解樹木生長狀況，為樹木可視化以及整個林區(qū)的生產(chǎn)控制提供重要數(shù)據(jù)。早期測量胸徑采用卡尺或圍尺人工測量[1]，這種測量方式勞動強度大，特別是對于有雜草的森林。隨著電子技術(shù)的不斷發(fā)展，各種測量樹干胸徑方法相繼產(chǎn)生，實現(xiàn)無接觸的樹干胸徑測量[2-16]。有學(xué)者采用數(shù)字圖像方法獲取樹干胸徑，如利用條形碼閱讀器掃描并讀取樹干上帶有樹木胸徑的條形碼帶的數(shù)值[2]，獲得樹干胸徑。王雪峰等[3]采用原野服務(wù)器傳回的圖像，并通過立體的視覺技術(shù)重建了遠(yuǎn)距離樹木的胸徑。王建利等[4]采用光學(xué)三角形測量理論，搭建一個由線性激光傳感器與CMOS圖像傳感器組成的測量系統(tǒng)，通過圖像數(shù)據(jù)與樹干坐標(biāo)信息獲取樹干表面輪廓圖像，最后通過最小二乘擬合橢圓法求取樹干胸徑。除了直接根據(jù)圖像獲取樹干直徑以外，F(xiàn)ORSMAN等[5]采取多視覺圖像重構(gòu)樹干，獲得樹干點云數(shù)據(jù)，采用Gauss-Newton法擬合圓，求取樹干胸徑。黃曉東等[6]采用CCD、傾角傳感器、距離傳感器等設(shè)計了一套自動測量胸徑與樹高的測量儀。近幾年，較多學(xué)者采用地面激光點云數(shù)據(jù)分析樹干參數(shù)[7-11]，也有較多學(xué)者采用二維激光數(shù)據(jù)測量樹干直徑[12-15]。也有學(xué)者融合激光傳感器與機器視覺測量單木樹胸徑[16]。機器視覺比較符合人的思維，但是在自然環(huán)境下，容易受到光照等條件的影響。地面激光雷達技術(shù)點云數(shù)據(jù)處理非常費時，二維激光技術(shù)特別是胸徑位置處采用二維激光技術(shù)測量速度較快，且輕便，容易制成測量儀。

在解決優(yōu)化問題中，差分進化算法(Differential evolution, DE)是一種非常有效的優(yōu)化算法[17]。它是由STORN等[18]于1995年提出的。為解決差分進化算法對參數(shù)敏感的問題，許多研究者提出了參數(shù)自適應(yīng)的差分進化算法。QIN等[19]提出了自適應(yīng)差分進化算法(SaDE)。LIU[20]提出參數(shù)自適應(yīng)差分算法(JADE)優(yōu)化JIT(Just-in-time)與相關(guān)向量機(Relevant vector machine，RVM)。PEUURI等[21]針對DE/rand/1/bin策略算子提出一種自適種群數(shù)的DE算法，找出合適的交叉概率與對應(yīng)的種群數(shù)，變異尺度在[0,1)內(nèi)隨機取，該算法對較復(fù)雜的函數(shù)優(yōu)化效果較好。本文提出一種新的非接觸式測量樹干胸徑方法，采用實驗室自制的基于激光傳感器的履帶移動機器人胸徑測量平臺測量樹干胸徑。針對樹干近似圓形，將傳感器采集的樹干表面參數(shù)用圓進行擬合，擬合出圓的半徑，從而獲得樹干胸徑。針對本研究數(shù)據(jù)，在PEUURI等[21]研究基礎(chǔ)上，加入自適應(yīng)策略與自適應(yīng)控制參數(shù)，實現(xiàn)圓的參數(shù)擬合。

1 實驗材料

本文實驗數(shù)據(jù)采用實驗室自制胸徑測量儀測量獲得，其測量平臺示意圖如圖1所示，以Arduino為微處理器設(shè)計測量控制系統(tǒng)。采用長、寬、高為540、280、110 mm 的履帶小車為載體，將控制器以及傳感器固定在智能小車平臺上。平臺上固定一伸縮式鋁合金撐桿，底部用螺絲螺母連接于小車底盤上，高度可以調(diào)整。撐桿頂端帶有三維多角度旋轉(zhuǎn)云臺，可以滿足多角度的測量需求。激光傳感器(VL53L0X型)與舵機用L型連接件連接，采用透明亞克力塑料板作為激光傳感器的固定板，用螺絲固定在L型金屬連接件上。測量平臺采用紅外接收模塊與紅外遙控器控制小車前進、后退、左右轉(zhuǎn)、停止以及采集數(shù)據(jù)等。測量數(shù)據(jù)存放于控制系統(tǒng)的SD卡內(nèi)。采用超聲波傳感器測量樹干表面到測量平臺的距離。

圖1 測量平臺示意圖Fig.1 Sketch of sample collection platform1.激光傳感器 2.舵機 3.控制線 4.可調(diào)整鋁合金撐桿 5.超聲波傳感器 6.履帶移動機器人平臺 7.電動機 8.控制系統(tǒng) 9.紅外接收模塊 10.紅外遙控器

測量平臺可以通過遙控器實現(xiàn)遠(yuǎn)程控制，控制測量平臺運動與數(shù)據(jù)采集。激光傳感器測量范圍在2 m以內(nèi)。本實驗平臺測量范圍為50～1 000 mm，測量精度為±1.0 mm，舵機轉(zhuǎn)角范圍在0°～180°，環(huán)境工作溫度為-10～45℃。

2 自適應(yīng)差分進化算法擬合圓

2.1 擬合圓方程的建立

由于大部分樹干呈圓臺形，對于同一高度的樹干截面呈圓形，故根據(jù)同一平面上任意3個點能確定圓。為了使擬合圓更精確，每次舵機帶動激光傳感器從0°到180°采集數(shù)據(jù)，對同一個方位采集3次。如圖2所示，每次采集數(shù)據(jù)時傳感器自動調(diào)整到零初始位置。初始位置設(shè)置為極坐標(biāo)起始坐標(biāo)位置，傳感器中心為坐標(biāo)原點，每隔15 ms激光傳感器轉(zhuǎn)動1°，采集一次數(shù)據(jù),數(shù)據(jù)單位均為mm。將采集到的數(shù)據(jù)利用K-means算法聚類，保留目標(biāo)數(shù)據(jù)點。如圖2所示，設(shè)轉(zhuǎn)動角度與初始位置之間的夾角為α。設(shè)擬合圓心坐標(biāo)為(xc,yc)，半徑為R，采集樣本點t時刻的坐標(biāo)(xt,yt)到圓心距離為dt，其中xt=ρtcosα，yt=ρtsinα，ρt為傳感器到樹干表面的距離，為使樣本點盡可能擬合在圓心為(xc,yc)、半徑為R的圓上，則所有樣本點到圓心距離與半徑差的和應(yīng)最小，即優(yōu)化目標(biāo)方程為

(1)

(2)

(3)

式中N——目標(biāo)樣本點數(shù)θ——優(yōu)化參數(shù)

圖2 樣本采集原理示意圖Fig.2 Sample collection principal diagram

圓心坐標(biāo)與半徑均為未知數(shù)，即優(yōu)化參數(shù)θ=(xc,yc,R)。需要擬合優(yōu)化算法對其進行優(yōu)化，基于梯度的Levenberg-Marquardt(LM)優(yōu)化算法、進化優(yōu)化算法、粒子群優(yōu)化算法等均有各自的優(yōu)缺點。本文采用差分進化算法擬合圓。

2.2 自適應(yīng)差分進化算法

差分進化算法是基于群體智能理論的優(yōu)化算法，通過群體內(nèi)個體間的合作與競爭產(chǎn)生的群體智能指導(dǎo)優(yōu)化搜索，主要有變異、交叉與選擇3個過程，而算法過程中的種群初始化、種群規(guī)模、進化策略、變異尺度以及交叉概率等均影響優(yōu)化算法的收斂性與魯棒性。因此本文主要對種群規(guī)模、進化策略、進化算子以及交叉概率在進化過程中自適應(yīng)調(diào)整進行研究，其算法過程如下：

(1)初始化

設(shè)置初始化種群與代數(shù)以及計算過程中的其他參數(shù)初始值。假設(shè)用G=0,1,…,Gmax表示進化代數(shù)，則當(dāng)前代數(shù)下種群中第i個個體表示為

Xi,G=(xi,G,1,xi,G,2,…,xi,G,D)
(i=1,2,…,Np)

(4)

式中D——種群個體維數(shù)

Np——種群個數(shù)

在種群初始化時,初始的種群需覆蓋整個搜索空間RD，初始化為

xi,0,j=xL,j+r(xU,j-xL,j)
(j=1,2,…,D)

(5)

式中xU,j——第j維的上界

xL,j——第j維的下界

r——[0,1]區(qū)間內(nèi)均勻分布的隨機數(shù)

種群個數(shù)必須大于進化向量數(shù)，目前較多的學(xué)者對種群個數(shù)Np進行研究，種群個數(shù)與種群向量幅度有關(guān)，本研究采用PEUURI等[21]提出的種群自適應(yīng)算法

Np=kDln(xU-xL+e)

(6)

式中k——比例系數(shù)

xL——下界xU——上界

本文D為3，初始種群數(shù)Np0=30，k由PEUURI 等[21]提出的自適應(yīng)算法獲取。

(2)差分變異操作

在當(dāng)前代數(shù)中，對于每一個個體矢量Xi,G(稱為目標(biāo)矢量)，使用變異算子生成一個新的個體Vi,G(稱為變異矢量)。目前變異策略有多種形式，經(jīng)過多次實驗可知DE/rand/1/bin策略與DE/current-to-best/1策略對圓擬合效果較好，從當(dāng)前種群中隨機挑選3個個體矢量Xr1,G、Xr2,G與Xr3,G，并選出最優(yōu)Xbest,G，則變異策略為[22]

(7)

(8)

式中Fi——變異尺度因子

ζ——選擇概率

λ——自適應(yīng)因子，取0.5

γ——常數(shù)，取0.01

對差分矢量進行縮放，從而控制搜索步長。較大Fi對全局搜索比較有效，較小的Fi可以加速收斂。可見，選擇合適的Fi非常重要，一般選擇Fi∈(0.4，0.9)，然而對不同的進化代數(shù)Fi不是一個定值，F(xiàn)i隨著進化過程變化而動態(tài)變化。本文選用文獻[23]提出的按照Cauchy分布，其參數(shù)隨進化代數(shù)變化而變化。

(3)交叉操作

差分進化算法采用離散交叉算子:二項式交叉和指數(shù)交叉。交叉算子把通過變異操作得到的變異矢量Vi,G與個體目標(biāo)矢量Xi,G進行離散交叉生成試驗矢量Ui,G，具體的二項式交叉操作為

(9)

式中Cri——第i次進化交叉概率因子

jrand——隨機整數(shù)

一般Cri∈(0，1)，但在Cri∈(0.1，0.8)時更有效。在j維上，若隨機生成數(shù)小于Cri時，試驗矢量繼承變異矢量，反之繼承父代目標(biāo)矢量。一般而言Cri越大則選擇的交叉位也就越多，意味著試驗矢量更傾向于變異矢量。本文Cri隨著進化過程正態(tài)分布，其正態(tài)分布均值隨進化代數(shù)變化而變化[23]。

(4)選擇操作

差分進化算法通過變異操作和交叉操作產(chǎn)生后代群體之后，采用一對一的貪婪篩選算子將子個體與相應(yīng)的父個體進行比較，較優(yōu)者保存到下一代，選擇操作為

(10)

(5)優(yōu)化結(jié)束條件判斷

若不滿足最大迭代次數(shù)1 000，繼續(xù)進化過程，采用式(6)更新種群數(shù)，進入變異、交叉與選擇過程。否則結(jié)束進化優(yōu)化過程，輸出最優(yōu)值。

3 實驗與分析

圖3 樣本采集場景Fig.3 Sample collection scene

在林分測定中，胸徑(DBH)指樹干距離地面以上1.3 m處樹干的直徑。本次測量平臺為履帶機器人平臺，樣本采集場景如圖3所示。為驗證機器人行走穩(wěn)定性，在校園與人工林地隨機選擇大小不同的40棵樹進行測量，對每一棵樹進行標(biāo)記。為驗證本文測量系統(tǒng)測量胸徑的準(zhǔn)確性，首先對標(biāo)記好的樹采用圍尺人工測量出胸徑值作為樹干胸徑實際值，其數(shù)據(jù)統(tǒng)計分析表如表1所示。

表1 樣本胸徑統(tǒng)計Tab.1 DBH statistics of measured sample mm

為驗證系統(tǒng)測量的穩(wěn)定性，分別在陰天的早晨、中午、下午與晴天的早晨、中午、下午進行了6次數(shù)據(jù)測量，每次對每個場景(校園與人工林地)有標(biāo)記的40棵樹以相同順序進行測量記錄數(shù)據(jù)，每次測量3個方位，求取平均值作為測量值。實驗數(shù)據(jù)處理器為Intel i5-6500 CPU 3.2 GHz，內(nèi)存8.0 GB，數(shù)據(jù)處理軟件為Matlab 2016b。

激光傳感器采集的數(shù)據(jù)由樹干表面反射到傳感器的時間與速度計算出來，由于激光傳感器存在一定的發(fā)散性，本研究首先將采集的數(shù)據(jù)經(jīng)過發(fā)散角校正，然后計算樹干表面點的坐標(biāo)值。分別將不同時間段與不同方位采集的數(shù)據(jù)采用K-means算法分割出目標(biāo)數(shù)據(jù)。采用文獻[14]提出的弧長法矯正激光傳感器的發(fā)散角，擬合出發(fā)散角二次方程，每次計算時采用角度補償?shù)姆绞綔p少誤差，擬合R2為0.907，均方根誤差(RMSE)為0.626°,其方程為

Fρ=-0.000 592ρ2+0.064 28ρ-11.1

(11)

式中ρ——激光傳感器中心到樹干表面點距離，mm

Fρ——補償角，(°)

補償角隨著距離的增加而增大，因此每次計算樹干表面點坐標(biāo)值之前，將對應(yīng)的角度減去補償角即為補償后角度。

圖4 二維坐標(biāo)點擬合圓Fig.4 Two dimensional coordinate point fitting circle

計算出補償后數(shù)據(jù)對應(yīng)的坐標(biāo)值，采用2.2節(jié)的自適應(yīng)差分進化算法擬合圓。圖4是經(jīng)過處理后的數(shù)據(jù)點擬合圓效果圖，顯示大部分?jǐn)?shù)據(jù)點比較集中在圓弧上，極少部分?jǐn)?shù)據(jù)有一定的偏差，由于樹干表面不是絕對的光滑，因此表面的部分?jǐn)?shù)據(jù)不在同一圓弧上。但是對于同一個方向的數(shù)據(jù)點，大部分在同一個圓弧上。分別對3個方向的數(shù)據(jù)進行分割與擬合，擬合出最優(yōu)半徑，計算3個方向的平均值即為本文所求樹干胸徑。

本次實驗分別對基于梯度下降法Levenberg-Marquardt(LM)優(yōu)化算法、非梯度算法粒子群方法(PSO)以及本文提出的自適應(yīng)差分進化算法(ADE)進行了比較分析。對同一組數(shù)據(jù)進行比較，其結(jié)果如表2所示，基于梯度下降方法的LM算法收斂較慢，運行時間較長，PSO算法與ADE算法收斂速度快，而ADE算法最快。擬合圓的直徑較相近，因此均方根誤差RMSE相差較小。從實驗結(jié)果可以看出，ADE算法較優(yōu)。

表2 不同算法擬合結(jié)果比較Tab.2 Comparison of different algorithms

將Hough變換算法與ADE算法進行比較。對同一棵樹的6次測量數(shù)據(jù)進行了統(tǒng)計分析，測量誤差在±5 mm之間，求取平均值作為測量值。將實驗測量值分別與實際值進行對比分析，圖5與圖6分別給出了校園內(nèi)與人工林地不同直徑的40棵樹胸徑測量值與實際值之間的關(guān)系。由圖5與圖6可知，本文算法數(shù)據(jù)點較集中。表3給出了采用本文算法與Hough變換算法擬合的測量值與實際值的直線擬合結(jié)果。本文算法對校園內(nèi)數(shù)據(jù)擬合直線斜率為0.993，偏離值為3.782，R2為0.989，RMSE為4.996 mm。而Hough變換算法擬合的直線斜率為1.038，偏離值為-7.981，R2為0.947，RMSE為12.18 mm。對于人工林地，本文擬合算法的RMSE為4.500 mm，Hough變換算法的RMSE為11.97 mm。由實驗分析可知，本文測量胸徑方法受樣地場景影響較小。雖然本文算法擬合圓效果較好，但是實際值與測量值之間存在一定的誤差。引起誤差的因素較多，如樹干實際測量的誤差、傳感器誤差以及傳感器發(fā)散角補償誤差等。在以后的研究工作中，應(yīng)盡量減少測量誤差，提出更有效的發(fā)散角補償算法，使測量值更逼近于真實值。

4 結(jié)論

(1)采用實驗室自制的基于激光傳感器的胸徑測量平臺對校園內(nèi)與人工林地不同直徑的40棵樹進行多次測量，每次測量對同一棵樹采集3個方向的數(shù)據(jù)，每個方向采集3次，獲得不同方位的測量數(shù)據(jù)，并將數(shù)據(jù)保存于SD卡。

(2)對采集的數(shù)據(jù)采用K-means進行聚類，分

圖5 校園內(nèi)樹干胸徑測量值與實際值關(guān)系Fig.5 Relationship between actual DBH and measured DBH in campus

圖6 人工林地樹干胸徑測量值與實際值關(guān)系Fig.6 Relationship between actual DBH and measured DBH in artificial forest

擬合方法擬合方程RMSE/mmR2ADE算法校園內(nèi)y=0.993x+3.7824.9960.989人工林地y=0.979x+4.9754.5000.993Hough變換算法校園內(nèi)y=1.038x-7.98112.180.947人工林地y=0.973x+8.51211.970.955

割出背景與目標(biāo)。采用弧長法計算出補償角與激光傳感器到樹干表面點距離的擬合公式。將采集到的數(shù)據(jù)角度分別減去補償角度，對分割的目標(biāo)樣本數(shù)據(jù)進行補償。對補償后的數(shù)據(jù)，以激光傳感器中心為坐標(biāo)原點，計算出樹干表面點的橫縱坐標(biāo)。

(3)根據(jù)每棵樹的橫縱坐標(biāo)，分別采用基于梯度的LM優(yōu)化算法、粒子群(PSO)優(yōu)化算法、本文提出的自適應(yīng)差分進化算法以及Hough變換算法擬合圓測量出樹干胸徑，并對測量值與實際值進行了分析與比較。本文算法擬合時間最短，為1.41 s，對校園內(nèi)和人工林測量結(jié)果與實際值比較分析，RMSE分別為4.996 mm與4.500 mm。實驗結(jié)果表明，本文提出的自適應(yīng)差分進化算法收斂快，且比Hough變換擬合圓方法更逼近真實值。