基于改進(jìn)K均值聚類的葡萄果穗圖像分割

劉智杭， 于 鳴， 任洪娥

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

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

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

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

1 改進(jìn)的K均值聚類算法

1.1 基本算法描述

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

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

(1)

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

(2)

1.1.2 局部異常因子(LOF)算法 Breunig等在2000年提出基于局部密度概念的局部異常因子(LOF)算法[14]，其中局部由集合中k個(gè)最近鄰居給出，密度由局部中k個(gè)鄰居的距離得出。有關(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)時(shí)，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中某個(gè)對象p之間的歐氏距離dist(Pi，p)，它需要滿足2個(gè)條件：至少有k個(gè)對象p′∈P/{Pi}，d(Pi，p′，w)≤d(Pi，p，w)；至多有k-1個(gè)對象p′∈P/{Pi}，d(Pi，p′，w)

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

(5)

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

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

(6)

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

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

(7)

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

1.2 基于LOF的改進(jìn)K-means算法

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

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

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

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

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

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

2 葡萄果穗圖像分割

2.1 選取顏色空間

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

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

2.2 光線補(bǔ)償和去噪

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

2.3 圖像分割過程

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

(8)

(9)

(10)

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

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

3.1 試驗(yàn)環(huán)境

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

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

3.2 試驗(yàn)結(jié)果分析

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

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

4 結(jié)論

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