基于类间蚂蚁竞争模型的显著图像分割算法

黄小童，程 虹，罗 颖

(湖北文理学院，湖北 襄阳 441053)

0 引 言

图像分割和对象提取一直是图像处理中的重要分支，在计算机视觉、智能图像识别、生物医学、气象、军事、遥感等众多领域有着广泛的应用。近年来交互式的半自动分割通过用户交互，获取尽可能多的分割信息，大多是基于图论的最优分割，基本原则是使得划分的子图(区域)内部相似度最大，子图之间的相似度最小，同时应约束划分区域的特性。其中常见的图像聚类问题或分割割集准则包括：Minimum Cut、Average Cut、Grow Cut、Normalized Cut[1]、Random Walks[2]、Geodesic[3]、Spline Regression[4]，其缺点在于需要人工交互，从很大程度上依赖用户的标记情况，自动性较差。

20世纪末，意大利学者Dorigo提出了蚁群优化(ant colony optimization，ACO)的概念和算法，该算法是通过观察蚂蚁寻找食物的过程，能够找到从巢穴到食物源最短路径这一现象。近年来，蚁群算法在图像分割方面的应用研究主要包括以下几个改进：

(1)最优分割的收敛：文献[5]设计了一种基于随机游走更新策略的蚂蚁聚类算法，通过蚂蚁的群体智能自组织地产生聚类，能自适应更新参数。文献[6]采用蚁群搜索与模糊聚类相结合的方法，蚁群搜索仅仅用来确定聚类数目和中心。根据“分而治之”的原则，单蚁群可演化到多蚁群策略，即先由各蚁群独立优化各自子问题，然后采用动态自适应信息交换策略进行局部最优解传递，成功降低了二维图像分割中最小能量化函数的病态性[7]。(2)边缘断裂的改善：文献[8]首先进行边缘检测获取由真实边缘和噪声组成的边缘备选集，以较大概率选择梯度值高的像素点，使搜索向边缘收敛，然后根据蚁群搜索路径上信息素的累积结果提取边缘。但是该方法计算量大，同时边缘散乱不连续。为此，引入幅度、相位和搜索方向信息作为启发信息，加强蚁群边缘提取中的抑噪能力[9]。

从整体来看，蚁群图像分割算法的相关研究尚处于起步阶段。该文的研究重点是类间蚂蚁竞争模型的显著图像分割，发展具有人工干预少、精度高、可靠性好等优点的显著图像分割算法。在此基础之上进行的应用研究将使得本项目的研究有着重要的现实意义。著名的单种群动力学Logistic模型关注了单个种群的数量变化情况，事实上任何生物种群中都存在类间竞争情况，从而实现种群之间的协同进化。受到这种竞争关系的启发，该文以传统蚁群算法为基础，提出类间蚂蚁的竞争模型，设想基于两类蚂蚁相互竞争的显著图像分割。算法首先采用SLIC(simple linear iterative clustering)超像素分割对图像的预处理，保留原始图像信息，将图像分割成不同区域，既可以提高分割精度得到理想的分割结果，同时可以缩短运算时间。然后根据蚁群算法的思想，为了弥补单类蚂蚁分割易造成的欠分割或者过分割，引入两类蚂蚁，每一类蚂蚁寻找各自目标(前景/背景)，不同类别的蚂蚁之间进行信息互补与竞争，使得分割结果更加准确。根据种群竞争思想，设定两类蚂蚁，根据每类蚂蚁设定食物目标不同，从而相互竞争，最终找到各自的食物，多类蚂蚁相互竞争，“优胜劣汰”，最终根据两类蚂蚁分泌的信息素竞争得到最终的结果。

1 改进的类间蚂蚁竞争模型显著图像分割

首先将SLIC超像素分割引入算法中，然后分别从类内蚂蚁的运动模型和类间蚂蚁的竞争模型进行阐述。

1.1 SLIC超像素分割，构建区域邻接图

传统的蚁群算法为了保证分割结果的有效性，需要在图中放置大量蚂蚁，导致运算时间复杂度较大。该文引用SLIC算法[10]，即简单的线性迭代聚类。它是将彩色图像转化为CIELAB颜色空间和XY坐标下的5维特征向量，然后对5维特征向量构造距离度量标准，对图像像素进行局部聚类的过程。该文采用文献[11]超像素分割的方法将图像分成n个超像素块R={Ri|i=1,2,…,n}，图1所示为经SLIC预分割后的结果图像，其主要区域较好地保持了原始图像结构信息，而且运行速度、生成超像素的紧凑度、轮廓保持方面都比较理想。为了提高蚁群算法的运算速度，蚂蚁被放入每个超像素块内，该文根据预分割的超像素块建立区域邻接图G=(V,E)，区域块Ri构成V，其相邻区域构成E，每个顶点vi的颜色值Ii是区域内像素的颜色均值。该文所有的计算均是针对区域邻接图。

图1 SLIC超像素预分割结果

1.2 显著性计算

目前的显著性目标检测方法是通过对输入图像多特征通道分析，来得到图像中每个像素点感兴趣程度的显著性分布图，其采用的低层特征主要集中在图像的颜色和对比度。

当前景和背景颜色有重合的时候，仅仅依赖于它们的颜色和梯度等相关特征是基本不起作用的，且图像分割是由边界区域决定。为了弥补这一影响，该文将引入显著性，显著值越高的区域，用户越能被吸引，则这一区域属于前景的可能性较大；显著值越低的区域，用户越不能被吸引，属于背景的可能性较大[12-17]。图2显示了图像上显著性检测及感兴趣目标区域提取结果[14]。显著图通常也被直接用来进行图像分割，但是其中大多数都是基于阈值分割的方法[15-17]，往往缺少通用性。该文在蚁群算法的框架下，将图像内容的显著性用来辅助颜色进行分割，较好地解决了这一问题。

