使用蚁群算法进行图像分割报告

1、使用蚁群算法进行图像分割报告绪论蚁群算法是模拟蚂蚁群体觅食行为的仿生优化算法。本文利用蚁群算法进行图像分割，提取目标图像的边缘路径，概括来说，是通过一定数量的人工蚂蚁根据图像的灰度值特性自由觅食，在觅食的过程中形成的信息素矩阵即代表了图像的边缘特征信息。1本例中蚁群算法的几个要素一幅图像中包括目标、背景、边界和噪声等内容，边缘提取的目的是要找出体现这些内容之间区别的特征量。区别目标和背景的一个重要的特征是像素灰度，因此选用像素的灰度值作为主要特征。另外，边界点或噪声点往往是灰度值发生突变的地方，而该点处的梯度体现出这种变化，是反映边界点与背景或目标区域内点区别的重要特征。因此，在定义可见度因数

2、时，一定要把梯度值作为首要特征。1.1 确定初始蚂蚁数目蚁群算法是一种随机搜索算法，它通过多个候选解组成群体的进化过程来寻求最优解，在这个进化过程中，既需要每个个体的自适应能力，更需要群体的相互协作，这个相互协作，通过个体之间的信息交流来完成。蚁群的数量越多，算法的全局搜索能力以及算法的稳定性越高，但是若蚂蚁数目较大，会使大量的曾被搜索过的解上的信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性虽然得到了加强，但收敛速度减慢，在本例中，蚂蚁数目取为图像像素数的开方值。1.2 蚂蚁转移概率在蚁群算法的第n步，某一点处的蚂蚁转移到像素点（i,j）的概率主要由该点信息素浓度和能见度因数来决定

3、，其计算公式为【1】：(n)Pi,j（MNi,j广（）：（i,j）：j-.i1其中，Q表示蚂蚁k下一步容许去的城市集合。p2与d,j成正比，J为从像素点i,j的信息素因数，北为像素点i,j的能见度因数，%B参数分别反映了蚂蚁在转移过程中，像素点所累积的信息素和像素点的启发信息，在蚂蚁选择转移时的相对重要性。a为信息启发因子，反映了蚂蚁在向另一个像素点转移时，这目标像素点所累积的信息素在指导蚁群搜索中选择像素点转移时的相对重要程度，反映了蚁群在路径搜索中随机性因素作用的强度。a值越大，蚂蚁选择以前走过的像素点的可能性越大，搜索的随机性越弱。a值过大也可能使蚁群的搜索过早陷于局部最优。本例中a值取

4、为1。B为期望值启发式因子，反映了蚂蚁在搜索过程中启发信息在指导蚁群搜索中的相对重要程度。期望值启发因子B的大小反映了蚁群在道路搜索中先验性、确定性因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大。虽然它使搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性减弱，容易陷入局部最优。本例中B值取为0.1。1.3 信息素矩阵的更新蚁群有着令人惊奇的信息系统，研究发现，当蚂蚁外出觅食或在回巢穴的途中，它们都会释放一种特殊的信息素气味来标识行进的轨迹，蚂蚁用这种独有的无声语言来设置类似人类路标的蚁踪。蚂蚁在寻找食物过程中，在它们经过的地方所留下的信息素，不仅能被同一蚁群中

5、的其他蚂蚁感知到，而且其强度也能被感知，蚂蚁会倾向于沿信息素浓度较高的方向移动，而移动过程又会留下新的信息素，对原有的信息素进行加强。信息素的更新策略主要有蚁密模型、蚁量模型和蚁周模型。其中，蚁周模型用的是全局信息，即完成一次循环对所经过的整条路径上的信息素进行更新，整体性较强；而蚁量和蚁密两种模型用的是局部信息，即蚂蚁每完成一步后就对刚经过的路径上的信息素进行更新。在本例算法中，像素点之间的信息素变化参考的是蚁密模型的思想，但是在具体的计算方法上又结合了本例的特点。即当每一只蚂蚁完成一次移动以后进行一次信息素的更新，具更新公式为：TiJn）=（1_P）黑%Jn出+PxAtxij）父Af+4j

6、（n4'）x1-At其中，勒（？是新信息素浓度，和（7）是旧信息素浓度，1,j是能见度因数。考虑到片和Ae均为矩阵，式中的乘法表示的均为矩阵中元素分别相乘。At在所有蚂蚁完成一次移动以后置零。1.4 蚂蚁的记忆值当某两个像素点的信息素浓度较高时，某只蚂蚁很有可能会在这两个像素点之间进行往复运动，造成了算法的局部收敛。为了克服这一缺陷，本文定义了蚂蚁的记忆值，记忆值的大小要小于某只蚂蚁移动的总步数，从而保证当蚂蚁移动一定步数以后，会消除某一时间点之前的记忆”。蚂蚁记忆值长度的定义公式为：memory_length=B父（0.3MA）+0.85父A其中，A的值可以根据图像的大小人为设定，本

7、文中取为40,B为01之间的随机值。在本例中，每只蚂蚁的记忆值长度相等。当蚂蚁准备移动时，首先检查其临近点中有没有记忆值中的像素点，如果存在，则将其移动至该像素点的概率置零。若该蚂蚁临近的八个像素点都包含在了蚂蚁记忆值当中，那么还需要对蚂蚁临近点的移动概率进行人为设置。当蚂蚁移动到某一像素点时，需要将该像素点记录到蚂蚁的记忆值当中，若蚂蚁的记忆值溢出，则还需要进行数值的平移处理。2用于图像分割的蚁群算法的流程NONO忘记已移动蚂蚁2.1 初始化过程导入图片后，首先将RGB真彩图转换为灰度值图，然后将K只蚂蚁随机地分散在这张灰度值图像上，图像大小为MIXM2,初始蚂蚁的数量为图像面积的开方值，如

