基于改進K均值特征點聚類算法的作物行檢測

孟笑天,徐艷蕾,2,王新東,何 潤,翟鈺婷

(1.吉林農業大學 信息技術學院,長春 130118;2.吉林大學 工程仿生教育部重點實驗室,長春 130022)

0 引言

精準施藥技術是精準農業的一個重要組成部分,能夠減少對生態系統的破壞,保障人類的生命健康安全[1-2]。精準施藥是通過空間傳感技術采集并解析具有地理位置的農田作物長勢、病蟲草害等農作物信息,再依據不同的農情制定不同的噴霧方案,按需噴藥,實現無人操作。而在精準施藥的過程中,作物行檢測是關鍵環節,很大程度上影響農業機械的視覺導航效果和施藥的精準度。目前,常用的作物行檢測算法有霍夫變換法(Hough transform, HT)[3]和最小二乘法[4]?；舴蜃儞Q法魯棒性強且抗干擾性好,但也存在計算量大、內存需求高等不足。近年來,很多學者在基本霍夫變換的基礎上進行改進,提出優化的霍夫變換方法。Jiang 等[5]提出了霍夫變換與消隱點約束相結合的算法,運用移動窗口的方法來提取代表作物行的特征點,并利用霍夫變換算法檢測出大于實際作物行數的候選直線,最后基于消隱點的方法得到真正的作物行。Xu等[6]提出隨機霍夫變換,以多對一的映射方式減少數據計算量,采用動態鏈表降低內存。但是,上述方法在實時性和精確度方面仍存在不足。最小二乘法作為一種數學優化技術,速度快是區別于其他方法的一個顯著優勢。司永勝等[7]提出基于最小二乘法的早期作物行中心線檢測算法,利用特征點的鄰近關系對目標點分類,對點集里的特征點用最小二乘法進行直線擬合。但是,最小二乘法對噪聲敏感,導致對直線的擬合效果有很大影響。

針對上述方法的不足,提出一種改進K均值聚類算法,以苗期玉米為研究對象,將作物行中心線候選點集進行分類,再采用最小二乘法提取作物行中心線,以期能夠提高作物行檢測的精確度。

1 圖像獲取與預處理

1.1 圖像獲取

本文所用的玉米圖像均取自于吉林農業大學科研試驗田。采用陜西維視數字圖像技術有限公司生產的 MV-EM040M工業相機,配有可變焦距的C口鏡頭,能夠對自然環境下的玉米作物行圖像進行采集。相機距地面高度約為1.6m,輸出8位RGB彩色圖像。試驗計算機環境配置為CPU主頻2.4 GHz,RAM為8.0 GB。圖像處理所用的軟件平臺為MatLab R2014a。

1.2 圖像預處理

1.2.1 灰度化

獲取原作物圖像[見圖1(a)]后,為了更好地將作物圖像與背景分離,在常規超綠法(excess green)[8](即2G-R-B特征因子的基礎上)減小綠色分量的比例因子,對圖1(a)進行灰度化處理得到圖1(c)。常規超綠法處理結果如圖1(b)所示。對比處理后的圖片可以看出:改進的超綠法使作物行更突出,分離效果更好。

圖1 常規超綠法與改進超綠法灰度化Fig.1 Conventional super green method and improved super green method graying。

1.2.2 二值化

為了進一步將作物行與背景分離,提取作物行相關信息,需要進行二值化處理。Otsu作為最為常用的圖像分割方法[9],可以自動確定分割閾值,且計算方法簡單、適應性強。因此,采用Otsu算法對圖像進行二值化處理,如圖2所示。

圖2 Otsu二值化圖像Fig.2 Otsu binarized image。

1.2.3 特征點提取

為了減少下文聚類算法的計算量,減少噪聲點的影響,本文采用左右邊緣中間線檢測算法[10]從圖2中提取代表作物行的像素點,如圖3所示。

圖3 特征點圖像Fig.3 Feature point image。

2 K均值聚類算法基本原理及改進

2.1 基本原理

K均值聚類算法是最早由J.B.MacQueen提出的一種基于劃分的聚類方法,其具有簡單和高效的特點,在各個領域得到廣泛應用。K均值聚類算法首先從原始的數據集中隨機選擇K個數據點作為初始聚類中心(也稱簇中心);然后計算數據集中其它數據點與每個初始聚類中心的距離,根據距離大小將其劃分到與之最近的類中;再計算各類中所有數據點的平均值,調整各類的聚類中心,更新其它數據點的所屬的類;如此反復迭代,直至目標函數收斂。通常目標函數采用均方差定義,則

(1)

式中k—聚類的個數;

x—原始數據集中任意1個數據點;

ci—1個類(簇);

2.2 改進K均值聚類算法

K均值聚類算法雖然原理簡單、運行效率高,但需要事先已知聚類的個數K,且初始聚類中心的隨機性容易使算法陷入局部最優,從而導致分類效果不理想。針對上述問題,從確定聚類個數和選擇初始聚類中心兩個方面進行改進,以提高聚類的效果。

2.2.1 聚類個數的確定

(2)

式中L1—平均類間距離;

k—聚類數目;

(3)

式中L2—平均類內距離;

k—聚類數目;

x—類ci中的數據;

n—原始數據集的數據個數。

L(k)=L1-L2

(4)

2.2.2 初始聚類中心的選擇

