李海洋， 文永革， 何紅洲， 李柏林

(1. 綿陽師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，四川 綿陽 621000；2. 北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100876；3. 西南交通大學(xué)機(jī)械工程學(xué)院，四川 成都 610031)

基于隨機(jī)權(quán)重粒子群和K-均值聚類的圖像分割

李海洋1,2， 文永革1， 何紅洲1， 李柏林3

(1. 綿陽師范學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，四川 綿陽 621000；2. 北京郵電大學(xué)計(jì)算機(jī)學(xué)院，北京 100876；3. 西南交通大學(xué)機(jī)械工程學(xué)院，四川 成都 610031)

K-均值聚類具有簡單、快速的特點(diǎn)，因此被廣泛應(yīng)用于圖像分割領(lǐng)域。但K-均值聚類容易陷入局部最優(yōu)，影響圖像分割效果。針對(duì)K-均值的缺點(diǎn)，提出一種基于隨機(jī)權(quán)重粒子群優(yōu)化(RWPSO)和 K-均值聚類的圖像分割算法RWPSOK。在算法運(yùn)行初期，利用隨機(jī)權(quán)重粒子群優(yōu)化的全局搜索能力，避免算法陷入局部最優(yōu)；在算法運(yùn)行后期，利用K-均值聚類的局部搜索能力，實(shí)現(xiàn)算法快速收斂。實(shí)驗(yàn)表明：RWPSOK算法能有效地克服 K-均值聚類易陷入局部最優(yōu)的缺點(diǎn)，圖像分割效果得到了明顯改善；與傳統(tǒng)粒子群與 K-均值聚類混合算法(PSOK)相比，RWPSOK算法具有更好的分割效果和更高的分割效率。

隨機(jī)權(quán)重；粒子群優(yōu)化；K-均值聚類；圖像分割

圖像分割是指將圖像分為不同區(qū)域，每個(gè)區(qū)域內(nèi)部的灰度、紋理、顏色等特征盡可能相同，而不同區(qū)域之間的特征盡可能不同[1]。圖像分割在圖像處理領(lǐng)域具有廣泛應(yīng)用，并涉及各種類型[2-3]。聚類是將一批現(xiàn)實(shí)或抽象的數(shù)據(jù)對(duì)象分組成為多個(gè)類或簇的過程，常常用于圖像分割[4]。通過聚類方法對(duì)圖像進(jìn)行分割，人們能夠識(shí)別圖像全局分布模式以及特征之間的相互關(guān)系[5]。

K-均值算法是解決聚類分析問題的經(jīng)典算法，具有收斂速度快，容易實(shí)現(xiàn)、局部尋優(yōu)能力強(qiáng)的特點(diǎn)[6]。但是，K-均值聚類在算法初始化階段難于給出一個(gè)明確的合適的K-均值，并且容易陷入局部最優(yōu)[7]。針對(duì)K-均值算法缺點(diǎn)，人們提出了許多改進(jìn)方法。Lin等[8]提出了一種基于水平直方圖的K-均值圖像檢索方法，提高了傳統(tǒng)K-均值聚類效率。劉小丹和牛少敏[9]提出了一種將K-均值聚類、蟻群算法以及分水嶺算法相結(jié)合的分割方法，能有效克服K-均值聚類數(shù)目依賴于初始值的選取的缺點(diǎn)。賴玉霞等[10]將遺傳算法與K-均值聚類相結(jié)合，使算法具有較好的全局收斂性。然而在實(shí)踐中，這些改進(jìn)算法仍然沒能很好解決K-均值聚類算法容易陷入局部最優(yōu)的問題，難以應(yīng)用在圖像分割領(lǐng)域。Kennedy和Eberhart[11]于1995年提出的粒子群優(yōu)化(particle swarm optimization，PSO)算法。PSO算法具有很強(qiáng)的全局尋優(yōu)能力，通過適當(dāng)調(diào)整權(quán)重系數(shù)，可以提高全局搜索能力，滿足不同的應(yīng)用場(chǎng)合。胡捷等[12]采用動(dòng)態(tài)改變權(quán)重粒子群算法并實(shí)現(xiàn)了在工件球度誤差的精確評(píng)定。韓鵬飛等[13]提出一種基于激勵(lì)原則的改進(jìn)離散粒子群優(yōu)化算法并實(shí)現(xiàn)在飛機(jī)裝配過程中的任務(wù)調(diào)度。史嬌嬌等[14]提出一種基于慣性權(quán)重的自適應(yīng)粒子群優(yōu)化算法并應(yīng)用于測(cè)試數(shù)據(jù)的自動(dòng)生成，可以有效地提高自動(dòng)生成測(cè)試數(shù)據(jù)的效率。因?yàn)镻SO算法具有很強(qiáng)的全局尋優(yōu)能力而K-均值聚類局部尋優(yōu)能力強(qiáng)，所以，陶新民等[15-16]采用PSO與K-均值相結(jié)合的算法(本文簡稱 PSOK)對(duì) K-均值算法進(jìn)行了改進(jìn)，并取得了一定成果。但是，如何將PSO算法的全局尋優(yōu)能力和K-均值算法的局部尋優(yōu)能力相結(jié)合，使之更有效地應(yīng)用于圖像分割，仍然是圖像處理和優(yōu)化技術(shù)研究的熱點(diǎn)問題。

