基于改進Floodfill算法的田壟視覺導航系統*

謝仕爍，黃偉鋒，2，朱立學，楊塵宇，張世昂，付根平，2

(1.仲愷農業工程學院自動化學院，廣州市，510225；2.仲愷農業工程學院現代農業工程創新研究院，廣州市，510225；3.廣東省現代精準農業智能化裝備技術研發中心，廣州市，510225；4.仲愷農業工程學院機電工程學院，廣州市，510225)

0 引言

近年來，我國大部分農作物產量保持增長狀態[1-2]，但生產成本增加過快等因素仍然制約著我國農戶的利潤增長[3]。研究指出，農業自動化對提高農產品的產量和減少勞動力的制約具有一定的積極作用[4]，且機器人自主導航技術已有一定成果[5-8]，因此，農業機器人具備一定的發展前景和意義。

視覺處理技術和衛星定位技術為農業機器人自主作業能力提供了可能[9-12]。導航技術中，衛星定位導航可以提供一定的導航指引，但難以根據實際道路情況等因素進行導航，難以對實際環境做出反應；視覺導航易受光照等環境干擾影響，但其外部信息感知量豐富，因此該方法受到了許多研究者的青睞。

在圖像分割方面，高國琴等[13]提出基于K-means算法的溫室路徑分割方法；田巍等[14]提出基于HSV閾值法的皮膚對象分割方法；Bakker等[15]提出基于2G-R-B方法的作物圖像分割方法；Long等[16]使用FCN網絡實現了多個對象的分割方法。以上方法均具備一定的分割能力，但在計算負擔與分割結果的綜合表現上效果欠佳，難以兼顧強分割性和算法簡易性。

在對導航計算上，吳剛等[17]提出基于hough法的路徑擬合方法，實現了小麥田間的路徑計算；李亭等[18]使用掃描法進行路徑計算實現了智能車的自主導航；王新忠等[19]使用最小二乘法實現番茄壟間的導航；hough擬合法和掃描法均能產生一定效果，但并無法區分道路類型，其導航效果易受道路筆直程度影響，且機器人無法單獨依靠視覺系統針對特定路況執行相應任務。

綜上所述，許多學者對圖像分割及路徑導航計算進行一定的研究試驗，取得了一些成果，但機器人導航領域仍然存在一定問題。本文針對Floodfill算法進行路徑分割改良，通過對十字法和掃描法進行結合改良，對不同路況使用相應方法進行計算，構建了基于改進Floodfill算法的田壟視覺導航系統，實現機器人視覺導航功能。

1 材料與方法

1.1 算法流程

算法流程如圖1所示，流程分為三個部分：第一部分，從攝像頭獲取壟間圖像并對圖像進行預處理操作；第二部分，使用Floodfill算法分割路徑圖像，將路徑圖像輸入十字法進行路徑情況分類；第三部分，在已知路徑情況的基礎上應用相應算法進行導航信息計算。

圖1 導航算法流程圖

1.2 圖像預處理

在圖像處理領域中，常用的顏色空間有RGB顏色空間(Red紅色，Green綠色，Blue藍色)、HSV顏色空間(Hue色相，Satuation飽和度，Value明度)。其中，RGB顏色空間采用R(紅)、G(綠)、B(藍)三個通道來表達顏色，HSV顏色空間采用H(色相)、S(飽和度)、V(明度)來表達顏色，兩種顏色空間之間可相互轉換。

Floodfill算法需要進行顏色相似程度判斷，具有尋找相似顏色的需求。在HSV色彩空間中，若兩種顏色相似，其色相也會相近。因此，通過H(色相)參數尋找相似顏色的方法較為簡單且無需大量運算，受光照等外部干擾的影響相對較小，本方法使用HSV顏色空間進行計算。

為了獲得更加精確的計算結果，在計算前對圖像進行高斯模糊處理，對圖像進行濾波。

1.3 路徑分割

