王亮 趙德安 劉曉洋

摘 要：為了優(yōu)化蘋果采摘機(jī)器人采摘路徑，在獲得蘋果樹場(chǎng)景三維位置信息的基礎(chǔ)上，提出一種具有多種地形損耗的A*算法。結(jié)合ToF（Time-of-Flight）深度相機(jī)和Hu不變矩獲取蘋果和不同障礙物的三維位置信息，建立存在果實(shí)和多種障礙物的二維地圖。在二維地圖上，利用具有不同地形損耗函數(shù)的A*算法進(jìn)行仿真實(shí)驗(yàn)。改進(jìn)后的A*算法將障礙物分為可通過(guò)的障礙物（樹葉）和不可通過(guò)的障礙物（樹枝），且障礙物存在位置處的自帶移動(dòng)耗費(fèi)向周圍以線性遞減，避免了基本的A*算法中只具有單種障礙物問(wèn)題，從而增加了不同種類障礙物對(duì)路徑選擇的影響程度，優(yōu)化了路徑質(zhì)量。對(duì)比實(shí)驗(yàn)表明：改進(jìn)后的算法提高了對(duì)于復(fù)雜地圖的處理能力，產(chǎn)生的路徑長(zhǎng)度更短，轉(zhuǎn)折次數(shù)更少。

關(guān)鍵詞：蘋果采摘;ToF;Hu不變矩;A*算法;路徑規(guī)劃

DOI：10. 11907/rjdk. 182257

中圖分類號(hào)：TP301文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2019）003-0001-06

0 引言

中國(guó)是世界上最大的蘋果生產(chǎn)國(guó)。隨著我國(guó)城鎮(zhèn)化步伐的加快，大量青年進(jìn)城務(wù)工，導(dǎo)致農(nóng)村勞動(dòng)力短缺，不能滿足蘋果采摘對(duì)勞動(dòng)力的需求，蘋果人工采摘還存在作業(yè)量大和效率低下問(wèn)題[1]，農(nóng)業(yè)生產(chǎn)方式向自動(dòng)化智能化轉(zhuǎn)變迫在眉睫。

使用機(jī)器人采摘果實(shí)最先由Schertz & Brown[2]在20世紀(jì)60年代提出，之后采摘機(jī)器人經(jīng)歷了50多年的發(fā)展，從最早期的機(jī)器人采摘果實(shí)需要數(shù)十秒到如今采摘果實(shí)在10秒以內(nèi)。國(guó)內(nèi)采摘機(jī)器人發(fā)展起步較晚，采摘果實(shí)的快速性與實(shí)時(shí)性不能滿足要求。為提高機(jī)器人采摘蘋果效率，必須解決蘋果圖像處理和采摘路徑規(guī)劃兩大難題。江蘇大學(xué)2011年研制的蘋果采摘機(jī)器人，采用單目USB 攝像頭，圖像處理程序用C++編寫，圖像處理算法基于蘋果在RGB空間的顏色特征，平均采摘一個(gè)蘋果的時(shí)間為15s[3-4]。由于沒有使用路徑規(guī)劃算法，導(dǎo)致采摘路徑出現(xiàn)重疊，采摘時(shí)間過(guò)長(zhǎng)，不能勝任野外采摘工作。

