劉智杭， 于 鳴， 任洪娥

(東北林業(yè)大學(xué)信息與計算機工程學(xué)院，黑龍江哈爾濱 150040)

葡萄是一種重要的農(nóng)作物，全球市場報告顯示，2017年我國的葡萄產(chǎn)量達到1 020萬t[1]。依靠人工進行大面積葡萄采摘耗時費力，葡萄采摘機器人可以有效改善這一情況[2]，如何提高機器采摘的速度和準確率已成為國內(nèi)外現(xiàn)代化農(nóng)業(yè)研究的重點問題。

采摘機器人對果實位置定位的準確程度是采摘成功的關(guān)鍵因素。圖像分割是圖像識別和機器視覺的基礎(chǔ)，對于加快機器采摘速度和提高機器采摘準確率的意義重大。圖像分割是指根據(jù)顏色、紋理等特征將圖像分成若干個互不交疊區(qū)域并提出感興趣目標的技術(shù)和過程[3]。常用的圖像分割方法主要有：基于圖像灰度特征的閾值分割、利用圖像局部特征不連續(xù)性的邊緣檢測分割、根據(jù)圖像相似性準則的區(qū)域分割及利用聚類分析的圖像分割等[4]。其中基于K均值聚類的圖像分割方法不受圖像形狀和邊界的限制，分割效果顯著，在人臉識別、醫(yī)學(xué)造影、果實識別等方面都有應(yīng)用[5]。如劉國成用色度值作為特征向量進行K-means聚類，將對圖像進行分割的任務(wù)轉(zhuǎn)化為對數(shù)據(jù)集合進行分類的任務(wù)，從背景中能有效地識別出葉片上的葉螨害蟲，平均識別率達93.95%[6]。由于K-means聚類算法本身存在著過于依賴于初始聚類中心的選擇、對于離群點和孤立點過于敏感和容易陷入局部最優(yōu)等問題，很難保證分割精確度，很多學(xué)者將K-means算法與其他算法結(jié)合進行改進[7]。徐黎明等在Lab空間下結(jié)合同態(tài)濾波和K-means算法對彩色楊梅圖像進行分割，并進行了3組試驗來比較不同形態(tài)的楊梅分割情況，一定程度上減少了光照對于分割的影響，但若背景復(fù)雜會導(dǎo)致較大的誤差[8]；張善文等根據(jù)圖像直方圖的峰值劃分區(qū)域，并將區(qū)域中值作為聚類中心，改善了初始聚類中心選擇的不足，但邊緣處分割效果不好[9]；趙文昌等提出一種人工蜂群融合K-means聚類的分割算法，提高了4.8%的分割準確率，但算法沒有考慮自然環(huán)境因素，實用性效果不好[10]。

針對上述問題，本研究提出一種改進K-means聚類算法的圖像分割方法。采用局部異常因子算法[11]來優(yōu)化K-means聚類中心的選擇，可以有效地剔除數(shù)據(jù)集合中的離群點，使分割后的葡萄果穗圖像更加完整，能夠滿足采摘機器人對目標圖像在復(fù)雜背景下分割精確度高的要求。

1 改進的K均值聚類算法

1.1 基本算法描述

1.1.1 K-means算法 MacQueen在1967年提出了K-means算法[12]。該算法是一種基于距離的聚類算法，基本思想是對于給定的觀測值集合P={P1，P2，…，Pn}，根據(jù)集合P的某種屬性特征將集合分為k個類別S={S1，S2，…，Sk}(k≤n)，然后隨機選擇k個數(shù)據(jù)點作為Si(i=1，2，…，k)的初始聚類中心，計算對象到初始聚類中心的距離將其分配給最近的類別，最后計算重新劃分的k個集合的聚類中心，算法不斷迭代分配然后計算的這一整個過程，直到聚類中心基本不變。最終以群內(nèi)平方和(即方差)作為聚類準則函數(shù)，方差越小聚類效果越好[13]。有關(guān)概念：

概念1：分配原則。給定初始聚類中心集合s={s1，s2，…，sk}，比較數(shù)據(jù)點Pi到sj歐氏距離d(Pi，sj)，將Pi分配給最小歐氏距離時sj所屬的類別

