使用蟻群算法進(jìn)行圖像分割報(bào)告

1、使用蟻群算法進(jìn)行圖像分割報(bào)告緒論蟻群算法是模擬螞蟻群體覓食行為的仿生優(yōu)化算法。本文利用蟻群算法進(jìn)行圖像分割，提取目標(biāo)圖像的邊緣路徑，概括來(lái)說(shuō)，是通過(guò)一定數(shù)量的人工螞蟻根據(jù)圖像的灰度值特性自由覓食，在覓食的過(guò)程中形成的信息素矩陣即代表了圖像的邊緣特征信息。1本例中蟻群算法的幾個(gè)要素一幅圖像中包括目標(biāo)、背景、邊界和噪聲等內(nèi)容，邊緣提取的目的是要找出體現(xiàn)這些內(nèi)容之間區(qū)別的特征量。區(qū)別目標(biāo)和背景的一個(gè)重要的特征是像素灰度，因此選用像素的灰度值作為主要特征。另外，邊界點(diǎn)或噪聲點(diǎn)往往是灰度值發(fā)生突變的地方，而該點(diǎn)處的梯度體現(xiàn)出這種變化，是反映邊界點(diǎn)與背景或目標(biāo)區(qū)域內(nèi)點(diǎn)區(qū)別的重要特征。因此，在定義可見(jiàn)度因數(shù)

2、時(shí)，一定要把梯度值作為首要特征。1.1 確定初始螞蟻數(shù)目蟻群算法是一種隨機(jī)搜索算法，它通過(guò)多個(gè)候選解組成群體的進(jìn)化過(guò)程來(lái)尋求最優(yōu)解，在這個(gè)進(jìn)化過(guò)程中，既需要每個(gè)個(gè)體的自適應(yīng)能力，更需要群體的相互協(xié)作，這個(gè)相互協(xié)作，通過(guò)個(gè)體之間的信息交流來(lái)完成。蟻群的數(shù)量越多，算法的全局搜索能力以及算法的穩(wěn)定性越高，但是若螞蟻數(shù)目較大，會(huì)使大量的曾被搜索過(guò)的解上的信息量的變化比較平均，信息正反饋的作用不明顯，搜索的隨機(jī)性雖然得到了加強(qiáng)，但收斂速度減慢，在本例中，螞蟻數(shù)目取為圖像像素?cái)?shù)的開(kāi)方值。1.2 螞蟻轉(zhuǎn)移概率在蟻群算法的第n步，某一點(diǎn)處的螞蟻轉(zhuǎn)移到像素點(diǎn)（i,j）的概率主要由該點(diǎn)信息素濃度和能見(jiàn)度因數(shù)來(lái)決定

3、，其計(jì)算公式為【1】：(n)Pi,j（MNi,j廣（）：（i,j）：j-.i1其中，Q表示螞蟻k下一步容許去的城市集合。p2與d,j成正比，J為從像素點(diǎn)i,j的信息素因數(shù)，北為像素點(diǎn)i,j的能見(jiàn)度因數(shù)，%B參數(shù)分別反映了螞蟻在轉(zhuǎn)移過(guò)程中，像素點(diǎn)所累積的信息素和像素點(diǎn)的啟發(fā)信息，在螞蟻選擇轉(zhuǎn)移時(shí)的相對(duì)重要性。a為信息啟發(fā)因子，反映了螞蟻在向另一個(gè)像素點(diǎn)轉(zhuǎn)移時(shí)，這目標(biāo)像素點(diǎn)所累積的信息素在指導(dǎo)蟻群搜索中選擇像素點(diǎn)轉(zhuǎn)移時(shí)的相對(duì)重要程度，反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度。a值越大，螞蟻選擇以前走過(guò)的像素點(diǎn)的可能性越大，搜索的隨機(jī)性越弱。a值過(guò)大也可能使蟻群的搜索過(guò)早陷于局部最優(yōu)。本例中a值取