8、下式：K=JM1父M2。同时，信息素矩阵也被初始化为.init=0.001其次，我们需要进行的是能见度因数”的确定。在本例中，将能见度因数”定义为：i,j=；Vc(Ii,j)其中Z=£1Mlzj：M2Vc(Ii,j),Vc(i,j)是临近像素灰度值的一个函数，它被定义为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为每个像素点的灰度值。本例中，我们要

9、寻找的是两只老虎的边界，边界点的特点是该点与周边几个点的像素灰度值差别较大，所以这里我们定义了一个能够反映灰度值差别的函数Vc,当该值较大时，说明该像素点为老虎边界点的概率就大一些。计算完能见度因数后，本文又定义了一个新的参数，蚂蚁的记忆值。该值的设定是为了防止蚂蚁在信息素浓度较高的两个像素点进行往复移动，造成算法的局部收敛。蚂蚁记忆值的大小计算也遵从一定的随机性，如下式：memory_length=8m(0.3mA)+0.852其中，A的值可以根据图像的大小人为设定，本文中取为40,B为01之间的随机值。2.2 移动过程本文共进行了900次移动过程，在每一次的移动过程中，被放置的K只蚂蚁都会

10、在概率p：7的指导作用下选择下一个目的地(像素点)，而该蚂蚁的目标像素点必须临近其所在的像素点。存在一个问题是当蚂蚁在某一像素点时，它可以移动到哪些像素点。在这里，我们既可以设为邻近的四个像素点也可以设为邻近的八个像素点。在本例中，蚂蚁在某一像素点时，可移动到的像素点为邻近的八个像素点【3】。在蚂蚁选择目标像素点之前，首先要进行图像的边缘检测，因为蚂蚁是不能够移动到图像之外的，因此需要将图像外的点的信息素浓度置零。另外还需要检查在蚂蚁的记忆值中已经包含了哪些像素点，也要给以去除。如果邻近的八个像素点都包含在了蚂蚁记忆值当中，那么还需要对蚂蚁临近点的移动概率进行人为设置。确定当前蚂蚁可以到达的像

11、素点以后，本文接下来计算了移动到各个像素点的概率值，即蚂蚁移动到各个像素点的可能性，然后用一个随机数来确定目的地。到达目的地后，需要将目的地信息记录到蚂蚁的记忆值当中，如果蚂蚁的记忆值已经溢出，则需要进行数值的平移处理。在将目的地信息记录到蚂蚁的记忆值当中时，本文采用了将二维数据转化为一维数据的方法，这样可以降低运算复杂度并简化读入、读出和遗忘”记忆值的程序。2.3 更新过程当每只蚂蚁完成一次移动过程以后，将目标像素点的信息素进行一次更新。这样可以及时地更新信息素浓度。在本例中，其更新公式定义为：G,j(n)=(1_p)M*,j(nq+PxATXn.,.)xAT+T.,.(nJ-)x1-ZkT

12、其中，w?是新信息素浓度，wn)是旧信息素浓度，是能见度因数2.4 决策过程决策过程是为了决断信息素较高的若干点是否为所求的图像边缘，即在若干次蚂蚁的移动循环之后，找到图像的边缘信息。此时，要对信息素矩阵T(N)设定一个门限值To第一步，最初的T的定义是信息素矩阵的平均值。如下式：77-(N)-id:M1-j3M2i,jM1M2并令迭代索引数l=0第二步，信息素矩阵的全部元素被划分为两类，分别是大于T的元素和小于T的元素，并分别计算这两类元素的平均值，如下式:（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第三步，将迭代索引数和门限值更新，如下式:T(l)mL",mU"2第四步，如果T（l）-T（i>8（e为一设定值，本例中取为1）则返回第二步。否则，就可以将灰度值大于T的像素点定义为需提取图像的边界E。

14、如下式:Ei,j1,i(N)-T(l)0,otherwise结论与分析本文应用了蚁群算法来进行图像边缘的检测，主要结果如下图:书中作业的图片没有电子版，在书中的打印质量不是很清晰，我是用扫描仪获得的该图像，扫描出来的图像轮廓比较模糊，再加上背景非常复杂，所以应用算法的结果也不是非常的理想，仅得到了大致的轮廓和一些老虎身上的纹路。因此，我又从网络上下载了一张比较清楚的老虎照片进行算法分析，由于这张照片图像清晰，背景较简单，所以结果也比较理想，能够得到老虎的大致轮廓。从这几幅图中的对比可以看出，虽然老虎的边缘基本上被检测出来，但是老虎身上的纹路依然有很大的梯度，因此，老虎身上的斑纹也被描绘了出来。

15、而目标任务仅仅是将图像中的老虎进行分离，因此，如何区别老虎身上的噪声点和老虎与背景之间的轮廓是一个以后需要研究的内容。参考文献1李人厚.王拓.智能控制理论和方法M.西安电子科技大学出版社2JingTian.WeiyuYu.ShengliXie.AnAntColonyOptimizationAlgorithmForImageEdgeDetectionJ.2008IEEECongressonEvolutionaryComputation3韩彦芳.施鹏飞.基于蚁群算法的图像分割方法J.计算机工程与应用附录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,: