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

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

?

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

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

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

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

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

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

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

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

1　K-均值聚類算法

(1)

當函數(shù)取最小值時，計算聚類中心

(2)

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

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

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

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

設(shè)在d維搜索空間內(nèi)粒子i的位置為Xi=(xi1,xi2,…,xid)，速度為Vi=(vi1,vi2,…,vid)。在迭代過程中，粒子發(fā)現(xiàn)本地最優(yōu)解為 ，整個群體目前找到的全局最優(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之間均勻分布的隨機數(shù)。粒子 的位置更新公式為

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

(4)

3　RWPSO算法

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

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

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

(5)

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

種群多樣性測量公式如下

(6)

4　RWPSO-KM 算法

4.1算法思想

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

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

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

(7)

圖1　RWPSO-KM算法流程圖

5　仿真實驗

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

圖2第1行分別為Lenna原圖、K-均值算法實驗結(jié)果和PSOK算法實驗結(jié)果、RWPSO-KM算法結(jié)果?？梢钥闯鲈谌宋镅劬兔济?、嘴唇和下巴以及冒頂?shù)念^發(fā)等處，PSOK算法和RWPSO-KM算法比K-均值算法有更加的分割效果，RWPSO-KM算法比PSOK算法和K-均值算法更加細致。圖2中第2行分別為Baboon原圖、K-均值算法實驗結(jié)果和PSOK算法實驗結(jié)果、RWPSO-KM算法結(jié)果?？梢钥闯鲈卺翎舻难劬捅亲拥忍帲琍SOK算法和RWPSO-KM算法比K-均值算法有更好的分割效果，RWPSO-KM算法比PSOK算法和K-均值算法更加細致。圖2第3行分別為Barbara原圖、K-均值算法實驗結(jié)果、PSOK算法實驗結(jié)果和RWPSO-KM算法結(jié)果?？梢钥闯?種算法分割效果差異不大，原因在于原圖中的物體和人物分別在顏色和形狀上存在明顯的差別，算法能較好地分割。

圖2　3種算法實驗結(jié)果

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

表1　算法的運行時間比較　　　　　/ms

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

6　結(jié)束語

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

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

[2]許新征,丁世飛,史忠植,等. 圖像分割的新理論和新方法[J]. 電子學報, 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-均值混合聚類算法[J].電子與信息學報, 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]. 計算機研究與發(fā)展, 2004, 41(8): 1333-1338.

[8]陶新民,徐晶,楊立標,等. 一種改進的粒子群和 K 均值混合聚類算法[J]. 電子與信息學報, 2010,32(1): 92-97.

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

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

[11]劉靖明,韓麗川,侯立文. 基于粒子群的K均值聚類算法[J]. 系統(tǒng)工程理論與實踐, 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

國家自然科學基金資助項目(61202376)

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

TP391.41

A

1007-7820(2016)08-093-04