基于改進(jìn)粒子群算法的多閾值圖像分割_武燕

1、Microcomputer Applications Vol. 27, No.5, 2011 技術(shù)交流 微型電腦應(yīng)用 2011年第27卷第5期 ·59·文章編號(hào):1007-757X(201105-0059-03基于改進(jìn)粒子群算法的多閾值圖像分割武 燕,張 冰摘 要:提出了一種改進(jìn)的粒子群算法,在初始化種群時(shí)采用相對(duì)基學(xué)習(xí)原理,以獲得較優(yōu)的初始候選解;在后期迭代過(guò)程中引入擴(kuò)張模型,使粒子不易陷入局部極小值點(diǎn),并將其用于多閾值圖像分割。由最大熵閾值法得到所要優(yōu)化的目標(biāo)函數(shù),用改進(jìn)的粒子群算法對(duì)其進(jìn)行優(yōu)化,使其能夠準(zhǔn)確并迅速的得到分割的最佳閾值組合,并用該閾值組合對(duì)圖像進(jìn)行分割。

2、將此分割結(jié)果與遺傳算法的多閾值分割結(jié)果相比較可以看出,該算法可更為準(zhǔn)確快速的實(shí)現(xiàn)圖像分割。關(guān)鍵詞:粒子群優(yōu)化算法;相對(duì)基學(xué)習(xí);擴(kuò)張模型;多閾值;圖像分割中圖法分類號(hào):TP301 文獻(xiàn)標(biāo)志碼:A0 引 言圖像分割是目標(biāo)識(shí)別的首要和關(guān)鍵步驟,其目的是將背景與目標(biāo)分離,為計(jì)算機(jī)視覺(jué)的后續(xù)處理提供依據(jù)。圖像分割的方法主要包括閾值法、邊緣檢測(cè)等1。其中,閾值分割因其快速簡(jiǎn)單使其成為圖像分割中最基本最常用的方法。常用的閾值法有最大熵閾值法、最大類間方差閾值法及最小誤差閾值法等。最大熵閾值法的原則使得總熵最大。所以確定閾值是閾值分割的關(guān)鍵,根據(jù)閾值的個(gè)數(shù),圖像閾值分割可以分為單閾值分割和多閾值分割。多閾值分

3、割問(wèn)題可轉(zhuǎn)化為一系列單閾值分割問(wèn)題來(lái)進(jìn)行解決,但此需要在全灰度范圍內(nèi)搜索一個(gè)最佳門限的組合,耗時(shí)較多,難于實(shí)際應(yīng)用。為了簡(jiǎn)化計(jì)算,可以利用遺傳、免疫等進(jìn)化算法來(lái)搜索最佳閾值2。而在本文中,將改進(jìn)的粒子群算法引入圖像分割中的多閾值選擇,對(duì)最大熵閾值法(ME進(jìn)行了優(yōu)化,使其能夠準(zhǔn)確并迅速地找到圖像分割的最佳閾值,對(duì)圖像進(jìn)行多閾值分割。1 基于最大熵的多閾值圖像分割最大熵閾值法的基本依據(jù)是使得圖像中目標(biāo)與背景分布的信息量最大,即通過(guò)測(cè)量圖像灰度直方圖的熵,找出最佳閾值。對(duì)于灰度范圍在0,1L 的圖像,其熵為:10ln L i ii H p p = (1i p 為灰度級(jí)i 出現(xiàn)的概率。對(duì)于灰度范圍為0

4、,1,.,1L 的圖像,設(shè)閾值t 將圖像分成兩部分, (/,(0(1i p h i N i L =,其中(h i 表示灰度值為i 的像素個(gè)數(shù),N 表示圖像中像素的總數(shù)。則圖像的熵01(H t H H =+的最佳閾值t 使得總熵取最大值。其中,100t i i P =,10000ln t i i i P P H =,和11L i i t P =,1111ln L i i i t P P H =。擴(kuò)展到多閾值分割,假設(shè)有c 個(gè)閾值,則圖像的熵為: 1201(,.,.c c H t t t H H H =+ (2 其中1100t i i P =,110000ln t i i i P P H =; 2

5、111t i i t P =,211111ln t i i i t P P H =;1c L c i i t P =,11ln c L i i i t c c P P H =;找出最佳閾值c 維向量12,.,c t t t 使得熵最大。 這樣,利用最大熵閾值法,圖像的多閾值分割的閾值求解問(wèn)題就可簡(jiǎn)單歸納為最佳閾值12,.c t t t 的優(yōu)化問(wèn)題。 2 改進(jìn)的粒子群算法 2.1 粒子群算法 粒子群優(yōu)化算法是由Eberhart 和Kennedy 共同提出的一種進(jìn)化計(jì)算算法3,4,這種算法源于對(duì)鳥群捕食行為的研究。粒子群算法中每個(gè)粒子就是解空間中的一個(gè)可行解,它是根據(jù)粒子自己的飛行經(jīng)驗(yàn)以及同伴的飛

6、行經(jīng)驗(yàn)來(lái)調(diào)整自作者簡(jiǎn)介:武燕(1986-,女,江蘇省常州市武進(jìn)區(qū),碩士研究生,研究方向:問(wèn)信號(hào)處理理論與技術(shù),212003;張冰(1967-,女,江蘇省無(wú)錫市,博士,教授、碩士研究生導(dǎo)師,研究方向:控制理論與控制工程、信號(hào)與信息處理、智能控制,212003Microcomputer Applications Vol. 27, No.5, 2011 技術(shù)交流 微型電腦應(yīng)用 2011年第27卷第5期 ·60·身的飛行。每個(gè)粒子在飛行過(guò)程中所經(jīng)歷的最好位置,叫做個(gè)體極值(pbest 。整個(gè)群體所經(jīng)歷的最好位置,叫做全局極值(gbest 。每個(gè)粒子都可以通過(guò)上述兩個(gè)極值來(lái)不斷更新自

7、己,從而產(chǎn)生新一代群體。粒子群算法的優(yōu)勢(shì)在于簡(jiǎn)單、易實(shí)現(xiàn)且參數(shù)較少,現(xiàn)已被廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、模糊系統(tǒng)控制以及其它遺傳算法的應(yīng)用領(lǐng)域。如果粒子的群體規(guī)模為M ,則第(1,2,.,i iM =個(gè)粒子的位置可表示為i X ,它所經(jīng)過(guò)的“最好”位置記為pbest i ,速度用i V 表示,群體中“最好”粒子的位置的索引號(hào)用g 表示,那么粒子i 將根據(jù)下面的公式來(lái)更新自己的速度和位置:(1(i i i V V c RAND pbest i X =×+××(2(i c rand gbest g X +×× (3i i i X X V =+

8、(4其中,1c ,2c 為常數(shù),稱為學(xué)習(xí)因子;(RAND 和(rand 是0,1上的隨機(jī)數(shù);為慣性權(quán)重。由式(3和式(4可知,越大,微粒的飛行速度越大,微粒將以比較大的步長(zhǎng)進(jìn)行全局探測(cè);越小,微粒的速度步長(zhǎng)越小,微粒趨于進(jìn)行精細(xì)的局部搜索。所以,在搜索過(guò)程中可以對(duì)進(jìn)行動(dòng)態(tài)調(diào)整:max minmax max iter iter =×。這樣則可以保證在算法開始時(shí),各微粒能以較大的速度步長(zhǎng)在全局范圍內(nèi)探測(cè)到較好的結(jié)果;在搜索后期,較小的值則能保證微粒在極點(diǎn)周圍做精細(xì)的搜索,從而使算法有較大的幾率以一定精度收斂于全局最優(yōu)值。學(xué)習(xí)因子1c ,2c ,通常取12 2.05c c =。最大迭代次數(shù)

9、max iter 和群體規(guī)模M 。另外,粒子在不斷根據(jù)速度調(diào)整自己的位置時(shí),還要受到最大速度max V 的限制,當(dāng)i V 超過(guò)max V 時(shí)被限定為max V 。本文在上述粒子群算法的基礎(chǔ)上對(duì)其進(jìn)行了一些改進(jìn),提出了一種基于擴(kuò)張模型的粒子群算法,并在算法中引入了相對(duì)基學(xué)習(xí),避免早熟現(xiàn)象,免遭“維數(shù)災(zāi)”的困擾提高了算法的有效性5。2.2 相對(duì)基初始化相對(duì)基學(xué)習(xí)(Opposition-Based Learning 是Tizhoosh 于2005年提出的一種新的機(jī)器學(xué)習(xí)算法。它的主要思想是:在求解優(yōu)化問(wèn)題時(shí),同時(shí)考察一個(gè)可行解和它的相對(duì)解,通過(guò)評(píng)價(jià)他們的優(yōu)劣來(lái)獲得較優(yōu)的候選解。一般來(lái)說(shuō),在對(duì)解無(wú)任何

10、先驗(yàn)知識(shí)的情況下,通常我們是采用隨機(jī)法初始化群體。本文將相對(duì)基學(xué)習(xí)嵌入到PSO 算法中,通過(guò)同時(shí)評(píng)價(jià)一個(gè)可行解及其相對(duì)解的優(yōu)劣,以獲得較優(yōu)的初始候選解,從而提高收斂速度。具體方法如下: (1隨機(jī)生成均勻分布的初始群體,1,2,.,i i X X V i N =; (2計(jì)算相對(duì)群體OX :分別對(duì)X 中的每個(gè)粒子按(3、(4式計(jì)算其相對(duì)粒子(包括位置和速度,構(gòu)成相對(duì)群體,1,2,.,i i OX OX OV i N =;id d d id ox L U x =+ (5 min max id d d id ov V V v =+ (6 其中d L 和d U 分別表示第d 維分量取值范圍的上下界(,i

11、d d d x L U ;每個(gè)粒子的速度限制在區(qū)間min max ,d d V V 內(nèi),一般地,min max d d V V =且max 0.1(d d d V U L =; (3最后根據(jù)個(gè)體適應(yīng)度值從X 和OX 中選擇N 個(gè)粒子作為初始種群 000,1,2,.,i i X X V i N =, 0ii i i i X X OX X OX =,優(yōu)于,否 0i i i i i V X OX V OV =,優(yōu)于,否(7 相對(duì)基初始化可以在一定程度上減少粒子群尋優(yōu)的時(shí)間,提高搜索效率和精度。 2.3擴(kuò)張模型 2.3.1 擴(kuò)張的定義 所謂擴(kuò)張模型是指粒子向前推移并保持運(yùn)動(dòng)方向不變,而運(yùn)動(dòng)粒子在空間中

12、發(fā)生了擴(kuò)張性的變化6。例如粒子在三維空間中從點(diǎn)A (1,1,1到B (2,2,2生了帶有強(qiáng)制性的擴(kuò)張。相應(yīng)的位置變化公式為:(1(x i x i x i +=+,本文中采用的為: (1(x i x i a x i +=+其中a 為擴(kuò)張因子。 2.3.2算法特點(diǎn) 擴(kuò)張算法具有以下的特性:強(qiáng)制性:即粒子被強(qiáng)行向前推移;不變性:被強(qiáng)行向前推移的粒子飛行方向不變;擴(kuò)張性:即粒子保持運(yùn)動(dòng)方向不變而各個(gè)維數(shù)的值發(fā)生成倍的擴(kuò)Microcomputer Applications Vol. 27, No.5, 2011 技術(shù)交流 微型電腦應(yīng)用 2011年第27卷第5期 ·61·大或縮小;同一

13、性:即各個(gè)維數(shù)的值同時(shí)并統(tǒng)一發(fā)生成倍的擴(kuò)大或縮小;有效性:為了提高粒子子的有效性,粒子的位置被最大位置和最小位置限制。為了加快搜索速度,發(fā)生擴(kuò)張的對(duì)象,不僅是處于歷史全局最優(yōu)位置的一個(gè)粒子,而是所有與最優(yōu)點(diǎn)適應(yīng)度相等的粒子。由于這些粒子處于停滯狀態(tài)且是來(lái)自各不同的方向,如果對(duì)它們同時(shí)采用擴(kuò)張,便產(chǎn)生以最優(yōu)點(diǎn)為中心向四周開花的“星火式”的變異效果。3 基于改進(jìn)粒子群算法的多閾值圖像分割3.1 實(shí)驗(yàn)算法粒子群算法尋找的是全局最小值,而本文所應(yīng)用的閾值選擇方法是最大化公式(1和(2.所以將適應(yīng)度函數(shù)定義為:(112,.c Fit H t t t = (8粒子群算法的步驟如下:(1相對(duì)基初始化所有的粒

14、子(群體規(guī)模為M 。在允許的范圍0,255內(nèi)隨機(jī)設(shè)置粒子的初始位置、速度、pbest 和gbest 。 (2評(píng)價(jià)每個(gè)粒子的適應(yīng)值。將位置取整,根據(jù)式(9計(jì)算每個(gè)粒子的目標(biāo)函數(shù),如果優(yōu)于pbest ,則pbest 被當(dāng)前位置替換;如果所有粒子的pbest 中有優(yōu)于gbest 的,則置為新的gbest 。 (3根據(jù)公式(3和(4調(diào)整粒子的速度和位置,檢查速度和位置是否在允許范圍之內(nèi),如果不在,將二者調(diào)整到允許范圍之內(nèi)。如果最優(yōu)解不變,則對(duì)位置進(jìn)行擴(kuò)張。 (4檢查終止條件,如果達(dá)到最大迭代次數(shù)就終止迭代,否則回到步驟(2。 3.2 實(shí)驗(yàn)結(jié)果 利用最大熵閾值法得到最佳多閾值圖像分割函數(shù)后,再用粒子群算

15、法對(duì)函數(shù)進(jìn)行優(yōu)化取得最優(yōu)分割閾值.本文中的處理對(duì)象為256×256的Lena 圖像,群體規(guī)模M =20,最大疊代次數(shù)max iter =100,慣性權(quán)重參數(shù)min 0.4=,max 0.9=,擴(kuò)張因子1a =。Lena 原始圖像(見(jiàn)圖2。實(shí)驗(yàn)結(jié)果如下,(見(jiàn)圖3圖4并將此算法與相同條件下的遺 傳算法相比較,如表1所示: 圖2. Lena原始圖像 圖3.粒子群最大熵4閾值 圖4.粒子群最大熵5閾值表1 圖像的多閾值分割最大熵四閾值 最大熵五閾值四閾值 最大熵 五閾值 最大熵 遺傳算法 75,100,174,213 16.6792 73,100,157,174,213 18.5795 粒子

16、群算法 81,112,168,245 17.3137 83,114,149,184,225 19.1461比較以上實(shí)驗(yàn)結(jié)果可以看出,基于粒子群的多閾值圖像分割方法可以找到更優(yōu)的閾值,且優(yōu)化結(jié)果穩(wěn)定,從而有利于計(jì)算機(jī)視覺(jué)的后續(xù)處理,體現(xiàn)了粒子群算法在圖像分割多閾值選取中的優(yōu)越性。4 結(jié)語(yǔ)基于粒子群的多閾值圖像分割方法能夠充分利用粒子群算法的特點(diǎn),較好地解決了多閾值選取中計(jì)算量過(guò)大的問(wèn)題。實(shí)驗(yàn)結(jié)果表明,粒子群算法簡(jiǎn)單、參數(shù)少、魯棒性好,與遺傳算法相比,具有操作方便、可靠性好、不易陷入局部極值等優(yōu)點(diǎn),完全能夠?qū)崿F(xiàn)滿意的多閾值圖像分割。參考文獻(xiàn):1章毓晉.圖像分割M.北京:科學(xué)出版社.2001. 2壬春柏,趙寶軍,何佩琨.基丁免疫遺傳算法的自適應(yīng)圖像分割方法J.紅外與激光,2004,33(2:178.181 3SHI Yu-hui, EBERHART R.Parameter selection in particle swarm optimizationA.Evolutionary Programming VII: Proceedings of El98c.New York :Springer-Verlag,1998.591-600. 4SHI Yu-hui, EBERHART R. Empirical study of particle swarm optimi