基于PSO 優(yōu)化K 均值聚類的葡萄果穗圖像分割算法

張永劍, 任洪娥

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

0 引 言

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

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

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

1 改進的K 均值聚類算法

1.1 K 均值聚類算法

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

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

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

輸入n 個m 維的樣本X

輸出樣本集合的聚類C

(1)類簇初始化,隨機選擇k 個樣本點作為初始聚類中心。

(2)對樣本進行聚類。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

算法流程如下：

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

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

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

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

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

2 葡萄圖像分割

2.1 圖像預(yù)處理

為了解決相機拍攝的圖像光線分布不均勻、整體圖像過明或過暗的問題,如圖1 所示。 首先采用伽馬變換,增強圖像對比度,之后采用中值濾波進行降噪處理。 中值濾波法是一種非線性平滑濾波,它將窗口中心的像素點的像素值設(shè)為該窗口內(nèi)所有像素值的中值［14］。 經(jīng)過上述處理后,原始圖像的噪聲降低,光照更加均勻,改善了圖片質(zhì)量,如圖2 所示,為下一步分割實驗處理做好了準(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ù)葡萄圖像分割實驗采用了RGB 和HSV 顏色空間模型。 相對于RGB 空間,HSV 空間能夠非常直觀的表達顏色的明暗、色調(diào)以及鮮艷程度,方便進行顏色的對比及分割。 HSV 中的H、S、V 分別代表了色相、飽和度和明度。 本文采用的是普通數(shù)碼相機拍攝的葡萄果穗圖像,屬于RGB 顏色空間模型,利用公式(6)由RGB 到HSV 進行轉(zhuǎn)換

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

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

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

2.3 葡萄圖像分割過程

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

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

3.1 實驗環(huán)境

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

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

3.2 實驗結(jié)果分析

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

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

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

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

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

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

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

4 結(jié)束語

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