1.3.1 改進Floodfill算法

本文使用Floodfill算法分割道路信息，為后續導航計算算法提供數據。Floodfill算法又稱漫水填充算法，該算法的計算方法與水流動的規律相似。首先輸入種子點(Seed Point)的坐標，將種子點作為“水源”，向四周符合漫延條件的位置漫延。漫延條件為：該位置與本位置的數值的相似程度符合要求。漫延方式有4方向漫延法和8方向漫延法兩種，4方向漫延法規定水流只能向當前位置的“上、下、左、右”4個方向流動，而8方向漫延法則在4方向漫延法的基礎上增加了“左上、右上、左下、右下”四個方向。圖2為同一種子點下，不同漫延規則的計算結果。圖中，黑格為不符合漫延條件的像素，灰格為被漫延區域，白格為未漫延區域。經測試，8方向漫延法具有較好的效果，故采用8方向漫延法。

(a)4方向漫延法

機器人正常行駛過程中，路徑圖像的中下區域包含道路信息的可能性較高。基于該先驗知識，可以使用固定點法進行道路分割：選取圖像底部中點作為種子點進行Floodfill算法的計算，分割結果如圖3(b)所示。

(a)路徑圖像

試驗發現，固定點法選取種子點的分割效果尚好，但若固定點處存在塑料袋等干擾物體，路徑信息將被錯誤分割，如圖4(b)所示。針對該問題，本文使用點迭代法進行改進。

(a)測試圖片

點迭代法通過評價的方式選取合適的種子點，運行流程如圖5所示。

圖5 點迭代法運行流程

第一步，選取圖像底部中點為準種子點的起始點。

第二步，使用準種子點進行Floodfill算法運算。

第三步，對本次計算結果進行評價，評價合格則進入輸出分割結果，不合格則向上偏移準種子點并回到第二步進行下一次迭代。

圖4(c)為使用點迭代法的分割結果。試驗驗證，點迭代法具備更好的魯棒性，更適合在實際路況中使用。

1.3.2 濾波處理

道路信息雖然已經被計算出來，但仍包含一定噪聲，噪聲干擾將對后續的導航信息計算造成一定負面影響。針對該問題，本文引入腐蝕算法與膨脹算法對路徑分割結果進行進一步濾波。

腐蝕算法與膨脹算法采用矩陣對圖像進行運算，對圖像進行形態學運算。腐蝕算法作用為收縮圖像，其效果如圖6(b)所示；膨脹算法作用為擴大圖像，其效果如圖6(c)所示。若使用相同矩陣在膨脹運算后進行腐蝕運算，可以在不影響原圖像大小的情況下濾去原圖像的“空洞”，濾波結果如圖7(b)所示。

(a)原圖像

(a)原圖像

1.4 分類導航計算

機器人在田壟中將遇到三種情況：方向大致準確、嚴重偏向和駛出田壟，使用同一算法對多種路況進行計算較為困難。針對該問題，本文使用十字法對3種路況進行分類，針對不同路況采用不同算法。十字法用于嚴重偏向及駛出田壟2種情況的分類和方向矯正，掃描法用于方向大致準確時的方向微矯正。

1.4.1 十字法路徑分類

十字法示意圖如圖8(a)所示，其算法計算過程如下。

1)以點Sp為起點向上尋找跳變點。若存在跳變點則將該點設為A點，否則將頂端設為A點。

2)設A點下方一定距離的點為B點。

3)尋找B點兩側的跳變點，將出現以下情況。

① 若本步驟無跳變點或跳變點均處于圖像邊界附近：判定當前路況為“駛出田壟”，如圖8(b)所示。

(a)算法示意圖

② 若本步驟存在跳變點：a)若第1步存在跳變點：將距離B點較近的跳變點設為C點，判定當前路況為“嚴重偏向”，進入下一步的導航計算。b)若第1步沒有跳變點：判定當前路況為“方向大致準確”，使用掃描法進行導航計算。

