基于改进蚁群算法的图像分割＊

刘晓龙，王任伟，陈 超

（内江师范学院数学与信息科学学院，四川 内江 641110）

图片背景的复杂性、目标特征的多样性、噪声等因素会影响图像分割的复杂程度，从而使图像分割成为图像处理中的难点。现有的图像分割方法众多，如阈值法、数学形态学法、边缘检测法、基于区域处理的方法、蚁群算法、快速自适应狼群优化算法[1]与二维最大熵的图像分割算法[2]等，针对不同的图像，其分割的效果都比较好，成为了目前比较受欢迎的方法。最常用的一种算法就是蚁群算法，蚁群算法是模拟蚂蚁觅食行为的一种优化算法，蚂蚁在觅食的途中会释放一种被称为信息素的化学物质，如果其中一条路上的信息素比较多，那么后面的蚂蚁选择这条路的概率会很大。

然而，由于图像分割目的不同的和图像特征的差异，现有的方法还存在着很多的不足。例如阈值法，虽然这种方法运算速度很快，但是受噪声的影响程度很大，往往会将噪声作为目标来处理；边缘检测算子往往检测到的边缘不连续或边缘不准确；数学形态学方法可以降低噪声对图像的影响程度，但是开、闭、腐蚀、膨胀等运算会造成图像过于平滑，从而导致分割后图像的不准确和图像的细节丢失[3]；传统的蚁群算法出现停滞和早熟现象的几率很大[4]。为了解决以上问题，本文提出了一种基于改进蚁群算法的图像分割方法，改进了蚁群算法中的初始聚类中心、动态更新信息素浓度和参数变量等，提高了图像分割的准确度，得到了理想的图像分割结果，缩短了算法的运算时间。

1 阈值分割法

阈值分割法就是在图像处理中利用人为主观的或者客观的方法计算出灰度阈值，将灰度值根据阈值进行划分，然后将像素进行归类，这就是阈值分割法的基本思想。简单地说，其原理就是把图像的像素分为若干个类。因为阈值分割的实现原理简单、计算量小、稳定性好，所以在运用到图像分割法时备受青睐。在图像分割方法中，阈值分割是最早的一种分割方法，也是目前所有图像分割中应用最广泛的分割方法。阈值分割的优点有很多，不像其他分割方法那么复杂，相对于其他方法来说，其运算速度快，而且它的分割方法是依据图像最基本的属性进行的，具有较高的成功率和可信度，在人工智能领域中运用的比较广泛。

阈值分割的特点如下：首先，它最适用于图像中多目标和背景的灰度级不同的情况；其二，阈值分割能够极好的降低分析和处理步骤的复杂度；其三，阈值分割的方法能够极大的压缩数据量。阈值分割法在许多的图像处理情况中都充当了图像预处理的作用，如图像分析、特征提取、模式识别等。根据目标的数量不同，可以选取单个阈值或多个阈值进行分割。

将图像进行阈值化的主要目的是将各个像素按照灰度级编排好，通过设定出不同的特征阈值将图像像素点的集合分为若干类，然后对这些像素集合进行聚类划分，这样就能得到每个子集像素与一个现实景物相对应的区域，并且可以保证各个区域内的属性达到极高的相似性，不同区域内的属性差异比较大。

2 区域分割法

图像分割中的区域分割法与其他分割方法有着明显的不同，其他的分割方法基本上都是基于像素的灰度进行阈值分割，但是区域分割是一种以区域作为基础的分割方法。区域分割有两种最主要的方法，一是区域扩张；二是排斥分割与融合。

区域扩张有三个步骤，首先是选择一个适合的扩张起始点，然后确定出一个合理的区域扩张规则，最后就是给出停止扩张的条件。区域扩张法是从扩张点出发，根据定义好的扩张规则开始扩张，直到到达停止扩张的条件为止，将图像的子区域聚合成更大的区域的过程。图像像素的灰度值、纹理和颜色等可以作为扩张出发点和相邻区域的相似性判断依据。区域生长可以是单个像素预期相邻区域的灰度特征值相互比较来实现区域扩张，也可以将图像分割成若干个小区域，比较相邻小区域的相似性，如果两个区域之间的相似性程度较高，就将它们合并。

区域排斥分割与融合同区域扩张有很多相似的地方，但区域排斥与融合是从一组扩张点开始扩张的，而不是一个。首先进行区域排斥分割，将图等分成k份，然后将这k个区域再进行排斥分割，并且也是分割为k份。直到任意的若干份之间满足相似性准则为止。排斥分割结束之后的结果中，一般会包含满足相似性规则的邻近区域，将这些区域进行融合。排斥分割与融合的操作顺序是先排斥分割后融合，但是并不一定是所有分割结束后才开始融合。如果第一次分割结束后，有满足相似性规则的邻近区域的部分，就可以马上开始融合。这样的话，排斥分割与融合就可以被视为是“同时”进行的。

