鄔春學(xué)，劉訓(xùn)洋

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

?

改進(jìn)粒子群結(jié)合K-均值聚類(lèi)的圖像分割算法

鄔春學(xué)，劉訓(xùn)洋

(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093)

K-均值聚類(lèi)的分類(lèi)結(jié)果過(guò)分依賴(lài)于初始中心的選擇且容易陷入局部最優(yōu)。文中針對(duì)K-均值的缺陷，提出了一種基于隨機(jī)權(quán)重粒子群和K-均值聚類(lèi)的圖像分割算法RWPSO-KM。在算法開(kāi)始，利用隨機(jī)權(quán)重粒子群算法的全局搜索能力避免算法陷入局部最優(yōu)。然后根據(jù)公式計(jì)算種群多樣性執(zhí)行K-均值算法，利用K-均值算法的局部搜索能力實(shí)現(xiàn)算法的快速收斂。實(shí)驗(yàn)結(jié)果表明, RWPSO-KM與K-均值聚類(lèi)和PSOK相比具有更好的分割效果和更高的分割效率。

K-均值聚類(lèi)；隨機(jī)權(quán)重粒子群；圖像分割

圖像分割指的是根據(jù)灰度、顏色、紋理和形狀等特征把圖像劃分成若干互不交迭的區(qū)域，并使這些特征在同一區(qū)域內(nèi)呈現(xiàn)出相似性，而在不同區(qū)域間呈現(xiàn)出明顯的差異性[1]。圖像分割是圖像處理過(guò)程中的基礎(chǔ)環(huán)節(jié)，是由圖像處理到圖像分析的關(guān)鍵步驟[2]。聚類(lèi)[3-4]分析是數(shù)據(jù)挖掘的重要手段，聚類(lèi)算法應(yīng)用于圖像分割時(shí)能夠獲得較好的分割效果而得到了廣泛關(guān)注和應(yīng)用。

K-means[5]算法是該類(lèi)方法中比較常用的一種算法，這種方法首先選定某種距離度量作為元素間的相似性度量，然后確定某個(gè)評(píng)價(jià)聚類(lèi)劃分結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，在給出聚類(lèi)中心點(diǎn)后，用迭代的方法找出使準(zhǔn)則函數(shù)取極大值或極小值的最好聚類(lèi)結(jié)果。但是，K-均值算法的聚類(lèi)結(jié)果依賴(lài)于初始值的選取，并且基于梯度下降進(jìn)行搜索常常使算法陷入局部最優(yōu)。Kennedy 和Eberhart[6]于1995 年提出的粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法，由于其收斂速度較快[7]，需要設(shè)置和調(diào)整的參數(shù)較少，算法實(shí)現(xiàn)比較簡(jiǎn)單，一直以來(lái)受到學(xué)術(shù)界的廣泛重視。PSO 算法具有較強(qiáng)的全局尋優(yōu)能力，通過(guò)適當(dāng)調(diào)整權(quán)重系數(shù)，可以提高全局搜索能力，滿(mǎn)足不同的應(yīng)用場(chǎng)合。因?yàn)镻SO算法具有較強(qiáng)的全局尋優(yōu)能力而K-均值算法局部尋優(yōu)效果好，所以陶新民等[8-9]用PSO改進(jìn)K-均值(PSOK)來(lái)進(jìn)行圖像分割，取得了一定的效果。但如何將PSO算法和K-均值聚類(lèi)更好的結(jié)合發(fā)揮各自的優(yōu)勢(shì)[10-11]，仍是圖像分割研究的熱點(diǎn)問(wèn)題。

本文提出一種隨機(jī)權(quán)重粒子群算法和K-均值相結(jié)合的圖像分割方法RWPSO-KM。針對(duì)PSO算法缺點(diǎn)進(jìn)行改進(jìn)(RWPSO)并提出群多樣性測(cè)量方法來(lái)實(shí)現(xiàn)從RWPSO到K-means的切換。

1　K-均值聚類(lèi)算法

(1)

當(dāng)函數(shù)取最小值時(shí)，計(jì)算聚類(lèi)中心

(2)