图2 显著图

1.3 类内蚂蚁的运动模型

(1)

(2)

(3)

其中，h和c分别表示梯度和颜色特征，s表示区域块Ri的显著均值：

h(i,j)=max|Ii,j-Im,n|,m=i-1,i,

i+1,n=j-1,j,j+1

(4)

(5)

其中，‖Ii-Ij‖2是第i个超像素块与第j个超像素块的像素平均值的欧氏距离，σ为邻接像素的颜色距离均值。

1.4 类间蚂蚁的竞争模型

由于单类蚂蚁分割易造成欠分割或者过分割，根据种群间存在的竞争关系，提出类间蚂蚁的竞争模型，设想基于类间蚂蚁竞争模型的显著图像分割。

算法设定两类蚂蚁，每一类蚂蚁寻找各自目标，一类蚂蚁以前景(显著图像)为目标进行寻找，另一类蚂蚁以图像背景为目标进行寻找。两类蚂蚁分别以各自目标寻找最优解，并留下可供交换信息的信息素，当信息素分布趋于稳定时，两类蚂蚁进行种群竞争。两类蚂蚁信息素的更新如下所示：

(6)

(7)

最后将得到的信息素map图通过形态学后处理得到最终的map图，图3表示两类蚂蚁信息素在待分割图像上最终的分布，其中黑色部分和灰色部分分别表示第一类蚂蚁所处的前景区域和第二类蚂蚁所处的背景区域。

图3 两类蚂蚁竞争后最终的分布

1.5 基于类间蚂蚁竞争模型的显著图像分割算法流程

Step1：预处理，采用SLIC算法对输入图像进行超像素预分割，得到区域块和其在HSV空间的颜色值，构建区域邻接图。

Step2：采用类间蚂蚁的竞争模型对图像进行分割。

Step2.1：初始化两类蚂蚁以及信息素矩阵，计算显著图和显著值，并结合SLIC预分割结果对每个区域 计算显著均值和初始化启发式矩阵与信息素矩阵；

Step2.2：两类蚂蚁各自根据式(1)的状态转移概率进行路径选择，完成觅食；

Step2.3：每一次进行路径选择后，对路径信息素进行更新，如式(6)；

Step2.4：判断是否寻到最优，否则跳转到(3)；

Step2.5：根据式(7)完成两类蚂蚁竞争。

2 实验结果与分析

为了验证该算法的正确性和有效性，在Windows 7操作系统下，采用Matlab R2010进行仿真实验，实验数据集是公开数据集：Berkeley Segmentation Data Set and Benchmarks 500 (BSDS50)(https://www2.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/resources.html#algorithms)，并从分割效果、分割准确率、交互时间3个方面分析算法的性能。

2.1 分割效果

实验中，对类间蚂蚁竞争模型算法的参数设置为：α=1,β=4,ρ=0.2，经类间蚂蚁竞争模型算法计算得到的分割结果对比不同算法，如表1所示。

表1 分割结果对比

由表1可得，当前景和背景颜色差别较小时，GrowCut算法分割结果性能降低，并且GrowCut需要人工预先标定图片的前景和背景，且分割效果很大程度上依赖于人工预先标定。文中所提出的算法不需要人工干预，直接由算法分割出显著图像，由于算法采用SLIC超像素分割使得图像原有的结构得到保留，类间蚂蚁竞争模型使得两类蚂蚁各自寻找自己的目标，一类寻找前景，一类寻找背景，相互合作，提高了分割效果准确性。

2.2 分割准确率

为了定量计算文中算法的分割正确率，对图片库中所有500幅图片的分割效果进行比较，将实验数据库中的标注结果作为评价标准(ground truth)，计算文中算法和传统分割算法的敏感性(TPF)和特异性(FPF)。TPF是指正确识别的目标显著图像素数与参考标准中的目标显著图像素数的比率，其代表了算法针对目标区域的有效性，其值越高则表示算法越有效；FPF是指正确识别的背景像素数与参考标准中的背景像素数的比率，代表了算法可能出现的对非目标区域的正确分割能力，其值越高则表示算法能力越强。测试结果如表2所示。

表2 不同分割算法性能对比

由表2可以看出，对于图片库中所有500幅图片进行测试，文中算法的分割效果、平均敏感性和特异性优于其他2种算法。

2.3 交互时间

文中算法的运行时间由SLIC超像素预分割的时间、显著图的计算时间和类间蚂蚁竞争模型算法时间构成，由于SLIC预处理算法与显著图只需要计算一次，分割过程可能需要多次交互，多次运行类间蚂蚁竞争模型。算法的运行时间比较如表3所示，文中算法由于在区域邻接图上进行计算，交互时间有了大幅的缩减，提高了算法效率。

表3 交互时间对比 s

3 结束语

针对单类蚁群算法分割易造成欠分割或过分割这一现象，提出基于类间蚂蚁竞争模型的显著图像分割算法。首先采用SLIC超像素分割算法对图像进行预分割，将图像分割成多个区域，不仅可以提高分割精度得到理想的分割结果，同时可以缩短运算时间。然后根据种群竞争思想，设定两类蚂蚁，根据每类蚂蚁设定食物目标(前景/背景)，从而相互竞争，找到各自的食物，最终根据两类蚂蚁分泌的信息素竞争得到最终的结果。结果表明，该算法运行快速，分割结果更加精确。同时算法可进一步由两类蚂蚁延伸至多类蚂蚁，由逻辑映射到线性映射转变，以实现更加复杂的分割。