張永劍, 任洪娥

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

0 引 言

葡萄是一種重要的農(nóng)作物,在我國各個(gè)省市都有分布,然而葡萄采摘季節(jié)性強(qiáng),采摘工作勞動(dòng)強(qiáng)度大,效率低,費(fèi)時(shí)費(fèi)力。 因此,研制葡萄自動(dòng)采摘機(jī)器人來提高效率。 研制葡萄自動(dòng)采摘機(jī)器人,首先要解決的就是圖像的分割問題。 葡萄圖像分割是葡萄圖像由處理到識(shí)別的重要過程, 分割結(jié)果的好壞會(huì)直接影響到葡萄圖像特征提取、目標(biāo)分類等階段的性能［1］。

在計(jì)算機(jī)視覺領(lǐng)域中,圖像分割是指將數(shù)字圖像分割成多個(gè)片段并提取感興趣的目標(biāo)的技術(shù)和過程［2］。 圖像分割方法有很多種,如基于聚類［3］、基于閾值［4］、基于深度學(xué)習(xí)［5］等方法。 其中,基于聚類的分割算法因其快速有效的分割特點(diǎn)已成功應(yīng)用于智能交通、醫(yī)學(xué)影像、遙感圖像等領(lǐng)域［6］。 如吳迪等人采用K-means 算法,將彩色圖像從RGB 顏色空間變換到Lab 顏色空間,再對(duì)圖像聚類實(shí)現(xiàn)分割［7］；徐黎明等使用K-means 算法對(duì)楊梅圖像進(jìn)行分割,并取得較好的分割效果［8］。 呂小蓮等基于顏色特征的成熟番茄果實(shí)分割實(shí)驗(yàn),根據(jù)彩色番茄圖像的特征分布,將彩色圖像轉(zhuǎn)換為灰度圖像,并根據(jù)灰度直方圖中目標(biāo)和背景不同峰值進(jìn)行分割［9］。

針對(duì)葡萄果穗圖像分割問題,本文提出了一種基于粒子群優(yōu)化的改進(jìn)K 均值聚類算法,采用粒子群優(yōu)化算法作為初始聚類中心的選擇,不斷進(jìn)行迭代,可以有效地改善K 均值聚類易受初始化聚類中心影響的問題,使分割后的葡萄果穗圖像更加完整,可以滿足進(jìn)一步葡萄果穗處理實(shí)驗(yàn)的要求。

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

1.1 K 均值聚類算法

K 均值聚類是基于樣本集合劃分的聚類算法,樣本被劃分為k 個(gè)子集,組成k 個(gè)簇,每個(gè)樣本被劃分到k 個(gè)簇中且與其所屬簇中心的歐式距離最小。

K 均值聚類是一個(gè)迭代的過程,每次迭代包括兩個(gè)步驟,首先初始化k 個(gè)聚類簇,將樣本逐個(gè)指派到與其距離最近的中心的簇,得到一個(gè)聚類結(jié)果,然后更新每個(gè)簇的樣本的各個(gè)維度的均值,將其作為新的簇；重復(fù)以上過程,直至兩次迭代中聚類簇不發(fā)生改變或者達(dá)到迭代次數(shù)停止算法。

K 均值聚類算法的具體流程如下：

輸入n 個(gè)m 維的樣本X

輸出樣本集合的聚類C

(1)類簇初始化,隨機(jī)選擇k 個(gè)樣本點(diǎn)作為初始聚類中心。

(2)對(duì)樣本進(jìn)行聚類。

(3)計(jì)算新的聚類中心。

(4)重復(fù)2、3 步,直至迭代收斂或符合停止條件。

雖然K 均值算法具有簡潔、時(shí)間復(fù)雜度較低的優(yōu)點(diǎn),但不能保證收斂得到全局最優(yōu)解,而且對(duì)初始聚類簇比較敏感。 聚類簇在聚類的過程中會(huì)發(fā)生移動(dòng),但是往往不會(huì)移動(dòng)太大,因此選擇不同的初始聚類中心,經(jīng)常會(huì)得到不同的聚類結(jié)果。

1.2 粒子群優(yōu)化算法

粒子群優(yōu)化算法的思想源于對(duì)鳥或魚群捕食行為的研究,Eberhart 和Kennedy 在1995 年提出［10］。通過模擬鳥群飛行覓食之間的行為, 鳥群之間通過集體協(xié)作使群體達(dá)到最優(yōu)目的［11］。

