王丹　周錦程

【摘 要】量子粒子群優(yōu)化算法克服了傳統(tǒng)粒子群優(yōu)化算法中無法保證全局收斂、容易陷入局部最優(yōu)的缺點(diǎn)，是近年來優(yōu)化技術(shù)領(lǐng)域的一個研究熱點(diǎn)。本文結(jié)合當(dāng)前圖像分割中常用的K-均值聚類算法中的相關(guān)技術(shù)，設(shè)計了基于QPSO的聚類算法并將其用于圖像分割處理問題中。實驗結(jié)果表明：在圖像分割處理中，相對于K-均值聚類算法，QPSO聚類算法不僅不依賴于初始聚類中心的選擇，而且還能得到相對于K-均值聚類算法精度更高的聚類中心，其在圖像分割中的效果優(yōu)于通常的K-均值聚類算法。

【關(guān)鍵詞】PSO算法；QPSO算法；K-Means聚類；圖像分割

【Abstract】The quantum particle swarm optimization（QPSO） algorithm overcomes the shortcomings of the traditional particle swarm optimization algorithm which can not guarantee the global convergence， easy to fall into the local optimal. QPSO algorithm has become a research hotspot in the optimization technology filed in recent years. In this paper， combined with the relevant technology of the current commonly K-Means clustering algorithm in the image segmentation problem， we propose a new QPSO based clustering algorithm and we use it to the image segmentation filed. Experimental results show that， with respect to the K-means clustering algorithm， QPSO clustering algorithm does not rely on the choice of the initial cluster center， but compared with the K-means clustering algorithm， it can get higher precision clustering center. Thus， it is better than the usually K-means clustering algorithm in the image segmentation problem.

【Key words】PSO Algorithm； QPSO Algorithm； K-Means Clustering； Image Segmentation

0 引言

群體智能算法是基于群體行為對給定目標(biāo)進(jìn)行尋優(yōu)的一種啟發(fā)式搜索算法，自20世紀(jì)80年代出現(xiàn)這類算法以來，已經(jīng)得到了眾多研究人員的廣泛關(guān)注，并已發(fā)展成為優(yōu)化技術(shù)領(lǐng)域的一個熱點(diǎn)研究方向。粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法[1]是一種典型的群智能優(yōu)化算法，該算法于1995年由美國社會心理學(xué)家Kennedy博士和電氣工程師Eberhart博士在對社會型生物群體行為模擬的基礎(chǔ)上提出。由于PSO算法計算簡單、控制參數(shù)較少且易于實現(xiàn)，因此已被廣泛應(yīng)用于各種優(yōu)化計算領(lǐng)域[2-4]。因為PSO算法通常無法保證收斂于優(yōu)化問題的全局最優(yōu)解甚至于局部最優(yōu)解[5]，因此，國內(nèi)學(xué)者孫俊等人受量子力學(xué)等相關(guān)理論的啟發(fā)，利用量子測不準(zhǔn)原理來描述粒子的運(yùn)動狀態(tài)，并在PSO算法基礎(chǔ)上提出了具有量子行為和全局收斂性能的量子粒子群優(yōu)化（Quantum-behaved Particle Swarm Optimization，QPSO）算法[6]，該算法認(rèn)為處于量子束縛態(tài)的粒子可以以一定的概率密度出現(xiàn)在空間中的任何點(diǎn)，粒子可以在整個可行空間中進(jìn)行搜索且不會發(fā)散到無窮遠(yuǎn)處。

在圖像處理的研究中，人們通常會關(guān)注圖像中的某些局部內(nèi)容，如目標(biāo)或者前景，以便進(jìn)行后續(xù)的圖像處理，這種把圖像分成若干個特定的、具有獨(dú)特性質(zhì)的區(qū)域并提取出感興趣的目標(biāo)的技術(shù)和過程，稱為圖像分割。圖像分割是圖像分析的重要環(huán)節(jié)，經(jīng)過圖像分割所提取出的目標(biāo)可以廣泛應(yīng)用于圖像的語義識別、圖像搜索等眾多領(lǐng)域。