相關(guān)研究主要有：呂繼東等[5]首先對(duì)蘋果果實(shí)進(jìn)行OTSU動(dòng)態(tài)閾值分割，之后利用采集圖像之間的信息關(guān)聯(lián)性縮小目標(biāo)果實(shí)處理區(qū)域，并采用快速去均值歸一化積相關(guān)算法跟蹤識(shí)別目標(biāo)果實(shí)。司永勝等[6]先使用紅綠色差法分割出蘋果并提取圓心和半徑，通過(guò)建立基于面積特征與極線幾何相結(jié)合的匹配策略，實(shí)現(xiàn)雙目視覺下的果實(shí)匹配與定位。以上兩個(gè)研究?jī)H對(duì)普通的RGB圖像進(jìn)行算法處理，復(fù)雜度較高。苑嚴(yán)偉、張小超等[7]將蘋果采摘的路徑規(guī)劃問(wèn)題轉(zhuǎn)化為三維旅行商問(wèn)題進(jìn)行求解，結(jié)合雙目攝像頭獲得的蘋果位置信息提出了改進(jìn)的蟻群算法，解決了局部收斂問(wèn)題，提高了采摘效率。但該算法沒有考慮到實(shí)際采摘情況下的障礙物問(wèn)題，對(duì)于現(xiàn)實(shí)情況下果樹生長(zhǎng)的復(fù)雜環(huán)境適用性不是很高。比利時(shí)學(xué)者 Tien Thanh Nguyen利用 Kinect 相機(jī)提供的顏色信息和三維形狀信息，基于點(diǎn)云PCL（PointCloud Library），蘋果識(shí)別率高，定位精度在10mm以下，同步識(shí)別20個(gè)蘋果的圖像處理時(shí)間在1s以內(nèi)[8]。該研究利用深度相機(jī)識(shí)別和定位蘋果，速度很快，但沒有從采摘路徑規(guī)劃方面提高蘋果采摘效率。

針對(duì)以上研究存在的問(wèn)題，本文選擇ToF深度相機(jī)作為采摘攝像頭，快速獲取整個(gè)蘋果樹的多種類型圖像，從三維點(diǎn)云圖像和深度圖像中準(zhǔn)確定位多個(gè)成熟蘋果的三維位置，并且篩選蘋果所處范圍內(nèi)的障礙物，將三維視圖轉(zhuǎn)化為二維圖像，形成存在多種障礙物的二維地圖。根據(jù)蘋果采摘的實(shí)際情況，改進(jìn)A*算法中的地形移動(dòng)損耗，在具有多種障礙物的二維地圖上進(jìn)行路徑規(guī)劃。編寫路徑規(guī)劃的算法代碼，對(duì)改進(jìn)后的A*算法在路徑規(guī)劃中的效果進(jìn)行驗(yàn)證，從而在有限時(shí)間內(nèi)達(dá)到路徑距離最短、規(guī)劃速度最快的采摘要求。本文從圖像處理和采摘路徑規(guī)劃兩個(gè)方面提高了蘋果采摘效率。

1 三維信息獲取

1.1 Balser ToF工作原理

Balser ToF（Time-of-Flight）相機(jī)是德國(guó)Balser公司生產(chǎn)的一種工業(yè)3D相機(jī)。相機(jī)自帶的傳感器發(fā)出經(jīng)調(diào)制的近紅外光，遇物體后反射，傳感器通過(guò)計(jì)算光線發(fā)射和反射時(shí)間差或相位差計(jì)算被拍攝景物的距離，產(chǎn)生深度信息。再結(jié)合傳統(tǒng)的相機(jī)拍攝，就能將物體的三維輪廓以不同顏色代表不同距離的地形圖方式呈現(xiàn)。原理如圖1所示，實(shí)物如圖2所示。

本文先利用ToF相機(jī)對(duì)蘋果樹整體場(chǎng)景進(jìn)行采集，同時(shí)獲得整個(gè)場(chǎng)景的強(qiáng)度圖、置信圖、深度圖、三維點(diǎn)云圖像。強(qiáng)度圖代表整個(gè)場(chǎng)景接收到的反射光強(qiáng)弱，如圖3（a）所示。置信圖代表整個(gè)場(chǎng)景的每一個(gè)點(diǎn)深度的可信度，如圖3（b）所示。圖中點(diǎn)的亮度越大，則該點(diǎn)的深度距離準(zhǔn)確度越高。深度圖表示了場(chǎng)景中的深度信息，如圖3（c）所示，越靠近相機(jī)，顏色顯示越深，若顯示黑色，表示該點(diǎn)距離不可測(cè)。三維點(diǎn)云圖像是場(chǎng)景中點(diǎn)云數(shù)據(jù)的集合，如圖3（d）所示。