十字法分類后，若路況不為“駛出田壟”，則進入下一步進行導航計算。

1.4.2 十字法導航計算

十字法對“嚴重偏向”的路況進行導航計算。以點Sp作為原點、點Sp向上為x軸的方向、點Sp向左為y軸方向，構建新的坐標軸空間，為使效果更加直觀，將原示意圖順時針旋轉90°，如圖9所示，其偏移幅度

圖9 新坐標空間示意圖

(1)

其中，Kp>0表示道路向左，Kp<0表示道路向右。

圖8(a)與圖10中，A點B點和C點均處在同一位置，但道路邊緣彎曲度不同。道路偏移程度Kp相同的情況下，彎曲程度更高的路徑需要機器人更快地調整方向，避免駛出道路損壞農作物。基于以上分析，加入對彎曲邊緣的判斷對于增強機器人導航的可靠性具有一定意義。針對該問題，本文在彎曲邊緣的道路處引入曲率計算和權值參數參與計算。取曲線起始點E，若點A、C、E不在同一直線上，使用兩點間距離公式分別計算線段a，c，e的長度。

圖10 十字法曲率計算示意圖

平均曲率

(2)

(3)

小車與彎道的距離影響因子

(4)

由式(1)～式(4)可計算出道路偏移值

K=W1×Kp+W2×Kcir+W3×Kd

(5)

其中，W1，W2，W3為作用系數。

1.4.3 掃描法導航計算

掃描法對“嚴重偏向”的路況進行導航計算。掃描法使用逐行遍歷的方式，尋找每一行位于中點兩側的跳變點，記錄兩個跳變點之間的中點。本方法在與十字法相同的坐標空間內采用一元線性回歸計算的方法進行計算，設中點坐標為(xi，xi)，可得

(6)

道路信息的回歸方程只表示道路走向，因此機器人處于非道路中央位置時需要使機器人向道路中心靠近，因此引入矯正權值Ke控制矯正強度，偏移值K的計算公式

K=Lb+Ke×La

(7)

當Lb≠0，即機器人處于非道路中央位置時，算法通過Lb對偏移值K的計算結果進行干涉，實現機器人向道路中心靠攏的效果。

2 試驗驗證

2.1 試驗平臺

硬件平臺為香蕉采摘履帶機器人，計算平臺為搭載1.4 GHz主頻的Cortex-A53處理器以及1 GB運行內存的Raspberry Pi 3B+，計算平臺搭載操作系統為基于Linux的Raspbian。計算平臺使用單目攝像頭獲取實時道路圖像，通過STM32F103RC單片機對Safari-880T加強版履帶機器人進行移動控制。部分功能借助OpenCV[20](Intel?開源計算機視覺庫)輔助實現。

2.2 試驗方法

路徑分割性能測試：取50張多個時段的果林田壟照片，將照片轉換為640像素×480像素的分辨率，使用改良Floodfill法、K-means法、點閾值法三種方法分別進行道路分割，統計計算時間和正確提取路徑信息的圖片數量。統計三種方法的準確率及計算時間，測試改良Floodfill法在田壟圖像路徑分割方面的可行性及優缺點。

導航算法測試：搭建“U”形路段作為測試路段，如圖11所示，機器人以與道路中線成40°夾角的初始姿態進入路段并使用本方法進行自主導航，并在駛出測試路段時停止導航。機器人履帶底盤寬0.735 m，測試路段寬約1 m，其中直道總長度約6.3 m，彎道長度約4.7 m，直道用于測試田壟中的微矯正功能；彎道用于模擬“嚴重偏向”的情況，測試大偏移矯正能力；采用路段出口模擬駛出田壟的情況，測試分類狀況。在測試路段中設置6個檢查點，在圖中分別標記為點1、點2、點3、點4、點5和點6，同一側的檢查點之間的間隔為1 m，其中檢查點1用于測量人為制造的偏移量。本試驗通過偏移值變化情況測試導航算法的穩定性及導航性能。

