基于蚁群算法的图像边缘检测

基于蚁群算法的图像边缘检测作者：whyproE-mail:[e-mail]章节安排•图像边缘检测概述•蚁群算法边缘检测模型•算法的实现•总结和展望图像边缘检测概述图像的边缘•边缘是指图像强度（灰度值）发生急剧变化的区域边界，是图像最基本的特征之一。图像边缘可分为阶跃型、屋顶型两种类型。如图所示。阶跃型边缘屋顶型边缘常用边缘检测方法•基于微分算子的边缘检测（传统方法）–Robert算子–Sobel算子–Laplacian算子–Canny算子•基于小波理论的多尺度图像边缘检测•基于数学形态学的图像边缘检测•基于模糊数学的图像边缘检测•基于神经网络的图像边缘检测•基于遗传算法的图像边缘检测蚁群算法边缘检测模型蚁群算法的基本原理•蚁群算法是一项基于蚁群特点的群智能技术，最早由MarcoDorigo等人于1992年提出，称之为蚂蚁系统(antsystem，AS)，用于解决在图中寻找最优路径问题，即旅行商问题(TSP)。•蚁群算法模拟了自然界蚂蚁的觅食过程，它们起初随机地移动，当找到食物后，在返回蚁群的途中分泌一种信息素(pheromone)，吸引其他蚂蚁趋向于选择该路径，从而对路径进行巩固和加强。•这样，当一只蚂蚁在蚁群与食物之间找到了一条最佳（最短）路径，其他蚂蚁也随之选择同样的路径，这种正反馈机制使得蚁群最终会趋向于一条路径。蚁群算法正是模拟了这种群体行为来解决多种多样的问题。蚁群算法的基本原理蚁群算法的基本原理•蚁群中的蚂蚁开始随机地移动。•如果它发现了食物，就立即返回蚁巢，并在返回途中释放信息素。•信息素吸引附近的其他蚂蚁沿着信息素轨迹移动。•这些蚂蚁找到食物返回蚁巢后，该路径上的信息素浓度得到巩固和加强。•如果有两条路径通向相同的食物源，那么经过足够的时间，短路径上的蚂蚁会越来越多。•短路径上的信息素浓度将越来越高，从而吸引更多的蚂蚁。•长路径上的信息素不断挥发，直至消失。•最终，几乎所有的蚂蚁将选择最短的路径。蚁群算法的基本原理蚁群算法的基本特征•正反馈性：蚂蚁个体趋向于选择最优路径，从而最优路径上将积累更多的信息素，而高浓度的信息素又会吸引更多的蚂蚁，正反馈过程引导整个系统向最优解的方向进化。•分布式计算：每只人工蚂蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。•鲁棒性：相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖于初始路线的选择，而且在搜索过程中不需要进行人工的调整。•并行性：蚁群算法中蚂蚁个体搜索的过程彼此独立，仅通过信息素进行通信。因此算法可看作是一个分布式多Agent系统，它在问题空间的多点同时开始独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。•自组织性：蚂蚁个体作用简单，而个体之间的协作作用特别明显，因而可以将蚁群当做一个整体，甚至可以看做一个独立生物体来研究。基于蚁群算法的边缘检测模型流程•首先，我们对原始图像（真彩色）进行灰度化处理，得到单通道的灰度图像；•其次，选用一种微分算子对灰度化后的图像进行预处理；预处理后我们就可以将图像灰度值看作信息素量而将蚁群按照一定规则分布其中，进行足够次迭代后得到结果；•最后，需要对其进行阈值化，即根据设定的阈值，将图像按照每个像素的灰度值大小转换为二值图像，经过这步我们便已经得到边缘结果图；•根据需要，可进一步使用细化算法对其进行细化（这一步是可选的）。原始图像灰度图像[灰度化]预处理后的图像[使用微分算子进行预处理]蚁群算法后的图像[蚁群算法]阈值化后的图像最终图像[阈值化][细化]邻域结构及蚂蚁的移动方式•邻域是蚂蚁下一步可移动到的节点集。本文采用8邻域结构，如图所示。蚂蚁移动到各节点的概率定义为：其他若0,,,,,,,WjpWuuiuiuijijijiji邻域结构及蚂蚁的移动方式•信息启发式因子反映了蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度，其值越大，蚂蚁选择以前走过路径的可能性就越大，搜索的随机性就越弱。•期望启发式因子反映了启发信息在指导蚁群搜索过程中的相对重要程度，其大小反映了蚁群寻优过程中先验性、确定性因素的作用强度。其值越大，则蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然这时算法的收敛速度得以加快，但蚁群搜索最优路径的随机性减弱，易于陷入局部最优。•惯性启发式因子决定着蚂蚁保持当前运动方向的强度，当越大时，蚂蚁越趋向于沿直线运动，当时，不考虑其他因素，蚂蚁向各个方向运动的概率相等。邻域结构及蚂蚁的移动方式•if(蚂蚁的状态为激活态){•for(遍历8个邻域节点){•计算节点的概率值•if(该节点存在于蚂蚁的记忆中){•删除该节点•}•}•if(可移动的节点集不为空){•模拟概率执行移动，为当前节点重新赋值•将当前节点加入蚂蚁的记忆中•if(蚂蚁记忆中节点数蚂蚁记忆长度){•遗忘最早记忆的节点•}•}•else{•设置蚂蚁状态为停止移动•}•}蚂蚁的记忆与禁忌表•我们为每只蚂蚁设置一段临时记忆，也称作“禁忌表”，每次迭代中，蚂蚁个体都不会移动到自己先前访问过的节点。•记忆的长度作为算法的一个参数，也影响着算法的运行效率。下面我们在的空白测试图中，为3只蚂蚁设置不同的记忆长度和参数，以随机点开始觅食，进行50次迭代后，对信息素矩阵进行了色彩化处理，实验结果如下。蚂蚁的记忆与禁忌表记忆长度=1记忆长度=10蚁群规模和初始分布蚁群规模和初始分布nfTniistart1蚁群规模和初始分布Lena原图蚁群规模和初始分布512只蚂蚁，随机分布方式9325只蚂蚁，随机分布方式蚁群规模和初始分布3*3均匀分布方式（自动计算出蚂蚁的个数为29241个3*3智能方式（自动计算出蚂蚁的个数为9325个信息素更新方式•蚁群能感受到的信息素分为两类，第一类为蚁群释放的信息素，我们称之为信息素，第二类为图像的灰度值，我们称之为启发信息。•随着迭代次数的增加，大部分路径上都会留下信息素。为了防止信息素的过度积累而使蚂蚁决策时忽略能见度信息，在完成每次迭代后，各路径上的信息素浓度需要根据公式进行更新。nkkjijiji1,,*,1终止条件•本文使用给定的迭代次数作为算法的终止条件，即算法将在进行I次迭代之后无条件终止，因此，迭代次数的选择对于算法性能的影响很大，选择适当的迭代次数尤其重要。•当蚂蚁的临时记忆包含其所有可移动节点，即蚂蚁无法决策下一步移动的节点时，终结蚂蚁个体的生命，不再进行移动。阈值的选择•蚁群算法运行之后，需要对其进行阈值化，即根据设定的阈值，将蚁群释放的信息素量所对应的边缘图像按照每个像素的灰度值大小转换为二值图像，经过这步我们便可得到边缘结果。其他若0),(552),(ThjiMjiMpheromone阈值的选择0.050.150.250.350.450.550.650.750.850.95细化•常用的细化算法有Hilditch算法、Pavlidis算法、Rosenfeld算法和Skeleton算法等。因细化并非边缘检测的必需步骤之一，同时也非本文的重心所在，本文算法的实现程序可自由地选用以上细化算法对检测结果进行细化，具体在这里不再赘述。算法的实现类设计类设计字段方法类设计字段方法界面设计运行结果性能评价与传统算法的比较Lena原图Roberts算法Sobel算法Laplacian原图Canny算法本文算法与传统算法的比较Peppers原图Roberts算法Sobel算法Laplacian原图Canny算法本文算法与传统算法的比较Airplane原图Roberts算法Sobel算法Laplacian原图Canny算法本文算法总结和展望总结•本文首先回顾了常用的边缘检测算法以及对蚁群算法的基本理论作了简单的介绍。其次，提出了一种基于蚁群算法的边缘检测模型，并对影响算法性能的各个参数作了详尽的分析。本文主要的研究成果如下：•采用8邻域结构，蚂蚁可向8个方向自由移动，概率计算函数分别由信息素量、图像灰度值、蚂蚁的惯性因子决定。•蚂蚁拥有短暂的记忆，记忆长度作为本文算法的参数之一。•提出了一种更智能的蚁群初始分布方式。•在撰写论文过程中，我们进行了大量的实验。最后，通过与传统方法的比较，从实验结果来看，本文算法在图像边缘检测中的表现令人满意。展望•在研究过程中，我们也意识到了蚁群算法客观存在的缺陷。蚁群算法属于群智能算法的一种，而群智能算法是一种基于概率计算的随机搜索进化算法，在现阶段仍然存在着一些问题：•算法的数学理论基础相对薄弱，关于此类的研究发展相对缓慢；同时，关于参数的设置现阶段并没有确切的理论依据，对具体问题与应用环境存在着很大的依赖性；•时间性能差，算法的收敛速度较慢；•与其他算法的比较性研究不足，缺乏合适的性能评估标准和测试方法；•因为算法本身基于概率，因此不具备绝对可信性，应用时或多或少地存在着一些风险。•其中，时间性能在现阶段是蚁群算法最大的缺陷之一，如何改善算法的收敛速度，仍是未来的研究方向之一。不过，蚁群算法作为一种群智能算法，与并行计算的结合，会大大提高算法的性能和运行效率，随着并行计算和云计算的发展，蚁群算法的先天优势可以很好地适应于并行计算和云计算。因此，对蚁群算法的进一步研究，仍具有很大的理论意义和实践意义。？？？？谢谢观赏