基于PSO與K-均值聚類算法優(yōu)化結(jié)合的圖像分割方法

曹帥帥，陳雪鑫，苗 圃，卜慶凱

(青島大學(xué)電子信息學(xué)院，山東 青島 266071)

0 引 言

圖像分割是根據(jù)圖像的不同特征劃分為不同的區(qū)域并提取出感興趣的區(qū)域。圖像分割是在保留圖像相關(guān)特征的基礎(chǔ)上，將圖像空間的對(duì)象目標(biāo)分成若干個(gè)有效區(qū)域，有利于減少在后續(xù)分析和處理數(shù)據(jù)的工作量，提高圖像處理的效率[1-2]。

許多學(xué)者引進(jìn)新的方法和思想不斷完善圖像分割的領(lǐng)域，憑借聚類技術(shù)的出現(xiàn)為圖像分割方法提供了更多可能。MacQueen[3]在1967年提出了K-均值聚類算法(K-means clustering algorithm)，K-均值聚類算法是到目前為止應(yīng)用最廣泛最成熟的一種聚類分析算法，具有高效性、可伸縮性和局部尋優(yōu)能力強(qiáng)的特點(diǎn)，它適用于數(shù)據(jù)挖掘，同時(shí)也適用于圖像處理領(lǐng)域。李光等[4]提出了一種基于K-均值聚類與區(qū)域合并的彩色分割方法，有效地提高了自然彩色圖像的分割效果。趙麗[5]通過結(jié)合圖像空間信息，將K-均值聚類算法用于含有噪聲的圖像分割，加強(qiáng)了K-均值算法在復(fù)雜環(huán)境中的圖像分割能力。但是，K-均值算法對(duì)初始聚類中心選取要求很高而且容易收斂到局部最優(yōu)解從而錯(cuò)過全局最優(yōu)解。鑒于K-均值算法存在的缺陷，研究人員對(duì)其進(jìn)行了改進(jìn)優(yōu)化。Kennedy和Eberhart在1995年提出了粒子群優(yōu)化(Particle Swarm Optimization， PSO)算法，PSO算法擁有強(qiáng)大的全局尋優(yōu)能力，適當(dāng)優(yōu)化慣性權(quán)重可以增強(qiáng)全局搜尋能力。李凱等[6]提出了一種粒子群優(yōu)化算法和K-means聚類算法混合的棉花葉片圖像分割方法。夏奇等[7]將PSO與K-means算法結(jié)合應(yīng)用在組合導(dǎo)航中。Zhang等[8]提出了一種適用于多目標(biāo)粒子群優(yōu)化算法，通過調(diào)整粒子群權(quán)重系數(shù)等參數(shù)，實(shí)現(xiàn)算法的快速收斂。將全局尋優(yōu)能力強(qiáng)大的PSO算法與局部尋優(yōu)能力強(qiáng)大的K-均值算法如何有效地強(qiáng)強(qiáng)聯(lián)合并且應(yīng)用于圖像分割方面，是眾多學(xué)者研究的方向。

本文受PSO算法權(quán)重系數(shù)的啟發(fā)，對(duì)傳統(tǒng)固定值慣性權(quán)重做出改變的同時(shí)調(diào)整學(xué)習(xí)因子做輔助，改善PSO算法過早收斂到局部最小值的弊端。在后期，以合適的粒子適應(yīng)度切換至K-均值算法完成圖像分割，可以獲得更有效的結(jié)果。

1 HSV顏色空間

圖1 HSV顏色空間模型