本文借鑒文獻(xiàn)[15-16]的思想，提出一種基于隨機(jī)權(quán)重粒子群優(yōu)化(random weight particle swarm optimization，RWPSO)和K-均值混合的圖像分割算法RWPSOK。針對(duì)PSO算法缺點(diǎn)，利用RWPSO算法對(duì)PSO算法進(jìn)行了改進(jìn)，并測(cè)試了RWPSO的有效性，給出了RWPSO和K-均值相結(jié)合的方法和步驟。

1 K-均值聚類算法

K-均值聚類是MacQueen提出的解決聚類問題的經(jīng)典算法[5]。一幅圖像，可以看成是具有d維向量的數(shù)據(jù)點(diǎn)集合對(duì)該圖像進(jìn)行 K-均值分割，是對(duì)數(shù)據(jù)點(diǎn)集合Χ進(jìn)行聚類，目的是找到Χ的一個(gè)劃分使目標(biāo)函數(shù)的值最小。其中，是數(shù)據(jù)點(diǎn)jX到聚類中心點(diǎn)iC的歐式距離。

K-均值聚類算法通過不斷迭代，使目標(biāo)函數(shù)值取最小值，不斷更新聚類中心，使同一類中的數(shù)據(jù)點(diǎn)相似性不斷增大，不同的類之間的數(shù)據(jù)點(diǎn)相似性越來越小，從而達(dá)到聚類目的。其目標(biāo)函數(shù)為：

當(dāng)目標(biāo)函數(shù)值取最小值時(shí)，令：

這時(shí)，找到的聚類中心為：

其中，in是第i組分類的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

K-均值聚類算法流程如圖1所示。

圖1 K-均值聚類算法流程

K-均值算法主要存在如下缺點(diǎn)：算法首先必須給定明確的聚類數(shù)目K才能選定初始聚類中心，但在實(shí)踐中很難選擇適當(dāng)?shù)木垲悢?shù)目K；并且，在實(shí)踐中算法常常陷入局部最優(yōu)解而找不到全局最優(yōu)解[7]。

2 粒子群優(yōu)化

粒子群優(yōu)化作為一種進(jìn)化計(jì)算技術(shù)，它將每個(gè)優(yōu)化問題的解抽象成沒有質(zhì)量和體積的飛行在 N維空間的微粒，粒子i具有自己的飛行速度、空間位置以及一個(gè)被優(yōu)化函數(shù)決定的適應(yīng)度[11]。通過對(duì)自身飛行經(jīng)驗(yàn)的積累，粒子i能知道自己當(dāng)前發(fā)現(xiàn)的最好位置；通過對(duì)其他粒子的學(xué)習(xí)，粒子i能知道目前整個(gè)群體所發(fā)現(xiàn)的最好位置。PSO算法首先在解空間內(nèi)產(chǎn)生一個(gè)隨機(jī)解，將這個(gè)隨機(jī)解看成一群粒子，然后根據(jù)自身適應(yīng)度，通過迭代更新速度和位置，跟隨當(dāng)前最優(yōu)粒子在解空間搜索，直到找到最優(yōu)解。

