基于隨機權重粒子群和K-均值聚類的圖像分割

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

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

基于隨機權重粒子群和K-均值聚類的圖像分割

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

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

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

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

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

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

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

1 K-均值聚類算法

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

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

當目標函數(shù)值取最小值時，令：

這時，找到的聚類中心為：

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

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

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

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

2 粒子群優(yōu)化

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

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

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

3 隨機權重粒子群優(yōu)化

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

圖2 RWPSO算法流程

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

RWPSO算法的權重系數(shù)w計算公式如下：

其中， (0,1)N 是標準正態(tài)分布的隨機數(shù)；σ是隨機權重的方差；μ是隨機權重的均值，計算方法為：

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

RWPSO算法流程如圖2所示。

為了說明RWPSO算法的有效性，本研究選取了四個標準測試函數(shù)對RWPSO算法和標準PSO算法進行了測試對比。4個測試函數(shù)的參數(shù)設置如表1所示。

表1 標準測試函數(shù)參數(shù)設置

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

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

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

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

表2 兩種算法的運行時間比較(ms)

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

4 RWPSOK算法

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

4.1 算法思想

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

4.2 粒子適應度計算

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

則將ix分配到j類。第i個粒子的適應度為：

4.3 算法切換時機的判斷

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

4.4 算法流程

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

圖4 RWPSOK算法流程

5 實驗結果和分析

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

圖5 三種算法實驗結果

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

在對四幅圖像進行圖像分割實驗的同時，本研究對K-均值、PSOK和本文RWPSOK三種算法的運行時間進行了比較，比較結果如表3所示。

表3 算法的運行時間比較(ms)

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

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

圖6 三種算法抗噪實驗結果

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

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

6 結 束 語

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

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

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

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

[3] 張 敏, 于 劍. 基于劃分的模糊聚類算法[J]. 軟件學報, 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]. 計算機應用研究, 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] 劉小丹, 牛少敏. 一種改進的 K-means聚類彩色圖像分割方法[J]. 湘潭大學自然科學學報, 2012, 34(2): 90-93.

[10] 賴玉霞, 劉建平, 楊國興. 基于遺傳算法的K均值聚類分析[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] 胡 捷, 崔長彩, 黃富貴. 基于動態(tài)改變權重粒子群算法的球度誤差評定[J]. 圖學學報, 2012, 33(5): 99-103.

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

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

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

[16] 時 顥, 賴惠成, 覃錫忠. 粒子群與K均值混合聚類的棉花圖像分割算法[J]. 計算機工程與應用, 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

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

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