基于K-means聚類的計算機視覺下楊梅水果圖像識別

盧 巍

（昆明文理學院信息工程學院，昆明 650222）

0 引言

隨著人工智能在工業和農業中的逐步運用，傳統的手工業行業都在探索機器視覺下的自動控制技術，計算機視覺下的水果采摘也在如火如荼的研究當中。目前大多數計算機視覺下的水果采摘研究，關注點都放在水果品種和大小分類的算法研究上，而對直接進行果樹上水果和背景分離的計算機視覺算法研究不多。這主要是當前市場對分鏈需求的導向所致。但是，從長遠人工智能發展角度來看，機械采摘技術也會不斷發展和運用。云南有著大量的大樹楊梅種植，傳統人工采摘技術耗工耗時，機械臂采摘可以解決這一問題。要研究機械臂采摘，就要解決計算機視覺下的水果和背景分離，使機械臂能準確定位水果，完成采摘。

1 K-means聚類基本原理

K-means 聚類是這樣一種聚類算法，它用質心定義數據原型。算法開始時，將數據根據其到初始質心的距離不同隨機指派到一個最近鄰的質心形成簇。為了將數據指派到最近鄰的質心，就需要一個鄰近性度量來量化所謂數據的“最近”概念。在聚類算法中，通常使用歐幾里德距離并同時對數據文檔使用余弦相似性進行度量。可是，由于K-means聚類所使用的鄰近性度量非常簡單，因為算法要不斷地重復計算每個數據點與質心之間的鄰近度。考慮鄰近性度量為歐幾里德距離的數據。所以使用誤差的平方和（sum of the squared error，）作為度量聚類質量的目標函數。也稱為散布。換言之，計算每個數據點到近鄰質心的歐幾里德距離，也就是每個數據點的誤差，然后計算誤差的平方和。給定由兩次運行后產生的兩個不同的，我們更喜歡誤差的平方和最小的那個，因為它說明聚類的質心可以更好地代表族的中心。的定義如式（1）所示：

其中，是歐幾里德空間中兩個對象之間的標準歐幾里德距離。對于給定一個，可以把聚類問題看為優化問題。更確切的說是可以看為一個全局最優問題，解決這個問題的一種方法是窮舉法，即找到將所有數據點劃分成簇的所有可能方法，然后選擇最好的滿足目標的一個。這種方法可以保證實現誤差最小化算法，可是，在實際運用中，這種方法沒有計算可行性，因此，需要尋找一個更加實際的方法，在數據挖掘領域一種常用的解決這個問題的方法是梯度下降法。這個方法雖然無法保證實現最優解，可是它卻是實際可行的。對于這種方法，只需要選擇一個初始解，然后重復計算最好的優化目標函數的解的改變和更新解這兩個步驟。將其運用到要解決的問題中，現假定數據是一維的，即滿足式（2）：

這個假設沒有改變任何東西，但是可以大大地簡化所需要的論證過程。現在的目標是最小化，因為最小化就可以得到K-means的最優化質心。對于式（1），當數據是一維數組的時候，可以簡化為式（3）：

其中C是第個簇，是C中的點，c是第個簇的均值。

對第個質心c求解，最小化式（3），也就是對求導，求導過程如下所示，得到式（4）：

將式（4）進行進一步化簡，可以推導得到式（5）:

并最終推導得到式（6）:

從式（6）可以看出一個重要的結論，簇最小化的最佳質心是簇中各點的均值。至此，證明了質心的最優取得是各點的均值。可是，同時也帶來另外一個問題，這樣的質心是否可以運用于各種不同的目標函數。這個問題在數學上可以表示為將數據劃分為個簇，使得數據點到其簇中心的曼哈頓距離（）之和最小。即把目標轉化為尋求最小化，式（7）給出了的絕對誤差和。

其中dist是的距離。為了簡單起見，再次使用一維數據，即dist= ∣c-∣。

可以對第個質心c求解，最小化式（7），即對求導，令導數等于0，并求解c，得到式（8）。

對c求解，可以發現求解結果就是各點的中位數。同時，這也為計算帶來方便，因為一組點的中位數的計算是簡單明了的，而且受到離群點影響較小。以上解釋了算法中用均值作為質心，同時，證明了這樣的質心具有普適性。根據式（6），定義第個簇的質心（均值）為式（9）：