1 相關(guān)概念

1.1 標(biāo)準(zhǔn)PSO算法

由Kennedy和Eberhart所提出的PSO算法，其主要思想來源于對鳥類群體行為的研究。在利用該算法解決優(yōu)化問題的過程中，首先是要初始化一組隨機(jī)解，然后通過迭代方式來搜尋最優(yōu)值。在PSO算法中，每個優(yōu)化問題的解都被看做搜索空間中的一只鳥，稱為“粒子”。所有的粒子對應(yīng)著優(yōu)化問題的適應(yīng)值，粒子的速度決定了其飛行的方向和距離，粒子通過追尋群體中的最優(yōu)粒子來完成解空間的搜索，其具體的算法原理描述如下：

1.2 QPSO算法

由于PSO算法不能收斂于全局最優(yōu)解，甚至局部最優(yōu)解[5]，許多學(xué)者提出了大量的方法以改進(jìn)PSO算法的收斂性能，但實際情況表明，很多方法對PSO算法的改進(jìn)是有限的。孫俊等人在研究了Clerc等人關(guān)于收斂行為的研究成果后，從量子力學(xué)的角度出發(fā)，提出了具有量子行為的粒子群優(yōu)化算，即QPSO算法[6]。在該算法中，由于其采用了量子測不準(zhǔn)理論，因此粒子的位置和速度不能同時被精確測定，但由波函數(shù)的統(tǒng)計意義，可以通過波函數(shù)給定的概率密度函數(shù)來確定粒子在某個時刻出現(xiàn)的概率，該算法原理描述如下：

1.3 K-均值聚類算法

K-均值聚類算法又叫K-Means聚類算法，其算法原理是：首先隨機(jī)地從數(shù)據(jù)集中選取K個點(diǎn)作為初始聚類中心，然后計算各個樣本到聚類中的距離，把樣本歸到離它最近的那個聚類中心所在的類；然后計算新形成的每一個聚類的數(shù)據(jù)對象的平均值來得到新的聚類中心，如果相鄰兩次的聚類中心沒有任何變化，說明樣本調(diào)整結(jié)束，聚類準(zhǔn)則函數(shù)已經(jīng)收斂。K-均值聚類算法的一個特點(diǎn)是在每次迭代中都要檢查每個樣本的分類是否正確，若不正確，則需進(jìn)行調(diào)整，待全部樣本調(diào)整結(jié)束后，再修改聚類中心，進(jìn)入新一輪的迭代。如果在迭代過程中，所有的樣本均被正確分類，則聚類中心不會再有變化，這標(biāo)志著算法已經(jīng)收斂。K-均值聚類算法的算法流程可以描述如下：

Step 1 從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心。

Step 2 根據(jù)每個聚類對象的均值（中心對象），依據(jù)距離公式（8）計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)的對象進(jìn)行劃分。

Step 3 按照公式（9）重新計算每個（有變化）聚類的均值（中心對象）。

Step 4 計算誤差平方和準(zhǔn)則函數(shù)（10）的值，判斷是否滿足算法結(jié)束條件，若滿足，則算法結(jié)束。否則循環(huán)Step 2到Step 3，直到滿足算法結(jié)束條件為止（即每個聚類不再發(fā)生變化，或達(dá)到最大迭代次數(shù)）。

2 基于QPSO聚類算法的圖像分割

2.1 QPSO聚類算法的圖像分割流程

K-均值聚類算法是當(dāng)前流行的基于圖像顏色的圖像分割方法，在進(jìn)行QPSO算法聚類分割時，受K-均值聚類算法的良好性能的啟發(fā)，我們采用K-均值聚類算法中樣本到聚類中心的距離作為QPSO算法中聚類的度量標(biāo)準(zhǔn)，即：