(1)

概念2：聚類中心。聚類中心即每個類別Sj的質(zhì)心，計算公式如下：

(2)

1.1.2 局部異常因子(LOF)算法 Breunig等在2000年提出基于局部密度概念的局部異常因子(LOF)算法[14]，其中局部由集合中k個最近鄰居給出，密度由局部中k個鄰居的距離得出。有關(guān)概念：

概念2：對象空間距離。集合P中的對象之間的可度量距離，記為k-d(Pi，Pk，w)，給定對象Pi，Pk∈{P}兩者間的顏色特征加權(quán)距離為

(3)

(w∈[0，1])，該距離為數(shù)據(jù)間基于k維非空間屬性的加權(quán)距離。

概念3：對象Pi的K-距離鄰居。在給定對象Pi的k-d(Pi)時，Pi的K-距離鄰居包括所有和對象Pi之間的帶權(quán)距離小于或等于k-d(Pi)的對象的集合，記為Nk(Pi)。

Nk(Pi)={k-d(Pi,p′,w)≤k-d(Pi)}(p′∈P/{Pi})。

(4)

k-d(Pi)是對象Pi的K-距離，即對象Pi與集合P中某個對象p之間的歐氏距離dist(Pi，p)，它需要滿足2個條件：至少有k個對象p′∈P/{Pi}，d(Pi，p′，w)≤d(Pi，p，w)；至多有k-1個對象p′∈P/{Pi}，d(Pi，p′，w)

概念4：Pi的局部偏離率。Pi的局部偏離率反映了對象Pi附近數(shù)據(jù)點的分布情況，記為LDRk(Pi)。

(5)

p′為Pi的K-距離鄰居的質(zhì)心，LDRk(Pi)的值越大說明對象Pi附近的分布密度越小，該點是離群點的概率越大；LDRk(Pi)的值越小說明對象Pi附近的分布密度越大，該點是離群點的概率越小。

概念5：Pi的局部偏離影響率。Pi的局部偏離影響率反映了屬于對象Pi的K-距離鄰居集合的數(shù)據(jù)點對于對象Pi的偏離程度的影響，記為LIRk(Pi)。

(6)

分子為對象Pi的K-距離鄰居集合中所有數(shù)據(jù)點的局部偏離率之和。

概念6：Pi的局部偏離因子。Pi的局部離群因子反映了對象Pi的K-距離鄰居集合中相鄰數(shù)據(jù)點的分散程度，記為LOFk(Pi)即

(7)

局部偏離因子的值越大，表明該對象周圍的鄰居數(shù)據(jù)點分布密集，不是離群點，局部偏離因子的值越小，表明該對象離其他鄰居數(shù)據(jù)點較遠，分布較為稀疏，很可能是離群點。

1.2 基于LOF的改進K-means算法

(1)輸入?yún)?shù)計算。參數(shù)1：數(shù)據(jù)集P。初始化數(shù)據(jù)集合P={P1，P2，…，Pn}，將圖片中的每個像素點作為數(shù)據(jù)點放入集合P，提取每個像素點的R、G、B3個通道分量值，構(gòu)造三維數(shù)組A(i，j，k)，存放像素點的值(圖1)。根據(jù)CIE國際照明委員會給出的RGB顏色空間色度值在結(jié)合專家意見給不同色度值分配權(quán)重，W={w1，w2，…，wd}。

參數(shù)2：聚類的類別數(shù)k?？紤]到試驗所用的葡萄圖片整體上可以分為葡萄果穗和背景2個部分，再綜合對運行速度等因素的考慮，將聚類的類別數(shù)k設(shè)定為2。

(2)根據(jù)式(3)計算每個對象與集合中其他數(shù)據(jù)點之間的加權(quán)空間距離，挑選出k個最小距離的點作為對象的 K- 距離鄰居，其中距離最大者為對象的K-距離，然后求算對象與其K-距離鄰居的質(zhì)心之間的距離，再根據(jù)式(5)計算出對象的局部偏離率，根據(jù)式(6)計算局部偏離影響率，根據(jù)式(7)計算局部偏離因子。