圖11 測試環境示意圖

3 試驗結果及分析

3.1 路徑分割性能測試

本試驗正確分割的判斷標準為：算法分割區域與實際道路區域的相交面積達到實際道路區域面積的70%以上且包含較少非道路信息。為保證試驗的準確性，本試驗的測試數據集選取不同光照情況下不同位置的田壟道路圖片，使用樹莓派3B+進行計算，試驗結果如表1所示。測試數據集中部分圖像含有較嚴重的光照干擾，測試環境較為嚴格，因此會出現整體準確率偏低的情況。

表1 路徑分割算法測試結果

試驗結果中，K-means算法的準確率達到了58%，但計算時間長；HSV閾值算法的計算耗時最短，但僅有26%的準確率；改進Floodfill算法平均計算時間為120.18 ms，達到了76%的準確率。相對于K-means算法，本算法節約了92.2%的計算時間；相對于HSV算法，本算法增加了166.1%的計算時間，但準確率提高較大。試驗結果表明，改進Floodfill算法具備一定優點，其計算時間與準確率符合需求。

圖12為部分分割結果，其中K-means算法可分離出道路圖像，但包含較多干擾信息；HSV閾值法可大致將道路分割出來，但分割結果包含了與道路顏色相近的植物；改良Floodfill算法的分割結果包含干擾信息較少，對后續導航計算的精度保證具有重要的意義。本文使用的改進Floodfill算法具備一定的優點。

(a)測試圖片

3.2 導航性能測試

在機器人履帶底盤頭部的中央處安裝一個沾濕的刷子，利用刷子記錄下移動路徑。導航結束后，在檢查點處測量小車的偏移程度。開始測試時，機器人以與道路中心線成40°夾角的初始姿態進入測試場地，試驗中的導航情況如圖13所示。

(a)直道微矯正

試驗結果如圖14所示，本方法在僅使用比例控制的情況下仍具備一定的收斂能力，誤差變化趨勢相對穩定。在加入起始干擾的情況下可迅速調整姿態，矯正后的偏移值保持在6 cm以內。檢查點3、檢查點4分布在彎道出入口附近，由于機器人對入彎姿態的調整會導致行駛路線出現一定偏移，因此偏移值波動為正常現象。多次試驗中，均無出現與物體碰撞的情況，機器人駛出測試路段時均可正確判斷“駛出田壟”，驗證了算法的可行性。

圖14 自主導航試驗結果

4 結論

針對果林環境下的自主導航機器人，為解決的田壟視覺導航計算復雜導致實時性弱的問題，本文提出了改進Floodfill算法結合分類導航的方法進行導航計算。該方法先對圖像進行預處理，然后使用改進Floodfill算法進行道路分割并對分割結果進行濾波處理。得到路徑分割結果后，使用十字法對路徑情況進行分類，再根據路徑情況使用十字法或掃描法進行導航計算。

對路徑分割性能和導航算法的試驗及分析表明：

1)改進Floodfill算法具有計算速度快且準確率良好的特點。在小型低算力平臺中，單次分割耗時約120 ms(不包含導航計算)且達到了76%的準確率，具有良好的計算實時性和準確率，相比其他方法具有一定優勢，改善了視覺導航計算量大以及室外機器人計算平臺體積大且成本高昂的問題。

2)分類導航的方法具有一定的可行性，且具備一定的導航質量。

3)道路偏移值保持在6 cm內，改善了低算力平臺在田壟視覺導航中實時性差及導航效果弱的問題。

本方法是對農業機器人視覺導航方法的一種探索和嘗試。此外，分類導航的方法可搭配于其他路徑分割算法上，具備一定可移植性，有利于提升開發效率，對視覺導航方法的研究探索和農業機器人自主作業相關技術的發展具有一定的意義。