基于蚁群算法和C－means 算法的图像分割方法

吴小菁，陈星娥

(福建江夏学院，福建福州 350108)

图像分割是对图像进行处理以及计算机视觉领域的最基础工作，具有很多种分割办法。而第一代编码技术主要依据波形编码，利用像素来表示图像;第二代编码主要针对图像内容进行编码，其信源模型利用对图像的划分，让它们变成很多不一样的对象，随后对每个对象进行编码，通过一个统一程序，发送运动的轨迹和纹理。此外，可以参照人们视觉的爱好对象进行分配比特数。和波形的编码压缩法比较，这种方式具有更高的效率，也为查询对象的内容夯实了基础。

1 蚁群算法基本原理

蚂蚁会在行走的路线上释放信息素以实现和其他蚂蚁的间接交流，启发了蚁群算法的诞生，该算法有信息素挥发、正反馈两种机制［1］。从蚁穴到食物源会存在多条路径，但绝大多数蚂蚁都能选择出最短的路径，就是利用了正反馈机制，因为单位时间内最短路径上通过的蚂蚁数量较多，信息素含量也就会随之增多，吸引越来越多的蚂蚁，最终实现蚂蚁都经过最短路径寻找食物源或返回蚁穴;信息素挥发则可避免路径上信息素含量的大幅增加。蚁群算法中的蚂蚁与现实中的蚂蚁存在区别:蚁群算法中的蚂蚁并不是完全依照信息素强度进行路径选择，它们具有记忆区，而且还处在离散时间状态中。如图1 可进行抽象说明:(a)表明蚁群蚂蚁沿着A－E 路径行走;(b)说明当出现障碍物时，蚂蚁们会分成两条路径行走;(c)显示绝大部分蚂蚁都会选择较短路径行走，较短路径上聚集了更多的信息素，吸引越来越多的蚂蚁选择。

如图1 所示，设定A 点为蚁穴，E 点是食物源，HC 是障碍物。蚂蚁行走要绕开障碍物，有两种选择，经过H或经过C 到达食物源，路径距离为:BH=HD=1，BC=CD=0.5。假设t=1 的时候，有30 只蚂蚁从蚁穴出发去往食物源，路径上没有信息素，蚂蚁分开绕行，BH 和BC 均有15 只蚂蚁选择，由于信息素会伴随时间的流逝而逐渐挥发，如果蚂蚁群的运动速度一样，路径信息素的留余会和路径长度成反比，而蚂蚁算法和路径的概率与信息浓度成正比，所以BH、DH 路径上蚂蚁留下的信息素挥发量是BC、DC 路径上的2 倍。t=2 时，30 只蚂蚁返回蚁穴，就会选取信息量浓度较多的DC 和BC 路径，也就是说有20 只蚂蚁会选择DCB 路径，而同时有15 只DHB 路径［2－3］。照此推理，经较长时间运动后，选择DCB 路径的蚂蚁会越来越多，最终都选择DCB 路径。

图1 蚂蚁觅食抽象图

2 基于蚁群算法和C－means 算法的图像分割算法

采用蚁群算法进行图像分割的主要指导思想是:由于图像分割是一种把图像中全部的像素记作不同类别的过程，在应用蚁群算法求解时，蚂蚁会对图像中的全部像素进行分类标记，记下每个像素中相对应的类别就组成了解决图像分割问题的一个解。如果把一幅图像分为C 类，在此基础上，把每个像素依据一定的规则划分到C 类中的某一类。那么对于一张M×M 面积的影像来说，共有CM－M种划法，一般情况下，根据固定的划分判断标准选取一种最佳划分方法从而达到分割图像的目标，如果像素的空间较大，相应的划分数量也会较大;如果把这一个聚类过程直接在像素集合方面进行的话，分割过程中的计算量也是惊人的［4－5］。从本质来讲，聚类算法是利用像素的灰度信息，以图像中存在的灰度级别作为分析的对象，能够减少搜索的划分组合数，缩短计算时间。采用蚁群算法解决聚类问题的流程如下:

2.1 解析问题，确定问题的编码