Step 1 提取圖像的RGB通道的灰度級強(qiáng)度作為特征向量。

Step 2 初始化（聚類中心、個體最優(yōu)解、全局最優(yōu)解）。

Step 3 根據(jù)式式（11）計算聚類，根據(jù)式式（12）計算個體的適應(yīng)度函數(shù)值。

Step 4 計算并更新粒子群的平均最好位置mbest，更新個體最好位置pbest和全局最好位置gbest。

Step 5 根據(jù)式（6）計算隨機(jī)點(diǎn)p。

Step 6 根據(jù)式（7）更新粒子的中心向量。

Step 7 重復(fù)Step 2至Step 6，直到滿足迭代結(jié)束條件或最大迭代次數(shù)為止。

3 實驗結(jié)果

為驗證基于QPSO聚類算法的圖像分割性能，我們分別采用基于QPSO聚類算法和K-均值聚類分割算法對255×255的Lenna灰度圖和250×350的彩色嬰兒圖進(jìn)行實驗對比分析，實驗環(huán)境選用AMD Athon 645 4核3.10GHz處理器，內(nèi)存為4GB的PC機(jī)，其分割結(jié)果如圖1所示：

通過對以上兩組分割結(jié)果圖像的對比，我們看到QPSO聚類算法和K-均值聚類算法對原圖（a）和原圖（b）進(jìn)行的圖像分割都取得了比較良好的效果，且基于QPSO聚類算法的圖像分割結(jié)果輪廓更為清晰，層次更為分明。

表1給出了二種算法對Lenna灰度圖和彩色嬰兒圖分割的對比數(shù)據(jù)，從表1可以看出，K-均值聚類算法在分割時間開銷上相對于QPSO聚類算法有著一定的優(yōu)勢，且基于QPSO聚類算法在分割Lenna灰度圖和彩色嬰兒圖中，其誤差平方和項對應(yīng)的J值均小于相應(yīng)的K-均值聚類算法。此外，由于K-均值聚類算法對初始聚類中心的選取至關(guān)重要，若選取不得當(dāng)，可能會大大增加聚類的時間開銷，甚至在一定的迭代步內(nèi)可能無法得到滿足精度要求的解。而QPSO聚類算法對初始聚類中心沒有任何要求，且其可以得到比K-均值聚類算法精度更高的聚類中心。

4 結(jié)語

受K-均值聚類算法的啟發(fā)，我們設(shè)計了基于QPSO的聚類算法來處理圖像分割問題。實驗結(jié)果表明，相對于K-均值聚類算法，QPSO聚類算法在不需要選擇適當(dāng)?shù)某跏季垲愔行牡那闆r下也能夠獲得精度比K-均值聚類算法更高的聚類中心，且基于QPSO聚類算法的圖像分割方法比K-均值聚類算法的圖像分割得到的分割圖像輪廓更為清晰，層次更為分明。

【參考文獻(xiàn)】

[1]Kennedy J， Eberhart R C. Particle swarm optimization[C]. IEEE International Conference on Neural Networks，1995， 1942-1948.

[2]Cohen S， de Castro L N. Data clustering with particle swarms[C]. IEEE Congress on Evolutionary Computation， 2006： 1792-1798.

[3]Lope H S， Coelho L S. Particle swarn optimization with fast local search for the blind traveling salesman problem[C]. Fifth International Conference on Hybrid Intelligent Systems， 2005： 245-250.

[4]Nenortaite J， Simutis R. Adapting particle swarm optimization to stock markets[C]. Proceedings 5th International Conference on Intelligent Systems Design and Applications， 2005： 520-525.

[5]Van Den Bergh F. An analysis of particle swarm optimizers[D]. University of Pretoria， 2006.

[6]Sun J， Feng B， Xu W. Particle swarm optimization with particles having quantum behavior[C]. IEEE Congress on Evolutionary Computation， 2004： 325-331.

[責(zé)任編輯：楊玉潔]