3 边缘检测法

在图像处理和计算机视觉中边缘检测是最基本的问题，因为在图像分割中需要检测出图像中亮度变化比较明显的像素点，而边缘检测恰恰就是能够检测出亮度变化最明显的像素点的有效方法。在图像中，可以通过像素的亮度变化来反映图像属性的重要变化。因此，要想将图片更好的分割出来就需要判断出像素点的变化规律。图像深度上的不连续、表面方向的不连续、物质特征的变化和背景的变化都是由于像素点亮度的明显变化所引起的。在计算机视觉中，边缘检测是比较常用的算法，在特征向量的提取和区域分割等领域都有着广泛的使用。

与边缘有关的因素比较多，比如视角、像素的亮度和物质的差异等，最容易处理的边缘分割就是处理阶梯边缘。但自然界中所遇到的图片往往都是不规则的、模糊的、目标边缘附近有漫反射的等情况。

图像边缘检测不但减少了较多影响不大的数据，而且还消除了许多不相关的数据，只保留了对于图像比较重要的数据，这样就使得算法更简单、更便于操作。边缘检测主要有两种方法，一种是使用查找的方法，将图像中一阶导数的最大值和最小值寻找出来，然后利用最大值和最小值检测图像的边界；另一种方法将找图像二阶导数中的零穿越寻找出来，然后检测图像的边界。

图像整体光照强度的变化不容易影响基于边缘的检测分析，所以许多图像理解方法都将边缘检测分析作为基础。图像对比度在边缘检测中非常重要，图像对比度反映了图像在亮度上的差别，图像亮度可以使增强图像的边界特征更明显。目标边界体现了图像亮度的阶梯变化。

通过对相邻点进行差分处理可以使图像的亮度变化更加明显。通过差分处理水平方向上的相邻点，可以检测出图像在垂直方向上的亮度变化，这种算子被称为水平边缘检测算子。垂直算子可以检测出水平方向的亮度变化，因而垂直边缘检测算子检测的是水平边缘。在本文中主要运用的是一阶边缘检测，其中常用的算子如下：

Roberts边缘检测算子：一种最简单的算子，是一种通过局部差分来寻找边缘的算子，也可以说是用两像素之差近似梯度的变化值来进行边缘检测的算子。

Prewitt边缘检测算子：这是一种一阶微分算子，它是一种先求出图像上下左右相邻点的灰度差，再求出灰度差的极限值，再用极限值来检测边缘的一种算子。Prewitt算子的基本原理就是建立一个水平方向的边缘检测和一个垂直方向的边缘检测。

Sobel边缘检测算子：这是一种一阶离散型差分算子，主要用来计算图像像素亮度函数的梯度近似值，能够对像素位置的影响进行加权，还引入了局部平均的算法，这样就能够很好地去除噪声的影响。

4 传统的蚁群优化算法

蚁群算法是一种通过观察蚂蚁觅食行为而提出的仿生进化算法。在蚂蚁觅食的时候，有多条路径可以到达食物源，在最开始的时候，各条路径上是没有信息素的，因此刚开始蚂蚁行走的路径是随机的，蚂蚁在行走过程中会不断释放信息素来标识自己所行走的路线，随着时间的推移，走在最短路径上的蚂蚁最先到达食物源，同时，在最短路径上的蚂蚁也最先将食物原路运回到出发点，蚂蚁经过的路径上都会释放出这种信息素，随着时间的延长，该激素会不断挥发。因为蚂蚁在觅食的行径路上会不停地释放信息素，信息素浓度较高的那条路对后面的蚂蚁的影响就越大，后面的蚂蚁选择该路径的概率就越大，这样就会使这条路上的蚂蚁越来越多，信息素浓度也会变得越来越大。因此使得“信息素浓度”与“蚂蚁数量”之间形成了正反馈的关系。最终，通过的蚂蚁数量最多并且信息素浓度最高的那条路径就是最短路径。

图像当中包含了目标、背景、边界和噪声等，要切割图片，就先要对图片进行分类，而分类的关键就是找出图片中目标之间具有区别的特征量。图像目标和图像背景主要是靠像素灰度来区别的，所以依据像素灰度的不同进行聚类划分是比较有效的。灰度在边界点和噪音点很可能会发生突变，这种突变反映出边界点与背景、目标区域区别的重要特征。先计算出灰度差阈值，再将各像素与灰度差阈值进行对比，如果比阈值小，那么就是我们所要提取的周边像素的特征。