其中,ni是第i組的數(shù)據(jù)點(diǎn)個(gè)數(shù)。然后不斷更新聚類(lèi)中心使同一個(gè)類(lèi)中的數(shù)據(jù)點(diǎn)相似性不斷增大，不同的類(lèi)之間的數(shù)據(jù)點(diǎn)相似性越來(lái)越小，從而達(dá)到聚類(lèi)目的。

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

粒子子群優(yōu)化算法最初是由Kennedy和Eberhart于1995年受人工生命研究結(jié)果啟發(fā), 在模擬鳥(niǎo)群覓食過(guò)程中的遷徙和群集行為時(shí)提出的一種基于群體智能的進(jìn)化計(jì)算技術(shù)。與其他進(jìn)化尋優(yōu)算法相類(lèi)似，PSO通過(guò)個(gè)體間的協(xié)作與競(jìng)爭(zhēng), 實(shí)現(xiàn)多維空間中最優(yōu)解的搜索。

PSO算法不像遺傳算法那樣對(duì)個(gè)體進(jìn)行選擇、交叉和變異操作, 而是將群體中的每個(gè)個(gè)體視為多維搜索空間中一個(gè)沒(méi)有質(zhì)量和體積的粒子，這些粒子在搜索空間中以一定的速度飛行, 并根據(jù)粒子本身的飛行經(jīng)驗(yàn)以及同伴的飛行經(jīng)驗(yàn)對(duì)自身的飛行速度進(jìn)行動(dòng)態(tài)調(diào)整, 即每個(gè)粒子通過(guò)統(tǒng)計(jì)迭代過(guò)程中自身的最優(yōu)值和群體的最優(yōu)值來(lái)不斷修正自己的前進(jìn)方向和速度大小, 從而形成群體尋優(yōu)的正反饋機(jī)制。PSO算法就是這樣依據(jù)每個(gè)粒子對(duì)環(huán)境的適應(yīng)度將個(gè)體逐步移到較優(yōu)的區(qū)域, 并最終搜索、尋找到問(wèn)題的最優(yōu)解。

設(shè)在d維搜索空間內(nèi)粒子i的位置為Xi=(xi1,xi2,…,xid)，速度為Vi=(vi1,vi2,…,vid)。在迭代過(guò)程中，粒子發(fā)現(xiàn)本地最優(yōu)解為 ，整個(gè)群體目前找到的全局最優(yōu)解 ，則迭代中粒子i的速度更新公式為

vij(t+1)=wvij(t)+c1r1(pij-xij(t))+c2r2(pgj-xij(t))

(3)

其中，w是慣性重量；c1、c2是加速度常數(shù)，取值在0～4之間，r1和r2為0～1之間均勻分布的隨機(jī)數(shù)。粒子 的位置更新公式為

xij(t+1)=xij(t)+vij(t+1),j=1,2,…,d

(4)

3　RWPSO算法

雖然PSO廣受歡迎，因?yàn)樗?jiǎn)單的概念、較少的參數(shù)、且易于實(shí)現(xiàn)，它也有過(guò)早收斂的問(wèn)題，特別是在大型復(fù)雜的問(wèn)題。觀察式(1)可以看出，粒子速度收斂快粒子飛行速度V(t)快速下降趨于0，即|V(t+1)|>|V(t)|的概率太小甚至為0，粒子活性缺失，使得粒子很難跳出局部極值區(qū)域，這就是PSO算法容易陷入過(guò)早收斂的原因。文獻(xiàn)[2]提出的ARPSO算法根據(jù)一定的評(píng)判標(biāo)準(zhǔn)來(lái)判定粒子活性的大小，當(dāng)粒子活性很小時(shí)就使粒子發(fā)散。但粒子活性評(píng)判標(biāo)準(zhǔn)的計(jì)算量遠(yuǎn)大于粒子速度和位置變化公式的計(jì)算量，因此該方法并不實(shí)用。

要使粒子速度發(fā)散概率較大必須降低粒子收斂速度，保持粒子活性和算法的多樣性。本文提出一種慣性權(quán)重因子在一定范圍內(nèi)隨機(jī)取值并且去掉隨機(jī)參數(shù)r1和r2的改進(jìn)PSO算法RWPSO。其速度更新公式為