(3)通過得到的局部偏離因子的值將數(shù)據(jù)集合重新排序，剔除局部偏離因子值偏大的前n個數(shù)據(jù)，創(chuàng)建新的數(shù)組A′(i，j，k)，用來存放去除離群數(shù)據(jù)點后的數(shù)據(jù)集合。

(4)用LOF算法輸出的數(shù)據(jù)集合重新構(gòu)造R、G、B等3個通道的分量值，然后合并3個通道并轉(zhuǎn)換為HSI顏色空間，最后提取H分量值構(gòu)成新集合P′。

(5)根據(jù)式(1)將集合P′中的每個對象分配給與其歐氏距離最近的第k個類別，根據(jù)式(2)計算分配后k個類別的聚類中心。

2 葡萄果穗圖像分割

2.1 選取顏色空間

對于一張彩色葡萄圖片，人眼可以輕松地觀察出背景和葡萄果穗的分界線，識別出自己需要的部分。計算機以像素數(shù)據(jù)的形式存儲彩色圖片，要在大量的像素數(shù)據(jù)中得到需要的目標圖像，需要選擇合適的顏色空間和算法對圖片進行有效分割。

通過CIE(國際照明委員會)提出的CIE1931-RGB標準色度系統(tǒng)演變出的顏色空間有RGB、HSI、LAB等[15]。普遍使用的RGB顏色空間是由三原色R(紅)、G(綠)、B(藍)進行不同程度的疊加形成的。由于缺少人的視覺系統(tǒng)對于顏色感知的亮度等信息，表示出的圖片顏色與人眼識別出的顏色色差較大，不適用于自然背景下圖像的顏色聚類。為解決RGB顏色空間顏色不均勻的問題，本算法采用了HSI顏色空間，HSI顏色空間使用色調(diào)(H)、飽和度(S)、亮度(I)來描述色彩，一方面HSI表示顏色的方式更加符合人眼對顏色的感知和描述；另一方面，HSI空間將亮度I與色調(diào)H分離，用飽和度S表示顏色的純凈度，降低顏色空間3個通道的關(guān)聯(lián)性，減小自然光照下試驗圖片亮度不均勻?qū)υ囼灲Y(jié)果的影響[16]。

2.2 光線補償和去噪

數(shù)字圖像在拍攝和傳輸?shù)倪^程中會受到成像設(shè)備和外部環(huán)境的影響，易造成圖像色彩偏差、圖像中細節(jié)不突出或者圖像產(chǎn)生噪聲點等問題[17]，這些因素會干擾圖像分割的精準度，因此在進行圖像分割前對圖像進行預(yù)處理是必要的。本算法首先采用gamma校正來對圖像進行光線補償，以圖2所示葡萄果穗原圖為例，圖3-a為原圖的散點圖，進行光線補償后得到的散點圖見圖3-b，剔除離群點后得到的散點圖見圖3-c，比較發(fā)現(xiàn)，gamma校正[18]后圖像中的像素點集中在坐標系對角線上，有效地解決了光照不平衡造成的色彩偏差問題。然后使用中值濾波去除gamma校正過程中產(chǎn)生的噪聲，其結(jié)果如圖4所示。經(jīng)過上述處理后，降低了噪音和光照的影響，使圖像的光照更加均勻，實現(xiàn)了提高試驗圖像質(zhì)量的目的，為之后的圖像分割做好了準備。

2.3 圖像分割過程

對圖4的RGB空間圖像提取R、G、B等3個通道的分量值進行FOL算法去除離群點[19]，如圖3-c所示，分散在整體像素點邊緣的稀疏分布像素點被準確剔除。FOL算法輸出的像素點數(shù)據(jù)合并成的圖像是RGB模式的，因此需要將圖像從RGB空間轉(zhuǎn)換為HSI空間，轉(zhuǎn)換公式如下：

(8)

(9)

(10)

將根據(jù)公式(8)、(9)、(10)得到H、S、I等3個通道的分量值繪制成顏色直方圖(圖5)。觀察圖5-a可以發(fā)現(xiàn)，H分量直方圖中背景與目標對象呈明顯的雙峰，選擇H分量對圖片進行聚類，然后再根據(jù)聚類結(jié)果對圖像進行分割。