粒子i的位置更新公式為：

在式(3)中，w是慣性權(quán)重，它代表粒子i下一次飛行速度對(duì)當(dāng)前速度的承襲； c1和 c2是學(xué)習(xí)因子，代表粒子i的自身學(xué)習(xí)能力和向優(yōu)秀同伴學(xué)習(xí)的能力。在PSO算法中，w、c1、 c2均為常數(shù)，w取值一般根據(jù)具體應(yīng)用指定； c1和 c2取值在0到4之間，通常c1= c2= 2.0；r1和r2為0到1之間均勻分布的隨機(jī)數(shù)。

3 隨機(jī)權(quán)重粒子群優(yōu)化

在優(yōu)化問題解決過程中，很多應(yīng)用往往通過調(diào)整粒子群優(yōu)化算法參數(shù)來提高算法性能，從而滿足應(yīng)用需求。其中，調(diào)整權(quán)重系數(shù)是其重要手段。標(biāo)準(zhǔn)PSO算法的權(quán)重是一個(gè)常數(shù)，代表PSO粒子對(duì)當(dāng)前速度的承襲度，通過恰當(dāng)?shù)恼{(diào)整能使粒子既具有很強(qiáng)的全局尋優(yōu)能力，又具有一定的局部尋優(yōu)能力。但是，在調(diào)整權(quán)重系數(shù)時(shí)，在保持全局尋優(yōu)和局部尋優(yōu)之間往往難以權(quán)衡，很難找到一個(gè)合適的常數(shù)作為權(quán)重系數(shù)。如果在算法進(jìn)化初期找不到最優(yōu)點(diǎn)，由于權(quán)重系數(shù)是固定值，這時(shí)往往會(huì)出現(xiàn)算法在最優(yōu)點(diǎn)附近振蕩而陷入局部最優(yōu)的情況。這也是PSOK圖像分割算法容易早熟收斂而陷入局部極值，圖像分割效果相對(duì)較差的一個(gè)重要原因，同時(shí)，這還會(huì)導(dǎo)致 K-均值算法迭代次數(shù)過多，降低聚類效率。

圖2 RWPSO算法流程

RWPSO算法將權(quán)重系數(shù)設(shè)為服從某種隨機(jī)分布的隨機(jī)數(shù)。這樣做的好處是：如果在進(jìn)化初期就已經(jīng)在最優(yōu)點(diǎn)附近，RWPSO算法可能會(huì)產(chǎn)生相對(duì)小的權(quán)重值，加快算法的收斂速度；如果在進(jìn)化初期找不到最優(yōu)點(diǎn)或在進(jìn)化過程中陷入局部極值，由于權(quán)重是隨機(jī)數(shù)，會(huì)使RWPSO算法在每次迭代過程中改變粒子速度，不斷嘗試而最終跳出局部最優(yōu)。因此，RWPSO算法比標(biāo)準(zhǔn)PSO算法具有更好的全局尋優(yōu)能力和尋優(yōu)效率。

RWPSO算法的權(quán)重系數(shù)w計(jì)算公式如下：

其中， (0,1)N 是標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)；σ是隨機(jī)權(quán)重的方差；μ是隨機(jī)權(quán)重的均值，計(jì)算方法為：

其中， μmax是隨機(jī)權(quán)重的最大值； μmin是隨機(jī)權(quán)重的最小值；r and (0,1)是0到1之間均勻分布的隨機(jī)數(shù)。

RWPSO算法流程如圖2所示。

為了說明RWPSO算法的有效性，本研究選取了四個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)對(duì)RWPSO算法和標(biāo)準(zhǔn)PSO算法進(jìn)行了測(cè)試對(duì)比。4個(gè)測(cè)試函數(shù)的參數(shù)設(shè)置如表1所示。

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)參數(shù)設(shè)置

