李玉梅

(天津城市建設(shè)管理職業(yè)學(xué)院,天津市 300134)

基于蟻群模糊聚類算法的圖像分割研究

李玉梅

(天津城市建設(shè)管理職業(yè)學(xué)院,天津市 300134)

論文提出了一種基于蟻群動(dòng)態(tài)模糊聚類算法的計(jì)算機(jī)圖像分割方法,有效地利用蟻群算法的聚類分析能力,克服了FCM算法對(duì)初始化的敏感,動(dòng)態(tài)地確定了聚類數(shù)目和中心。然后利用蟻群聚類算法得到的模型進(jìn)行修改,再進(jìn)行模糊聚類彌補(bǔ)蟻群算法的不足。最后將該算法應(yīng)用到計(jì)算機(jī)圖像分割技術(shù)。對(duì)比實(shí)驗(yàn)表明,該算法實(shí)驗(yàn)表明該算法速度快、劃分特性好,可以準(zhǔn)確地分割出目標(biāo)。

計(jì)算機(jī)圖像分割;蟻群算法;模糊聚類

一、引言

本文用蟻群算法實(shí)現(xiàn)了基于改進(jìn)的目標(biāo)函數(shù)的模糊聚類,解決了動(dòng)態(tài)確定聚類數(shù)目問題和防止遺傳算法早熟現(xiàn)象的產(chǎn)生,并在計(jì)算機(jī)圖像分割實(shí)驗(yàn)中驗(yàn)證了這一算法的有效性。

二、蟻群算法

蟻群算法是意大利學(xué)者M(jìn).Dorigo等人受自然界中螞蟻覓食行為的啟發(fā)而發(fā)展起來的一種新的模擬進(jìn)化算法。該算法利用蟻群在搜索食物源的過程中所體現(xiàn)出來的尋優(yōu)能力來解決一些離散系統(tǒng)優(yōu)化中困難問題。蟻群算法的主要特點(diǎn)是通過正反饋、分布式協(xié)作來尋找最優(yōu)解,這是一種基于種群尋優(yōu)的啟發(fā)式搜索算法,能根據(jù)聚類中心的信息量把周圍數(shù)據(jù)歸并到一起,從而得到聚類分類,最終得到最優(yōu)解。

應(yīng)用蟻群算法解決問題的一般步驟如下:

1.初始化:給各參變量賦初值,相當(dāng)于螞蟻勻在蟻巢,等待出發(fā)。

2.優(yōu)化過程:螞蟻根據(jù)給定路徑長度和信息素強(qiáng)度做動(dòng)態(tài)選擇,并在運(yùn)動(dòng)中釋放信息素。

3.路徑?jīng)Q策:螞蟻記錄本次迭代的最佳路線。

4.終止條件:對(duì)于給定條件,若滿足,則算法停止;否則,跳轉(zhuǎn)步驟(2)。

三、模糊C均值聚類算法

模糊C均值聚類是模糊聚類算法中非常有效的一種,它能給出每個(gè)樣本隸屬于某個(gè)聚類的隸屬度,即使對(duì)于很難明顯分類的變量,模糊C均值聚類也能得到較為滿意的效果?？紤]一個(gè)樣本集合X=[xij],其中:i=1,2,…,n;j=1,2,…,m;n代表所含的樣本數(shù),m代表每個(gè)樣本中所含的變量數(shù)。此集合也可表示為:

式(1)中 ,xi={xj1,xj2,…xjm}j=1,2,…,m

將此集合依據(jù)一定的準(zhǔn)則用模糊聚類的方法分成c個(gè)模糊子集,這里c為事先給定的聚類個(gè)數(shù),所用的準(zhǔn)則一般是某個(gè)用來表征聚類的性能指標(biāo)的目標(biāo)函數(shù)。模糊聚類的結(jié)果可用隸屬度矩陣U來表示。U=[uij],uij的值在[0,1]之間,表示樣本集合中的元素xj屬于第i個(gè)聚類的程度,同時(shí)uij還必須滿足:

FCM算法的目標(biāo)函數(shù)一般為:

式(3)中,m′為影響隸屬度矩陣模糊化程度的指數(shù)權(quán)重。

求式(3)的極小化問題,可得到uij,vj。

FCM算法提供了一種迭代算法來近似地得到目標(biāo)函數(shù)的最優(yōu)化值。

模糊C均值算法確定隸屬度的具體步驟:

1.根據(jù)模糊聚類算法得到的類別數(shù)c作為分類個(gè)數(shù),允許誤差 Emax,t=1。

2.將利用蟻群算法得到的聚類中心點(diǎn)作為FCM初始化聚類中心wi(t),i=1,2,…,c。

3.計(jì)算隸屬度 uij(t),t=1,2,…c;j=1,2,…n。

4.修正所有聚類中心wi(t+1),i=1,2,…,c。

如果e

四、蟻群模糊聚類算法

蟻群算法主要是利用正反饋原理,當(dāng)進(jìn)化到一定代數(shù)后,就會(huì)由于最優(yōu)路徑的信息素不斷增強(qiáng)而使螞蟻大量聚集于少數(shù)的幾條路徑上,從而出現(xiàn)早熟、停滯現(xiàn)象。因此,單純的蟻群算法并不能完全有效實(shí)現(xiàn)模糊聚類。另外,當(dāng)聚類數(shù)與樣本數(shù)相等時(shí),顯然FCM算法的目標(biāo)函數(shù)為0,這已是最小值。這樣,當(dāng)聚類數(shù)不確定時(shí)就必須對(duì)目標(biāo)函數(shù)改進(jìn)用蟻群算法實(shí)現(xiàn)。應(yīng)用蟻群算法與FCM算法相結(jié)合進(jìn)行模糊聚類。一方面,蟻群算法的魯棒性(穩(wěn)定性)可以有效地克服FCM算法對(duì)初始化的敏感;另一方面,它的并行分布式計(jì)算可以加速收斂,提高聚類效率。最重要的是該算法的智能搜索和自適應(yīng)特點(diǎn)可以達(dá)到全局最優(yōu)?；谝陨戏治?用蟻群算法實(shí)現(xiàn)基于目標(biāo)函數(shù)的動(dòng)態(tài)模糊聚類的方法(AC-FCM算法)。

