盧 巍

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

0 引言

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

1 K-means聚類基本原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 算法設計

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

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

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

3 實驗和聚類結果

實驗中使用的數(shù)據(jù)信息如表1所示。

表1 測試樣本參數(shù)對照

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

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

表2 K-means聚類混合K分布數(shù)據(jù)效果

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

4 結語

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