vij(t+1)=w(t)vij(t)+c1(pij-xij(t))+c2(pgj-xij(t))

(5)

其中，w(t)是在一定范圍內(nèi)的隨機(jī)值，使其滿(mǎn)足c1+c2>2(w+1)，這樣粒子的速度有可能收斂也有可能發(fā)散，保證了種群的多樣性。

種群多樣性測(cè)量公式如下

(6)

4　RWPSO-KM 算法

4.1算法思想

RWPSO-KM 算法在圖像分割時(shí)主要分為兩個(gè)階段。算法前期使用RWPSO算法搜索整個(gè)解空間，尋找全局最優(yōu)解。當(dāng)RWPSO算法搜索到全局最優(yōu)解時(shí)，算法切換到K-means算法，并將搜索到的全局最優(yōu)解作為K-means聚類(lèi)的初始聚類(lèi)中心。在算法的后期階段，按照K-means算法進(jìn)行局部的尋優(yōu)。這樣RWPSO-KM算法既利用了 PSO算法的全局搜索能力，又保持了K-means算法的局部尋優(yōu)能力，同時(shí)克服了K-means算法容易陷入局部最優(yōu)的缺點(diǎn)。

4.2粒子適應(yīng)度計(jì)算

首先在數(shù)據(jù)點(diǎn)集合X中隨機(jī)選取m個(gè)數(shù)據(jù)點(diǎn)作為初始聚類(lèi)中心，作為優(yōu)化問(wèn)題的解空間(m個(gè)粒子)。當(dāng)聚類(lèi)中心確定后將集合X中n個(gè)數(shù)據(jù)點(diǎn)分配到這m個(gè)類(lèi)，設(shè)xi為集合X的第i個(gè)數(shù)據(jù)點(diǎn)，cj為第j個(gè)聚類(lèi)中心，當(dāng)‖xi-cj‖取最小值時(shí)將xi分配到第j類(lèi)。第i個(gè)粒子的適應(yīng)度為

(7)

圖1　RWPSO-KM算法流程圖

5　仿真實(shí)驗(yàn)

為驗(yàn)證算法的優(yōu)勢(shì)，在Matlab 環(huán)境下對(duì)3幅圖像分別采用K-means，PSOK和RWPSO-KM算法進(jìn)行了圖像分割實(shí)驗(yàn)。實(shí)驗(yàn)圖像為L(zhǎng)enna(圖像大小768 kB，512×512像素)；Baboon(圖像大小703 kB，500×480像素)；Barbara(圖像大小1.18 MB，720×576像素)。

圖2第1行分別為L(zhǎng)enna原圖、K-均值算法實(shí)驗(yàn)結(jié)果和PSOK算法實(shí)驗(yàn)結(jié)果、RWPSO-KM算法結(jié)果?？梢钥闯鲈谌宋镅劬兔济⒆齑胶拖掳鸵约懊绊?shù)念^發(fā)等處，PSOK算法和RWPSO-KM算法比K-均值算法有更加的分割效果，RWPSO-KM算法比PSOK算法和K-均值算法更加細(xì)致。圖2中第2行分別為Baboon原圖、K-均值算法實(shí)驗(yàn)結(jié)果和PSOK算法實(shí)驗(yàn)結(jié)果、RWPSO-KM算法結(jié)果?？梢钥闯鲈卺翎舻难劬捅亲拥忍?，PSOK算法和RWPSO-KM算法比K-均值算法有更好的分割效果，RWPSO-KM算法比PSOK算法和K-均值算法更加細(xì)致。圖2第3行分別為Barbara原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSO-KM算法結(jié)果?？梢钥闯?種算法分割效果差異不大，原因在于原圖中的物體和人物分別在顏色和形狀上存在明顯的差別，算法能較好地分割。

圖2　3種算法實(shí)驗(yàn)結(jié)果