1.2 蘋果形狀特征獲取

由于Basler的ToF相機(jī)獲得圖像中并沒有RGB圖像，通過(guò)在強(qiáng)度圖和三維圖中分析蘋果和障礙物可以發(fā)現(xiàn)，蘋果和障礙物在圖像中顏色上是相近的，因此利用顏色特征確定蘋果位置是不準(zhǔn)確的，但是蘋果反射的光強(qiáng)和障礙物樹枝樹葉返回的光強(qiáng)不一樣，導(dǎo)致在圖像中有著明顯區(qū)別。因此本文先對(duì)場(chǎng)景圖像在像素方面進(jìn)行預(yù)處理，RGB值大于150設(shè)置為白色，小于150設(shè)置為黑色（如圖4所示），然后在預(yù)處理的圖像上對(duì)蘋果形狀特征進(jìn)行提取。場(chǎng)景的形狀特征提取采用平移不變形、旋轉(zhuǎn)不變性、縮放不變性的Hu不變矩方法[8]。

1.2.1 Hu不變矩提取蘋果圖像特征

矩特性主要表征了圖像區(qū)域的幾何特征，又稱為幾何矩。因?yàn)槠浯嬖谛D(zhuǎn)、平移等多個(gè)不變特征，所以又稱其為不變矩。在圖像處置中，不變矩能夠描述圖像的整體性質(zhì)，在邊緣提取、圖像匹配及目標(biāo)識(shí)別中得到廣泛應(yīng)用[9]。

Hu不變矩概念由Hu[10]提出，闡述了Hu不變矩中連續(xù)函數(shù)矩的定義和矩的基本性質(zhì)，并給出了由二階和三階歸一化中心矩的非線性組合構(gòu)成的7個(gè)量值，并證明了這些矩具有平移、比例、旋轉(zhuǎn)不變性，后被人們稱為Hu不變矩。

Hu不變矩對(duì)分割后的圖像中的目標(biāo)連通域進(jìn)行形狀特征提取。設(shè)圖像中的目標(biāo)連通域上的某一像素點(diǎn)位置為[（x，y）]，則整個(gè)連通域的（[p+q]）階矩為：

在對(duì)圖片中物體的實(shí)際識(shí)別過(guò)程中發(fā)現(xiàn)，只有一階矩到四階矩保持較好，其它幾個(gè)不變矩帶來(lái)的誤差較大，所以只選擇前4個(gè)矩進(jìn)行計(jì)算。表1是任意選取的3幅蘋果目標(biāo)區(qū)域和從圖中截取的葉子的不變矩特征值。從表中可以看出不變矩值整體呈現(xiàn)遞減趨勢(shì)，蘋果和葉子的不變矩值差異明顯，即不同目標(biāo)區(qū)域的Hu不變矩值是不同的，因此采用不變矩值獲取目標(biāo)物的形狀特征可行。

因?yàn)樘O果本身紋理特征并不復(fù)雜，并且形狀特征和周邊障礙物區(qū)別較大，所以利用Hu不變矩識(shí)別蘋果的輪廓速度很快，效果很好。識(shí)別結(jié)果如圖5所示。

1.3 果實(shí)與障礙物三維位置獲取

1.3.1 果實(shí)三維位置獲取

在確定了蘋果在圖像中的二維位置后，再利用Tof相機(jī)的深度圖獲取蘋果的深度信息。為了得到蘋果的準(zhǔn)確位置，在深度圖上對(duì)應(yīng)蘋果區(qū)域以蘋果為中心隨機(jī)選取5個(gè)點(diǎn)作為預(yù)選的蘋果三維數(shù)據(jù)，然后對(duì)這5個(gè)點(diǎn)求平均值，得到蘋果中心點(diǎn)的最終三維位置。