在PSO算法中，取c1= c2= 2.0， w= 0.5；在RWPSO算法中，取 c1= c2= 2.0。測(cè)試結(jié)果如圖3所示。

圖3 4個(gè)測(cè)試函數(shù)的迭代過程圖

圖3(a)是RWPSO和PSO算法對(duì)Sphere函數(shù)測(cè)試的迭代過程圖。從圖3(a)可以看出，兩種算法在 100次迭代中都能很快接近最優(yōu)值，兩者性能相差不大。原因在于Sphere是一個(gè)簡單的單峰函數(shù)，很容易找到極值。圖3(b)是RWPSO和PSO算法對(duì)Griewank函數(shù)測(cè)試的迭代過程圖。從圖3(b)可以看出，在100次迭代中，RWPSO比PSO算法更接近全局最優(yōu)值，PSO算法陷入了局部最優(yōu)。圖3(c) 是RWPSO和PSO算法對(duì)Rastrigrin函數(shù)測(cè)試的迭代過程圖。從圖3(c)可以看出，兩種算法在 100次迭代中都能接近最優(yōu)值，并且都能在陷入局部最優(yōu)后跳出，繼續(xù)進(jìn)行全局尋優(yōu)，但RWPSO表現(xiàn)更好，能更快跳出局部最優(yōu)。圖3(d)是RWPSO和PSO算法對(duì)Schaffer函數(shù)測(cè)試的迭代過程圖。從圖3(d)可以看出，兩種算法在100次迭代中都能接近最優(yōu)值，但RWPSO表現(xiàn)更好，收斂速度更快。

為了比較RWPSO和PSO兩種算法的執(zhí)行效率，本研究記錄了以上測(cè)試實(shí)驗(yàn)的兩種算法執(zhí)行時(shí)間，如表2所示。

表2 兩種算法的運(yùn)行時(shí)間比較(ms)

從表2可以看出，在最大迭代次數(shù)為100情況下，RWPSO對(duì)4種函數(shù)的執(zhí)行時(shí)間均比PSO執(zhí)行時(shí)間少，表明RWPSO比PSO具有更高的執(zhí)行效率。

4 RWPSOK算法

通過第3節(jié)的測(cè)試分析，可以看出RWPSO算法不但比PSO算法具有更好的全局搜索能力，而且比PSO算法具有更高地執(zhí)行效率。在此基礎(chǔ)上，本研究提出了一種基于RWPSO和K-均值聚類的混合圖像分割算法RWPSOK。

4.1 算法思想

RWPSOK算法在進(jìn)行圖像分割時(shí)，主要將算法分為兩個(gè)階段。在算法的前期階段，使用RWPSO算法，搜索整個(gè)解空間，尋找全局最優(yōu)解。當(dāng)RWPSO算法搜索到全局最優(yōu)解或接近全局最優(yōu)解時(shí)，算法切換到 K-均值聚類，并將搜索到的全局最優(yōu)解作為 K-均值聚類的初始聚類中心。在算法的后期階段，按照 K-均值聚類流程完成局部尋優(yōu)。這樣，RWPSOK既利用了RWPSO算法全局搜索能力，又保持了 K-均值算法局部尋優(yōu)能力，同時(shí)也解決了 K-均值無法準(zhǔn)確給出聚類數(shù)目和容易陷入局部最優(yōu)的缺點(diǎn)，提高了算法的分割效率和準(zhǔn)確性。

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

在進(jìn)行圖像分割時(shí)，首先在數(shù)據(jù)點(diǎn)集合Χ中隨機(jī)選取m個(gè)數(shù)據(jù)點(diǎn)作為初始聚類中心，構(gòu)成優(yōu)化問題的解空間(m個(gè)粒子)。當(dāng)聚類中心確定后，可將集合Χ中n個(gè)數(shù)據(jù)點(diǎn)分配到這m個(gè)類，設(shè)ix為集合Χ的第i個(gè)數(shù)據(jù)點(diǎn)，jc為第j個(gè)聚類中心，如果，