在對(duì)3幅圖像進(jìn)行圖像分割實(shí)驗(yàn)的同時(shí)，對(duì)K-均值、PSOK 和本文RWPSO-KM 這3種算法的運(yùn)行時(shí)間進(jìn)行比較，比較結(jié)果如表1 所示。

表1　算法的運(yùn)行時(shí)間比較　　　　　/ms

如表1所示，雖然測(cè)試的圖像不同但對(duì)于每一幅圖像來(lái)說(shuō)本文提出的RWPSO-KM 算法比PSO算法和K-means算法的運(yùn)行時(shí)間都少，該算法效率占優(yōu)。

6　結(jié)束語(yǔ)

本文針對(duì)K-均值聚類(lèi)算法對(duì)初始聚類(lèi)中心選擇敏感，后期收斂速度慢一般以局部最優(yōu)結(jié)束的缺陷，用粒子群優(yōu)化算法RWPSO加以改進(jìn)。RWPSO-KM算法既保留了K-均值收斂速度快的優(yōu)勢(shì)，又能避免K-均值易陷入局部最優(yōu)的缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，RWPSO-KM算法比K-均值和PSOK算法在圖像分割效果和效率方面都有較大的提高。

[1]王愛(ài)民,沈蘭蓀. 圖像分割研究綜述[J]. 測(cè)控技術(shù), 2004, 19(5):1-6.

[2]許新征,丁世飛,史忠植,等. 圖像分割的新理論和新方法[J]. 電子學(xué)報(bào), 2010, 38(2A): 76-82.

[3]Fu K S, Mui J. A survey on image segmentation[J].Pattern Recognition,1981,13(1):3-16.

[4]Halkidi M, Batistakis Y,Vazirgiannis M. On clustering validation techniques[J]. Journal of Intelligent Information Systems, 2001, 17(2-3):107-145.

[5]陳金山,韋崗. 遺傳+模糊C-均值混合聚類(lèi)算法[J].電子與信息學(xué)報(bào), 2002, 24(2):210-215.

[6]Kennedy J, Eberhart R. Particle swarm optimization [C].Perth, Australia: Proceedings of the 1995 IEEE International Conference on Neural Networks, 1995.

[7]曾建潮,崔志華. 一種保證全局收斂的PSO算法[J]. 計(jì)算機(jī)研究與發(fā)展, 2004, 41(8): 1333-1338.

[8]陶新民,徐晶,楊立標(biāo),等. 一種改進(jìn)的粒子群和 K 均值混合聚類(lèi)算法[J]. 電子與信息學(xué)報(bào), 2010,32(1): 92-97.

[9]時(shí)顥,賴(lài)惠成,覃錫忠. 粒子群與K均值混合聚類(lèi)的棉花圖像分割算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013,49(21): 226-229.

[10]赫然,王永吉,王青,等. 一種改進(jìn)的自適應(yīng)逃逸微粒群算法及實(shí)驗(yàn)分析[J]. 軟件學(xué)報(bào), 2006, 16(12):2036-2044.

[11]劉靖明,韓麗川,侯立文. 基于粒子群的K均值聚類(lèi)算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2005, 25(6):54-58.

A Modified PSO Combined K-Means Clustering Algorithm for Image Segmentation

WU Chunxue, LIU Xunyang

(School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China)

The heavy dependence of the K-means clustering classification on selecting of the initial centers makes it easy to fall into local optimum. A RWPSO-KM based on random weight particle swarm algorithm and K-means algorithm is proposed. The global search capability of random weight particle swarm optimization algorithm is used first to avoid falling into local optimum, after which the population diversity is calculated according to the formula to execute K-means algorithm, and the local search of K-means algorithm is employed to achieve fast convergence. Experimental results show that RWPSO-KM is superior to K-means clustering and PSOK in segmentation effect and efficiency.

K-means clustering; random weight particle swarm; segmentation

10.16180/j.cnki.issn1007-7820.2016.08.027

2015-11-29

國(guó)家自然科學(xué)基金資助項(xiàng)目(61202376)

劉訓(xùn)洋(1991-)，男，碩士研究生。研究方向：圖像分割。

TP391.41

A

1007-7820(2016)08-093-04