4、為1。B為期望值啟發(fā)式因子，反映了螞蟻在搜索過(guò)程中啟發(fā)信息在指導(dǎo)蟻群搜索中的相對(duì)重要程度。期望值啟發(fā)因子B的大小反映了蟻群在道路搜索中先驗(yàn)性、確定性因素作用的強(qiáng)度，其值越大，螞蟻在某個(gè)局部點(diǎn)上選擇局部最短路徑的可能性越大。雖然它使搜索的收斂速度得以加快，但蟻群在最優(yōu)路徑的搜索過(guò)程中隨機(jī)性減弱，容易陷入局部最優(yōu)。本例中B值取為0.1。1.3 信息素矩陣的更新蟻群有著令人驚奇的信息系統(tǒng)，研究發(fā)現(xiàn)，當(dāng)螞蟻外出覓食或在回巢穴的途中，它們都會(huì)釋放一種特殊的信息素氣味來(lái)標(biāo)識(shí)行進(jìn)的軌跡，螞蟻用這種獨(dú)有的無(wú)聲語(yǔ)言來(lái)設(shè)置類似人類路標(biāo)的蟻蹤。螞蟻在尋找食物過(guò)程中，在它們經(jīng)過(guò)的地方所留下的信息素，不僅能被同一蟻群中

5、的其他螞蟻感知到，而且其強(qiáng)度也能被感知，螞蟻會(huì)傾向于沿信息素濃度較高的方向移動(dòng)，而移動(dòng)過(guò)程又會(huì)留下新的信息素，對(duì)原有的信息素進(jìn)行加強(qiáng)。信息素的更新策略主要有蟻密模型、蟻量模型和蟻周模型。其中，蟻周模型用的是全局信息，即完成一次循環(huán)對(duì)所經(jīng)過(guò)的整條路徑上的信息素進(jìn)行更新，整體性較強(qiáng)；而蟻量和蟻密兩種模型用的是局部信息，即螞蟻每完成一步后就對(duì)剛經(jīng)過(guò)的路徑上的信息素進(jìn)行更新。在本例算法中，像素點(diǎn)之間的信息素變化參考的是蟻密模型的思想，但是在具體的計(jì)算方法上又結(jié)合了本例的特點(diǎn)。即當(dāng)每一只螞蟻完成一次移動(dòng)以后進(jìn)行一次信息素的更新，具更新公式為：TiJn）=（1_P）黑%Jn出+PxAtxij）父Af+4j

6、（n4'）x1-At其中，勒（？是新信息素濃度，和（7）是舊信息素濃度，1,j是能見(jiàn)度因數(shù)?？紤]到片和Ae均為矩陣，式中的乘法表示的均為矩陣中元素分別相乘。At在所有螞蟻完成一次移動(dòng)以后置零。1.4 螞蟻的記憶值當(dāng)某兩個(gè)像素點(diǎn)的信息素濃度較高時(shí)，某只螞蟻很有可能會(huì)在這兩個(gè)像素點(diǎn)之間進(jìn)行往復(fù)運(yùn)動(dòng)，造成了算法的局部收斂。為了克服這一缺陷，本文定義了螞蟻的記憶值，記憶值的大小要小于某只螞蟻移動(dòng)的總步數(shù)，從而保證當(dāng)螞蟻移動(dòng)一定步數(shù)以后，會(huì)消除某一時(shí)間點(diǎn)之前的記憶”。螞蟻記憶值長(zhǎng)度的定義公式為：memory_length=B父（0.3MA）+0.85父A其中，A的值可以根據(jù)圖像的大小人為設(shè)定，本

7、文中取為40,B為01之間的隨機(jī)值。在本例中，每只螞蟻的記憶值長(zhǎng)度相等。當(dāng)螞蟻準(zhǔn)備移動(dòng)時(shí)，首先檢查其臨近點(diǎn)中有沒(méi)有記憶值中的像素點(diǎn)，如果存在，則將其移動(dòng)至該像素點(diǎn)的概率置零。若該螞蟻臨近的八個(gè)像素點(diǎn)都包含在了螞蟻記憶值當(dāng)中，那么還需要對(duì)螞蟻臨近點(diǎn)的移動(dòng)概率進(jìn)行人為設(shè)置。當(dāng)螞蟻移動(dòng)到某一像素點(diǎn)時(shí)，需要將該像素點(diǎn)記錄到螞蟻的記憶值當(dāng)中，若螞蟻的記憶值溢出，則還需要進(jìn)行數(shù)值的平移處理。2用于圖像分割的蟻群算法的流程N(yùn)ONO忘記已移動(dòng)螞蟻2.1 初始化過(guò)程導(dǎo)入圖片后，首先將RGB真彩圖轉(zhuǎn)換為灰度值圖，然后將K只螞蟻隨機(jī)地分散在這張灰度值圖像上，圖像大小為MIXM2,初始螞蟻的數(shù)量為圖像面積的開(kāi)方值，如

