基于改进的蚁群算法的边缘连接方法

宋建军， 侯志强， 余旺盛

(空军工程大学电讯工程学院，西安 710077)

0 引言

边缘检测在图像处理和计算机视觉中有着重要的作用，通过检测图像边缘可以完成对图像的分割，其正确性和自适应性在一定程度上影响着目标检测和识别的智能化程度。由于噪声的干扰、图像中的背景以及图像内容的复杂性影响，仅仅使用某种传统的边缘检测算子如 Roberts，Sobel，Prewitt，Kirsch，Laplacian 和Canny［1］等来进行边缘的提取，而不进行边缘连接的话，最后检测出来的边缘可能存在不连续现象，因此需要对获得的边缘图像做进一步的处理，即边缘连接。经过多年的研究，已经得到了多种边缘连接方法。例如，膨胀细化法［2］通过多次膨胀细化实现边缘的连接，会使图像边缘过度失真;最小点对法［2］直接使用直线连接两个相邻边缘端点，此方法得到的补偿边缘不能正确地反映原始图像边缘信息;填充小间隙法［3］相对于边缘简单的图像连接的效率和准确度比较高，但是对于边缘复杂的图像，可能造成图像过度分割，效果较差;Hough变换法［3］，并不是所有的边缘都能满足特定的形状，适用于此方法。基于模糊判决的图像边缘连接方法［4］，主要是基于局部范围内梯度值来决定像素属于边缘的隶属度，选择隶属度大的为边缘点。文献［5］提出结合分水岭算法实现边缘连接，在Canny算子检测到目标粗略轮廓的基础上，从基于标记的分水岭算法的过分割结果中根据最小距离准则搜索缺失的边缘段进行边缘连接。

蚁群算法是一种组合优化问题的启发式搜索算法，具有并行性、离散性、鲁棒性、正反馈的特点。近几年有不少学者将蚁群算法用于改进边缘检测算法。在基于蚁群优化的边缘检测算法中，大多选择图像像素的灰度梯度作为蚂蚁的启发信息。文献［6］提出一种基于梯度定义和蚁群算法的边缘提取算法;文献［7］提出了基于多态蚁群优化的图像边缘检测，而边缘连接可以看成一个寻找最优边缘像素点的过程;文献［8］提出使用蚁群算法来补偿传统边缘检测方法没有检测出来的边缘，通过引入原始图像信息，得到的补偿边缘能够正确反映原始图像信息，但是蚂蚁寻找路径的过程盲目性较大，容易陷入局部解，无法充分地连接断裂边缘;文献［9］在改进Canny算子检测的结果上，引入了方向信息，对蚂蚁寻找路径起一定指引作用，但是得到的补偿边缘正确性较低。本文提出一种基于改进的蚁群算法的边缘连接方法，从原始的彩色图像得到能见度矩阵，通过能见度矩阵设置每个像素点的初始信息激素，并控制信息激素的更新;综合考虑梯度幅值和梯度方向来确定启发式引导函数，使蚂蚁沿着真正的边缘行走;并且考虑了蚂蚁的走向问题，从而既保证了连接边缘的正确性，也在一定程度上降低了蚂蚁陷入局部解的可能性，从而能充分地连接断裂边缘。

1 蚁群算法

蚁群算法又称蚂蚁算法，是由意大利科学家M.Dorigo［10］等人受自然界蚂蚁寻找食物的过程启发而提出的一种新型搜索优化算法。

根据蚁群算法基本原理，假设第m只蚂蚁的当前位置为(x0，y0)，(i，j)为像素点(x0，y0)的其中一个领域像素，根据式(1)的路径转移规则选择路径

式中，N表示其中可选路径的集合，也就是像素点(x0，y0)的8邻域像素集合，但不包括蚂蚁记忆走过的路径。

随着每个蚂蚁的移动，各个像素上的信息激素强度将发生变化，经过一次迭代后，要对每个像素点的信息激素强度进行更新。像素点(i，j)处的信息激素强度根据式(4)进行调整

式中:ρ为信息激素的挥发率;Δτ(i，j)为本次循环中经过像素点(i，j)处的蚂蚁留下的信息激素的总和。

2 改进的蚁群算法

2.1 能见度矩阵的求取

由于对单独彩色平面的处理并不总是等于直接在颜色向量空间中的处理，分别计算图像梯度然后形成彩色图像可能得到与人眼视觉特性不一致的结果。因此，在彩色向量空间直接计算梯度比以单独的分量图像为基础计算梯度具有更高的准确度。本文采用彩色向量空间梯度算法［2］，直接在RGB向量空间计算梯度。