已有設(shè)備輸出的圖像以RGB(Red、Green、Blue)顏色模型為基礎(chǔ)，每種顏色出現(xiàn)在紅、綠、藍(lán)的原色光譜分量中，但在此模型中3個(gè)顏色分量之間存在高度相關(guān)性[9-11]。RGB顏色空間并不能滿足人對(duì)顏色的感知，而且，在RGB顏色空間2個(gè)顏色點(diǎn)之間的距離并不能完美地表示出知覺之間的差異。HSV(Hue、Saturation、Value)顏色模型更接近于人們的經(jīng)驗(yàn)和對(duì)彩色的感知，故采用HSV顏色空間來實(shí)現(xiàn)分割空間的選擇。其中，H代表色調(diào)，S代表飽和度，V代表亮度值。分別采用二維卷積濾波進(jìn)行去噪預(yù)處理，將去噪處理后的H、S、V分量通道三色圖重組得到預(yù)處理后的圖像，HSV彩色空間通過沿灰度軸研究RGB彩色立方體加以公式化，得出圖1所示的六邊形彩色調(diào)色板。

RGB顏色空間轉(zhuǎn)換到HSV顏色空間公式如下：

(1)

(2)

V=max

(3)

其中,max=max(R,G,B)，min=min(R,G,B)。H的取值范圍為0°～360°，S值和V值的范圍為0～1。

2 K-均值算法

使用聚類算法完成圖像分割，首先用特征向量的形式表示對(duì)應(yīng)的圖像空間中的像素點(diǎn)，然后借助特征向量的相似性劃分為不同的種類[12-13]，最后將其映射回原圖像空間，完成圖像分割。

K-均值算法能夠使聚類域中所有樣本到聚類中心距離的平方和最小[14]。在整體樣本數(shù)據(jù)中選取k個(gè)初始聚類中心，計(jì)算每個(gè)樣本到初始聚類中心的距離，找出最小距離把樣本歸入最近的聚類中心，如圖2(a)所示。修改中心點(diǎn)的值為本類所有樣本的均值，再計(jì)算各個(gè)樣本到k個(gè)中心的距離，重新歸類、修改新的中心點(diǎn)，如圖2(b)所示。直到新的距離中心等于上一次的中心點(diǎn)時(shí)結(jié)束。

(a) 將未歸類的樣本放入最近的聚類中心

(b) 將歸類的樣本重新歸入最近的類

K-均值算法在執(zhí)行過程中，采用歐氏距離計(jì)算數(shù)據(jù)樣本之間的距離，使用誤差平方和準(zhǔn)則函數(shù)評(píng)價(jià)聚類性能。給定樣本集D={x1,x2,…,xm}，K-均值算法針對(duì)聚類所得簇劃分C={C1,C2,…,Ck}最小化平方誤差為:

(4)

K-均值算法需要給定初始聚類中心，不同的初始聚類中心會(huì)有不同的結(jié)果，而且必須事先給定聚類數(shù)目，然而聚類個(gè)數(shù)k值往往是難以估計(jì)的。

3 粒子群算法

粒子群算法是一種群體智能的優(yōu)化算法，它從鳥群覓食行為特征中得到啟示[15-17]。假設(shè)粒子群由m個(gè)粒子組成，用種群X={X1,X2,…,Xm}來表示，當(dāng)它在一個(gè)n維空間中，其中第i個(gè)粒子所處的位置用Xi={Xi1,Xi2,…,Xin}T表示，每個(gè)位置都表示一種解。粒子通過不斷調(diào)整自己的位置Zi來搜索新解，第i個(gè)粒子搜索到的最好解，記做Pid，整個(gè)粒子群經(jīng)歷過的最好的位置，即目前搜索到的最優(yōu)解，記做Pgd。此外每個(gè)粒子都有一個(gè)速度，記做Vi={Vi1,Vi2,…,Vin}T，當(dāng)2個(gè)最優(yōu)解都找到后，每個(gè)粒子根據(jù)式(5)～式(6)來更新自己的速度和位置[18]。

圖3 粒子移動(dòng)方向的示意圖

速度向量迭代公式：

Vid(k+1)=ωVid(k)+c1r1(Pid(k)-Xid(k) )+

c2r2(Pgd(k)-Xid(k)) (5)

位置向量迭代公式：

Xid(k+1)=Xid(k)+Vid(k+1)

(6)

