基于蚁群算法的图像边缘检测实用教案

1、章节(zhngji)安排 图像边缘检测(jin c)概述 蚁群算法边缘检测(jin c)模型 算法的实现 总结和展望第1页/共42页第一页，共43页。图像(t xin)边缘检测概述第2页/共42页第二页，共43页。图像(t xin)的边缘 边缘是指图像强度（灰度值）发生急剧变化的区域边界，是图像最基本的特征(tzhng)之一。图像边缘可分为阶跃型、屋顶型两种类型。如图所示。阶跃型边缘(binyun)屋顶型边缘第3页/共42页第三页，共43页。常用边缘(binyun)检测方法 基于微分算子的边缘检测（传统(chuntng)方法） Robert 算子 Sobel 算子 Laplacian 算子 C

2、anny 算子 基于小波理论的多尺度图像边缘检测 基于数学形态学的图像边缘检测 基于模糊数学的图像边缘检测 基于神经网络的图像边缘检测 基于遗传算法的图像边缘检测第4页/共42页第四页，共43页。蚁群算法边缘检测(jin c)模型第5页/共42页第五页，共43页。蚁群算法(sun f)的基本原理 蚁群算法是一项基于蚁群特点的群智能技术，最早由Marco Dorigo等人于1992年提出，称之为蚂蚁系统(ant system，AS)，用于解决在图中寻找最优路径问题，即旅行商问题(TSP) 。 蚁群算法模拟了自然界蚂蚁的觅食过程，它们起初(qch)随机地移动，当找到食物后，在返回蚁群的途中分泌一种

3、信息素(pheromone)，吸引其他蚂蚁趋向于选择该路径，从而对路径进行巩固和加强。 这样，当一只蚂蚁在蚁群与食物之间找到了一条最佳（最短）路径，其他蚂蚁也随之选择同样的路径，这种正反馈机制使得蚁群最终会趋向于一条路径。蚁群算法正是模拟了这种群体行为来解决多种多样的问题。 第6页/共42页第六页，共43页。蚁群算法(sun f)的基本原理第7页/共42页第七页，共43页。蚁群算法(sun f)的基本原理 蚁群中的蚂蚁开始随机地移动。 如果它发现了食物，就立即返回蚁巢，并在返回途中释放信息素。 信息素吸引附近(fjn)的其他蚂蚁沿着信息素轨迹移动。 这些蚂蚁找到食物返回蚁巢后，该路径上的信息素

4、浓度得到巩固和加强。 如果有两条路径通向相同的食物源，那么经过足够的时间，短路径上的蚂蚁会越来越多。 短路径上的信息素浓度将越来越高，从而吸引更多的蚂蚁。 长路径上的信息素不断挥发，直至消失。 最终，几乎所有的蚂蚁将选择最短的路径。第8页/共42页第八页，共43页。蚁群算法(sun f)的基本原理第9页/共42页第九页，共43页。蚁群算法(sun f)的基本特征 正反馈性：蚂蚁个体趋向于选择最优路径，从而最优路径上将积累更多的信息素，而高浓度的信息素又会吸引更多的蚂蚁，正反馈过程引导整个系统向最优解的方向进化。 分布式计算：每只人工蚂蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问题

5、的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。 鲁棒性：相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。 并行性：蚁群算法中蚂蚁个体搜索的过程彼此独立，仅通过(tnggu)信息素进行通信。因此算法可看作是一个分布式多Agent系统，它在问题空间的多点同时开始独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。 自组织性：蚂蚁个体作用简单，而个体之间的协作作用特别明显，因而可以将蚁群当做一个整体，甚至可以看做一个独立生物体来研究。第10页/共42页第十页，共43页。基于蚁群算法(sun f)的

6、边缘检测模型流程首先，我们对原始图像（真彩色）进行灰度化处理，得到单通道的灰度图像；其次，选用一种微分算子对灰度化后的图像进行预处理；预处理后我们就可以将图像灰度值看作信息素量而将蚁群按照一定规则分布其中，进行足够次迭代后得到结果；最后，需要对其进行阈值化，即根据设定的阈值，将图像按照每个像素的灰度值大小转换(zhunhun)为二值图像，经过这步我们便已经得到边缘结果图；根据需要，可进一步使用细化算法对其进行细化（这一步是可选的）。第11页/共42页第十一页，共43页。邻域结构及蚂蚁的移动(ydng)方式 邻域是蚂蚁下一步可移动到的节点集。本文采用 8 邻域结构，如图所示。蚂蚁移动到各节点的概