則將ix分配到j(luò)類。第i個(gè)粒子的適應(yīng)度為：

4.3 算法切換時(shí)機(jī)的判斷

RWPSO算法在全局尋優(yōu)過程中，各個(gè)粒子的位置逐漸趨于一致，它們的適應(yīng)度也逐漸相同。設(shè)avgf 為粒子群平均適應(yīng)度，2δ為粒子群的群體適應(yīng)度方差。當(dāng)算法收斂時(shí)，所有粒子的適應(yīng)度從整體上不再變化，其群體適應(yīng)度方差2δ會(huì)縮小到一定范圍。當(dāng)2δ縮小到某個(gè)指定范圍時(shí)，表示算法已經(jīng)搜索到最優(yōu)解附近，沒有必要再繼續(xù)進(jìn)行全局尋優(yōu)，算法應(yīng)及時(shí)切換至K-均值聚類。群體適應(yīng)度方差反映的是粒子群中所有粒子的收斂程度，計(jì)算公式如下：

4.4 算法流程

RWPSOK算法的具體流程如圖4所示。

圖4 RWPSOK算法流程

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

在Intel Core i7 @ 2.67 GHz，Nvidia NVS 3100 M，4 GB內(nèi)存的環(huán)境下，采用Microsoft Visual Studio 2005在多幅圖像上對(duì) K-均值算法、PSOK和RWPSOK三種算法進(jìn)行了圖像分割實(shí)驗(yàn)。下面以其中四幅實(shí)驗(yàn)圖像為例給出實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)圖像1為Lena(圖像大小為732 KB；尺寸500×500像素)；實(shí)驗(yàn)圖像 2為 Penguins(圖像大小為 192 KB；尺寸256×256像素)；實(shí)驗(yàn)圖像 3為 Tulips(圖像大小為1.37 MB；尺寸800×600像素)；實(shí)驗(yàn)圖像4為Pearl Shoal(圖像大小為665 KB；尺寸477×477像素)。圖像分割實(shí)驗(yàn)結(jié)果如圖5所示。

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

圖5第一行分別為Lena原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSOK算法結(jié)果?？梢钥闯?，如圖中箭頭所指，在人物唇部和肩部，假發(fā)發(fā)梢以及帽頂鏡像等處，PSOK算法和RWPSOK比 K-均值算法有更佳的分割效果，RWPSOK算法比PSOK算法和K–均值算法更細(xì)致。圖5第二行分別為Penguins原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSOK算法結(jié)果?？梢钥闯?，如圖中箭頭所指，在企鵝的兩翼、胸部羽毛以及背景天空等處，PSOK算法和RWPSOK比K-均值算法有更佳的分割效果，RWPSOK算法比PSOK算法和K-均值算法更細(xì)致。圖5第三行分別為Tulips原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSOK算法結(jié)果?？梢钥闯觯N算法分割效果差異不大，原因在于原圖郁金香各花瓣、花莖、背景等分別在在顏色、形狀、紋理上存在較大差別，算法很好分割。圖5第四行分別為Pearl Shoal原圖、K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSOK算法結(jié)果?？梢钥闯?，如圖中箭頭所指，在瀑布幅面、巖石陰影和巖石紋理等處，PSOK算法和RWPSOK比K-均值算法有更佳的分割效果，RWPSOK算法比PSOK算法和K-均值算法更細(xì)致。

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

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

從表3可以看出，在不同的圖像分割情況下，K-均值算法運(yùn)行時(shí)間均低于 PSOK算法和本文RWPSOK算法，說明K-均值算法具有簡單、快速的優(yōu)點(diǎn)。相對(duì)于PSOK算法，本文RWPSOK算法運(yùn)行時(shí)間較少，本文RWPSOK算法效率占優(yōu)。

此外，為了說明算法的抗噪性能，本研究對(duì)Penguins圖像加入了不同的噪聲，在具有不同的噪聲情況下采用三種算法進(jìn)行了圖像分割實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如圖6所示。