其中，Vid(k+1)表示第i個(gè)粒子在k+1次迭代中第d維上的速度；ω為慣性權(quán)重，通過調(diào)整ω的大小，可以對(duì)全局尋優(yōu)能力和局部尋優(yōu)能力進(jìn)行調(diào)整；c1、c2為非負(fù)常數(shù)，r1、r2為0～1之間的隨機(jī)數(shù)；Pid(k)表示第i個(gè)粒子在第d維空間中k次迭代中的個(gè)體最優(yōu)值；Pgd(k)表示全局最優(yōu)解。

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

在算法的初期階段，粒子飛行的方向和位置全部取決于速度，保持粒子高效可靠的遺傳性，必須提高粒子速度的發(fā)散概率，為此要將粒子收斂速度降低。在PSO算法中的公式可以觀察到，存在ω、c1、c2等隨機(jī)參數(shù)，慣性權(quán)重ω使粒子保持運(yùn)動(dòng)慣性，c1、c2表示粒子向Pid(k)和Pgd(k)位置的加速項(xiàng)權(quán)重[19-21]。常用的慣性權(quán)重公式如下：

ω(k)=ωmax-(ωmax-ωmin)×k/itermax

(7)

ω(k)=ωmax-(ωmax-ωmin) (k/itermax)2

(8)

其中，ωmax表示最大慣性權(quán)重；ωmin表示最小慣性權(quán)重；itermax表示最大迭代次數(shù)；k表示當(dāng)前的迭代次數(shù)。

上述慣性權(quán)重都為線性權(quán)重，雖然符合整個(gè)搜尋過程中慣性權(quán)重遞減的要求，但在算法搜索過程中，種群粒子在靠近某些邊緣最優(yōu)解時(shí)，可能存在種群多樣性的缺失，尋優(yōu)性能上還有提升空間。眾多學(xué)者紛紛將固定慣性系數(shù)進(jìn)行動(dòng)態(tài)調(diào)整以此改善PSO算法過早收斂到局部最小值的弊端。例如，阮威[22]將動(dòng)態(tài)慣性系數(shù)定義為分段函數(shù)，將所有粒子當(dāng)前平均適應(yīng)度和粒子i當(dāng)前適應(yīng)度的大小關(guān)系作為分段條件，得到2個(gè)線性的慣性系數(shù)；姜建國(guó)等[23]采用余弦函數(shù)的形式來控制慣性權(quán)值的變化；楊雨航[24]將動(dòng)態(tài)慣性權(quán)重服從一個(gè)指數(shù)分布概率密度函數(shù)。結(jié)合上述對(duì)改進(jìn)慣性權(quán)重的分析，本文加入余弦函數(shù)控制線性權(quán)重的同時(shí)[24]，加入正態(tài)分布函數(shù)，使慣性權(quán)重在整體上呈現(xiàn)非線性變化。優(yōu)化的慣性權(quán)重公式如下：

(9)

其中，N(0,1)為正態(tài)分布，φ為慣性調(diào)整因子。余弦函數(shù)慣性權(quán)重的改進(jìn)策略為非線性地減小ω的取值,使種群粒子更快地接近最優(yōu)解，提高了搜索效率，相對(duì)于阮威提出的線性動(dòng)態(tài)慣性權(quán)重，不僅在搜索效率上更高,還能夠改善早熟問題。姜建國(guó)提出的余弦函數(shù)控制權(quán)值變化，在搜索后期，會(huì)出現(xiàn)收斂速度降低和種群多樣性缺失的現(xiàn)象。本文通過加入正態(tài)分布再次調(diào)整慣性權(quán)重的分布情況，以此改善上述現(xiàn)象，加入非線性隨機(jī)的權(quán)重可以在每次迭代中改變粒子速度，保證種群的多樣性。并通過φ控制取值范圍的偏離程度，在搜尋最優(yōu)解過程中，慣性權(quán)重減小可以通過φ值進(jìn)行調(diào)控，降低在局部極小值處丟失全局最優(yōu)解的概率。相較于楊雨航[24]僅僅把動(dòng)態(tài)慣性權(quán)重服從一個(gè)概率密度函數(shù)，本文提出的控制偏離程度的參數(shù)φ的概念，完美結(jié)合余弦函數(shù)，增強(qiáng)了全局尋優(yōu)能力。