设 r、g、b是 RGB 彩色空间沿 R、G、B 轴的单位向量，像素(x，y)沿水平方向和垂直方向的彩色梯度可用向量来表述

数量gxx、gyy、gxy定义为这些向量的点乘

据此可得彩色图像I的梯度为

式中

像素(x，y)在原始的彩色图像的能见度矩阵中的对应值为

式中:▽Imax(θ)表示彩色图像 I中的最大梯度值;▽I(x，y)(θ)表示像素(x，y)的梯度值。一般来说，如果像素(x，y)在边缘上，ξ(x，y)的值很大，如果像素(x，y)不在边缘上，ξ(x，y)的值较小。用能见度矩阵初始化每个像素的信息激素。

2.2 蚂蚁初始位量的设置

如果在边缘图像的每个边缘点上放若干只蚂蚁，搜索量相当大，文献［11］提出通过提取边缘端点，将它们作为蚂蚁的初始位置，从而大大地降低了搜索量。首先对边缘图像进行相关处理，使边缘为单像素，且边缘像素值为255，背景为0。然后根据式(10)计算像素的连接数，连接数为1的像素即为边缘端点。

如果E=1，则此像素点即为边缘的端点。式中:f(xk)表示像素点x的像素值;k代表8邻域的第k邻域，见图1。根据式(10)对每一个边缘像素点进行端点判断，得到端点的集合，这些端点即为蚂蚁的初始位置。

图1 像素x的8邻域Fig.1 Eight neighborhoods of pixel x

2.3 启发式引导函数设置

设(x0，y0)为蚂蚁的初始位置，(i，j)是以(x0，y0)为中心3×3结构的邻域像素，可根据梯度幅值和梯度方向的相近程度来判断像素(x0，y0)与(i，j)的相似性。像素间的相似性公式为

2.4 信息激素更新规则

蚁群算法的负反馈作用就是通过信息激素的更新实现的，为了防止早熟收敛行为，引入了信息激素的最大值和最小值的限制，即 τmin≤τi，j≤τmax。具体更新规则如式(13)所示。

式中:Np表示蚂蚁m所得到的路径的长度，即路径所包含像素点的个数;和σξ分别表示蚂蚁m所得到的路径上的像素所对应的能见度矩阵中元素值的均值和方差。越大，表明蚂蚁m所得到的这条路径与其领域的像素的对比度越大，边缘的可能性越大，则留下的信息激素越多;σξ越小，表明蚂蚁m所得到的这条路径上的像素更可能属于同一条边缘，避免蚂蚁经过边缘之间时在非边缘处留下信息激素。

2.5 蚂蚁停止行走规则

在探索的过程中，一幅图像包含许多边缘端点。因此一些蚂蚁可能会寻找到一些重复的图像区域，产生许多无效的探索路径。为了减少探索路径的次数，提高运算速度，本文提出了以下4种措施。

1)设置最长记忆路径长度。人工蚂蚁具有记忆功能，能够记忆所走过的路径。如果蚂蚁在此次路径寻找过程中，走过的路径长度大于设定值L，则蚂蚁停止行走，即寻找失败。

2)将一个端点设为初始位置，当蚂蚁行走到端点自身的边缘像素时，蚂蚁停止行走，即寻找失败。

3)当蚂蚁走到其他端点处的蚂蚁所走过的路径时，则蚂蚁停止行走，即寻找成功。

4)当蚂蚁走到除端点自身边缘以外的其他边缘点时，则蚂蚁停止行走，即寻找成功。

3 算法步骤

1) 初始化 C，L，τmin，τmax，ρ，q0，α，β 等参数。

2)对原始的彩色图像进行Canny边缘检测，使边缘像素值为255，背景为0，并根据式(10)对边缘图像进行端点提取，同时，根据能见度矩阵设置每个像素点的初始信息激素的强度。

3)选择一个端点，并且标记此端点所属的边缘，同时在该端点处放置m只蚂蚁，接着转步骤4);如果所有端点都已处理，则算法结束。

4)选择一只蚂蚁根据式(1)规则进行转移，并保留路径。如果满足2.5小节给出的停止行走规则，此蚂蚁停止行走。判断所有蚂蚁是否都已完成探索过程，如果是则进行步骤5)，否则继续进行步骤4)。