圖6 三種算法抗噪實(shí)驗(yàn)結(jié)果

圖 6第一列是加入了不同噪聲的 Penguins圖像。這些噪聲依次為均值為0、均方差為20的高斯噪聲；含鹽量、含椒量均為0.02的椒鹽噪聲；參數(shù)為0.1的指數(shù)噪聲。圖6第二列到第四列分別是在不同噪聲情況下的K-均值算法實(shí)驗(yàn)結(jié)果、PSOK算法實(shí)驗(yàn)結(jié)果和RWPSOK算法實(shí)驗(yàn)結(jié)果。從圖6可以看出，在加入噪聲情況下，三種算法都能保證較好的視覺效果，說明三種算法都具有一定的抗噪性能。但是，與圖5第二行相比，三種算法的分割質(zhì)量均有所降低，說明三種算法都受到了噪聲的影響。并且，在加入高斯噪聲情況下(圖6第一行)，K-均值、PSOK和RWPSOK的實(shí)驗(yàn)結(jié)果沒有明顯差異，說明RWPSOK算法對(duì)高斯噪聲較為敏感。而在加入椒鹽噪聲和指數(shù)噪聲情況下(圖 6第二行和第三行)，RWPSOK算法比PSOK算法和K-均值算法更細(xì)致，說明RWPSOK算法保持了對(duì)椒鹽噪聲和指數(shù)噪聲的抗噪性能。

總而言之，RWPSOK算法能在效率略微降低情況下，取得比K-均值算法更優(yōu)的分割效果；在效率提高同時(shí)，比 PSOK算法具有更優(yōu)的分割效果。PSOK算法分割效果優(yōu)于 K-均值算法的原因在于PSOK算法在算法初期采用PSO優(yōu)化，提高了分割算法的全局尋優(yōu)能力；RWPSOK算法分割效果優(yōu)于PSOK算法和K-均值算法的原因在于RWPSOK在算法初期采用了隨機(jī)權(quán)重系數(shù)，既提高了分割算法的全局尋優(yōu)能力，又克服了算法PSO優(yōu)化陷入局部最優(yōu)的缺點(diǎn)。RWPSOK在效率上優(yōu)于PSOK算法的原因在于RWPSOK算法在陷入局部極值時(shí)能及時(shí)跳出。

6 結(jié) 束 語

本文針對(duì) K–均值聚類在圖像分割中存在的問題，采用RWPSOK算法加以了改進(jìn)。RWPSOK算法既保留了 K-均值收斂速度快的優(yōu)點(diǎn)，又克服了K-均值聚類易陷入局部最優(yōu)的缺點(diǎn)。實(shí)驗(yàn)結(jié)果表明，RWPSOK算法比K-均值聚類算法具有更好的聚類效果，能有效進(jìn)行圖像分割。與傳統(tǒng)PSOK算法相比，RWPSOK算法在圖像分割效果和效率方面都有了較大提高。

作為優(yōu)化計(jì)算技術(shù)，粒子群優(yōu)化已經(jīng)在眾多領(lǐng)域獲得了廣泛應(yīng)用。但粒子群優(yōu)化自身還存在許多不足，需要不斷加以改進(jìn)。同時(shí)，如何將粒子群優(yōu)化更好地應(yīng)用在圖像處理領(lǐng)域還需要進(jìn)一步加以研究。

[1] 林開顏, 徐立鴻, 吳軍輝. 快速模糊C均值聚類彩色圖像分割方法[J]. 中國圖象圖形學(xué)報(bào), 2004, 9(2): 159-163.

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

[3] 張 敏, 于 劍. 基于劃分的模糊聚類算法[J]. 軟件學(xué)報(bào), 2004, 15(6): 858-868.

[4] Han Jiawei, Kamber M. Data mining: concepts and techniques [M]. San Francisco: Morgan Kaufmann Publishers, 2001: 383-386.

