蚂蚁算法实现图像分割论文

第PAGEI页蚂蚁算法实现图像分割摘要模式识别领域图像分割是图像处理的底层步骤，它对于图像识别和图像理解具有举足轻重的作用。一个好的图像分割算法对图形图像的处理会有意想不到的效果，因此探索更好的图像分割算法是图像处理领域中一个重要的研究方向。通过对蚂蚁、蜜蜂和其他群居昆虫的观察和研究，人们逐步发展了群体智能的概念。行为简单的个体聚合在一起就形成了具有某种智能的群体。群体所拥有的能力超过了个体能力的总合，其原因就是群体间存在着“协同合作”。本文将通过对蚂蚁观察和基于MARCODORIGO提出的蚂蚁算法研究，用于对图像分割问题的探索。将灰度图作为蚂蚁群落的栖息地、通过让蚂蚁个体具有的感知其周围有限的范围环境的激素状况和图像的边缘情况的简单能力，依据蚂蚁群觅食的基本原理，实现对图像的分割。实验中将对不同种类边缘图像的测试，证明该算法能够处理各种类型的图像边缘。通过与传统处理的对比实验，证明其能够在多方面获得更好的效果。关键词：蚂蚁算法;群体智能;图像分割;边缘检测TheantsystemrealizesimagesegmentationAbstractInpatternrecognitionsystem,imagesegmentationisalow-levelimage-processing.Thistaskisveryimportant,asweknow,sincetheoutputofanimagesegmentationalgorithmcanbefedasinputtohigher-levelprocessingtasks.Acquiringthebetterimagesegmentationalgorithmhasalwaysbeenanimportantsubjectinthisfiled.Sincepeoplehavestudiedthebehavioroftheantcolonyandothersocialinsert,thenotionofsocialintelligencehasbeenintroduced.Peoplefindthatthecolony’scollectivebehaviorexceedsthesumofitsindividualmember’sactions.Themainreasonofthiskindofphenomenonissomethingwecalledsynergy.Thispaperdiscussesthemethodofusingantsystem,whichisalsoasocialintelligencealgorithm,tosolveimagesegmentationproblem.Greylevelimagecanberegardasatopographicmapwheretheimageistheantcolonyhabit.Therespectivegraylevelintensitiesandpheromoneintensitiesareconsideredineachantperceptionofhisneighborhood.Followingtherulesofforagingactivityoftherealants,weobtainedthealgorithmforimagesegmentationproblemsolvedbytheantcolony.Inourexperiments,differenttypesofimageshavebeenusedprovingthatthisalgorithmcancommendablyobtaintheiredge-images.Comparingwiththeresultofthoseclassicalalgorithms,wefoundthatantsystemalgorithmobtainedabetterresultinmanyaspects.Keywords：Antsystem；Socialintelligence；Imagesegmentation目录摘要 IAbstract II目录 11绪论 11.1 课题研究的背景简介 11.2 课题的目的及意义 21.3 传统边缘检测算子 31.4 蚂蚁算法的国内外研究现状 61.5 本文的研究内容 72蚂蚁算法的原理 92.1简单的蚂蚁算法 92.1.1蚂蚁觅食过程的研究 92.1.1蚂蚁觅食过程的研究 102.2蚂蚁的群体智能现象 102.3本章总结 113蚂蚁算法用于图像分割的算法实现 123.1蚂蚁算法用于图像分割 123.1.1人工蚂蚁所处的环境 123.1.2路径的选择 123.2激素的遗留 133.2.1环境参数h 133.2.2激素遗留公式 144测试与结论 154.1蚁数量参数的选择 154.2时间参数step的选择 154.3激素权重参数的选择 154.4方向权重参数δ选择 174.5激素遗留参数p选择 174.6进一步的研究 174.7 本章总结 185程序的实现流程 195.1初始化 195.2 循环 195.3 伪算法和部分程序 195.4算法的时间复杂度 215.5程序及其参数的说明 21结论 22参考文献 23致谢 24附录1 25附录2 29第21页1绪论课题研究的背景简介群体智能是近年来人工只能领域出现的一个新算法热点。群居昆虫以集体的力量，进行觅食、御敌、筑巢、这种群体所所表现出来的“智能”，就称之为“群体智能”(SwarmIntelligence)。如，蜜蜂采蜜和筑巢、蚂蚁的觅食和筑巢等[1]。群居昆虫的集体行为是很复杂的，它是受简单规律支配的昆虫个体行为的聚合。蚂蚁、蜜蜂、白蚁和群居性黄蜂等。个体具有两种不同的属性，首先，它们是群体的一个成员，这样他们就具有社会性，觅食、筑巢是每一只工蚁都要参加的活动。其次，它们又具有独立性，如每一只蚂蚁在寻找食物的时候都是自己单独行动的。虽然，单看一只蚂蚁并不能看出什么高超的技能，但如果以一群相当数量的蚂蚁为基础就会发现它们的集体能力是非常强大的。蚂蚁能筑巢,我们感到很惊讶。而看到人建筑高楼大厦并不感到惊奇。这也许是因为,认为人有一个聪明的脑袋,故能设计建筑高楼大厦。那么,为什么有一个聪明的脑袋,就能完成各种工作,而没有聪明脑袋的动物就不能完成复杂的任务,是不是只有“聪明的脑袋”才能完成复杂的任务?若是这样,那么“脑袋”是什么?是否都一定像我们现在看到的那样?是否可以有其它形式?比如我们可否将整个“蚁群”看成一个“松散的脑袋”我想是可以这样看的[2]。因为人和蚂蚁都是从低等单细胞生物进化而来的。一个分支进化成像人这样的大型动物(包括其中的脑袋),另一分支进化成像蚂蚁一样的蚁群的脑袋。两者的不同在于前者(脑袋)是连通的,后者(蚁群)是离散的。在这样的看法下,一个蚂蚁就相当于脑中的一个细胞(神经元),蚂蚁之间的信息交流,就相当于大脑中各个细胞之间的联接。那么人工智能界用人工神经网络的技术来模拟人的大脑中某些功能,我们不就也可以用某种数学的模型来模拟"群体智能",用来说明蚂蚁筑巢的功能。所不同点在于一个是用固定连接的神经网络来模拟,另一个是用离散随机连接的神经网络来模拟。我们正是以这种想法为出发点,提出"群体智能"新的数学模型,并研究其基本性质。蚂蚁算法就是一种群体智能算法。是模仿蚂蚁工作方式的一种新的启发式算法。生物学研究表明一群互相协作的蚂蚁能够找到食物源和巢之间的最短路径,而单只蚂蚁则不能。蚂蚁间相互协作的方法是它们在所经过的路上留下一定数量的信息素(迹),该迹能被其它蚂蚁检测出来,一条路上的迹越多,其它蚂蚁将以越高的概率跟随此路径,从而该路径上的迹会被加强。最后最多拥有迹的路径为最短路径。计算机工作着通过对群居昆虫的模拟，构造了一系列对于传统问题的新的解决方法，这就是模式识别领域中对于群体智能的研究。群体智能中的群体是指“一组相互之间可以进行直接通信或者通过改变局部环境间接通信的主体，这组主体能够合作进行分布问题求解”。所谓群体智能指的是“无智能的主体通过合作表现出智能行为的特征”[3]。群体智能在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了基础。在不同的应用中，研究者通过模仿蚂蚁的觅食或是打扫巢穴等群体行为进行算法设计，最终达到实现某种人工智能的目的。这样的算法都被称之为蚂蚁算法或好似蚂蚁系统。1.2课题的目的及意义数字图像处理技术起源于20世纪20年代，经过半个世纪的发展，目前已经广泛的用于工业、医疗保健、航空航天、军事、地理等众多领域。随着网络的普及和互联网的高速发展数字图像处理越来越多的人的重视。同时它也在向其他相关的学科领域渗透。所谓数字图像的处理就是利用数字计算机或者其它数字硬件，对从图像信息转换而得的电信号进行某些数字运算，以提高图像的实用性。在人工智能领域进行图像处理的目的是希望能由计算机自动识别和理解图像。图像处理中的关键的一步是对包含有大量各式各样景物信息的原始图像进行分解。分解的最终结果是该图像被划分为一些具有某种特征的最小成分，称为图像的基元。相对于整幅图像来说，这种基元更容易被计算机快速处理[4]。当人们观察景物时，在视觉系统中对景物进行分割的过程是不可缺少的。这个过程的结果是，人们所看到的景物并不是一个复杂的整体，而是各种简单物体的集合。对于图像的感觉，人类首先是有选择的去掉图像的一些结构或物体，而保留了另外的一部分。这种选择主要是根据物体的几何形状和物体的形象在环境中的对比决定的。人的大脑很容易的完成了这项工作，将图像信息进行下一步处理。但是在人工智能的数字图像领域，这却不是一项简单的工作。必须通过某些图像的特征将其分离出来，然后把这种出来的结果作为下一步的处理输入。图像的特征，是指图像中可以用作标志的属性。它可分为图像的统计特征和图像的视觉特征两类。图像的统计特征是指一些人为的定义的特征，需要通过一定的变换处理才能得到，如直方图、矩、频谱等；图像的视觉特征是指人的视觉可以直接感受到的自然特征，如区域的亮度、纹理或轮廓等。利用这两类特征把图像、分解成一系列有意义的目标或区域的过程称为图像的分割[5]。图像的边缘是图像的最基本的特征。对于灰度来说，所谓的边缘，就是指周围的像素点的灰度有阶跃变化或屋顶变化的那些像素的集合。边缘广泛的存在于物体于背景之间，物体于物体之间、基元于基元间。因此，它是图像分割的重要特征。图像边缘和图像轮廓特征的检测与提取方法，一直是图形处理与分析技术中的热点研究方向。图像的边缘检测，或称之为图像分割，作为视觉处理的一个早期阶段，有着很长的研究历史。新理论、新方法的不断涌现，一方面说明该研究方向本身的重要性，另一方面也反映了它的深度和难度。用蚂蚁算法解决图像分割问题，是从群体智能的角度出发，希望将群体智能的基本原理应用于图像分割领域，使这一问题产生一种新的解决方法，并期待它能够获得较传统的边缘检测算法更为优越的处理效果。1.3传统边缘检测算子对于灰度图像来说，物体的边缘是由灰度不连续性所反映的。经典的边缘提取方法是考察图像的每一个像素在某个领域内灰度的变化，利用边缘领域一阶或二阶方向导数变化规律，用简单的方法检测边缘。这种方法称为边缘检测局部算子法[6]。边缘的种类可以分为两种：一种称为阶跃性边缘，它两边的像素的灰度值有着显著的不同；另一种称为屋顶状边缘，它位于灰度值从增加到减少的变化转折点。对于阶跃边缘，二阶方向导数在边缘处呈零交叉；而对于屋顶状边缘，二阶方向导数在边缘处取极值[7]。如果一个像素落在图像中某一个物体的边界上，那么它的领域将成为一个灰度级的变化带。对这种变化最有用的两个特征是灰度的变化率和方向，它们分别以梯度向量的幅度和方向来表示。这些计算大多都以方向导数掩模求卷积的方法。(1)Roberts边缘检测算子Roberts边缘检测算子是一种利用局部差分算子寻找边缘算子。它由公式g(x,y)=(1-1)其中f(x,y)是具有整数像素坐标的输入图像，平方跟运算使该处理类似于在人类视觉系统中发生的过程。(2)Sobel边缘检测算子如下图所示的两个卷积核形成了sobel边缘算子，图像中的每个点都用这两个核作卷积，一个核对通常的垂直边缘响应最大，而另一个对水平边缘的响应最大。两个卷积的最大值作为该点的输出位。运算结果得到一幅边缘幅度图像。-1-2-1-101000-202121-101水平检测垂直检测图1-1sobel边缘检测算子如下图所示的8个卷积核形成了Krisch边缘算子。图像中的每个点都用这几个核作卷积，每个掩模都对某个特定边缘方向做出最大响应，每个卷积的最大值作为该点的输出。最大响应掩模的序号构成了边缘方向的编码，以下就为Krisch算子，555-355303-305-3-3-3-3-3-3-3-35-3-3-3-305-305-3-35-355-1-2-1-101000-202121-101-1-2-1-101000-202121-101图1-2Krisch算子(3)prewitt边缘检测算子下图所示的两个卷积核形成了Prewitt边缘算子，图像中的每个点都用这两个核作卷积，一个核对通常的垂直边缘响应最大，而另一个对水平边缘的响应最大。两个卷积的最大值作为该点的输出位。运算结果得到一幅边缘幅度图像。和Sobel边缘检测算子差不多。-1-1-110-100020-111110-1图1-3prewitt边缘检测算子(4)高斯-拉普拉斯边缘检测算子高斯算子是一个平滑模板，平滑模板的思想是通过将一点和周围八个点作平均，从而去除突然变化的点，滤掉噪音，其代价是图像有一定程度的模糊。拉普拉斯算子是一个锐化模板，锐化和平滑恰恰相反，它是通过增强高频分量来减少图像中的模糊，故又叫做高通滤波。锐化处理在增强图像边缘的同时增强了图像的噪音。拉普拉斯算子是对二维函数进行运算的二阶导数算子。通常使用的拉普拉斯算子如图所示：0-10-1-1-1-14-1-18-10-10-1-1-1图1-4高斯-拉普拉斯边缘检测算子由于拉普拉斯算子是二阶导数算子，它将边缘处产生的陡峭的零交叉。因为噪音点对边缘检测有一定的影响，所以高斯-拉普拉斯算子是效果较好的边缘检测器。它把高斯平滑滤波器和拉普拉斯锐化滤波器结合在一起，先平滑掉噪音，再进行边缘检测，所以效果更好。-2-4-4-4-2-4080-4-48248-4-4080-4-2-4-4-4-2图1-5高斯-拉普拉斯算子上述边缘算子产生的边缘看起来很相似。但Robert算子是2*2模板的算子，它对陡峭的低噪音相应最好，而后面的都是3*3模板的算子，对灰度渐变和噪音较多的图像处理的较好。1.2蚂蚁算法的国内外研究现状该算法是由意大利学者M.Dorigo、V.Maniez-zo、A.Colorini等人首先提出的,称之为蚁群系统(antcolonysystem),该模型已成功应用于求旅行商问题(TSP),二次指派问题,排序问题等ＮＰ-困难的组合最优化问题,结果可与模拟退火,遗传算法等通用的启发式算法相媲美。蚁群算法和局部搜索算法相结合(称为混合蚁群算法)应用于解二次指派问题和排序问题,得到的结果可以与专用算法相媲美[8]。通过模仿蚂蚁觅食过程而解决的一个比较经典的问题是TSP(travelingsalesmanproblem)。TSP是指求一个周游所有指定城市，最后回到出发点的最短路径问题。蚂蚁算法在解决TSP问题中，先假定所有的城市在同一平面上，每两个城市之间都有路径存在，当蚂蚁经过路径时都会留下一定量的激素。初始化时，m只蚂蚁被随机的放在n的城市的点上面，蚂蚁们在每一个时间步到达一个新的城市，并且改变各个城市路径间的激素含量。与此同时随着时间的改变激素也会有挥发即激素不停的在减少。蚂蚁周游之后激素会在各城市之间留下不同数量的激素，蚂蚁在第二次经过时，激素量越大选择走的概率就越大。当然，解决此问题时必须给蚂蚁一些其它的功能，如它们能够确定城市间的远近，存贮已经走过的城市。这样，每一只蚂蚁前进时选择它没有到达过的城市，距离最短的城市，当然也是激素遗留最多的城市。针对对称实例的实验可以很好的检测出该算法的优越性，而针对不对称的实例可以考察它对问题的解决能力。通过对于对称的和不对称的TSP的研究，我们可以将蚂蚁算法和其他的算法进行比较而得出蚂蚁算法是一种很好的进行图像处理的方法。蚁群系统模型逐渐引起了其它研究者的注意,D.Costa和A.Hertz在M.Dorigo等人研究成果的基础上,提出了一种求解分配类型问题(assignmenttypeproblem)的一般模型,并用来研究图着色问题。G.Bilchev、I.C.Parmee研究了求解连续空间优化问题的蚁群系统模型。在国际上，已经出现了不少有蚂蚁算法或其他群体智能算法实现应用的事例。一群蚂蚁随机出发,遇到垃圾,就将其拉走(拉的方向也是随机的),拉垃圾时,若遇到某一堆垃圾时,就放下，放下垃圾后,再次进行拉垃圾行为。当然还要加了一些限制,才能达到人们所希望的结果。另外,蚂蚁同心协进行搬运食物,是我们见得最多的蚂蚁行为,有人以此为蓝本设计出几个机器人共同推盒子的算法。如美国阿尔伯塔大学设计出几个机器人共同推盒子的实验。借助蚂蚁分工合作的特点(蚁皇管生男育女,工蚁管干活,兵蚁管保卫)的启迪,人们设计了求解任务分配问题的蚂蚁算法,并应用于工厂中汽车喷漆问题。如美国西北大学将蚂蚁算法用于卡车厂油漆车间,负责给离开装配线的卡车上漆的工作安排。他们采取工人分组,各组只喷一种颜色,只有当某小组任务特别紧张时,才分配另一小组前去帮助。通过这种设计后工厂各车间改变颜色的次数更少,从而提高了整体的生产率。又如美国MCIWorld-com公司一直研究人工蚂蚁,并用于管理公司的电话网,对用户记帐收费等工作。另外,还设计"人工蚂蚁"打算用于因特网的路由管理。国内也有研究者用蚂蚁算法求解全国144个城市的最短回路问题,求得的解同其它方法求到得解一样精确,许多研究机构也进行了一些蚂蚁算法的研究工作。比如清华大学提出基于蚂蚁算法的拥塞规避路由算法；重庆大学研究了基于蚂蚁算法的机器人路径规划问题；上海理工大学研究了基于蚂蚁算法的函数优化问题等等[9]。这说明蚂蚁算法不但是求解组合优化问题的可行方法,而且是一种很有竞争力的算法。这种群体智能模型具有一下特点：(1)通用性强。同一问题，可以用多种相似的方法解决。(2)健壮性好。应用与其它问题是，在解决方案中需要做很少的改动。(3)它是一种基于群体的方法。这使的开发正反馈的搜索机制成为可能。1.2本文的研究内容本章介绍了群体智能的研究背景，论述了图像分割在模式在图像识别领域的地位，讨论了本课题研究的目的应用意义。简要介绍了几种常见的图像分割算法。在本章最后，介绍了几个蚂蚁算法的实际现状。本文主要讨论将蚂蚁算法应用于图像分割问题的基本原理和解决方案。通过模仿蚂蚁群体在觅食过程中，释放激素并依据激素选择路径，从而找到最短路径这一原理，构建了人工蚂蚁在数字图像背景下的运动模型，最终达到通过人工蚂蚁群落的爬行获得图像边缘的目的。通过实验，对该算法的主要参数逐一进行了测试，并尝试确定了各个参数值。通过对具有不同种类边缘的图像进行测试处理，证明该算法可以处理各种类型的边缘。与传统边缘检测算法的对比显示，使用蚂蚁算法进行图像边缘的处理具有一定的优势。2蚂蚁算法的原理2.1简单的蚂蚁算法2.1.1蚂蚁觅食过程的研究蚂蚁觅食的具体过程是这样的：在觅食的过程中，每一只蚂蚁都会在其沿途走过的地方留下一种化学激素，蚂蚁们彼此可以识别这种激素的味道。蚂蚁群寻找食物时，首先会派出一些蚂蚁分头在四周游荡，当某只蚂蚁搬运食物回巢后，其它蚂蚁就会沿着激素的味道寻找下去。如果某一路径上遗留的激素味道越重，那么它就越是容易吸引更多的蚂蚁爬向这条路径。同时，所有的路径上的激素都会缓慢地随着时间的流逝而挥发，在一段足够长的时间以后，蚂蚁中的绝大多数蚂蚁就会沿着最短的路径往来与蚁穴和食物之间[10]。蚁穴C食物B蚁穴C食物BAD图2－1简单的蚂蚁算法示意图如图示:在图中，C点为蚁穴，B点为食物所在地，A点为寻找食物途中所经过的一点，蚂蚁在寻找食物时，即可沿C->A->B路线，也可按C->B的路线寻找食物。在简单的模型中蚂蚁找到食物并按原路返回，那么当它们沿着原路返回时，由于CAB比较长，在BC返回时已经留下两次激素，而BAC只返回到D点，于是DAC点仅有一次，当蚂蚁下次出发时就回选择激素量高的，即沿着CB出发。经过一段时间BC上的激素积累多，就会有更多的蚂蚁选择BC，另一方面，由于所有路径上的激素都随着时间的推延缓慢的挥发，而BAC路径上的蚂蚁越来越少，激素也少，渐渐就没有蚂蚁去CAB路径上了。这样，最短路径上的激素积累和蚂蚁的爬行是一个正反馈的过程，因此它具有较快的收敛速度；而所有路径上激素的挥发又是一个负反馈的过程，因此它可以保证蚂蚁的爬行不会因为偶然因素最终收敛到非常短的路径上。2.1.2蚂蚁觅食过程的研究根据上述对于蚂蚁寻食过程的讨论，可以建立一个简单的寻找最短路径的蚂蚁算法模型：（1）一群蚂蚁随机出发，寻找食物；（2）蚂蚁爬行过程中，在沿途留下激素；（3）激素随时间蒸发；（4）蚂蚁选择路径的概率与各路径上的激素浓度成正比。上述模型就是通过模仿蚂蚁寻食过程而建立的基本模型。本文所讨论的用蚂蚁算法解决余下分割的问题，也是在这一基本模型的基础上展开的。2.2蚂蚁的群体智能现象人们观察到，自然界中每一只蚂蚁的头脑都是很简单的，但是蚂蚁群却显示出某种智能。蚂蚁群能够延最短路径觅食就是这样一种现象。下面将从群体智能的观点对此分析。有人提出，蚂蚁所组成的群落与神经细胞所形成的大脑结构有某些相似的地方，社会性昆虫群落通过遗留激素爬行的过程建立路径或有规律的交通网络。这样的模式在人脑中被称之为认识图。但是有本质的区别，比如昆虫将它们的空间记忆写在环境中，而人则完全留在大脑之中。这样的假设是一中理想状况的，但有科学根据的比如脑内的海马状突起中建立认知图的神经系统过程来进行直接的对比来证明。我们假设智能有两种表现形式，一种是生物单体经过长期的积累形成现在的所谓的“大脑”的机能所表现出来的对外界的响应，另一种是生物群体经过进化能够表现出的对外界刺激的反应。且都是生物为了生存对外界的表现的本能。这样就不难说明蚂蚁群落的行为是一种智能行为。此外，心理学和脑科学研究指出，感觉是一种整体影响增强的效果。即感觉不仅是由个体的基元构成，而更多的是基元间的动态的相互关系神经网络的智能来自于神经元的集体行动，每个神经元只负责很有限的工作。但是神经网络却是由数以万记的神经元组成的，当然它们必须是一致的即为了解决问题必需向这个方向努力，这样以来就表现出不可思议的结果。所以计算机虽然运算速度很快，但对于图像的识别却要比任何人逊色的多。蚂蚁智能所表现的不是一只蚂蚁、两只蚂蚁的行为，而且单只蚂蚁的能力加起来也不能谈智能，它必须是在这个群体的所有成员在内，而且基于相互协作的行为。2.3本章总结本章从蚂蚁觅食现象出发，说明了蚂蚁觅食的基本原理，并提出模型对蚂蚁群落的群体智能现象进行了初步分析和讨论，并且将蚂蚁算法的模型构造出来以便进一步的更好的实现蚂蚁算法。3蚂蚁算法用于图像分割的算法实现3.1蚂蚁算法用于图像分割3.1.1人工蚂蚁所处的环境如果将数字图像视为像素的聚合和组合的话，那么蚂蚁算法完全可以看成蚂蚁激素的遗留问题，这样对图像处理应用蚂蚁算法完全可行。这样以来，我们就讨论以下蚂蚁算法在图像处理中的实现。我们将一幅图像视为由像素点构成的，而且它们在同一水平面上面每一个点都可以由唯一的坐标来确定，显然这些完全能够实现。像素按行和列整齐排列，图像边缘的像素点可视为与其周围的点相邻。蚂蚁行走时，总是从它所在的一个位置，向与其向邻的一个位置移动。用于处理图像的蚂蚁带有四个参数：其位置的横坐标、纵坐标、头部朝向的横坐标和头部朝向的纵坐标。3.1.2路径的选择每只蚂蚁对路径的选择依据两个原则：一、根据周围的各点的激素浓度，浓度越大选择的概率越大。二、根据当前头部的方向，头部前方的位置选择的概率大于选择后方的概率，尽量避免走回头路。因此，每一只蚂蚁在进行下一点的选择时，首先要进行其周围八个点的激素权重和方向权重的计算，然后的到其所在3*3区域的可能矩阵，最终根据概率选择方向。我们用win1来代表激素权重，用win2来表示方向权重。那么激素权重可以表示为：win1=（1+δ/1+δ*ζ）^β(3-1)其中，δ是该像素位置上现有的激素量，常数β表示控制着每一只蚂蚁依据激素量进行随机选择的程度。β值较低是，激素权重较小，较高是相反。1/δ描述了蚂蚁感觉激素的变化能力。较小时，她对周围环境的变化不敏感，较大时则相反。方向权重表示为：11/21/41/211/21/2ant1/121/4ant1/81/41/121/201/121/201/12西北方向正北方向1/41/211/121/41/21/12ant1/21/20ant11/201/121/41/121/41/2东北方向正东方向1/201/121/41/121/201/121/12ant1/21/4ant1/41/41/211/211/2东南方向正南方向1/41/121/201/21/41/121/2ant1/121ant1/2011/21/41/21/41/12西南方向正西方向图2-1方向模板表格中的数字对于该蚂蚁来说，是该位置的方向权重值。头部的最大，依次减少为1/2、1/4、1/12、1/20。假设蚂蚁当前位置为ant(i,j)，那么欲选出蚂蚁下一个前进到的路径,就要计算其周围3*3的区域中每个被选中的概率。但是它计算的结果还是那一个点的激素权重和方向权重的积最大，就为下一个爬向的点，故其计算为：P(i,j)=win1*win2；(3-2)P(i,j)表示蚂蚁从位置(i,j)为、位置到下一位置的概率。计算相邻各点的选择概率后，蚂蚁再根据这个计算值选择下一个到达的点。3.2激素的遗留3.2.1环境参数h如果不考虑蚂蚁所要进行的寻找边缘的工作的话，那么每只蚂蚁只要在其行走的每一个点上面留下固定量的激素，这与自然界蚂蚁的习性是相同的。但自然界中的蚂蚁前行的目标是存在于某点的食物，通过激素信息传播的结果是找到最短路径，图像处理中人工蚂蚁的目的则是找到图像的边缘。为了达到这个目的，需要在蚂蚁遗留的激素中加入其所在环境的边缘性质，这样，激素的信息中就包含了环境的边缘信息。蚂蚁们在通过激素间接交流的同时，就实现了对周围区域图像边缘信息的交流。由于上述原因，引入激素环境参数h，其计算方法如下式(3-3)示：h=a*|m1-m2|/max|m1-m2|+b*|p1^2-p2^2|/max|p1^2-p2^2|+c*S/S_max(3-3)这个公式中，m表示灰度值，p表示标准方差。其中m1表示以蚂蚁所在位置为中心的3*3的灰度区域的平均值，m2表示蚂蚁选择的下一位置为中心的3*3灰度平均值，max|m1-m2|表示当蚂蚁所在点周围的8个点分别作为m2的中心点时，计算出来的最大差值，它的结果与下一位置和当前位置之间存在边缘的可能性的大小成正比。方差表示的与灰度基本类似。S表示两窗口之间的灰度直方图的不同，∑|f（1）-f（2）|计算。计算当前窗口与下一个位置窗口对应的灰度之差的和，表示从灰度直方图角度看，认为下一位置和当前位置之间存在边缘的可能性的大小。式子中的a，b，c为常数，a+b+c=1，用来调整以上三方面的各自的权重，具体的数值应视图像的灰度情况而定。 3.2.2激素遗留公式由于需要在蚂蚁遗留的激素中加入图像边缘的信息，所以它们行走时遗留的激素不再时一个定值，而需要公式来计算，如(3-4)示。T=(T0+η+p*h)*k(3-4)其中p为常数，控制着环境信息在遗留的激素中的权重。η是蚂蚁爬过一点时留下的激素的基本量。4测试与结论4.1蚂蚁数量参数的选择蚂蚁数量的选择也是对算法的时间影响很大的，当然对处理的结果有举足轻重的作用。我们经过处理可知，最好的蚂蚁数量在图像像素的30%左右，当蚂蚁数量偏少的时候，处理的图像上面是成点状的。太多时处理的效果和30%时是差不多的。所以蚂蚁数量可以在15%到30%最佳。图4-1和图4-2很容易得出我们的结论。4.2时间参数step的选择时间参数step主要控制算法的步数，所以对算法的处理时间有很大的影响，对处理的结果的优劣程度也有一定的影响。图像处理初始化完成后。分析测试的结果可以得出结论：当处理边缘明显的图像时，在初试参数条件下，当setp较小时图像的处理效果与处理次数间的关系比较明显。而当step较大时如150左右处理后得到的图像边缘几乎没什么变化。但是，随着step的增加，处理时间呈线形增加。所以，为获得较快的处理速度，可以选择setp在100到300作为处理次数参数。图4-3和图4-4的比较得出上述结论。4.3激素权重参数的选择在激素权重的公式中，我们知道win1=（1+δ/1+δ*ζ）^β中对激素权重影响的有三个因素，其中β的影响为指数增减的，因此β选择至关重要，一般在1.5到4间最佳。ζ视图形中的灰度情况而定，如果图像灰度差值较大时最好选择大一些，较小时小些。一般得出的值在1.0到2.5间。图4-1蚂蚁算法处理图像1蚂蚁数量为25%全图像素，步数为100步图4-2蚂蚁算法处理图像2蚂蚁数量为10%全图像素，步数为100步图4-3蚂蚁算法处理图像3蚂蚁数量为15%全图像素，步数为50步图4-3蚂蚁算法处理图像4蚂蚁数量为15%全图像素，步数为100步4.4方向权重参数δ选择方向权重完全取决与蚂蚁的方向，在这里我们不在做过多的介绍，它的大小描述蚂蚁对激素变化的能力。经过实验的验证选时一般在0.5到2.5间最好。4.5激素遗留参数p选择该参数决定了蚂蚁根据环境所遗留的激素的量。P的值越大，蚂蚁遗留的激素就越多，特别是处于图像的边缘的时候，但是p值过大时反而会使处理效果变的差一些。P值一般选在5.5到15左右，由于p与路径的收敛有很大的关系因此p选大一些处理会好一些的。但不是越大越好。因为路径的选择是基于两个因素的，它们的关系时制约的激素权重大时，方向权重有影响，所以找到的不一定是最好的。4.6进一步的研究本文对于蚂蚁算法的研究已经基本结束了，但是在未来还可以对这个算法进行进一步的研究。讨论一些更深的问题，比如对人工蚂蚁赋予更多的机能和更好的处理能力。如蚂蚁寿命，蚂蚁出错的概率，随机事件对蚂蚁的影响，将蚂蚁分为针对图像的特点分为比率不同的蚁群来处理图像等等。比如，对蚂蚁参数设一个比较小的随机系数在激素遗留公式里，来表示蚂蚁的出错概率，有如在人工蚂蚁的结构方面，我们可以分两类蚂蚁，其中一类可以设计的让它对连续的灰度值相近的像素更为容易选择，而另一类则对处理的更为综合一些。基于这样的思想，我们去设计蚂蚁，能使蚂蚁算法的性能更好。蚂蚁算法用于图像分割技术方面还不是很成熟，它拓展了人们关于图像处理的思路，并且显示出了很大程度的优越性，所以进行更深更广泛的研究是必须的也是必要的。如果蚂蚁算法的研究做的足够深入，那么它将很广泛的应用在社会各个方面。本章总结本章将算法通过MATLAB实现在图像的分割上面，并且对个主要参数进行了讨论。最后的得到处理图像。说明蚂蚁算法在图像分割中是可行的，本文对其它算子的讨论都是基于以前他人的讨论的，没有做深刻的讨论。最后对进一步的研究只是自己的一些想法而已。5程序的实现流程5.1初始化数字图像中，我们是图像为像素组成的，那么图像完全可以看成是一个由像素值组成的矩阵。这时的对图像的操作就看成了对矩阵的操作。我们选择用MATLAB来做。初始化的时候，一幅图像空间存放图像的信息，第二幅存放激素信息。申请相当数量的蚂蚁，将它们随机的放置在图上面，并随机的放置方向，然后读入方向参数，并将第一幅图像的灰度转化为激素权重.具体的看程序。5.2循环整个算法由两重循环组成：处理时间的循环和处理蚂蚁的循环。时间步和蚂蚁数也是影响算法处理的关键因素，在初始时先循环步数，再循环蚂蚁。在每一步里对每一只蚂蚁进行处理。蚂蚁数量和循环步数在初始化时确定，在处理蚂蚁时，先读入其位置所在的3*3区域的激素值。最后以比率k对激素进行挥发，并把挥发或的激素值转化为灰度值写回存放激素的图像中。5.3伪算法和部分程序开始：初始化:ant←0（ant为蚂蚁的数量）step←0(step为迭代步数)将m个蚂蚁随机置于n个顶点上;循环:fori←0ton-1dofork←1tomdo计算各蚂蚁的目标函数值；按概率选择顶点j;移动蚂蚁k至顶点j;更新当前的解；endend程序如下：function[image4,image2]=antcolony(image1)[r,p]=size(image1)；ants=;%蚂蚁数量steps=；%循环步数sigma=%激素初始量beta=；T0=；p1=；ka=；delta=；step=；a1=；b=；c=；add_sigma=；image1=zeros(r,p);image2=zeros(r,p);fori=1:rforj=1:pimage2(i,j)=sigma;endendstep=zeros(steps);whilestep<steps%对每一步进行循环.%关于蚂蚁的数组，第三、四列表示蚂蚁下一个位置如图所示%(-1,-1)(-1,0)(-1,1)%(0,-1)(0,0)(0,1)%(1,-1)(1,0)(1,1)ant=zeros(ants,4);forNo=1:antsant(No,1)=mod(round(r*rand(1,1))+1,r);ant(No,2)=mod(round(p*rand(1,1))+1,p);ant(No,3)=round(rand(1,1));ant(No,4)=round(rand(1,1));endforNo=1:ants%对每一只蚂蚁进行循环。win_fx=fx(ant,No);%提取方向权重。win_pher=pick(image2,ant(No,1),ant(No,2));%提取3*3的窗口的对应的激素。[fangxiang,P]=Max_P(win_fx,win_pher,delta,beta);%计算下一个点。ant(No,3)=fangxiang(1,1);ant(No,4)=fangxiang(2,1);h=huanjing(image1,ant,No,fangxiang,a1,b,c);image2(ant(No,1),ant(No,2))=T(T0,add_sigma,p1,h,ka);ant(No,1)=mod(ant(No,1)+ant(No,3),r);ant(No,2)=mod(ant(No,2)+ant(No,4),p);%更改参数。endstep=step+1;end5.4算法的时间复杂度时间复杂度为O（m*n），其中m为蚂蚁数，n为循环的步数。很容易的看出来程序的复杂度与步数和蚂蚁的个数联系最为紧密。5.5程序及其参数的说明以上程序是在BATLAB中实现的，主程序中有七个子程序。它们是fx函数它用来调用方向权重；w_p用来调用激素权重；pick用来读取像素信息；huanjing用来计算蚂蚁对周围环境的响应参数h；Max_P求取蚂蚁爬向的下一个点；T写入激素值；rgb2gray读图像进行灰度处理。在程序的运行中由于软件的原因，大约整幅图像30%的像素，运行200步大约需时12个小时（3%像素的蚂蚁，运行200步用时1小时10分钟），所以参数选择上多数基于已经形成的结论。当然简单的数据都是处理时的数据。结论本论文采用群体智能理论中的蚂蚁算法来实现图像分割的问题。将人工蚂蚁放置在数字图像上，给蚂蚁赋予一定的激素辨别和头部朝向进行下一步路径选择的能力，同时进行一定量的激素释放，使蚂蚁经过一段时间的爬行，最终将行走的路径收敛到图像的边缘上面去，达到图像分割的目的。本文的讨论是蚂蚁算法实现图像分割的基层，无论对于图像分割，还是蚂蚁算法的讨论都是浅薄的，蚂蚁算法的研究空间还很大的，由于水平的限制只能做出这么多的努力。有机会再深入的讨论。参考文献1[英]K.Sugawaraetal.,"ForagingBehaviorofMulti-robotSystemandEmergenceofSwarmIntelligence",Systems,Man,andCybernetics,1999.IEEESMC'99ConferenceProceedings.1999IEEEInternationalConferenceon,Volume:3,1999Page(s):257-262vol32[英]DorigoM,GambardellaLM.Antcolonysystem:Acooperativelearningapproachtothetravelingsalesmanproblem,IEEETrans.EvolutionaryComputation,1997,1(1):53-66.3[英]BillFulkerson,VanParunak,"TheLivingFactory:ApplicationsofArtificialLifetoManufacturing",IEEE19954张钤.浅谈蚂蚁算法.计算机与信息技术.2002,第100期5温文波,杜维.蚁群算法概述.石油化工自动化,2002年1月,第一期:19-226[英]ColorniA.Distributedoptimizationbyantcoloniest[R].Proc.of1stEuropeanConf.ArtificialLife.7[英]DorigoM,LucaMariaGamberdella.AntColonySystem:ACooperativeLearningApproachtotheTravelingSalesmanProblem[R].TR,IRIDIA,19968[英]WalterJ,Gutjahr.Agraph-basedAntSystemanditsconvergence[J]:FutureGenerationComputerSystem,2000,16:837-888.9熊伟清,余舜洁,赵杰煜.具有分工的蚁群算法及应用.模式识别与人工智能.2003年9月,第16卷第3期,328-33210张钤.浅谈蚂蚁算法.计算机与信息技术.2002,第100期致谢在此，我要衷心的感谢我的指导老师，从做设计的开始金雪松老师就给我很大的帮助和指导。从蚂蚁算法的学习，到matlab的上机实践都是在他的精心指导下进行的。老师孜孜不倦的教诲使我收益匪浅。毕业设计的完成与父母对我在精神上的支持是分不开的。谨以此论文来表达对我读书这么多年给予我帮助的人的感谢。附录1ArtificialAntsandMinimumCostPathsIntheprevioussectionwehaveshownthatasetofdifferenceequationscanreproduceratheraccuratelythemeanbehaviorofthecontinuousmodelofDeneubourgetal.Yet,ourgoalistodefinealgorithmsthatcanbeusedtosolveminimumcostproblemsonmorecomplicatedgraphsthanthoserepresentingthedoublebridgeexperiment(see,e.g.,thegraphinfigure1).Withthisgoalinmind,letusconsiderastatic,connectedgraphG=(N,A),whereNisthesetofn=|N|nodesandAisthesetofundirectedarcsconnectingthem.Thetwopointsbetweenwhichwewanttoestablishaminimumcostpatharecalledsourceanddestinationnodes,astypicallydoneintheliteratureonminimumcostpathproblems(whenthecostofarcsisgivenbytheirlength,theminimumcostpathproblemisthesameastheshortest-pathproblem);sometimes,inanalogytotheshortest-path–findingbehaviorofrealants,wewillalsocallthemnestandfoodsource.Unfortunately,ifwetrytosolvetheminimumcostpathproblemonthegraphGusingartificialantswhosebehaviorisastraightforwardextensionofthebehavioroftheantsdescribedintheprevioussection,thefollowingproblemarises:theants,whilebuildingasolution,maygenerateloops.Asaconsequenceoftheforwardpheromonetrailupdatingmechanism,loopstendtobecomemoreandmoreattractiveandantscangettrappedinthem.Butevenifanantcanescapesuchloops,theoverallpheromonetraildistributionbecomessuchthatshortpathsarenolongerfavoredandthemechanismthatinthesimplerdoublebridgesituationmadetheantchoosetheshortestpathwithhigherprobabilitydoesnotworkanymore.Becausethisproblemisduetoforwardpheromonetrailupdating,itmightseemthatthesimplestsolutiontothisproblemwouldbetheremovaloftheforwardupdatingmechanism:inthiswayantswouldrelyonlyonbackwardupdating.Still,thisisnotasolution:aswassaidbefore(seesection1.1.2,butseealsoexercise1.1attheendofthischapter),iftheforwardupdateisremovedthesystemdoesnotworkanymore,noteveninthesimplecaseofthedoublebridgeexperiment.Wethereforeneedtoextendthecapabilitiesoftheartificialantsinawaythat,whileretainingthemostimportantcharacteristicsofrealants,allowsthemtosolveminimumcostpathproblemsongenericgraphs.Inparticular,artificialantsaregivenalimitedformofmemoryinwhichtheycanstorethepartialpathstheyhavefollowedsofar,aswellasthecostofthelinkstheyhavetraversed.Viatheuseofmemory,theantscanimplementanumberofusefulbehaviorsthatallowthemtoeffcientlybuildsolutionstotheminimumcostpathproblem.Thesebehaviorsare(1)probabilisticsolutionconstructionbiasedbypheromonetrails,withoutforwardpheromoneupdating;(2)deterministicbackwardpathwithloopeliminationandwithpheromoneupdating;and(3)evaluationofthequalityofthesolutionsgeneratedanduseofthesolutionqualityindeterminingthequantityofpheromonetodeposit(notethatwhileinthesimplecaseofminimumcostpathsearchanestimateofthesolutionqualitycanbemadebytheantalsoduringthesolutionconstruction,thisisnotnecessarilytrueinotherproblems,inwhichtheremaynotexistaneasywaytoevaluatepartialsolutions).Additionally,weshowthatbytakingintoaccountpheromoneevaporation,whichwasnotnecessarytoexplainrealants’behavior,performancecanbegreatlyimproved.Inthefollowingwebrieflyexplainhowtheabove-mentionedants’behavior,aswellaspheromoneevaporation,isimplementedinanalgorithmthatwecallSimple-ACO(S-ACOforshort).Itshouldbenotedthat,althoughitrepresentsasignificantsteptowardthedefinitionofaneffcientalgorithmforthesolutionofminimumcostproblemsongraphs,S-ACOshouldbetakenforwhatitis:adidactictooltoexplainthebasicmechanismsunderlyingACOalgorithms.Probabilisticforwardantsandsolutionconstruction.S-ACOantscanbethoughtofashavingtwoworkingmodes:forwardandbackward.Theyareinforwardmodewhentheyaremovingfromthenesttowardthefood,andtheyareinbackwardmodewhentheyaremovingfromthefoodbacktotheirnest.Onceanantinforwardmodereachesitsdestination,itswitchestobackwardmodeandstartsitstravelbacktothesource.InS-ACO,forwardantsbuildasolutionbychoosingprobabilisticallythenextnodetomovetoamongthoseintheneighborhoodofthegraphnodeonwhichtheyarelocated.(GivenagraphG=（A，T）twonodesi,j∈Nareneighborsifthereexistsanarc（i,j)∈NTheprobabilisticchoiceisbiasedbypheromonetrailspreviouslydepositedonthegraphbyotherants.Forwardantsdonotdepositanypheromonewhilemoving.This,togetherwithdeterministicbackwardmoves,helpsinavoidingtheformationofloops.Deterministicbackwardantsandpheromoneupdate.Theuseofanexplicitmemoryallowsananttoretracethepathithasfollowedwhilesearchingthedestinationnode.Moreover,S-ACOantsimprovethesystemperformancebyimplementingloopelimination.Inpractice,beforestartingtomovebackwardonthepaththey1.3ArtificialAntsandMinimumCostPaths11memorizedwhilesearchingthedestinationnode(i.e.,theforwardpath),S-ACOantseliminateanyloopsfromit.Whilemovingbackward,S-ACOantsleavepheromoneonthearcstheytraverse.Pheromoneupdatesbasedonsolutionquality.InS-ACOtheantsmemorizethenodestheyvisitedduringtheforwardpath,aswellasthecostofthearcstraversedifthegraphisweighted.Theycanthereforeevaluatethecostofthesolutionstheygenerateandusethisevaluationtomodulatetheamountofpheromonetheydepositwhileinbackwardmode.Makingpheromoneupdateafunctionofthegeneratedsolutionqualitycanhelpindirectingfutureantsmorestronglytowardbettersolutions.Infact,bylettingantsdepositahigheramountofpheromoneonshortpaths,theants’pathsearchingismorequicklybiasedtowardthebestsolutions.Interestingly,thedependen