為了克服隨機初始聚類中心對K均值算法的影響,本文提出改進的選擇方法。首先,計算出原始數據集的中心X1,并將其作為第1初始聚類中心;然后,根據點密度公式(5),在r∈(0,d)范圍內,計算X1的點密度D(X1)。當點密度最大時,在對應的領域內選取距離X1最遠的數據點作為第2初始聚類中心X2,并且除去X1、X2,再重復上述步驟,得到第3初始聚類中心X3;不斷迭代,直至獲取k個初始聚類中心。

D(xi)={x∈X|dist(xi,x)≤r}

(5)

式中D(xi)—xi的點密度,即處在點xi的r鄰域內的點的數量;

xi—聚類中心;

X—原始數據集;

x—數據集內的任意對象;

r—領域半徑,r∈(0,d),d為在數據集X中聚類中心與離它最遠數據點的距離。

通過改進方法獲取初始聚類中心,保證了算法的迭代起點更接近于真實的聚類中心,減少了迭代的次數,提高了算法的執行效率。

3 基于改進K均值特征點聚類的作物行檢測

3.1 基于改進K均值算法的特征點聚類

作物圖像經過1.2節的圖像預處理后,獲得可代表作物行的候選特征點,如圖3所示。下一步采用改進的K均值算法對候選特征點進行準確的聚類,使得代表每個作物行的特征點劃分為相應的類。算法的具體步驟如下:

1)從上到下,從左到右,找出所有像素值為1的特征點,統計其數量n。

3)計算所有特征點的平均值X1(即中心點),作為第1初始聚類中心,根據式(5)計算X1的最大點密度所對應的鄰域半徑r。在該鄰域半徑內,找出距離X1最遠的點X2作為第2初始聚類中心并刪除點X1。得到X2后,重復上述步驟直至找出第k個初始聚類中心Xk。

4)根據式(1)計算所有特征點到各聚類中心的歐式距離,并將其劃分到距離最近的類中。

5)根據式(6)更新聚類中心。

6)判斷目標函數是否滿足收斂條件,即|E-E′|ε。其中,E為本次的目標函數值,E＇為上次迭代的目標函數值。若不滿足,轉至4)、5)繼續迭代;若滿足,算法結束。

(6)

式中nj—第j類中的特征點個數;

xi—第j類中的特征點。

為了便于比較改進算法與傳統算法的聚類結果,基于MatLab軟件將圖片背景設為白色,并用不同的符號對每一類特征點進行標記。改進K均值算法和傳統K均值算法的特征點聚類結果如圖4所示。由圖4(a)可以看出:作物行特征點被清晰地劃分為5類,每一類代表1個作物行;而傳統K均值算法聚類后的圖像只有2～3個作物行特征點被準確地分類。由此可見,改進的K均值聚類算法對作物行特征點的劃分效果更好。

圖4 兩種算法對特征點聚類的結果Fig.4 The result of clustering of feature points by two algorithms。

3.2 最小二乘法直線擬合

最小二乘法是一種常用的數學優化方法,用于直線檢測準確度高且速度快。根據3.1節得到的作物行特征點圖像,采用最小二乘法分別對每一類作物行特征點進行直線擬合,擬合結果如圖5所示。

圖5 作物行中心線檢測結果Fig.5 Crop line centerline test results。

4 試驗與分析

為了驗證本文算法對不同天氣狀況和光照強度的適應性和效率,選取200幅玉米的苗期圖片。其中,100張為天氣晴朗、光照強的圖片,剩余100張為陰天、光照弱的條件下拍攝。分別采用改進的K均值算法和標準霍夫變換算法進行作物行中心線檢測,試驗結果如表1所示。

表1 兩種作物行檢測算法的性能對比Table 1 Performance comparison of two crop line detection algorithms。

由表1可以看出:不管在晴朗、光照強還是在陰天、光照弱的拍攝條件下,相對于標準霍夫變換算法,改進的K均值算法均有較高的識別率,整體識別率達到91%。為了進一步說明本文算法的效率,采用Jiang等[12]提出的誤差計算方法,以原作物圖1(a)為例,通過手工繪制作物行的參考直線(參考直線盡可能無限接近作物行的中心線),如圖6中粗線所示;然后,分別計算參考直線與改進K均值聚類檢測直線[圖6(a)中細線所示]、霍夫變換檢測直線[圖6(b)中細線所示]的夾角,夾角越小,檢測算法的精確度越高。經過試驗,霍夫變換算法和改進K均值算法的平均誤差分別為2.103 5°、1.141 1°。這說明,改進的K均值聚類算法對作物行特征點分類的效果更好,檢測直線平均誤差更小,具有較高的檢測精度。

圖6 兩種算法檢測直線與參考直線對比Fig.6 Two algorithms detect line and reference line contrast。

5 結論

1)為了更加準確地檢測作物行,在深入研究傳統K均值聚類算法的基礎上提出改進:首先,根據距離函數最值關系求出最佳聚類數目;然后,依據點密度大小和鄰域半徑確定初始聚類中心,減少了迭代次數,提高了算法的執行效率和劃分效果。

2)采用改進的K均值聚類算法對作物行特征點進行聚類,并采用最小二乘法進行直線擬合,提高了直線擬合的效果,總識別率為91%,高于標準霍夫變換的82%;且改進的K均值聚類算法和標準霍夫變換的平均誤差分別為2.103 5°、1.141 1°。試驗數據表明:提出的基于改進的K均值特征點聚類算法識別效果好,精確度高,可為精準施藥提供理論依據。