在粒子群算法中,每個(gè)粒子都有速度v 和位置x兩個(gè)屬性,x 代表粒子移動(dòng)的快慢,v 代表粒子移動(dòng)的方向。 每個(gè)粒子搜索的最優(yōu)值成為個(gè)體極值,粒子群中最優(yōu)的個(gè)體極值稱為當(dāng)前全局最優(yōu)值。 算法不斷迭代,更新每個(gè)粒子的速度和位置以及全局最優(yōu)值,最終得到滿足適應(yīng)度(fitness) 或迭代次數(shù)的最優(yōu)值。

在N 維問題空間中,第i 個(gè)粒子速度更新公式(1)如下：

第i 個(gè)粒子的位置更新公式(2)為：

1.3 基于粒子群優(yōu)化的K 均值聚類算法

K 均值聚類算法對(duì)初始化聚類中心比較敏感,而且容易陷入局部最大值,因此,本文提出了一種PSO 的K 均值聚類算法,首先利用PSO 算法尋找兩個(gè)像素粒子,作為K 均值聚類算法的初始聚類簇中心,然后K 均值聚類算法根據(jù)初始聚類中心進(jìn)行聚類,得到最終的分割后的圖像。

在進(jìn)行圖像分割時(shí),待分割的每一幅圖像可以看作是具有n 維空間向量的像素點(diǎn)集合X = ｛X1,X2,…, Xn｝［12］。 隨機(jī)選取像素點(diǎn)集X 中的m 個(gè)像素點(diǎn)作為初始聚類中心,cj為第j 個(gè)聚類中心。 確定m 個(gè)聚類中心后,將像素點(diǎn)集X 中剩余像素點(diǎn)分配到m 個(gè)類中。 粒子i 的適應(yīng)值用fi表示,其計(jì)算公式(3) 如下［13］：

粒子平均適應(yīng)值用favg表示,其計(jì)算公式(4)為：

粒子群的收斂程度可用粒子群的適應(yīng)性(fitness)變化來表示。 設(shè)var 為粒子群適應(yīng)度方差,其計(jì)算公式(5) 如下：

在葡萄圖像聚類分割過程中,將葡萄果穗視為前景,其余視為背景,因此可以設(shè)置初始聚類數(shù)目k= 2。 聚類準(zhǔn)則如下： xi為第i 個(gè)像素點(diǎn), cj為第j個(gè)聚類中心,當(dāng)‖xi-cj‖=min‖xi-ck‖, k=1,2,...,m 時(shí),將xi分配到第j 類。

算法流程如下：

(1)種群初始化：隨機(jī)選取2 個(gè)像素點(diǎn)作為初始聚類中心,將剩余的像素點(diǎn)按照聚類準(zhǔn)則分配給這2 個(gè)聚類中心。

(2)根據(jù)公式(3)計(jì)算每個(gè)粒子的fitness,同時(shí)計(jì)算每個(gè)粒子的個(gè)體極值和全局最值。

(3)根據(jù)公式(1)、(2)更新粒子的速度和位置。

(4)以更新后的粒子為聚類中心,對(duì)種群進(jìn)行K 均值聚類,并分別計(jì)算每個(gè)像素點(diǎn)的適應(yīng)度值。

(5)判斷當(dāng)前種群適應(yīng)度方差是否低于某個(gè)閾值(說明種群已經(jīng)收斂)或者達(dá)到最大迭代次數(shù),如果是,算法結(jié)束；否則轉(zhuǎn)向(3)。

2 葡萄圖像分割

2.1 圖像預(yù)處理

為了解決相機(jī)拍攝的圖像光線分布不均勻、整體圖像過明或過暗的問題,如圖1 所示。 首先采用伽馬變換,增強(qiáng)圖像對(duì)比度,之后采用中值濾波進(jìn)行降噪處理。 中值濾波法是一種非線性平滑濾波,它將窗口中心的像素點(diǎn)的像素值設(shè)為該窗口內(nèi)所有像素值的中值［14］。 經(jīng)過上述處理后,原始圖像的噪聲降低,光照更加均勻,改善了圖片質(zhì)量,如圖2 所示,為下一步分割實(shí)驗(yàn)處理做好了準(zhǔn)備。

圖1 原始葡萄圖像Fig.1 The original grape image

圖2 預(yù)處理后的圖像Fig.2 The image after preprocessing

2.2 顏色空間轉(zhuǎn)換

目前RGB、HSV (HIS)、Lab、以及YCrCb 等顏色模型被廣泛應(yīng)用于圖像處理。 多數(shù)葡萄圖像分割實(shí)驗(yàn)采用了RGB 和HSV 顏色空間模型。 相對(duì)于RGB 空間,HSV 空間能夠非常直觀的表達(dá)顏色的明暗、色調(diào)以及鮮艷程度,方便進(jìn)行顏色的對(duì)比及分割。 HSV 中的H、S、V 分別代表了色相、飽和度和明度。 本文采用的是普通數(shù)碼相機(jī)拍攝的葡萄果穗圖像,屬于RGB 顏色空間模型,利用公式(6)由RGB 到HSV 進(jìn)行轉(zhuǎn)換