5)在所有连接成功的路径中，选择fm最大的路径作为选择的端点在本次迭代过程中获得的最佳路径，并与原最优路径进行比较，如果更优，则替代最优路径。同时根据式(13)来更新信息激素的强度。更新完成后，清除所有已找到路径，进入步骤6)。

6)判断迭代是否停止，如果不停止，则返回步骤4);如果停止，则将得到的最优路径与原边缘图像进行叠加，并剔除已进行连接的边缘，同时返回步骤3)。

4 实验结果及分析

本文所有的处理过程均是在Matlab7.0下编程实现的。实验过程中一些参数的选择为:C=1，L=30，τmin=0.001，τmax=10，ρ=0.1，q0=0.9，α =1，β =2，迭代次数为100次。测试图像及其处理结果如图2和图3所示。图2a和图3a是原始的Lena图像和House图像;图2b和图3b是经过Canny算子边缘检测的边缘图像;图2c和图3c是根据文献［8］中方法得到的结果;图2d和图3d是根据文献［9］中方法得到的结果;图2e和图3e是使用本文改进方法得到的结果。

通过仿真试验比较，发现采用文献［8］中方法得到补偿的效果比较差，有的边缘没有连接起来，例如图2c中Lena图的头顶的边缘还没有完全连接起来，图3c中树枝也存在断裂部分。由于文献［8］中蚂蚁寻找路径的过程盲目性较大，容易陷入局部解，无法充分地连接断裂边缘;而根据文献［9］中方法得到补偿效果相对文献［8］较好，但是效果仍然不理想，例如图2d中Lena图的头顶出现虚假边缘。由于文献［9］中引入了方向信息，对蚂蚁寻找路径起一定指引作用，但是得到的补偿边缘正确性较低。本文改进方法能够补偿所有的断裂边缘，并且补偿结果与原图像边缘信息完全吻合，比其他两种方法更好。

图2 仿真结果对比Fig.2 Comparison of simulation results

图3 仿真结果对比Fig.3 Comparison of simulation results

5 结束语

蚁群算法是一种较新的应用于组合优化问题的启发式搜索算法。本文将蚁群算法应用于图像边缘检测领域中，进行了有效的探索，提出了一种基于改进蚁群算法的边缘连接方法。该方法利用能见度矩阵来设置像素点的初始信息激素和调节信息激素的更新，从而减小了在算法运行初期定位错误的概率，提高了迭代过程中信息更新的准确性，提高了算法的时间性能。实验结果表明，得到的补偿边缘能够很好地反映原始图像信息，连接效果较好，能满足一些应用场合对边缘检测的轮廓封闭性需要。但基于蚁群算法的边缘连接方法中的参数是人为设定的，而没有理论上指导，根据图像的自身特征自适应地调整参数可能会取得更好的边缘连接效果，有待于实验验证。同时蚁群算法花费的时间很大，也需要进一步研究。

［1］ CANNY J.A computational approach to edge detection［J］.IEEE Transactions on Pattern Analysis And Machine Intelligence，1986，8(6):678－698.

［2］ 冈萨雷斯.数字图像处理［M］.北京:电子工业出版社，2005:420－482.

［3］ 董梁.基于哈夫变换的图像边缘连接［J］.现代电子技术，2008，31(18):149－150.

［4］ 杨绍清，贾传莹.基于模糊判决的图像边缘连接［J］.光学技术，2002，28(2):108－112.

［5］ 刘荣，侯志强，谭洪波.结合分水岭变换的彩色图像边缘检测算法［J］.微计算机信息，2010，26(9):189－191.

［6］ 陈亮，郭雷.一种基于蚁群算法的边缘提取算法［J］.光子学报，2010，39(4):759－763.

［7］ 张健，周激流，何坤，等.基于多态蚁群优化的图像边缘检测［J］.计算机工程与应用，2011，47(3):20－23.

［8］ LU D S，CHEN C C.Edge detection improvement by ant colony optimization ［J］.Pattern Recognition Letters，2008，29(4):416－425.

［9］ WONG Y P，SOH V C M，BAN K W，et al.Improved canny edges using ant colony optimization［C］//The Fifth International Conference on Computer Graphics，Imaging and Visualisation，Penang，2008:197－202.

［10］ DORIGO M，CARO G D.The ant colony optimization meta－heuristic［C］//New Ideas in Optimization，London，1999:1－27.

［11］ 路漫漫，滕奇志.蚁群算法实现的图像边缘连接［J］.计算机应用，2010，30(4):932－935.