在Tof顯示圖像中，圖像中心點(diǎn)的二維位置是（0，0），x軸坐標(biāo)值隨著方向向右增大，y軸坐標(biāo)值隨著方向向下增大。表2展示從左到右蘋果的三維位置信息（蘋果3：從左往右時(shí)，圖像上偏下部的蘋果。蘋果4：從左往右時(shí)，圖像上偏上部的蘋果，坐標(biāo)單位為dm）。

1.3.2 附近障礙物三維位置獲取

以上節(jié)得到的蘋果位置作為中心，選取邊長(zhǎng)13cm的正方形作為蘋果和障礙物共存的區(qū)域位置，選取邊長(zhǎng)8cm的正方形區(qū)域作為蘋果存在區(qū)域（實(shí)驗(yàn)室所用塑料蘋果的寬度在8～10cm左右），在三重構(gòu)圖和強(qiáng)度圖上找尋預(yù)測(cè)的障礙物區(qū)域內(nèi)亮度和蘋果亮度有明顯區(qū)別的點(diǎn)，利用找尋到的點(diǎn)坐標(biāo)，在深度圖上找到對(duì)應(yīng)的深度位置，若深度位置與蘋果的深度位置在±8cm范圍內(nèi)，就認(rèn)定以該點(diǎn)為蘋果附近障礙物的位置。

對(duì)于找到的障礙物，針對(duì)樹枝和樹葉的亮度不一樣設(shè)置閾值，當(dāng)亮度閾值大于85小于100時(shí)視為樹葉，其余的障礙物視為樹枝。圖6為障礙物樹葉的位置。

由于樹枝的亮度和環(huán)境背景的亮度相似，所以并不能識(shí)別出樹枝，只要認(rèn)定蘋果附近存在障礙物，通過(guò)亮度判斷是否為可通過(guò)的樹葉，若不為樹葉，則直接判定為不可通過(guò)的障礙物樹枝。表3表示不同障礙物的位置信息。不同障礙物的位置如圖7所示，單位為dm。

2 采摘路徑最優(yōu)化方法

2.1 障礙柵格法模型建立

本文在二維空間進(jìn)行路徑規(guī)劃，用柵格法表示存在障礙物的地圖，該方法起源于美國(guó)CMU大學(xué)。柵格法的基本思想是：將規(guī)劃空間劃分成等面積的小區(qū)，每個(gè)小區(qū)稱為一個(gè)柵格，柵格面積大小一般由所描述的問(wèn)題及所要求的搜索精度決定[12]。本文選取8cm長(zhǎng)度作為柵格的邊長(zhǎng)，因?yàn)楸緦?shí)驗(yàn)所選用的塑料蘋果橫向平均長(zhǎng)度在8cm左右。圖8顯示一個(gè)規(guī)劃空間的柵格劃分情況。每個(gè)柵格上的運(yùn)動(dòng)信息規(guī)定了機(jī)器人在這個(gè)柵格上的運(yùn)動(dòng)擴(kuò)展方向，它們分別是前、后、左、右、右前、右后、左后、左前，如圖9所示[13]。

通過(guò)柵格法得到的地圖可把搜索區(qū)域簡(jiǎn)化成一個(gè)二維數(shù)組，數(shù)組的每一個(gè)元素是網(wǎng)絡(luò)的一個(gè)方塊，方塊被標(biāo)記成完全可通過(guò)（無(wú)任何障礙）、可通過(guò)障礙（樹葉）、不可通過(guò)障礙（樹枝）和蘋果。利用蘋果和不同障礙物的相對(duì)位置，初始化圖中的方格，A代表蘋果在圖中所處位置，B代表不可通過(guò)的障礙物樹枝的位置，L代表可通過(guò)障礙物樹葉的位置，如圖10所示。

2.2 基于A*算法的路徑啟發(fā)式搜索