首先，将原始图像G的每个像素g视为一只蚂蚁，因为每只蚂蚁都被视为以灰度、梯度和邻域为特征的三维向量，因此，图像分割就转化为了具有不同特征的蚂蚁搜索食物源的过程，若任何两个像素gi到g的距离为dij，则dij为

其中，蚂蚁的维数用m表示，这里m等于3，q是加权因子。

设r是像素灰度值聚类的半径，φ作为蚂蚁释放的信息素，则

其中，gi选择到gj路径的概率为Piji，β(t)是启发式引导函数，α和β分别是对蚂蚁选择路径的影响因子。表示为可行路径,则有

蚂蚁在移动过程中，各路径上的信息素浓度会发生变化，通过一次循环，每条路径上信息素浓度都会发生变化，通过下式调整

△dij其中，ρ表示为路径上已有信息素的衰减程度，△dij表示为每次循环路径上的增量，△αkij表示第k只蚂蚁在该次循环的路径上所留下的信息素，不同路径上的信息素的浓度会随时间发生变化，每次循环之后路径上的信息素也会不断更新。

4.1 传统蚁群算法的不足之处

从上面传统蚁群算法的图像分割模型可以看出，虽然传统蚁群算法已经被证明是一种有效的解决图像分割的方法，但是还存在以下的不足[5]：

1）限于局部最优解。对算法的解来说，传统蚁群算法寻找的是一个有效的局部最优解，而求解得到的不是全局最优解。

2）求解算法中的停滞问题。算法开始时收敛速度很快，在算法求解的过程当中，迭代到特定的次数后，蚂蚁也会在某个或某些局部最优解的邻域附近发生停滞。

3）搜索时间较长。尽管和其他算法相比，传统的蚁群算法在迭代次数和解的质量上都有一定的优势，但目前计算机的运算速度还不理想，搜索的时间还很长。虽然随着计算机计算性能的提高、蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于规模大且复杂的图像分割模型，这还是一个急需解决的难题。

5 蚁群算法的改进

先用命令imread读取原图像，然后用命令rgb2gray将图像转化为灰度数字图像并得到灰度图像矩阵，将图像中的每个像素Xi（i=1，2，…，N）看作是一只蚂蚁，所以每只蚂蚁都是具有灰度特征的一维矢量，图像分割的过程就转化成了具有不同特征矢量的蚂蚁 i（i=1，2，…，N）寻找食物源的过程，而食物源即是图像分割的最佳阈值T，如图1所示。

图1 改进的蚁群算法流程图

改进的蚁群算法步骤如下：第一步，初始化相关参数，确定信息素重要程度参数α，确定启发式因子参数β，获取最大蚂蚁数目x，确定聚类半径r，确定挥发系数ρ，确定信息素随时间变化的系数，初始化类集合中所有像素灰度值总和m为0，初始化类集合中所有像素个数为n为0，确定食物源中心（初始聚类中心）c为128；第二步，计算每只蚂蚁i到食物源中心c的距离；第三步，更新类集合中每只蚂蚁i与食物源c之间的距离di；第四步，计算t时刻每只蚂蚁i在路径上放置的信息浓度τi；第五步，计算每只蚂蚁i与聚类中心c的相似度；第六步，更新类中每只蚂蚁i的信息素浓度τi；第七步，更新每只蚂蚁i与聚类中心c的相似度；第八步，计算每只蚂蚁i到阈值集合的概率；Pi第九步，计算类间每只蚂蚁i的灰度值的平均值得到最佳阈值T。

5.1 改进后蚁群算法的详细步骤

步骤一：初始化阈值。

为了减少大量无关的计算，加快算法的运行进程，初始阈值的设置只要合理即可，因此本文将初始阈值设置为256灰度级图像中最大像素值256的一半，即初始化阈值（即食物源中心）c为128

c=128

步骤二：计算每只蚂蚁i到食物源中心c的距离。

根据欧氏距离公式计算每只蚂蚁i到实物源中心c的距离dj

步骤三：更新类集合中每只蚂蚁i与食物源c之间的距离dj。

如果di小于等于蚂蚁的聚集半径r，则dj等于di

步骤四：计算t时刻每只蚂蚁i在路径上放置的信息浓度τi。

计算t时刻每只蚂蚁i到初始食物中心c的路径上的信息素浓度τi，若蚂蚁i到初始阈值c的距离di小于等于r，则τi等于1，否则τi等于0

步骤五：计算每只蚂蚁i与初始食物中心c的相似度ηi。

如果蚂蚁i到初始食物中心c的距离di为0，那么蚂蚁i与初始食物中心c的相似为1，否则蚂蚁i与初始食物中心c的相似度ηi为