圖2 轉(zhuǎn)化為HSV 顏色空間后,H、S、V 分量如圖3 所示：

圖3 H、S、V 分量Fig. 3 H、S、V components

由實(shí)驗(yàn)圖像可知,H 分量下,葡萄圖像與背景顏色差異較大,因此,采用H 分量作為分割輸入圖像。

2.3 葡萄圖像分割過程

將圖2 的H 分量作為輸入圖像,利用公式(2)、(5)進(jìn)行種群初始化,依據(jù)公式(3)進(jìn)行圖像聚類,執(zhí)行算法(1)～(5),得到算法處理后的圖像,將處理后的圖像二值化處理。 由于聚類二值化處理后的圖像仍存在一些細(xì)小連接及孔洞,因此,要對(duì)圖像進(jìn)行形態(tài)學(xué)開運(yùn)算消除孔洞,最終得到分割后的葡萄果穗圖像。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)環(huán)境

計(jì)算機(jī)的處理器為Intel(R) Core(TM) i5-7200U,＠2.5 GHz 2.7 GHz,內(nèi)存為8GB。 佳能50D數(shù)碼相機(jī)。 軟件運(yùn)行環(huán)境：64 位Windows 操作系統(tǒng),算法在Python 3.6 下實(shí)現(xiàn)。

本文所用采集圖像包括順光、逆光下的自然葡萄果穗圖像。 選取了40 幅不同背景、不同生長形態(tài)的葡萄果穗圖像作為實(shí)驗(yàn)圖像。

3.2 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證本文算法,選取葡萄圖像,光照條件均為晴天逆光、沒有套袋、背景較為復(fù)雜,如圖4 所示；分別采用本文算法、傳統(tǒng)K 均值聚類算法和Canny 算法進(jìn)行圖像分割。 三種算法的分割結(jié)果如圖5 所示。

圖4 原始圖像Fig. 4 The original image

圖5 算法分割結(jié)果Fig. 5 Segmentation results

從分割效果來看,Canny 邊緣檢測(cè)效果最差,在有葉子遮擋或者復(fù)雜背景情況下,不能檢測(cè)出葡萄果穗完整輪廓,傳統(tǒng)K 均值聚類算法能有效檢測(cè)識(shí)別葡萄果穗輪廓,但有少量像素點(diǎn)丟失,還存在將背景錯(cuò)分為前景的情況；基于PSO 優(yōu)化的K 均值聚類分割算法則可以有效識(shí)別出葡萄果穗,輪廓較為完整,邊緣清晰,誤分率明顯低于傳統(tǒng)聚類算法,分割結(jié)果優(yōu)于其余另外兩種算法。

圖像的分割效果可用自動(dòng)分割與手動(dòng)分割的匹配率、錯(cuò)分率以及準(zhǔn)確率來評(píng)價(jià)。 匹配率越高,錯(cuò)分率越低,準(zhǔn)確率越高,分割效果就越好。 定義如下：匹配率= ［(M1-| M2-M1|)／M2］ ×100%；錯(cuò)分率=［(M2-M1)／(m ×n)］ × 100%；準(zhǔn)確率=匹配率-錯(cuò)分率［15］。 其中,M1為自動(dòng)分割圖像的目標(biāo)像素值,M2為手動(dòng)分割圖像的目標(biāo)像素值,m、n 分別為圖像的寬度和高度。 表1 展示了20 幅葡萄圖像,分別采用傳統(tǒng)K 均值聚類算法和本文算法分割得到的匹配率、錯(cuò)分率以及準(zhǔn)確率。

表1 實(shí)驗(yàn)分割結(jié)果分析（%）Tab. 1 Experimental segmentation results analysis %

由表1 可知,采用本文算法得到的匹配率和準(zhǔn)確率明顯高于傳統(tǒng)聚類算法,對(duì)葡萄圖像分割效果比較理想。

4 結(jié)束語

為解決K 均值聚類算法不能保證收斂得到全局最優(yōu)解,而且對(duì)初始聚類中心比較敏感的問題,本文提出了一種基于粒子群優(yōu)化的改進(jìn)K 均值聚類算法的圖像分割算法,利用粒子群算法初始化聚類中心,在此基礎(chǔ)上進(jìn)行聚類圖像分割。 實(shí)驗(yàn)結(jié)果表明,此算法分割效果較好,準(zhǔn)確度較高,優(yōu)于K 均值聚類等傳統(tǒng)分割算法。