[5] 李峻金, 向 陽, 蘆英明, 吳朔桐. 粒子群聚類算法綜述[J]. 計(jì)算機(jī)應(yīng)用研究, 2009, 26(12): 4423-4427.

[6] MacQueen J. Some methods for classification and analysis of multivariate observations [C]// Proceedings of the 5th Berkeley Symposium on Mathematics Statistic Problem, Berkeley, USA, 1967, 1(14): 281-297．

[7] Isa N A M, Salamah S A, Ngah U K. Adaptive fuzzy moving K-means clustering algorithm for image segmentation [J]. IEEE Transactions on Consumer Electronics, 2009, 55(4): 2145-2153.

[8] Lin C H, Chen C C, Lee H L, Liao J R. Fast K-means algorithm based on a level histogram for image retrieval [J]. Expert Systems with Applications, 2014, 41(7): 3276-3283.

[9] 劉小丹, 牛少敏. 一種改進(jìn)的 K-means聚類彩色圖像分割方法[J]. 湘潭大學(xué)自然科學(xué)學(xué)報(bào), 2012, 34(2): 90-93.

[10] 賴玉霞, 劉建平, 楊國興. 基于遺傳算法的K均值聚類分析[J]. 計(jì)算機(jī)工程, 2008, 34(20): 200-202.

[11] Kennedy J, Eberhart R. Particle swarm optimization [C]// Proceedings of the 1995 IEEE International Conference on Neural Networks. Perth, Australia, 1995, 4(2): 1942-1948.

[12] 胡 捷, 崔長彩, 黃富貴. 基于動(dòng)態(tài)改變權(quán)重粒子群算法的球度誤差評(píng)定[J]. 圖學(xué)學(xué)報(bào), 2012, 33(5): 99-103.

[13] 韓鵬飛, 孫占磊, 趙 罡. 改進(jìn)離散粒子群算法及其在飛機(jī)裝配任務(wù)調(diào)度中的應(yīng)用研究[J]. 圖學(xué)學(xué)報(bào), 2013, 34(1): 60-65.

[14] 史嬌嬌, 姜淑娟, 韓 寒, 王令賽. 自適應(yīng)粒子群優(yōu)化算法及其在測(cè)試數(shù)據(jù)生成中的應(yīng)用研究[J]. 電子學(xué)報(bào), 2013, 41(8): 1555-1559.

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

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

An Image Segmentation Algorithm Based on Random Weight Particle Swarm Optimization and K-means Clustering

Li Haiyang1,2, Wen Yongge1, He Hongzhou1, Li Bolin3
(1. School of Math & Computer Science, Mianyang Normal University, Mianyang Sichuan 621000, China; 2. School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China; 3. School of Mechanical Engineering, Southwest Jiaotong University, Chengdu Sichuan 610031, China)

K-means clustering is widely used in image segmentation due to its simplicity and rapidity. However, it is easy to fall into local optimum, leading to poor image segmentation results. In order to overcome this disadvantage of K-means, this article proposes a mixed image segmentation algorithm based on random weight particle swarm optimization (RWPSO) and K-means clustering. In the early stages of the algorithm running, it can avoid falling into local optimal using the global search capability of RWPSO. In the later stages of the algorithm running, it can achieve fast convergence using the local search capability of the K-means clustering. Experimental results show that RWPSOK algorithm can effectively overcome the weak global search capability drawback of the K-means clustering. It can significantly improve the image segmentation results. Compared with traditional particle swarm K-means clustering algorithm (PSOK), RWPSOK algorithm has better segmentation results and higher efficiency.

random weight; particle swarm optimization; K-means clustering; image segmentation

TP 391.41

A

2095-302X(2014)05-0755-07

2014-04-13；定稿日期：2014-06-12

四川省科技廳資助項(xiàng)目(2012JYZ013)；四川省教育廳資助項(xiàng)目(12ZB070)；綿陽師范學(xué)院資助項(xiàng)目(2013A12)

李海洋(1972–)，男，四川雙流人，副教授，碩士。主要研究方向?yàn)閳D形圖像處理、優(yōu)化技術(shù)。E-mail：lhy1301@126.com