對(duì)規(guī)劃空間建立必要的空間障礙物，以及采用合理的數(shù)據(jù)結(jié)構(gòu)對(duì)規(guī)劃空間中的自由區(qū)域和障礙物區(qū)域進(jìn)行描述，無(wú)碰撞路徑規(guī)劃就是選取某種有效的搜索方法，搜索出一條經(jīng)過(guò)所有蘋果且移動(dòng)耗費(fèi)總和最小的無(wú)碰撞路徑[14]。

路徑規(guī)劃常見的啟發(fā)式優(yōu)先搜索包括局部擇優(yōu)搜索、全局擇優(yōu)搜索、A*算法以及近幾年發(fā)展起來(lái)的人工神經(jīng)網(wǎng)絡(luò)搜索、遺傳算法搜索等[15]，這些算法都使用了啟發(fā)函數(shù)，但在具體選取最佳搜索節(jié)點(diǎn)時(shí)策略不同。局部擇優(yōu)搜索法是在搜索過(guò)程中選取“最佳節(jié)點(diǎn)”后，舍棄其它的兄弟、父親節(jié)點(diǎn)，然后一直搜索下去。這種搜索結(jié)果由于舍棄了其它節(jié)點(diǎn)，可能也把最好的節(jié)點(diǎn)舍棄了，求解的最佳節(jié)點(diǎn)只是在該階段的最佳并不一定是全局最佳。最好優(yōu)先搜索沒有舍棄節(jié)點(diǎn)（除非該節(jié)點(diǎn)是死節(jié)點(diǎn)），在每一步的估價(jià)中都把當(dāng)前的節(jié)點(diǎn)和以前的節(jié)點(diǎn)估價(jià)值比較，得到一個(gè)“最佳的節(jié)點(diǎn)”，這樣可有效防止“最佳節(jié)點(diǎn)”丟失。在最好優(yōu)先搜索算法基礎(chǔ)加上一些約束條件，就是本文采用的A*算法[16-20]。

A*算法的估價(jià)函數(shù)是F（n）=G（n）+H（n）。這里，F(xiàn)（n）是估價(jià)函數(shù)，G（n）是起點(diǎn)到當(dāng)前指定方格的移動(dòng)耗費(fèi)，H（n）是當(dāng)前點(diǎn)到指定目標(biāo)方格的預(yù)估耗費(fèi)。

在A*算法中，令水平或垂直方向移動(dòng)一格的耗費(fèi)為方格的邊長(zhǎng)，沿對(duì)角線移動(dòng)耗費(fèi)是沿水平或垂直移動(dòng)的1.414倍。之所以選取近似小數(shù)，是因?yàn)楸壤菊_，避免了求根運(yùn)算，從而加快代碼的運(yùn)算速度[20]。對(duì)于完全可通過(guò)方格，方格自帶的移動(dòng)耗費(fèi)是0，對(duì)于存在可通過(guò)的障礙物（樹葉）方格，方格的自帶移動(dòng)耗費(fèi)為方格邊長(zhǎng)的一半。然后以該節(jié)點(diǎn)為中心，向水平和垂直方向依次遞減1/2。而對(duì)于不可通過(guò)的障礙物（樹枝）方格，并不能夠到達(dá)該節(jié)點(diǎn)，所以不會(huì)計(jì)算到該節(jié)點(diǎn)的移動(dòng)耗費(fèi)，并且鄰近節(jié)點(diǎn)進(jìn)行移動(dòng)時(shí)不能通過(guò)其頂點(diǎn)。圖11顯示了各個(gè)方格自帶的移動(dòng)耗費(fèi)。

事先是沒有辦法知道路徑的長(zhǎng)度和路徑上是否具有障礙物的，所以使用曼哈頓方法直接計(jì)算H值[21]。曼哈頓方法是一種計(jì)算城市中一個(gè)地方到另一個(gè)地方的街區(qū)數(shù)的方法。該方法只計(jì)算沿水平方向和豎直方向的方格數(shù)，不能沿對(duì)角線穿過(guò)方格。并且在計(jì)算H值時(shí)忽略一切障礙物，僅僅對(duì)剩余的距離進(jìn)行一個(gè)估算而非實(shí)際值。