王丹　周錦程

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

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

【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 引言

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

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

1 相關(guān)概念

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

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

1.2 QPSO算法

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

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

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

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

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

Step 3 按照公式（9）重新計(jì)算每個(gè)（有變化）聚類(lèi)的均值（中心對(duì)象）。

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

2 基于QPSO聚類(lèi)算法的圖像分割

2.1 QPSO聚類(lèi)算法的圖像分割流程

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

4 結(jié)語(yǔ)

受K-均值聚類(lèi)算法的啟發(fā)，我們?cè)O(shè)計(jì)了基于QPSO的聚類(lèi)算法來(lái)處理圖像分割問(wèn)題。實(shí)驗(yàn)結(jié)果表明，相對(duì)于K-均值聚類(lèi)算法，QPSO聚類(lèi)算法在不需要選擇適當(dāng)?shù)某跏季垲?lèi)中心的情況下也能夠獲得精度比K-均值聚類(lèi)算法更高的聚類(lèi)中心，且基于QPSO聚類(lèi)算法的圖像分割方法比K-均值聚類(lèi)算法的圖像分割得到的分割圖像輪廓更為清晰，層次更為分明。

【參考文獻(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é)任編輯：楊玉潔]