3 試驗結(jié)果與分析

3.1 試驗環(huán)境

聯(lián)想電腦：處理器為Intel? CoreTMi7-6700，主頻 3.40 GHz，內(nèi)存為4 GB；軟件運行環(huán)境：64位Windows操作系統(tǒng)，算法在MATLAB R2015b下實現(xiàn)。

為了驗證本算法的有效性，選取50幅不同環(huán)境背景、不同光線、不同生長形態(tài)的葡萄果穗圖片作為測試圖片，分析其中4種具有典型特征的葡萄果穗圖片：帶有露珠的葡萄果穗如圖6-a，2串相疊且有葉片遮擋的葡萄果穗如圖6-b，有套袋遮擋的葡萄果穗如圖6-c，背景復(fù)雜的葡萄果穗如 圖6-d。

3.2 試驗結(jié)果分析

為測試本算法的圖像分割效果，分別使用Otsu、傳統(tǒng)聚類算法和本算法對圖6所示4種具有典型特征的葡萄果穗原圖進行圖像分割試驗，3種算法的試驗結(jié)果如圖7所示。對于葡萄果穗的分割效果，Otsu算法最差，帶有露珠和2串相疊有葉子遮擋的葡萄果穗分割后還能夠分辨出整體葡萄輪廓，但在有葡萄套袋遮擋和復(fù)雜背景的葡萄果穗分割結(jié)果中，基本輪廓與背景部分相互交雜難以識別；傳統(tǒng)的K-means算法在帶有露珠、2串相疊有葉子遮擋和復(fù)雜背景的葡萄果穗分割試驗中，能夠識別出果穗輪廓但有部分缺失，在有葡萄套袋遮擋的葡萄果穗分割試驗中，受葡萄套袋影響，果粒像素點丟失嚴重；本算法的葡萄果穗分割試驗結(jié)果達到預(yù)期目標，實現(xiàn)了葡萄果穗輪廓的識別，其中帶有露珠的葡萄果穗分割效果最好，對復(fù)雜背景中的葡萄果穗分割時，僅在果粒上有斑點的區(qū)域丟失少量像素點。

從圖7-a可以看出，在果穗上的單顆果粒識別中，Otsu算法受到露珠影響較大，識別不出帶露珠葡萄果粒的部分區(qū)域；傳統(tǒng)K-means算法受到葡萄果穗上葡萄果粉面積不均勻的影響，導(dǎo)致屬于目標對象聚類區(qū)域像素點部分被劃分為非目標對象區(qū)域，且出現(xiàn)小面積的背景區(qū)域劃分入目標區(qū)域內(nèi)；本算法能夠準確分割出果穗輪廓，且果穗上所有果粒的像素點沒有缺失；觀察圖7-b發(fā)現(xiàn)，用Otsu算法分割的試驗結(jié)果中有部分果?；烊肽繕藚^(qū)域且果粒區(qū)域像素點丟失嚴重；傳統(tǒng)K-means算法分割結(jié)果中存在部分果粒區(qū)域丟失現(xiàn)象；本算法只有小面積果?；烊耄粓D7-c中只有本算法準確將葡萄套袋區(qū)域識別并分割出來；圖7-d中傳統(tǒng)K-means算法和本研究算法都沒有準確識別出葡萄果粒上的斑點區(qū)域，但本算法損失的葡萄果穗有效像素點數(shù)目更少。

4 結(jié)論

為解決K-means算法對離群點和孤立點敏感度高，容易陷入局部最優(yōu)和過分依賴初始聚類中心選擇等問題，提出一種融合LOF和K-means聚類算法的圖像分割算法，利用LOF算法剔除數(shù)據(jù)中的離群點，采用局部偏離因子優(yōu)化初始聚類中心的選擇。將本算法分別與Otsu算法、傳統(tǒng)聚類算法進行試驗對比，結(jié)果表明本算法在分割準確度方面優(yōu)于后2種算法。本算法為果實結(jié)構(gòu)呈穗狀且果粒密集相互堆疊的水果圖像分割提出了一種新的思路。