基于改进蚁群算法的图像边缘提取的研究

李伟研，杜玉晓

0 引言

图像的边缘提取是计算机视觉和图像处理中重要的内容[1]，广泛应用于目标识别与跟踪、机器人视觉、图像数据压缩等领域。准确可靠的边缘提取方法，对这些系统的整体性能起到至关重要的作用，因此边缘提取成为研究人员进行图像特征分析研究时最为关注的热门课题之一。边缘提取的目的就是找到属于感兴趣的目标轮廓的边缘，目前，用于图像边缘提取的方法很多，主要有 Roberts算子、Sobel算子、Prewitt算子、LOG算子、Canny算子、小波法等[2]，这些方法的特点是运算简单、可并行处理，但对噪声比较敏感，也没有考虑人眼视觉特性，测得的边缘比较粗糙，尤其在图像较复杂或含有噪声时更是如此。针对图像的特点，人们又提出多种提取方法，如基于 Gabor滤波器虚部的方法[3]、基于数学形态学的方法[4]等，它们在图像处理领域已被广泛采用，大多是针对各种不同类型的图像所提出的，通用性不是很强，因而还没有一种方法能适用于所有类型图像的边缘提取。

蚁群算法（Ant Colony Algorithm，ACA），是近几年发展起来的一种新型概率搜索算法[5]，它利用生物信息激素作为蚂蚁选择后续行为的依据，并通过蚂蚁间的协同与交互来完成全局寻优搜索过程。该算法具有高适应性、正反馈性和分布式处理等特点，已被成功用于解决诸如旅行商、图着色等复杂问题。将蚁群算法用于边缘提取领域，主要分为3大类：1）基于图像边缘特征的蚁群算法[6]；2）基于模糊聚类的蚁群算法[7]；3）与其他算法的融合，如遗传算法[8]、Snake模型[9]、Markov随机场[10]等。本文在传统边缘提取方法的基础上，提出了一种基于图像边缘特征的蚁群算法，用于图像边缘提取，提高了对复杂图像的适应性，实验结果证明了其有效性。

1 蚁群算法及边缘提取的基本原理

1.1 蚁群算法的基本原理

蚁群算法是由M.Dorigo等人受真实蚁群集体觅食行为的启发而提出的一种模拟仿生算法。经长期大量观察研究后发现：最初单个蚂蚁的行为是随机的。每只蚂蚁在随机行走的过程中，会在其经过的路径上留下一种叫做外激素的信息素。一方面，该信息素会随着时间的延续逐渐挥发衰减；另一方面，后来的蚂蚁能够感知这种信息素并以路径上残留信息量的多少指导其行为，一只蚂蚁选择一条路径的概率，随着以前选择该路径的蚂蚁数量的增多而增大。因此由大量蚂蚁组成的蚁群的集体行为，就表现出了一种信息的正反馈现象，从而整个蚁群的行为表现出了具有找出最短路径的能力。

1.2 蚁群算法的特性

蚁群算法最主要的特性如下：

1）正反馈。正反馈机制能够扩大解的质量对个体选择路径的影响，使得算法能够快速地发现较好的解或最优解。

2）分布式计算。分布式计算要求个体独立地搜索最优解，而个体之间互不干扰，这对于避免过早收敛有一定的效果。

3）启发性。人工蚂蚁能够利用反映可行解质量的启发信息，借以指导自己的搜索方向，这使得算法在搜索过程的早期就能发现质量较好的解，而完全随机的选择路径，会造成早期搜索到的解的质量不高。

4）鲁棒性。通过稍加修改，就可以应用到其他类型的问题当中。

5）并行性。由于每个蚂蚁个体是独立地搜索可行解，容易实现该算法的并行化，从而提高算法效率。

1.3 蚁群算法的应用步骤

应用蚁群算法解决问题的一般步骤如下：

1）分析问题，建立模型：对要解决的问题进行建模，抽象成蚂蚁觅食的过程，赋予问题空间参变量在此过程中具体意义。

2）初始化：给各参变量赋初值，将蚂蚁随机或者均匀分布到问题空间各处。