學(xué)習(xí)因子的取值對(duì)粒子的“認(rèn)知”能力與“社會(huì)”能力具有很大的影響，學(xué)習(xí)因子做出的變化為:

(10)

(11)

其中，c1s、c2s分別表示學(xué)習(xí)因子c1和c2的初始值，c1e、c2e分別表示學(xué)習(xí)因子c1和c2的終值；t表示當(dāng)前迭代次數(shù)；T表示最大迭代次數(shù)。

這樣的改變使得粒子的“認(rèn)知”能力和“社會(huì)”能力得到了充分的發(fā)揮?！罢J(rèn)知”能力的加強(qiáng)便于實(shí)現(xiàn)快速搜索，提高全局搜索能力；“社會(huì)”能力的加強(qiáng)有利于局部的精細(xì)化，獲得更好的全局最優(yōu)解。確定好權(quán)重系數(shù)與學(xué)習(xí)因子之后，PSO算法就可以在搜索算法初期，僅使用PSO算法在全局尋優(yōu)過程中不斷逼近解子空間，增加收斂的速度。一旦PSO算法處于收斂狀態(tài)，此時(shí)每個(gè)粒子的適應(yīng)度相同，是切換K-均值算法的最佳時(shí)刻，充分發(fā)揮K-均值算法局部尋優(yōu)能力，加快收斂速度。

粒子群適應(yīng)度方差σ2定義如下：

(12)

圖4為優(yōu)化算法流程圖，它包括2個(gè)階段:

1)使用PSO算法在解空間中搜索全局最優(yōu)解，利用PSO算法優(yōu)異的全局優(yōu)化能力，以避免收斂到局部最優(yōu)解。當(dāng)找到全局最優(yōu)解或近似全局最優(yōu)解時(shí)，停止PSO算法切換至K-均值算法。

2)利用K-均值算法進(jìn)一步優(yōu)化。在第1階段尋找到的全局最優(yōu)解可以看作是K-均值的聚類中心。

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

5.1 定性分析

為了驗(yàn)證本文改進(jìn)算法的有效性，選取2個(gè)標(biāo)準(zhǔn)的基準(zhǔn)測(cè)試函數(shù)對(duì)本文改進(jìn)PSO算法和傳統(tǒng)PSO算法進(jìn)行測(cè)試。

Rosenbrock函數(shù)的非凸函數(shù):

(13)

Schaffer函數(shù)：

(14)

算法參數(shù)設(shè)置如下：種群規(guī)模為30，粒子維數(shù)n=10,迭代次數(shù)T=50。2類函數(shù)優(yōu)化結(jié)果如圖5所示。

圖4 PSO優(yōu)化K-均值算法流程圖

(a) Rosenbrock函數(shù)迭代過程圖

(b) Schaffer函數(shù)迭代過程圖

圖5(a)和圖5(b)給出了優(yōu)化算法和PSO算法分別在測(cè)試函數(shù)中迭代50次的曲線圖。

從圖5(a)中可以看出，優(yōu)化的算法雖在其收斂速度上和傳統(tǒng)PSO算法相差甚少，在50次迭代中都能很快接近最優(yōu)解，但在優(yōu)化精度上相較于傳統(tǒng)PSO算法有明顯提高；圖5(b)中，PSO算法在此測(cè)試函數(shù)中曲線有強(qiáng)烈的震蕩性，很難搜尋到最優(yōu)解，而優(yōu)化算法不僅在優(yōu)化精度上遠(yuǎn)比PSO算法精確，還在收斂速度上更勝于PSO算法。整體來說，本文提出的優(yōu)化算法有更強(qiáng)的搜索最優(yōu)解的能力。

5.2 定量分析