步骤六：更新类中每只蚂蚁i的信息素浓度。

如果蚂蚁i到初始食物中心c的距离di小于等于蚂蚁的聚集半径r，则将信息素浓度更新为（ρ是挥发系数），并记录下位于蚂蚁聚集半径r内的像素个数n

其中，参数ρ的设置起了至关重要的作用，可以使用以下方式设置合适参数值，精调谐参数[6]：对参数ρ使用小范围的数值调谐获得较好的数值，即ρ=0.9。

步骤七：更新每只蚂蚁i与初始食物中心c的相似度。

如果蚂蚁i与食物中心c的距离di小于蚂蚁的聚集半径r，那么新相似度等于原来的相似度

步骤八：计算每只蚂蚁i到阈值集合的概率pi。

其中，α是与信息素浓度相关的重要程度参数，β是启发式因子参数，是路径集合。算法中参数α、β的设置起了非常重要的作用，决定了整个算法的收敛速度和搜索性能，可以使用粗调谐参数设置合适参数值，对参数α和β采用大范围的数值调谐以获得理想的值，即α=1，β=10。

步骤九：计算类间所有像素的灰度值的平均值T。

其中，如果pi小于p0，那么蚂蚁i就会被归为新的阈值集合内，所有归入到新的阈值领域的阈值集合表示为。

5.2 更新类中每只蚂蚁的信息素浓度

通过一次迭代，每个类中的信息激素浓度都会发生变化。为了得到全局优化的结果，降低算法的收敛速度，本文采用自适应调整信息激素浓度的方法为

式中：ρ是信息素随时间变化的系数；n是di≤r的时的像素数量；m是所有的像素总数；△τi是通过一次迭代后路径上信息素的改变量。

5.3 设置停止条件

一般以固定的数值作为停止条件，但这样会有很大的局限性和不确定性。比如设定的数值太小，那么会造成优化不够充分，可能得不到全局最优解。如果设定的数值太大，会使运算速度减慢，极大地降低了运算效率。因此想出了动态自适应的方法来控制循环，如下:

当上式满足ε=0.01时，算法终止，反之继续运行寻找最优阈值。

6 实验结果及分析

本文采用Matlab R2014a进行仿真实验。实验取用了四张像素的卡通图像分别记为原始图像1、原始图像2、原始图像3、原始图像4，分别为图2到图5的第一张图。为了分析并验证提出的改进蚁群算法的实际效果，采用了边缘检测算法、传统蚁群算法、改进后的蚁群算法对4张原始图片进行分割，分割的效果如图2、图3、图4、图5所示，其中，第2张图片为对原始图像进行Roberts边缘检测算子的分割结果，第3张图片为对原始图像进行Sobel边缘检测算子的分割结果，第4张图片为对原始图像进行Prewitt边缘检测算子的分割结果，第5张图片为传统蚁群算法（基本蚁群算法）的分割结果，第6张图片为改进后蚁群算法的分割结果。前2种方法大体可以将目标图像从背景中分割出来，但是在细微方面，卡通人物的分割效果不是很好，本文的方法能将图像的细节部分分割的更加准确。

图2 分割图像结果1

图2 分割图像结果1

图3 分割图像结果2

图4 分割图像结果3

图5 分割图像结果4

为了体现改进后蚁群算法的优越性，可以通过图像的信息熵和算法的运算时间来客观地分析和比较[7-8]。将图像信息熵H，运算时间t（单位为s）作为实验的结果来进行评判。图像信息熵是一种图像信息统计量，它反映了图像信息量的多少，分割后的图像信息熵值越大，说明图像从源图像得到的信息量越大，分割得到的图像细节越丰富，分割后的总效果越好，本文中信息熵定义为

表1 边缘检测法（prewitt算子）

表2 边缘检测法（sobel算子）

表3 边缘检测法（roberts算子）

表4 传统蚁群算法

表5 改进后的蚁群算法

从表1到表5得出本文改进蚁群算法的信息熵值最大，这说明了此算法从原始图像中得到的信息量最大，分割效果最好，从运算时间上比较，本文所提出的算法运行时间更少，更加高效。

7 结语

通过改进蚂蚁信息素浓度的更新、初始聚类中心和参数的设置，提高了蚁群算法对图像分割的精准度，获得较好的图像分割效果。从运算时间来看，本文改进后的蚁群算法比边缘检测算法缩短了大约58%，比传统蚁群算法缩短了大约3%，极大地提高了运算效率。蚁群算法已经越来越多地应用到图像处理中，如何能更好的改进此算法并将其应用到实际问题中，将会是未来主要的研究方向。