8、下式：K=JM1父M2。同時(shí)，信息素矩陣也被初始化為.init=0.001其次，我們需要進(jìn)行的是能見(jiàn)度因數(shù)”的確定。在本例中，將能見(jiàn)度因數(shù)”定義為：i,j=；Vc(Ii,j)其中Z=£1Mlzj：M2Vc(Ii,j),Vc(i,j)是臨近像素灰度值的一個(gè)函數(shù)，它被定義為2：i書,j書廣4I1214TI2j4TI124I-IVc(Ii,j)=100'i_2,j_11id2,j+/ii_2"由1i42,j_1/Ui_1,j_21i41,j42/甲i,j1,jT書,j4+(一書T,4+Qi,j&一L/4+Qi,j一L,j書其中I為每個(gè)像素點(diǎn)的灰度值。本例中，我們要

9、尋找的是兩只老虎的邊界，邊界點(diǎn)的特點(diǎn)是該點(diǎn)與周邊幾個(gè)點(diǎn)的像素灰度值差別較大，所以這里我們定義了一個(gè)能夠反映灰度值差別的函數(shù)Vc,當(dāng)該值較大時(shí)，說(shuō)明該像素點(diǎn)為老虎邊界點(diǎn)的概率就大一些。計(jì)算完能見(jiàn)度因數(shù)后，本文又定義了一個(gè)新的參數(shù)，螞蟻的記憶值。該值的設(shè)定是為了防止螞蟻在信息素濃度較高的兩個(gè)像素點(diǎn)進(jìn)行往復(fù)移動(dòng)，造成算法的局部收斂。螞蟻記憶值的大小計(jì)算也遵從一定的隨機(jī)性，如下式：memory_length=8m(0.3mA)+0.852其中，A的值可以根據(jù)圖像的大小人為設(shè)定，本文中取為40,B為01之間的隨機(jī)值。2.2 移動(dòng)過(guò)程本文共進(jìn)行了900次移動(dòng)過(guò)程，在每一次的移動(dòng)過(guò)程中，被放置的K只螞蟻都會(huì)

10、在概率p：7的指導(dǎo)作用下選擇下一個(gè)目的地(像素點(diǎn))，而該螞蟻的目標(biāo)像素點(diǎn)必須臨近其所在的像素點(diǎn)。存在一個(gè)問(wèn)題是當(dāng)螞蟻在某一像素點(diǎn)時(shí)，它可以移動(dòng)到哪些像素點(diǎn)。在這里，我們既可以設(shè)為鄰近的四個(gè)像素點(diǎn)也可以設(shè)為鄰近的八個(gè)像素點(diǎn)。在本例中，螞蟻在某一像素點(diǎn)時(shí)，可移動(dòng)到的像素點(diǎn)為鄰近的八個(gè)像素點(diǎn)【3】。在螞蟻選擇目標(biāo)像素點(diǎn)之前，首先要進(jìn)行圖像的邊緣檢測(cè)，因?yàn)槲浵伿遣荒軌蛞苿?dòng)到圖像之外的，因此需要將圖像外的點(diǎn)的信息素濃度置零。另外還需要檢查在螞蟻的記憶值中已經(jīng)包含了哪些像素點(diǎn)，也要給以去除。如果鄰近的八個(gè)像素點(diǎn)都包含在了螞蟻記憶值當(dāng)中，那么還需要對(duì)螞蟻臨近點(diǎn)的移動(dòng)概率進(jìn)行人為設(shè)置。確定當(dāng)前螞蟻可以到達(dá)的像

11、素點(diǎn)以后，本文接下來(lái)計(jì)算了移動(dòng)到各個(gè)像素點(diǎn)的概率值，即螞蟻移動(dòng)到各個(gè)像素點(diǎn)的可能性，然后用一個(gè)隨機(jī)數(shù)來(lái)確定目的地。到達(dá)目的地后，需要將目的地信息記錄到螞蟻的記憶值當(dāng)中，如果螞蟻的記憶值已經(jīng)溢出，則需要進(jìn)行數(shù)值的平移處理。在將目的地信息記錄到螞蟻的記憶值當(dāng)中時(shí)，本文采用了將二維數(shù)據(jù)轉(zhuǎn)化為一維數(shù)據(jù)的方法，這樣可以降低運(yùn)算復(fù)雜度并簡(jiǎn)化讀入、讀出和遺忘”記憶值的程序。2.3 更新過(guò)程當(dāng)每只螞蟻完成一次移動(dòng)過(guò)程以后，將目標(biāo)像素點(diǎn)的信息素進(jìn)行一次更新。這樣可以及時(shí)地更新信息素濃度。在本例中，其更新公式定義為：G,j(n)=(1_p)M*,j(nq+PxATXn.,.)xAT+T.,.(nJ-)x1-ZkT