為驗(yàn)證算法的優(yōu)勢(shì)，在Matlab環(huán)境下對(duì)3幅圖像分別采用K-均值算法、PSOK和本文改進(jìn)算法進(jìn)行分割試驗(yàn)。圖片分割效果如圖6所示。

(a) Lena原圖 (b) K-均值算法 (c) PSOK算法 (d) 本文改進(jìn)算法

(a′) Orangutan原圖 (b′) K-均值算法 (c′) PSOK算法 (d′) 本文改進(jìn)算法

(a″) Flower原圖 (b″) K-均值算法 (c″) PSOK算法 (d″) 本文改進(jìn)算法

圖6第1行分別為L(zhǎng)ena原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和本文改進(jìn)算法實(shí)驗(yàn)結(jié)果，從圖6中可以看出，圖6(b)有輕微曝光現(xiàn)象，人臉細(xì)節(jié)分割不夠細(xì)致，圖6(c)在特征細(xì)節(jié)都有所凸顯，但稍微有些色差，圖6(d)在人物的帽頂、嘴唇、鼻尖、發(fā)梢以及肩部上的細(xì)節(jié)上更加清晰明顯，較大程度上還原了Lena原圖。第2行分別為Orangutan原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和本文改進(jìn)算法實(shí)驗(yàn)結(jié)果，由圖6可以看出，圖6(d′)可以看出在猩猩的毛發(fā)、鼻子以及背景圖的部分紋理最為清晰，整體輪廓清晰，色差較小。第3行分別為Flower原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和本文改進(jìn)算法實(shí)驗(yàn)結(jié)果，圖6(d″)的花瓣紋理、云彩背景干擾處理得更完善，還原度較高。綜上所述，本文改進(jìn)的算法提高了圖像分割的質(zhì)量。

在對(duì)3幅圖像進(jìn)行分割的同時(shí)，對(duì)不同算法的運(yùn)行時(shí)間也進(jìn)行了比較，比較結(jié)果如表1所示。

表1 不同算法運(yùn)行時(shí)間 單位：ms

圖像K-均值PSOK本文改進(jìn)算法Lena242827902311Orangutan227426352023Flower169818751574

從表1中可以看出，K-均值算法、PSOK算法、本文改進(jìn)算法的運(yùn)行速度有明顯不同，本文改進(jìn)的算法分別在圖像Lena、圖像Orangutan、圖像Flower的處理上用時(shí)最少。K-均值聚類算法具有簡(jiǎn)單、快速的特點(diǎn)。PSOK是一種融合算法，全局搜索能力強(qiáng)，但容易陷入局部最優(yōu)，運(yùn)行的時(shí)間較長(zhǎng)。本文改進(jìn)的算法通過結(jié)合PSOK算法和K-均值算法，并對(duì)權(quán)重系數(shù)和學(xué)習(xí)因子進(jìn)行改進(jìn)，能準(zhǔn)確尋找從全局搜索到局部尋優(yōu)的切換時(shí)機(jī)，提高了運(yùn)行效率。

6 結(jié)束語

本文提出了一種基于粒子群優(yōu)化算法和K-均值聚類的優(yōu)化算法，通過不斷調(diào)整并改進(jìn)粒子群權(quán)重系數(shù)和學(xué)習(xí)因子的策略促進(jìn)粒子快速收斂至全局最優(yōu)，改善了粒子群算法存在的收斂性與多樣性之間的矛盾。改進(jìn)后的算法既保留了K-均值聚類算法收斂速度快的優(yōu)點(diǎn)，又克服了粒子群算法易陷入局部最優(yōu)的缺點(diǎn)。

實(shí)驗(yàn)結(jié)果表明，PSO算法與K-均值算法的結(jié)合具有更好的穩(wěn)定性，改進(jìn)的算法提高了圖像分割的質(zhì)量和效率。粒子群優(yōu)化技術(shù)已經(jīng)開始活躍在眾多領(lǐng)域，在以后的研究中更是熱門話題。