3）优化过程：蚂蚁根据给定路径长度和信息素强度做动态更新，并在运动中释放信息素。

4）终止条件：对于给定条件，若满足，则算法停止；否则，转第3）步。停止条件可以是最大的迭代次数、计算机运行时间、或者是系统所要达到的数据精度等。

第3）步是一个自适应过程，它体现了蚁群算法的本质：选择机制和更新机制。

1.4 边缘提取的基本原理

一幅图像中往往包括目标、背景、边缘和噪声等内容。边缘提取属图像分割算法中的一个算法，是图像分割、纹理特征提取和形状特征提取等图像分析的重要基础。图像中的边缘通常与图像灰度或图像灰度的一阶导数的不连续性有关。同时梯度也是反映边缘点与背景或目标区域内点区别的重要特征。图像中灰度变化较大的边缘区域其梯度值较大，灰度变化平缓的区域其梯度小，而在灰度均匀的区域其梯度值接近于0。

由于图像在采集、传输的过程中，不可避免地会伴随噪声从而导致图像质量变差，图像较为模糊不易识别。因此，首先对超声图像进行去噪处理，这里采用的是中值滤波法，它能有效地消除图像中的随机噪声。假定经中值滤波后的超声图像大小为m×n，将每个像素Xi（i=1，2....，m×n）都看作一只蚂蚁。由于目标边缘梯度未知，但可知目标内部或背景区域内像素的灰度变化平缓、梯度小，因此可以首先计算出图像中的最小梯度值Gmin，然后计算任意像素Xi的梯度与Gmin之间的幅值差，将大于阈值T的这些差值看作蚂蚁要搜索的食物。当蚂蚁寻找到“食物”，就意味着找到了目标内部或背景区域内的像素点，在输出图像中，将这些像素点颜色改为白色，而剩下的像素点颜色改为黑色，这样就提取出了图像边缘。

2 基于改进蚁群算法的图像边缘提取法

2.1 各像素点灰度梯度的计算

因为要将图像像素的灰度梯度作为蚂蚁路径选择的启发信息，所以要计算各个像素点灰度梯度，以下方法能更快的得到各点的灰度梯度。计算图像中相邻像素间的灰度差时，将图像作为相应矩阵，用相邻列或相邻行相减，可快速得到灰度差。设G为待处理图像，aij为像素点（i，j）灰度值，Gmin为图像最小梯度值，如式（1）

那么

2.2 改进的蚁群算法

在基本的蚂蚁算法中，信息素留在蚂蚁经过的路径上，本文的改进算法对此作了修改，将信息素遗留在蚂蚁所走过的每个像素点上。τij为信息素，T为梯度阈值，则

对于dij≥T，采用像素的3×3邻域来区分噪声点和边界点。邻域特征的提取方法为：先计算当前像素和邻域像素的灰度差，将该值与所设置的梯度阈值T作比较，小于T的邻域像素个数n即为该像素点的邻域特征。一般而言，当n=8时，该像素点可视为区域内点；当且时，该像素点可视为边界点；其它情况可视为噪声点。

像素点Xij被归为目标内部或非边缘区的概率为

其中，T为梯度阈值。T越大则η越大，像素点被归为非边缘区的概率就越大；dij越大则η越小，像素点被归为非边缘区的概率就越小。另外，a和β两个参数分别放置了像素被归为非边缘区的过程中所积累的信息素和启发信息素在选择像素点过程中的相对重要性。S为可选像素的集合，可定义为：

随着蚂蚁的移动，各像素点上的信息素会发生变化，每完成一次循环，各像素点上的信息素都要更新。更新规则如下[11]：

其中，（1p）为信息素的衰减系数，通常设置p＜1来避免像素点上信息素的无限增加。Δτij表示本次循环中像素点上信息素的增量，表示第k只蚂蚁在本次循环时留在像素点上的信息素。

2.3 参数说明

改进蚁群算法中共有6个主要参数：