K-means 算法接下來的步驟是最小化，這個步驟是通過將數據中每個點指派到最近鄰的質心形成簇，判斷是否達到局部最優，若沒有，就更新質心，重新指派，直至達到局部最優。

總體來說，K-means 是以局部最優為原則，通過不斷更新質心的迭代手段來實現對數據的聚類。其適應性較強，對數據所服從的分布沒有任何依賴，為聚類一些服從復雜分布的數據開辟了一個新的空間。

模仿機械臂安裝后計算機視覺成像距離進行圖片拍攝，將拍攝好的大樹楊梅圖片先進行灰度化處理，處理后的數據進行擬合優度檢測，運用柯爾莫哥洛夫-斯米諾夫檢驗（KS 檢測），來判斷圖像數據的統計分布特性，進一步運用擬合優度檢驗法對其進行參數估計，建立基礎分布模型，后嘗試數據聚類。

2 算法設計

根據K-means 聚類原理，將其運用到前期處理好的圖像數據中，根據實際圖片情況，初始選取質心時，將成熟楊梅顏色數據均值，未成熟果實和樹葉顏色數據和其它雜項數據均值選取為兩個質心，進行算法迭代，算法流程如圖1所示。

圖1 K-means聚類算法流程圖

根據圖1 所示算法編寫算法程序，運用Kmeans聚類算法分析所采集的實驗圖片數據，期望能證明其分類的有效性并找出此方法在數據運用中存在的不足。筆者在實驗基地運用高清照相機采集400張成熟期大樹楊梅的圖像進行實驗，為了實驗方便，采用圖形圖像處理軟件對圖片進行歸一化處理，將圖片像素統一成800×600，并對圖像做包括尺寸裁剪、濾波、圖像增強、特征抽取和分割等預處理后進行聚類實驗。

3 實驗和聚類結果

實驗中使用的數據信息如表1所示。

表1 測試樣本參數對照

表1中3個測試樣本均選取圖片中包含20個成熟楊梅果實圖片樣本。3個測試樣本都是同一角度下拍攝樣本，但拍攝光線不同，測試樣本一是在正常自然光線下拍攝，測試樣本二為正常光照不充分時拍攝樣本，模擬實際采摘中晨昏或者由于栽種密集而導致光線不足情況，測試樣本三為夜間人為打光光線下拍攝樣本。

實驗：驗證K-means 聚類效果為檢驗Kmeans 聚類算法數據的分類效果，運用K-means聚類算法對測試樣本一和測試樣本二進行聚類，其聚類結果如表2所示，表中顯示分類正誤個數和分類正確率。

表2 K-means聚類混合K分布數據效果

從表2可以看出，運用K-means聚類算法可以較好地聚類大樹楊梅圖片數據，測試樣本迭代5 次達到收斂。在對測試樣本一中400 個樣本進行聚類時，正確率93.26%，說明在光線充足的情況下，通過聚類可以很好地識別成熟楊梅果實和其他顏色背景。但是在測試樣本二中400個樣本進行聚類可以看出，自然光照對算法聚類的準確性有一定影響。測試樣本三的聚類效果不甚理想。分析原因，光照不充足，導致照片成像色彩變化，加之前期圖像處理過程中引入的誤差疊加，導致邊界模糊所致，特別是當人為補光時，照片色彩和自然光線下照片色彩改變較大，使得邊界模糊現象更加突出。

4 結語

以具有豐富信息的彩色圖像為處理對象，本文給出了運用K-means 聚類算法對云南當地農作物大樹楊梅進行聚類的一種算法，算法初始選取兩個質心進行迭代，經過5次迭代，可以實現將大樹楊梅成熟果實和其它背景識別的目標。同時，由于K-means 聚類對異常數據的敏感性，當圖片數據邊界模糊時，對質心的選取提出苛刻要求。綜上所述，算法可以快速、準確地對楊梅水果圖像進行識別，具有較好的魯棒性和泛化能力，可為水果采摘機器人視覺識別系統提供技術和理論支持。