7、率(gil)定义为：其他若 0 ,WjpWuuiuiuijijijiji第12页/共42页第十二页，共43页。邻域结构及蚂蚁的移动(ydng)方式 信息启发式因子反映(fnyng)了蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值越大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性就越弱。 期望启发式因子反映(fnyng)了启发信息在指导蚁群搜索过程中的相对重要程度，其大小反映(fnyng)了蚁群寻优过程中先验性、确定性因素的作用强度。其值越大，则蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然这时算法的收敛速度得以加快，但蚁群搜索最优路径的随机性减弱，易于陷入局部最优

8、。 惯性启发式因子决定着蚂蚁保持当前运动方向的强度，当 越大时，蚂蚁越趋向于沿直线运动，当 时，不考虑其他因素，蚂蚁向各个方向运动的概率相等。第13页/共42页第十三页，共43页。邻域(ln y)结构及蚂蚁的移动方式if (蚂蚁的状态为激活态) for (遍历8个邻域节点) 计算节点的概率值if (该节点存在于蚂蚁的记忆中) 删除该节点if (可移动的节点集不为空) 模拟概率执行(zhxng)移动，为当前节点重新赋值将当前节点加入蚂蚁的记忆中if (蚂蚁记忆中节点数 蚂蚁记忆长度) 遗忘最早记忆的节点else 设置蚂蚁状态为停止移动第14页/共42页第十四页，共43页。蚂蚁的记忆(jy)与禁忌

9、表 我们为每只蚂蚁设置一段临时记忆，也称作“禁忌表”，每次迭代中，蚂蚁个体都不会移动到自己先前访问过的节点。 记忆的长度作为(zuwi)算法的一个参数，也影响着算法的运行效率。下面我们在 的空白测试图中，为3只蚂蚁设置不同的记忆长度和参数，以随机点开始觅食，进行50次迭代后，对信息素矩阵进行了色彩化处理，实验结果如下。第15页/共42页第十五页，共43页。蚂蚁的记忆(jy)与禁忌表记忆( jy)长度 = 1记忆( jy)长度 = 10第16页/共42页第十六页，共43页。蚁群规模和初始(ch sh)分布第17页/共42页第十七页，共43页。蚁群规模和初始(ch sh)分布nfTniistart

10、1第18页/共42页第十八页，共43页。蚁群规模和初始(ch sh)分布Lena 原图(yun t)第19页/共42页第十九页，共43页。蚁群规模和初始(ch sh)分布512只蚂蚁，随机(su j)分布方式9325只蚂蚁，随机分布(fnb)方式第20页/共42页第二十页，共43页。蚁群规模(gum)和初始分布3*3均匀分布方式(fngsh)（自动计算出蚂蚁的个数为29241个3*3智能方式（自动计算(j sun)出蚂蚁的个数为9325个第21页/共42页第二十一页，共43页。信息素更新(gngxn)方式 蚁群能感受到的信息素分为两类，第一类为蚁群释放的信息素，我们称之为信息素，第二类为图像的

11、灰度值，我们称之为启发信息。 随着迭代次数的增加，大部分路径上都会留下信息素。为了(wi le)防止信息素的过度积累而使蚂蚁决策时忽略能见度信息，在完成每次迭代后，各路径上的信息素浓度需要根据公式进行更新。nkkjijiji1,*,1第22页/共42页第二十二页，共43页。终止(zhngzh)条件 本文使用给定的迭代次数作为算法的终止条件，即算法将在进行I次迭代之后无条件终止，因此(ync)，迭代次数的选择对于算法性能的影响很大，选择适当的迭代次数尤其重要。 当蚂蚁的临时记忆包含其所有可移动节点，即蚂蚁无法决策下一步移动的节点时，终结蚂蚁个体的生命，不再进行移动。第23页/共42页第二十三页，