首先把256 色的灰度图像按照一定的要求分成C 类，可以看作是蚂蚁要经过256 个灰度级找寻食物，通过每一个灰度级都要对其进行类别划分，随后前进一步，而每一步的选择都要划分类别数进行确定。对于第二类问题一共有2256种方法［6］。所以，这个问题的编码长度是256 位，每一位解元素的数值表示对应灰度级被划分到相应的类别标记。

2.2 确定相对应的适应函数

如果x=(x1，y1)表示一个像素的坐标，而g(x)表示像素的灰度数值，则C－means 算法就要最小化。而C－means 的值越小，表明聚类的效果越好;值越大，适应度的函数数值越大，说明计算所得的解的质量越好。

2.3 优化途径

2.3.1 构建解串

假若选用N 只蚂蚁来寻求问题的解，那么对于256 色的灰度影像，所得解的长度就等于256。为了建立一个解，蚂蚁会采用信息轨迹以及启发信息对每个灰度级进行标记。在算法的初步阶段，信息素矩阵就会被初始化成一个很小的数值。每一个灰度级具有相应的信息素浓度，一共有C 种。对于这种问题，信息素的矩阵大小一共有256 ×C，并且随着迭代的进行而不断地进化。把灰度级和待标记类的灰度中心距离当作启发信息，假如灰度级和某一个种类的灰度中心相距较近，则说明该类的可能性很大［7］。因此蚂蚁第一次漫游对灰度级进行划分时，起初的类中心都是随机选取的，随后的迭代中类中心是通过最优解求得的。

2.3.2 小范围搜索

采用点式变异进行局部搜索。先从生成服从均匀布列的［0，1］之间的随机数，序列的长度就等于解的长度，代表对应解中某位能否发生变异的概率。假若某一个随机的数值比设定的概率阈值小，那么对应解中该位的标记就要发生变异。如果灰度级L 被选中进行变异，那么产生均匀分布的［1，c］间的随机整数就会代替原来的类别号。随后计算新解的适应度，假如比原来的适应度优良，就能够取代变异前的解串。

2.3.3 更新信息素，确定控制参数

在完成迭代以后，要从蚂蚁群中选取质量最好的20%的蚂蚁更新信息素。采用最优解的保留方法，在循环过程中建立一个全局最优解，把它作为全局的变量保存起来。假如迭代过程中得到的最优解比全局的最优解好，就可以用它代替全局的最优解;如果相反，则保持最优解不变［8］。每一个类别中的类中心都要根据最优解来解答。蚁群算法的控制参数主要有蚁群规模、局部搜索比例、搜索概率、循环次数等，选择最大的运行次数作为终止的条件，把适应度最大的划分当作聚类的结果。

3 结语

基于蚁群算法和C－means 算法的图像分割方法能够比一般的C－means 算法获得更好的聚类结果主要原因在于，蚁群算法在搜寻最优解的过程中采用的是群体寻优的方法，经过无数次的迭代操作以后，消除了初始类中心选择不佳的影响，经过在较优解元素的基础上释放出更多的信息素，使得群体合作搜索的方法让解的质量整体向更好的方向转化，最后生成了很好的解。总之，蚁群算法和C－means 算法相结合的图像分割方法，使分割结果有了较大程度的改善，使得聚类的精度更高，具有很大的应用前景。

［1］汤可宗，江新姿，高尚.蚁群模糊聚类的图像分割［J］.计算机工程与设计，2008(7):1770－1771.

［2］叶志伟，常胜，高山.基于蚁群算法的最佳熵图像分割阈值方法［J］.湖北民族学院学报:自然科学版，2007(3):304－307.

［3］卢珏.基于自适应蚁群算法的图像分割［J］.ITS 通讯，2005(4):886－889.

［4］何小娜，逄焕利.基于二维直方图和改进蚁群聚类的图像分割［J］.计算机技术与发展，2010(3):128－131.

［5］赵娜，王希常，刘江.自适应蚁群算法优化红外图像分割［J］.计算机应用研究，2009(11):4375－4377.

［6］叶志伟.一种基于蚁群算法和C－Means 算法的图像分割方法［J］.激光与红外，2007(13):106－107.

［7］白杨，孙跃，王君，等.基于动态自适应蚁群算法的MRI 图像分割［J］.计算机科学，2008(2):226－229.

［8］王爽，黄友锐，李冬.基于蚁群算法的改进Otsu 理论的图像多阈值分割［J］.微计算机应用，2008(4):25－28.