基于目標(biāo)函數(shù)的動(dòng)態(tài)模糊聚類的方法(AC-FCM算法)如下:

1.初始化

給定樣本點(diǎn)集X={x1,x2,…,xi,…,xn}

迭代次數(shù)N,特征矢量維數(shù)m,聚類半徑r,統(tǒng)計(jì)誤差ε,各信息素τij(0)=0,初始中心V;計(jì)算dij= ‖xi-vj‖。 (5)

2.優(yōu)化過程

(1)選擇機(jī)制:每個(gè)樣本點(diǎn)設(shè)置一個(gè)螞蟻.設(shè)簇半徑為r,計(jì)算各路徑上的信息素,若dij≤r,則τij(t)=1;否則pij(t)=0.(t)表示t時(shí)刻螞蟻i由 xi選擇到vj的概率:

其中S={Xs|dsjΦr,s=1,2…,j,j+1,…N},為螞蟻k下一步可以選擇的樣本點(diǎn)的下標(biāo)的集合。ηsj(t)為t時(shí)刻螞蟻i由xi選vj的啟發(fā)信息,可取。α和β分別為殘留信息和啟發(fā)信息的重要程度.

(2)更新機(jī)制

經(jīng)過Δt時(shí)刻,,t=t+Δt,,l=l+1,完成一次路徑搜索.則路徑(k,i)的信息素更新為:

其中ρ:為0～1之間的常數(shù),表示信息素的持久強(qiáng)度;1-ρ表示信息素的揮發(fā)程度。Δτij(t)表示第i個(gè)螞蟻在時(shí)間t～t+Δt之間,在邊(i,j)上的信息素改變量;Q是一常量,表示螞蟻完成一次路徑搜索所釋放的信息素總量.然后計(jì)算新的聚類中心V和樣本點(diǎn)到該新的聚類中心的距離dij。

3.路徑?jīng)Q策

若pijΕp0,則 Xi歸并到 Xj鄰域。令Cj={xi|dkjΦr,k=1,2,…J},Cj表示所有歸并到Xj鄰域的數(shù)據(jù)集合。根據(jù)下式求出理想的聚類中心:

其中:Xk∈Cj。

4.終止條件

聚類中心的第i個(gè)分量。計(jì)算總體誤差,再判斷ε≤ε0是否成立。成立輸出聚類個(gè)數(shù)c;若不成立,繼續(xù)迭代。

五、實(shí)驗(yàn)結(jié)果及分析

為了檢驗(yàn)AC-FCM算法的有效性,說明算法的性能,采用151 3 136的Lena(如圖1)所示,作演示實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為P4 3.0G,1G內(nèi)存,操作系統(tǒng)為W indow s XP Professional,實(shí)驗(yàn)效果圖采用Matlab7.0實(shí)現(xiàn)。取ρ=0.85,Q=100,N=50,ω=20,分別取C=3和C=6。蟻群算法圖像分割結(jié)果如圖2所示,AC-FCM算法圖像分割結(jié)果如圖3所示。

圖1 lena圖

圖2 蟻群算法的結(jié)果

圖3 AC-FCM算法的結(jié)果

實(shí)驗(yàn)結(jié)果表明,在聚類個(gè)數(shù)相同的情況,AC-FCM算法得到的圖像處理結(jié)果比蟻群算法的處理結(jié)果輪廓更加明顯,細(xì)節(jié)更加清晰,圖像分割的效果更好,隨著聚類個(gè)數(shù)的增多,更細(xì)微的邊緣信息也可以被檢測到。這說明算法使聚類表現(xiàn)出較優(yōu)的效果,有較大地可信度。

[1]高新波.模糊聚類分析及其應(yīng)用[M].西安:西安電子科技大學(xué)出版社,2004.

[2]劉文,鄭麗英.基于蟻群算法的模糊C均值聚類[J].太原科技,2009,(01).

[3]Zhe Yan,Han-ming Gu.Research of the Image Segmentation based on Ant Colony A lgo rithm[J].2009 10th ACIS International Conference on Software Engineering,A rtificial Intelligences,Netwo rking and Parallel/Distributed Computing,106-109.

A bs tra c t:This paper p roposes a method of computer image segmentation on the basis of the dy2 nam ic fuzzy clustering analysis of ant colony algorithm.The algorithm makes an effective use of the great clustering analysis ability,thus overcomes the sensitivity of fuzzy clustering method(FCM)to ini2 tialization and fixes the num ber and center of clustering dynam ically.Contrast tests show that this algo2 rithm is fast in calculation and accurate in target segmentation.

Ke y w o rd s:computer image segmentation;ant colony algorithm;fuzzy clustering analysis

Study on Com puter Im age Segm entation based on the Fuzzy Clustering A nalysis of A nt Colony A lgo rithm

L I Yu-mei

(Tianjin U rban Construction M anagement&Vocation Technology College,Tianjin 300134 China)

O 29

A

1673-582X(2011)02-0078-04

2010-10-20

李玉梅(1962-),女,天津市人,天津城市建設(shè)管理職業(yè)技術(shù)學(xué)院助講 ,從事計(jì)算機(jī)教學(xué)工作。