12、共43页。阈值(y zh)的选择 蚁群算法运行(ynxng)之后，需要对其进行阈值化，即根据设定的阈值，将蚁群释放的信息素量所对应的边缘图像按照每个像素的灰度值大小转换为二值图像，经过这步我们便可得到边缘结果。其他若 0),( 552),(ThjiMjiMpheromone第24页/共42页第二十四页，共43页。阈值(y zh)的选择0.050.150.250.350.450.550.650.750.850.95第25页/共42页第二十五页，共43页。细化 常用的细化算法有Hilditch算法、Pavlidis算法、Rosenfeld算法和Skeleton算法等。因细化并非边缘检测的必需步骤之

13、一，同时也非本文的重心所在，本文算法的实现程序可自由地选用以上(yshng)细化算法对检测结果进行细化，具体在这里不再赘述。第26页/共42页第二十六页，共43页。算法(sun f)的实现第27页/共42页第二十七页，共43页。类设计(shj)第28页/共42页第二十八页，共43页。类设计(shj)第29页/共42页第二十九页，共43页。类设计(shj)第30页/共42页第三十页，共43页。界面设计第31页/共42页第三十一页，共43页。运行(ynxng)结果第32页/共42页第三十二页，共43页。性能(xngnng)评价第33页/共42页第三十三页，共43页。与传统(chuntng)算法的比

14、较Lena 原图(yun t)Roberts 算法(sun f)Sobel 算法Laplacian原图Canny 算法本文算法第34页/共42页第三十四页，共43页。与传统(chuntng)算法的比较Peppers 原图(yun t)Roberts 算法(sun f)Sobel 算法Laplacian原图Canny 算法本文算法第35页/共42页第三十五页，共43页。与传统(chuntng)算法的比较Airplane 原图(yun t)Roberts 算法(sun f)Sobel 算法Laplacian原图Canny 算法本文算法第36页/共42页第三十六页，共43页。总结(zngji)和展望

15、第37页/共42页第三十七页，共43页。总结(zngji) 本文首先回顾了常用的边缘检测算法以及对蚁群算法的基本理论作了简单的介绍。其次，提出了一种基于蚁群算法的边缘检测模型，并对影响算法性能的各个参数作了详尽的分析。本文主要的研究成果如下： 采用8邻域结构，蚂蚁可向8个方向自由移动(ydng)，概率计算函数分别由信息素量、图像灰度值、蚂蚁的惯性因子决定。 蚂蚁拥有短暂的记忆，记忆长度作为本文算法的参数之一。 提出了一种更智能的蚁群初始分布方式。 在撰写论文过程中，我们进行了大量的实验。最后，通过与传统方法的比较，从实验结果来看，本文算法在图像边缘检测中的表现令人满意。第38页/共42页第三十

16、八页，共43页。展望(zhnwng) 在研究过程中，我们也意识到了蚁群算法客观存在(cnzi)的缺陷。蚁群算法属于群智能算法的一种，而群智能算法是一种基于概率计算的随机搜索进化算法，在现阶段仍然存在(cnzi)着一些问题： 算法的数学理论基础相对薄弱，关于此类的研究发展相对缓慢；同时，关于参数的设置现阶段并没有确切的理论依据，对具体问题与应用环境存在(cnzi)着很大的依赖性； 时间性能差，算法的收敛速度较慢； 与其他算法的比较性研究不足，缺乏合适的性能评估标准和测试方法； 因为算法本身基于概率，因此不具备绝对可信性，应用时或多或少地存在(cnzi)着一些风险。 其中，时间性能在现阶段是蚁群算法最大的缺陷之一，如何改善算法的收敛速度，仍是未来的研究方向之一。不过，蚁群算法作为一种群智能算法，与并行计算的结合，会大大提高算法的性能和运行效率，随着并行计算和云计算的发展，蚁群算法的先天优势可以很好地适应于并行计算和云计算。因此，对蚁群算法的进一步研究，仍具有很大的理论意义和实践意义。第39页/共42页第三十九页，共43页。？第40页/共42页第四十页，共43页。谢谢(xi xie)观赏第41页/共42页第四十一页，共43页。谢谢您的观看(gunkn)