基于圖論的蟻群算法在圖像分割的應(yīng)用

摘要：針對(duì)傳統(tǒng)的基于圖論的圖像分割方法分割效果不理想的問題，提出一種新的基于圖論使用蟻群算法分割圖像的算法。該算法基于圖論，考慮了圖像的灰度信息，采用蟻群算法的基本原理分割圖像，使得分割出目標(biāo)更為準(zhǔn)確。

關(guān)鍵詞：圖論；灰度；蟻群算法；

中圖分類號(hào)：TP391.41 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007—9599 （2012） 14—0000—02

一、引言

圖論是離散數(shù)學(xué)的一個(gè)分支，以圖為研究對(duì)象，研究頂點(diǎn)和邊組成圖形的數(shù)學(xué)問題?；趫D論的圖像分割是將圖像分割轉(zhuǎn)化為最優(yōu)化圖的劃分問題，相比于傳統(tǒng)的分割方法有著獨(dú)特的優(yōu)勢(shì)。

蟻群算法是由意大利學(xué)者于上世紀(jì)90年代提出來的，是分析螞蟻群體行為的基礎(chǔ)上提出來的一種新的仿生類進(jìn)化算法。蟻群算法在組合優(yōu)化問題求解方面獲得了成功的應(yīng)用，引發(fā)了學(xué)者們廣泛的關(guān)注。

蟻群算法逐次迭代正反饋的搜索目標(biāo)，將蟻群算法引入圖論中可降低算法復(fù)雜度，加快分割過程；同時(shí)蟻群算法具有較強(qiáng)的魯棒性，則將蟻群算法引入圖論中搜索過程中不需要進(jìn)行人工的調(diào)整，同時(shí)分割效果更加準(zhǔn)確。

二、圖論和蟻群算法的基本介紹

（一）圖論的基本介紹

基于圖論的圖像分割是將圖像映射為一幅無向權(quán)圖G=（V，E，W），其中V={v1，v2，…，vn}稱為頂點(diǎn)集，V中的元素vi稱為頂點(diǎn)，vi對(duì)應(yīng)于圖像中的像每個(gè)素點(diǎn)；E={eij}稱為邊集，E中的元素eij稱為邊，eij表示V中任意兩頂點(diǎn)之間的連線；W={wij}稱為權(quán)集，W中的元素wij稱為邊eij的權(quán)，wij表示頂點(diǎn)vi，vj之間的相似程度。

（二）蟻群算法的基本思路與步驟

蟻群算法是在分析螞蟻群體行為的基礎(chǔ)上提出來的。昆蟲學(xué)家觀察和研究發(fā)現(xiàn)，螞蟻具有在沒有任何提示的情況下，能夠找出從其窩巢到食物源的最短路徑，并且能夠隨著環(huán)境的變化而改變，適應(yīng)性搜索新的路徑，產(chǎn)生新的選擇。這是由于：在螞蟻搜索食物源時(shí)，能夠在爬過的路徑上釋放信息素，使得一定范圍內(nèi)的其它螞蟻能夠獲取信息素并影響這些螞蟻的行為。某條路徑上，信息素越多，螞蟻選擇該路徑的概率越大，從而又增加了道路上的信息素濃度。

表示螞蟻x從圖像的i行j列轉(zhuǎn)移到k行l(wèi)列的轉(zhuǎn)移概率，其中pq表示螞蟻x能夠允許轉(zhuǎn)移的城市，τijkl（t）表示路徑（ij，kl）上的信息素濃度，ηijkl表示路徑（ij，kl）的能見度，并有 ；

調(diào)整信息素濃度的公式為：

根據(jù)上面對(duì)圖論和蟻群算法的基本介紹，我們可以將蟻群算法引入圖論分割方法中，得出基于圖論使用蟻群算法分割圖像。

具體實(shí)施步驟為：

四、基于圖論的蟻群算法的改進(jìn)

對(duì)于圖論中，蟻群算法可以經(jīng)過一系列的改進(jìn)，從而使圖的分割更加清晰，更好分離出目標(biāo)和背景的同時(shí)計(jì)算量減小。

當(dāng)圖片像素點(diǎn)較多時(shí)，上述3基于圖論的蟻群算法計(jì)算量較大，假設(shè)一幅圖像有N個(gè)像素點(diǎn)，一群螞蟻中有n只螞蟻，則我們必須要重復(fù)n次步驟a到e，才能完成圖像的分割。因此，可以通過降低圖像的分辨率，使得圖中頂點(diǎn)的相似取值減少來減少計(jì)算量，也適當(dāng)?shù)拇只紙D片以減少步驟a到e中的運(yùn)算次數(shù)，可以大大的減少計(jì)算量。在3中僅僅考慮了圖的灰度屬性，可以同時(shí)考慮圖的亮度，紋理等屬性來改進(jìn)的蟻群算法，分析圖片，使得圖中兩頂點(diǎn)間相似度值更加準(zhǔn)確。

五、結(jié)論

利用蟻群算法進(jìn)行圖像分割較為精確，但是本算法耗時(shí)較長，通過改進(jìn)，可降低運(yùn)算量同時(shí)不影響圖像分割的精確度。

參考文獻(xiàn)：

[1]賀國光.ITS系統(tǒng)工程導(dǎo)論[M].中國鐵道出版社：181—184

[2]運(yùn)籌學(xué).《運(yùn)籌學(xué)》教材編寫組[M].清華大學(xué)出版社：251—253

[3]章毓晉.圖像處理和分析[M].清華大學(xué)出版社：179—215

[4]楊燕，靳蕃，Mohamed Kamel.一種基于蟻群算法的聚類組合方法[J].鐵道學(xué)報(bào)，2004，26，4：64—68

[5]M.Dorigo and T.Stutzle，“The ant colony optimization meta—heuristic：algorithms，applications and advances” in Handbook of Meta—heuristice，F(xiàn).glover and g.Kochenberger，Eds.Norwell，MA：Kluwer，2002，vol.57，International Series in Operations ResearchManagement Science.oo：251—285