基于粒子群優(yōu)化算法的閾值圖像分割研究

1、計算機應用 自動化技術與應用2007年第26卷第1o期 旦坐唑坐墅上恥韭壁旦墮一基于粒子群優(yōu)化算法的閾值圖像分割研究 汪筱紅-,須文波2(1.無錫廣播電視大學信息工程系,江蘇無錫214021;2.扛南大學信息工程系,江蘇無錫214021摘 要:研究將群體智能巾的粒了群優(yōu)化算法應用到圖像分割中,提r一種新的罔像分割算壯。新方法基于最佳熵閾值分割技 術,用粒子群優(yōu)化算法白適應選取分割閩值。仿真實驗針對Lella圖像分割問題,將遺傳箅法與粒子群優(yōu)化算法分別獨立運 行,對得到的聞俏以及均值、方差進行r比較,并將運行時問作為算法復雜度的泮價指標。統(tǒng)計結(jié)果晁示,淪文算怯不僅能 夠?qū)D像進行準確的分割.而且

2、運行時間明顯較短。仿真結(jié)果表明,基丁粒子群優(yōu)化的圖像分割算法是可行的、有效的。 關鍵詞:嗣像分割;粒子群優(yōu)化算法;遺傳算法中圄分類號:TP391.4l 文獻標識碼:B 文章編號:10037241(2007lO006卜03ThreshOld Irnage Segmentation Based On the ParticIe Sv組rm OptimizatiOn algor-thmw&NGao-h帥gl,xu win-b02(1.De恤0fC鋤叩u缸Sdence鋤dEngiIl嘟ing刪RadioAndTvUmversi吼m函2140210】iIla; 2.腳Lofc0吶sci跚ce鼬dE

3、n曲賦血g,Ji秈allunjver8時,wu】【i214021c抽詛Abstract:A novel algonthm based on panicle swa珊optlmization is presented in t|Iis papeL n shows that the algotlm presented in this paper can nnd better solutions with much lit【Ie complexity E1p甜Inent wi血吐le kna image sh。ws Ehat this me山od js feasible and etf色ctive.

4、Key wOrds:image s。gmentation,particle swarm optlmIzation algorithm.gene【ic algodmm1引言圖像分割是圖像處理和前輔稅覺中基本技術,是大多數(shù)圉 像分析和視覺系統(tǒng)的重要組成部分。圖像分割應用一種或多種運 算將圖像分成一些具有類似特性(如顏色,紋理,密度等的區(qū)域, 主要分為閾值方法,邊緣檢測法,區(qū)域跟蹤法等“。其中閾值方 法是圖像分割的常用方法。目前已經(jīng)提出了眾多的閾值圖像分割 方法,如最小誤差閾值法,最大類別方差法(0su法及最佳直方 圖熵法等。根據(jù)shaoo等人利用均勻性參數(shù)和形狀參數(shù)對標準圖 分割結(jié)果作酬自的評測結(jié)

5、論:吼su祛,最佳熵法,Johamserl法, Biue法和T鼢i矩不變法是較好的方法。以上所述的方法均涉及 到尋優(yōu)的問題,所【她口何快速有效地選取最優(yōu)閥值是基于閩值方 祛圖像分割技術的一個關鍵。粒子群優(yōu)化算法(Panicleswam Opn渤tion,PsO是 由Knedy和Eberhart于1995年提出的一種基于群智能(sWa徹收稿日期:20070521 IntcLugence的演化計算技術腳。PsO的優(yōu)點在于流程簡單易實現(xiàn), 算法參數(shù)簡潔,無需復雜的調(diào)整,因此,自算法提出以來。PsO 被迅速地應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制、數(shù)據(jù) 聚類等領域。實踐證明PSo算法在收斂速度和性

6、能上較之前的智 能優(yōu)化算法遺傳算法,都有了明顯的提高。本文將粒子群優(yōu)化算法應用到圖像分割中,提出了一種基 于最佳熵閾值分割技術的圖像分割算法,仿真實驗表明,新算法 不僅能夠?qū)D像進行準確的分割,而且與遺傳算法相比,能夠以 較少的計算代價得到最優(yōu)閾值。2粒子群優(yōu)化算法2.1算法原理粒子群算法將每個個體看作是D維搜索空間中的一個沒有 體積沒有質(zhì)量的粒子,在搜索空間中以一定的速度飛行。井根據(jù) 對個體和集體的飛行經(jīng)驗的綜合分析來動態(tài)調(diào)整這個速度。設群 體中第i個粒子為x=(ok,x。,它經(jīng)歷過的最佳位置為吾贏技術與應i贏7年第26黼10期 計算機應用 曼!苧e!皇鯉“!塑!P=m.R,j球。當前組成群

7、體的所有粒子經(jīng)歷過的最佳位置為:=蛾,已,j珞。粒子i的速度用Y=(7.t“表示。對每 一次迭代,粒子的進化方程為:vd(k+D=、(k+昭(也(k一x。(k+%q(kj一(1(的 (1 o(+D=+vdi=L衛(wèi)_,M d=LZ一;D (2 其中,cl和c2為加速常數(shù),它們使每個粒子向Pi和Pg位 置加速運動。rl,r2為f0,11范圍內(nèi)的隨機數(shù)。此外,粒子的速 度vi被最大蝴maX所限制。如果當前對粒子的加速將導致它在某維的速度vid超過該維的最大速度vmaXd,則該維的速度 被限制為該維的最大速度vInaxd。它決定r粒子在解空間的搜 索精度,如果vmx太高,粒子可能會飛過最優(yōu)解,如果V越

8、 太小,粒子陷人局部搜索空間而無法進行全局搜索。Yu smHui和Ru剛l Eberhar一首次提出了慣性權(quán)重 的概念,并對基本算法中的粒子速度更新公式(1進行了修正,如 式(3所示,以獲得更佳的壘局優(yōu)化效果:K時D=吼+啊啦飛塢瓴一k嘞 (3 其中為慣性權(quán)重(Iner幽w咄扭t,它繾粒子祭睜運動的 慣性,使其有能力探索新的區(qū)域。當個體察覺同事信念較好的時 候,它將進行適應陸地調(diào)整。其后的研究者普遍采用這種方式作 為系統(tǒng)粒子速度更新的基本方式,井在大量的應用問題中充分驗 證了其合理眭。式(3中的第一部分為粒子先前的速度乘個權(quán)值 進行加速,表示粒子對當前自身運動狀態(tài)的信任,依據(jù)自身的速 度進行憤

9、陸運動;第二部分為認知項(cogniuve Tem,表示粒 子本身的思考,即一個得到加強的隨機行為在將來的出現(xiàn)幾率增 大,從而實現(xiàn)一個增強學習過程。第三部分為社會項(social Tem,表示粒子間的信息共享與相互合作。2.2參數(shù)選擇粒子群優(yōu)化算琺模型中,cl反映了粒子飛行過程中所記憶 的最好位置對粒子飛行速度的影響,稱為“認知系數(shù)”;c2反映 了整個微粒群所記憶的最好位置對粒子飛行速度的影響,稱為 “社會學習系數(shù)”。大量實驗證明,c1與c2之和最好接近4,通常 取cIc2=2.O嚴7。由式(3可知,m越大,粒子的飛行速度越大,微粒將眈較久 的步長進行全局探測;m越小,微粒的速度步長越小,微粒

10、將趨 于進行精細的局部搜索。實驗發(fā)現(xiàn),當me【09,12時,算法具有較 理想的搜索陛能。所以,在搜索過程中可以對m進行動態(tài)調(diào)整:=%一警×k (41o 一 其中jtcmax為最大迭代次數(shù),這樣可以保證在算法開始 時,各微粒能以較大的速度步長在全局范圍內(nèi)探測到較好的種子; 在搜索后贛,較小的。值保證微粒在極點周圍做精細的搜索,從 而使算法有較大的兒率以一定精度收斂于全局最優(yōu)值。群體規(guī)模M越大,算法的尋優(yōu)能力越強,但計算量越大。本 文中選取M=20。3基于粒子群優(yōu)化算法的最佳熵閾值圖 像分割法3.1最佳熵閾值確定法嘲3.1.1單閾值分割將信息論中shallrIon熵概念應用于圖像分割時,

11、依據(jù)是使 圖像中目標與背景分布的信息量最大,通過分析圖像灰度直方圖 的熵,找到最佳閾值。對于灰度范圍為O,l,L一1的圖像, 假設圖中灰度級低于t的像素點構(gòu)成目標區(qū)域(0,灰度級高于 t的像素點構(gòu)成背景(B,那么各個灰度級在本區(qū)的分布概率為: o區(qū)巴,i二1,2 ,tIB區(qū)。尚 i二t+1,t+2, L 1i其中,量=P對于數(shù)字圖像中的目標和背景區(qū)域的熵分別為:比o=(斗7plgtP7p i_0,1.,t (5 m(,=哳,(1一P.(P,(1一時】i_t+1,t+2,L一1(6 則熵函數(shù)定必為:即=州。+m=岫(1一P+魯+等半 7 H=畫岫,H。=一B卸.當熵函數(shù)取得最大值時對應的灰度值t

12、幸就是所求的最佳閾 值,即t2AIg罌瑟“(3.1.2多閾值分割同一背景圖像上有多個物體,可采用多闡值分割。最佳熵自動門限祛適臺于多闋直(為k個閾值分割,此時:囀剛科n鼢塒一普式中s,s2,氣是分割閾值,且有%c s2c c sk。最佳閾值 s:,s:為僥總熵取最大值,即;8k“。冬鏟“小8,8:特別地,對于雙閾值情況,即為s.cs:,則有照燦盼阱n阱紫一紫警,最佳閾值g t為使總熵值取最大值,即:S5衄景。H￥,-R、 (11 3.2用于圖像分割的粒子群優(yōu)化算法的步驟將粒子群優(yōu)化算法應用于圖像分割中,通過尋找使得總體 熵值最大的聞值作為圖像的分割閾值,其具體步驟為:步驟l:初始化粒子群:設種

13、群規(guī)橫為M。隨機設置粒子的初 始位置和速度,并計算每個粒子的適應度值,其中單閾值采用式計算機應用 !宣墊堡墮查皇皇旦!墨蔓!查塑!塑 璺!塑日!皇PEI!型!墮(7,多閾值采用式(10。每個位置的P.設為初始位置,P.中的具 有最優(yōu)適應度值的位置設為Pg;步驟2:分別根據(jù)粒子群優(yōu)化算法的位置和速度更新公式調(diào) 整每一個粒子的位置和速度,得到新一代的粒子群,并評價每個 新粒子的適應度值,步驟3;更新新的P.和Pg,判斷終止條件,如果達到最大迭 代次數(shù)或者最優(yōu)解停滯不再變化,就終止迭代.否則回到步驟2; 步驟4:得到圖像的最冼分割閾值進行閾值分割。3.3仿真試驗結(jié)果及分析本試驗將基于粒子群算1弦的最

14、佳熵閾值圖像分割方法與基 于遺傳算法的最佳熵閾值圖像分割方法進行了對比。試驗對象為 圖l中的協(xié)圖像,兩種算法的種群規(guī)模均為20,最大迭代代數(shù)均為100。PS。算法的參數(shù)設置為c=c。=2.05,m作為迭代次數(shù) 的函數(shù)由1.2線性減小到0.9。GA的參數(shù)設置為交叉概率是O.8, 變異概率O.2,采用蒙特卡羅選擇。對兩種算法分別進行了10次 試驗。圖2和3分別為基于粒子群算祛的單閾值和雙聞值圖像分 割的結(jié)果。圖1Lena原始圈圖2單閾值分割結(jié)果圖3雙閾值分割結(jié)果 表1單閾值分割10次運行結(jié)果比較l 23567e 9lO均健 方差總運行時間A“赫舶腳甜甜船舶臂船盼“5t0越瑚盯甜惦瑚髓眠l也嘟 蚰基

15、盹謄 酷表1和袁絲臺出了兩種算法用于單聞值和多閾值圖像分割時10次獨立運行的結(jié)果。通過對運行結(jié)果的均值和方差進行統(tǒng)計比較, 并記錄lo次運行所需時間來衡量算法的計算量,可以看出粒子群 算法lO次運行的均值比遺傳算法更接近最優(yōu)值,且方差遠小于遺 傳箅法的結(jié)果,運行時【司也遠遠叫、于遺傳算法的結(jié)果。這充分說明 了粒子群算法的搜索精度,穩(wěn)定陛和速度均優(yōu)于相應的遺傳算法。 襄2雙閾值分割10次運行結(jié)果比較氐5舶糟柚¨¨,聃¨柏uJtml.髑舯瓣I盯n掃射舯7J“l(fā)&艟|鑫q¨赫耱旺nn¨盯l一。一皓*船赫赫"一奠蛔靠“TI一n-; :

16、4結(jié)束語 、 本文成功將群體智能算祛中的粒子群優(yōu)化算法應用于最佳 熵闡值圖像分割,并通過仿真實驗將其與基于遺傳算法的圖像分 割技術進行比較,結(jié)果表明新分割算法能更好地收斂到撮佳熵聞 值,并.臥萄i時間明顯少于相應的遺傳算法,且穩(wěn)定性也得到了較 大的提高。今后將進一步研究群體智能算法在圖像分割中的應用。 參考文獻:GONzALEz R.c,w00DS R.E.Digital irnage proo蝤ulg M1.3rd.ed.Addi”Wesley,L992.I 2】J.KENNEDY.BaIe bones part記1e gWa玎商c】.P代ceodm窖0f IEEEswam In坩ligen

17、ce symposium,2003:5357.(j龔聲蓉,劉純平,乇強數(shù)字圖像處理與分析M J.北京:清 華大學出版社2006.74】劉直芳,王運瓊,朱敏.數(shù)字圖像處理與分析【M】.北京:清華火學出版社2006.85】王玫,朱云龍,何小賢群體智能研究綜述f J】,計算機工程 2005.31(22:6】昊薇,基于最大模糊熵原理的多閾值圖像分割新算法【J】,系統(tǒng)工程與電子技術,2005,27(2:作者簡介:汪筱虹(1969一,女,江蘇無錫人,上海交通大學電子信息與電氣工程學院碩士、講師,研究方向:計算智能,圖像處理。(上接第31頁根據(jù)上式我們求的最大的歐氏距離和對應的時間偏移f。 如果我們選擇f=

18、o.4lo皇f枷,這時有叵:舊=擴O蝻=1.618l 再根據(jù)“找們可以得到這時最佳的錯誤概率為:只=Q(d 2n,2=Q(1r盯,2:2224×1035結(jié)束語本文討論了高斯信道條件下PPM調(diào)制uwB脈沖信號波形 確定的方法。包括確定信號持續(xù)時間和PPM信號的時間偏移。 信號持續(xù)時間通過對信號的頻譜要求來得到,而時間偏移可以 通過求信號歐氏距離的最大值來獲得。這樣確定的信號具有最 佳的錯誤概率。雖然本文僅討論在高斯信道的情況下,并且沒有考慮由于 多徑效應帶來的碼間干擾。但對進一步討論在多徑效應下PPM 調(diào)制uwB信號的脈沖波形參數(shù)確定具有一定的參考價值。參考文獻:1J黨梅梅.超寬帶無線

19、通信技術發(fā)展現(xiàn)狀f】.中國多媒體通 信,2006.(11:3436【2】J.D TAYLoR,EDITOR.An Tn缸州uc曲n枷ultm Wideband Radar Tcchno】og列M】,Boca Raton:cRc Press,1995【3龔江濤,尚琴,陳金鷹.uwB技術與應用【J】.山東通信技 術,2006.9(3:2022,26【4】F.RAMIREZMIRI,Es,on Perfonnance of Ultra wldeband s岫1ak i11Gau商an Noi鴕arld Der磷Mul廿patll,”【JEEE Trans.Veh.Techn01.20叭.50(1】:244249作者簡介:黃淑瓊(1972一 ,女,廣東高