12、其中，w?是新信息素濃度，wn)是舊信息素濃度，是能見(jiàn)度因數(shù)2.4 決策過(guò)程決策過(guò)程是為了決斷信息素較高的若干點(diǎn)是否為所求的圖像邊緣，即在若干次螞蟻的移動(dòng)循環(huán)之后，找到圖像的邊緣信息。此時(shí)，要對(duì)信息素矩陣T(N)設(shè)定一個(gè)門限值To第一步，最初的T的定義是信息素矩陣的平均值。如下式：77-(N)-id:M1-j3M2i,jM1M2并令迭代索引數(shù)l=0第二步，信息素矩陣的全部元素被劃分為兩類，分別是大于T的元素和小于T的元素，并分別計(jì)算這兩類元素的平均值，如下式:（i）mL(i)mu-L(N)-i4;M1-j4:M2gT(l)(i,j)：、,L.(N)i4:M1j4:M2hT(l)('i,

13、j)U(N)、i4:M1j4:M29t(1)(i,j)U.U.hU/(N)i4:M1-j4:M2hT(l)('i,j)LgT(l)="x,x<T(l)0,otherwisehT(l),1,x<T(l)0,otherwiseugT(l)="x,x<T(l)0,otherwise其中:1,x<T(l)0,otherwise第三步，將迭代索引數(shù)和門限值更新，如下式:T(l)mL",mU"2第四步，如果T（l）-T（i>8（e為一設(shè)定值，本例中取為1）則返回第二步。否則，就可以將灰度值大于T的像素點(diǎn)定義為需提取圖像的邊界E。

14、如下式:Ei,j1,i(N)-T(l)0,otherwise結(jié)論與分析本文應(yīng)用了蟻群算法來(lái)進(jìn)行圖像邊緣的檢測(cè)，主要結(jié)果如下圖:書中作業(yè)的圖片沒(méi)有電子版，在書中的打印質(zhì)量不是很清晰，我是用掃描儀獲得的該圖像，掃描出來(lái)的圖像輪廓比較模糊，再加上背景非常復(fù)雜，所以應(yīng)用算法的結(jié)果也不是非常的理想，僅得到了大致的輪廓和一些老虎身上的紋路。因此，我又從網(wǎng)絡(luò)上下載了一張比較清楚的老虎照片進(jìn)行算法分析，由于這張照片圖像清晰，背景較簡(jiǎn)單，所以結(jié)果也比較理想，能夠得到老虎的大致輪廓。從這幾幅圖中的對(duì)比可以看出，雖然老虎的邊緣基本上被檢測(cè)出來(lái)，但是老虎身上的紋路依然有很大的梯度，因此，老虎身上的斑紋也被描繪了出來(lái)。

15、而目標(biāo)任務(wù)僅僅是將圖像中的老虎進(jìn)行分離，因此，如何區(qū)別老虎身上的噪聲點(diǎn)和老虎與背景之間的輪廓是一個(gè)以后需要研究的內(nèi)容。參考文獻(xiàn)1李人厚.王拓.智能控制理論和方法M.西安電子科技大學(xué)出版社2JingTian.WeiyuYu.ShengliXie.AnAntColonyOptimizationAlgorithmForImageEdgeDetectionJ.2008IEEECongressonEvolutionaryComputation3韓彥芳.施鵬飛.基于蟻群算法的圖像分割方法J.計(jì)算機(jī)工程與應(yīng)用附錄MATLAB源程序functionfunc111filename='tigers'

16、;img=double(imread(filename'.bmp')./255;img=rgb2gray(img);nrow,ncol=size(img);v=zeros(size(img);v_norm=0;forrr=1:nrowforcc=1:ncoltemp1=rr-2cc-1;rr-2cc+1;rr-1cc-2;rr-1cc-1;rr-1cc;rr-1cc+1;rr-1cc+2;rrcc-1;temp2=rr+2cc+1;rr+2cc-1;rr+1cc+2;rr+1cc+1;rr+1cc;rr+1cc-1;rr+1cc-2;rrcc+1;temp0=find(temp

17、1(:,1)>=1&temp1(:,1)<=nrow&temp1(:,2)>=1&temp1(:,2)<=ncol&temp2(:,1)>=1&temp2(:,1)<=nrow&temp2(:,2)>=1&temp2(:,2)<=ncol);temp11=temp1(temp0,:);temp22=temp2(temp0,:);temp00=zeros(size(temp11,1);forkk=1:size(temp11,1)temp00(kk)=abs(img(temp11(kk,1),t

18、emp11(kk,2)-img(temp22(kk,1),temp22(kk,2);endifsize(temp11,1)=0v(rr,cc)=0;v_norm=v_norm+v(rr,cc);elselambda=100;temp00=lambda.*temp00.A4;endv(rr,cc)=sum(sum(temp00);v_norm=v_norm+v(rr,cc);endendv=v./v_norm;p=0.0001.*ones(size(img);alpha=1;beta=0.1;rho=0.1;ant_total_num=round(sqrt(nrow*ncol);ant_pos_

19、idx=zeros(ant_total_num,2);temp=rand(ant_total_num,2);ant_pos_idx(:,1)=round(1+(nrow-1)*temp(:,1);ant_pos_idx(:,2)=round(1+(ncol-1)*temp(:,2);A=40;memory_length=round(rand(1).*(0.3*A)+0.85*A);ant_memory=zeros(ant_total_num,memory_length);total_step_num=900;forstep_idx=1:total_step_numdelta_p_current

20、=zeros(nrow,ncol);forant_idx=1:ant_total_numant_current_row_idx=ant_pos_idx(ant_idx,1);ant_current_col_idx=ant_pos_idx(ant_idx,2);rr=ant_current_row_idx;cc=ant_current_col_idx;ant_search_range_temp=rr-1cc-1;rr-1cc;rr-1cc+1;rrcc-1;rrcc+1;rr+1cc-1;rr+1cc;rr+1cc+1;temp=ant_search_range_temp(:,1)>=1&

21、amp;ant_search_range_temp(:,1)<=nrow&ant_search_range_temp(:,2)>=1&ant_search_range_temp(:,2)<=ncol;ant_search_range=ant_search_range_temp(temp,:);ant_transit_prob_v=zeros(size(ant_search_range,1),1);ant_transit_prob_p=zeros(size(ant_search_range,1),1);forkk=1:size(ant_search_range,

22、1)temp=(ant_search_range(kk,1)-1)*ncol+ant_search_range(kk,2);ifisempty(find(ant_memory(ant_idx,:)=temp,1)ant_transit_prob_v(kk)=v(ant_search_range(kk,1),ant_search_range(kk,2);ant_transit_prob_p(kk)=p(ant_search_range(kk,1),ant_search_range(kk,2);elseant_transit_prob_v(kk)=0;ant_transit_prob_p(kk)=

23、0;endendif(sum(sum(ant_transit_prob_v)=0)|(sum(sum(ant_transit_prob_p)=0)forkk=1:size(ant_search_range,1)ant_transit_prob_v(kk)=v(ant_search_range(kk,1),ant_search_range(kk,2);ant_transit_prob_p(kk)=p(ant_search_range(kk,1),ant_search_range(kk,2);endendant_transit_prob=(ant_transit_prob_v.Aalpha).*(

24、ant_transit_prob_p.Abeta)./(sum(sum(ant_transit_prob_v.Aalpha).*(ant_transit_prob_p.Abeta);temp=find(cumsum(ant_transit_prob)>=rand(1),1);ant_next_row_idx=ant_search_range(temp,1);ant_next_col_idx=ant_search_range(temp,2);ifisempty(ant_next_row_idx)ant_next_row_idx=ant_current_row_idx;ant_next_co

25、l_idx=ant_current_col_idx;endant_pos_idx(ant_idx,1)=ant_next_row_idx;ant_pos_idx(ant_idx,2)=ant_next_col_idx;delta_p_current(ant_pos_idx(ant_idx,1),ant_pos_idx(ant_idx,2)=1;ifstep_idx<=memory_lengthant_memory(ant_idx,step_idx)=(ant_pos_idx(ant_idx,1)-1)*ncol+ant_pos_idx(ant_idx,2);elseifstep_idx>memory_lengthant_memory(ant_idx,: