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

胡春華 李萍萍 金成磊 朱 樂

(1.南京林業大學信息科學技術學院， 南京 210037； 2.南京林業大學生物與環境學院， 南京 210037)

0 引言

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

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

1 實驗材料

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

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

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

2 自適應差分進化算法擬合圓

2.1 擬合圓方程的建立

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

(1)

(2)

(3)

式中N——目標樣本點數θ——優化參數

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

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

2.2 自適應差分進化算法

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

(1)初始化

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

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

(4)

式中D——種群個體維數

Np——種群個數

在種群初始化時,初始的種群需覆蓋整個搜索空間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]區間內均勻分布的隨機數

種群個數必須大于進化向量數，目前較多的學者對種群個數Np進行研究，種群個數與種群向量幅度有關，本研究采用PEUURI等[21]提出的種群自適應算法

Np=kDln(xU-xL+e)

(6)

式中k——比例系數

xL——下界xU——上界

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

(2)差分變異操作

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

(7)

(8)

式中Fi——變異尺度因子

ζ——選擇概率

λ——自適應因子，取0.5

γ——常數，取0.01

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

(3)交叉操作

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

(9)

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

jrand——隨機整數

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

(4)選擇操作

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

(10)

(5)優化結束條件判斷

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

3 實驗與分析

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

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

表1 樣本胸徑統計Tab.1 DBH statistics of measured sample mm

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

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

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

(11)

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

Fρ——補償角，(°)

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

圖4 二維坐標點擬合圓Fig.4 Two dimensional coordinate point fitting circle

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

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

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

將Hough變換算法與ADE算法進行比較。對同一棵樹的6次測量數據進行了統計分析，測量誤差在±5 mm之間，求取平均值作為測量值。將實驗測量值分別與實際值進行對比分析，圖5與圖6分別給出了校園內與人工林地不同直徑的40棵樹胸徑測量值與實際值之間的關系。由圖5與圖6可知，本文算法數據點較集中。表3給出了采用本文算法與Hough變換算法擬合的測量值與實際值的直線擬合結果。本文算法對校園內數據擬合直線斜率為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。由實驗分析可知，本文測量胸徑方法受樣地場景影響較小。雖然本文算法擬合圓效果較好，但是實際值與測量值之間存在一定的誤差。引起誤差的因素較多，如樹干實際測量的誤差、傳感器誤差以及傳感器發散角補償誤差等。在以后的研究工作中，應盡量減少測量誤差，提出更有效的發散角補償算法，使測量值更逼近于真實值。

4 結論

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

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

圖5 校園內樹干胸徑測量值與實際值關系Fig.5 Relationship between actual DBH and measured DBH in campus

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

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

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

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