群体规模m×n、信息素浓度权重a和启发信息素权重β、梯度阈值T、释放信息素的基数η和信息素衰减速率p。其中信息素浓度权重a和启发信息的权重β将影响到算法的行为，过大信息素浓度权重将造成过多特征的丢失，而过大启发信息的权重将加大算法对噪声的敏感度；信息素释放基数η则是为了维持信息素的最低浓度，大信息素释放基数将降低算法对信息素的敏感度；过大的衰减速率p能提高边缘提取的精度但是进一步增加了算法的复杂度；群体规模m×n将影响到算法的时间性能；梯度阈值T的大小直接影响到边缘提取的精确度。在实验仿真中，群体规模m×n一般取图像象素点个数的10%～15%，a=2.5，β=1.2，T=25，释放信息素的基数η=4，信息素衰减速率p=0.95，各个参数对于具体图像也可以作适当的调整。

2.4 基于改进蚁群算法的边缘提取流程图

图1 改进蚁群算法的边缘提取流程图

3 实验结果及分析

为了验证算法的效果，在Windows XP，Visual C++ 6.0和Matlab 6.5的运行环境上，对该改进算法在图像边缘提取技术上进行了仿真。仿真参数由多次实验结果的效果分析后确定如下：m×n为500×500，a=2.3，β=1.4，T=25，η=5，p=0.98。图2和图3分别是原始图像和通过改进算法操作后的边缘图像对比。

图2（a）原始图像

图2（b）边缘图像

图3（a）原始图像

图3（b）边缘图像

由仿真结果可以看出，改进蚁群算法的提取效果良好，对噪声图像中的边缘提取具有算法效率高、抑制噪声能力强、主要边缘信息突出等特点，能够有效地从噪声图像中提取物体的真实边缘。此外，蚁群算法的正反馈特性以及抑制噪声的能力，使其在复杂场景中的特征提取方面具有一定的优势。

4 结束语

由以上分析，证明该改进的蚂蚁算法对于图像的边缘提取是有效的，它可以清晰地搜索出图像的边缘，较好地反映出图像的边缘特征。由于实验参数的确定也没有理论上的指导，目前基本上是基于实验分析。在今后的工作中，将尝试改进算法中阈值的设定方法，将人为设定参数法改进为计算机求解最优阈值法，相信会进一步地改进图像的边缘提取结果。

[1]YuJin Zhang.Image Engineering: Image Processing and Analysis，TUP Press，Beijing，China，1999.

[2]吴健辉，杨坤涛.数字图像处理中边缘检测算法的实验对比研究[J].湖南理工学院学报:自然科学版，2007，20（2）:25-27.

[3]雷印胜.基于Gabor滤波器虚部的CT脑血管医学图像边缘特征提取方法[J].天津大学学报，2007，40（7）:833-838.

[4]李丽，路小英等.基于数学形态学的镰刀菌显微图像边缘检测[J]，农机化研究，2009，5:48-50，54.

[5]Dorigo M，Di Caro G，Stutzle T .Ant algorithms[J].Future Generation Computer Systems，2000，16（8）:5-7.

[6]ZHUANG XIN-HUA.Image feature extraction with the perceptual graph based on the ant colony system[C]//Proceedings of the IEEE International Conference on Systems，Man，and Cybernetics（SMC2004）.Washington，DC:IEEE Computer Society，2004:6354-6359.

[7]HAN YAN-FANG，SHI PENG-FEI.An improved ant colony algorithm for fuzzy clustering in image

[8]segmentation[J].Neurocomputing，2007，70（4/6）:665-671

[9]张锋，卿粼波，王旭阳等.基于遗传算法和蚂蚁算法的图像分割[J].四川大学学报:自然科学版，2005，42（4）:735-738.

[10]曹会志，王晨，罗述谦.结合蚁群算法的Snake模型的医学图像分割方法[J].北京生物医学工程，2007，26（3）:245-248.

[11]卢晓东，周凤岐，周军.马尔可夫随机场中应用蚁群系统的红外图像分割[J].火力与指挥控制，2006，31（7）:86-89.

[12]Dorigo M，Di Caro G and Gambardella L，"Ant Colony Optimization:New Meta-Heuristic"，Proceedings of the Congress on Evolutionary Computation，1999，pp.1470-1477.