收稿日期：2014-03-24；修回日期：2014-05-16基金项目：国家自然科学基金资助项目（61073058，
61201347）；重庆市科委自然科学基金计划资助项目（cstc2012jjA40011）
作者简介：葛亮（1980-），男，重庆人，副教授，硕导，博士，主要研究方向为计算机视觉、数据挖据、Web 应用技术（geliang@cqu．edu．cn ）；杨竣铎（1989-），男，山东临沂人，硕士，主要研究方向为数字图像处理．胎盘提取液
*
葛
亮，杨竣铎
（重庆大学计算机学院软件理论与技术重庆市重点实验室，重庆400044）
摘
要：为了消除基于谱聚类的归一化切分图像分割中聚类参数对分割结果的约束，提出了一种基于蚁优 化
的多层图划分算法来进行归一化切分，进而对彩自然景观图像进行分割。该算法将代表图像的相似度图作为蚁的栖息环境，在归一化割准则的指导下，通过蚂蚁的觅食行为将相似的顶点逐渐聚集在一起，从而以多层的方式完成图划分。为了降低图像分割的计算量， 利用超像素对图像进行预处理。实验对比表明，该算法消除了归一化切分分割结果对聚类参数的依赖，并提高了归一化切分分割的准确性和速度。关键词：彩图像分割；归一化切分；蚁优化；多层图划分；超像素中图分类号：TP391.41
文献标志码：A
文章编号：1001-3695（2015）04-1265-04
doi ：10．3969/j．issn．1001-3695．2015．04．073
Color image segmentation based on multi-level graph
partitioning using ant colony optimization
GE Liang ，YANG Jun-duo
（Chongqing Key Laboratory of Software Theory ＆Technology ，College of Computer Science ，Chongqing University ，Chongqing 400044，China ）
Abstract ：In order to eliminate the restraint of clustering number to segmentation result of spectral clustering based normalized
cut image segmentation ，
this paper proposed an ant colony optimization based multi-level graph partition algorithm which was used to segment color natural landscape image．The proposed algorithm regarded similarity graph corresponding to image as ant colony ’s habitat ，and then grouped similar vertices into partitions gradually under the guidance of normalized cut criterion using ant ’s foraging behavior ，which completed graph partition problem by a multi-level way．To reduce calculated quantity of image segmentation ，it utilized an effective super-pixel algorithm to preprocess original image．Contrast experiment shows that the proposed algorithm eliminates the restraint ，while improves accuracy and speed of image segmentation based on normalized cut criterion．Key words ：color image segmentation ；normalized cut ；ant colony optimization ；multilevel graph partitioning ；super-pixel
0引言
图像分割是计算机视觉和图像处理领域中一个非常基本
而关键的问题。若想对图像信号进行识别和理解等高层次的处理，
图像分割是必不可少的预备性操作。图像分割的学科交叉性很强，近年来聚类分析、水平集、人工神经网络、小波变换、图论等其他领域的理论或工具都已被用来尝试解决图像分割问题。由于图论中的图与图像具有内在的对应性，所以基于图论的图像分割备受关注，经过近二十年的发展，
形成了智能剪、图切分、归一化切分、随机游走等具有代表性的图论分割方法
［1］
。其中，归一化切分建立了一种
均衡的图割准则，并利用谱聚类［2］
来近似求解，其分割结果体
现了图像全局信息，开创了图像分割问题研究的一个新方向。
归一化切分之所以要用到谱聚类，主要是由于其建立的图割准则是一个组合优化问题，对其求解至少是NP 难问题。然而，基于谱聚类的归一化切分图像分割不仅计算量大、分割时间长而且容易产生错误的歪斜分割
［3］
，这主要是因为谱聚类
需要建立规模庞大的像素相似度矩阵。矩阵越稠密，谱聚类时
分解特征值和特征向量的时间就越长；同时由于谱聚类的结果
受聚类数的影响，容易产生不正确的分割结果。
文献［4］使用社会启发式算法来求解归一化切分的图割准则，取得了较好的分割结果，但是该方法仍以像素为单位构造相似度矩阵。在文献［
5］中使用模糊C-均值聚类将原图像预先分成n 个区域，以ＲGB 三个信道上的灰度平均值作为区域的像素值，并以区域为单位构造相似度矩阵，从而大大地缩小了矩阵规模，然后通过鱼算法对归一化切分的图割准则进行迭代求解，实现了对彩图像的分割。但是文献［5］的分割结果受模糊C-均值
聚类结果的影响较大。文献［6］使用Mean Shift 算法对图像进行预分割，文献［7］则使用分水岭算法进行预分割，然后以区域为单位构造相似度矩阵，降低了矩阵规模，但是不规则的区域对相似度的计算又提出了挑战。
为了使归一化切分的分割结果免受聚类数的影响，本文提出使用蚁优化算法来代替谱聚类，对归一化切分所建立的图割准则进行优化求解，
将割值的减小看做食物源，利用蚁的觅食行为将割值最小化。为了降低图像分割的计算量从而加快分割的速度，本文利用超像素对图像进行预处理，并以超像素为单位将图像映射为图。
第32卷第4期2015年4月计算机应用研究
Application Ｒesearch of Computers Vol．32No．4Apr．2015
1
相关理论和技术
1.1
基于谱聚类的归一化切分图像分割
对于图像I ，令带权无向图G =（V ，
E ，W ）为图像I 所对应的图结构。其中：V 为图G 中顶点的集合，
代表图像I 中的所有像素点；E 为图G 中边的集合，代表图像I 中像素点与其邻
域内像素点有关系；W 为图G 中边的权值矩阵，衡量对应的像素点之间的相似度，
W 也称相似度矩阵。假设图G 被分割为两个互补的子图A 和B ，那么归一化切分所定义的图割准则称为归一化割，为NCut （A ，
B ）。NCut （A ，B ）=cut （A ，B ）ˑ
1vol （A ）+1vol （B []
）其中：cut （A ，B ）=∑u ∈V （A ），v ∈V （B ）
W （u ，v ），表示子图A 和B 之间的
割；vol （A ）=
∑u ∈V （A ），v ∈V
W （u ，v ），vol （B ）与vol （A ）类似，代表子图蛋白酶抑制剂
与原图的关联度。归一化割准则利用子图的关联度对图的割
进行归一化，避免了图的最小割准则容易产生孤立顶点的缺陷。Shi 等人
在网络暴力中捍卫自己
［8］
指出直接求解NCut 的最小值是NP 难问题，所以提出用谱聚类来近似求解：
设顶点相似度矩阵为W ，对角矩阵D 对角线上元素值分别为矩阵W 每一行元素值之和，谱聚类方法将NCut 最小化问题转换为求解矩阵W 的归一化的拉普拉斯矩阵L =D
－1
2
（D －
W ）D －1
2的特征值λ和特征向量x 的问题：Lx =λx 。将上式中第二小特征值对应的特征向量x 进行离散化，
如x i =1表示第i 个顶点在子图A 中，x i =0表示顶点i 在子图B 中。根据Fieder 矩阵特征理论［9］，离散化的x 即是让NCut 值最小的近似解。当需要将图像分割成多个区域时，可以通过将多个小特征值所对应的特征向量进行离散化得到。1.2
超像素
超像素是指在颜、纹理及亮度上一致性高的像素点组成的连通块，它在总体上形状规则并在很好地保持图像边缘基础上，
大大降低了图像的冗余。SLIC （simple linear iterative clustering ）［10］是Achanta 等人于2011年提出的专门用来快速生成超像素的算法。利用SLIC 生成的超像素不但规则紧凑而且超像素的边缘和原始图像的边缘拟合性高，
如图1所示。图1（c ）中每个小块即是超像素。SLIC 的速度非常快，其时间复杂度为O （n ），对于一幅321ˑ481的CIE Lab 彩图像生成1024个超像素点仅需0．5s 左右。最近Ｒen 等人［11］又利用GPU 将SLIC 的计算速度提高了10 20倍，从而促进了超像素在实时系统上的应用
。
图1SLIC 超像素效果
(a)原图像(b)超像素图像(c)超像素边界
1.3多层图划分
在对有很多顶点的图进行图分割时，多层图划分思想能够
大大加快划分速度和改善划分效果。多层图划分分为收缩、划分、膨胀三个步骤，如图2所示。首先对顶点进行逐渐收缩使
图的顶点减少，收缩到一定程度后进行子图划分，然后在顶点逐渐膨胀映射的过程中对划分进行调整。
收缩
膨胀
划分
图2多层图划分步骤
在对图进行顶点收缩时，好的收缩策略有利于后续的划分
及调整。Katerina 等人［12］
介绍了几种常用的收缩策略来折叠匹配顶点之间的边，如随机匹配、重边匹配、重集匹配等。这些
匹配方式速度快，但是缺乏灵活性并且可能导致两个原本相似性不强的点收缩到一起。1.4
蚁优化算法
蚁优化算法（ant colony optimization ，
ACO ）是一种模拟蚂蚁觅食行为的模拟优化算法，
由意大利学者Dorigo 等人［13］
提出。在初始启发信息的指导下，蚂蚁在觅食过程中，能够在
它所经过的路径上留下一种称为信息素（pheromone ）的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此灵活地指导自己的运动方向。因此由大量蚂蚁组成的蚁集体行为便表现出一种信息正负反馈现象：某一路径上走过的蚂蚁越多，积累的信息素浓度越高，则后来者选择该路径的概率就越大；如果某一路径上走的蚂蚁越少，则信息素会挥发以
至于浓度减小，
则后来者选择该路径的概率减小。蚁优化算法采用了分布式正负反馈并行计算机制，易于
与其他方法结合，而且具有较强的鲁棒性。蚁优化算法的通用性强，能够解决很多可以转换为连通图结构的问题。
2本文算法
为降低图像分割的计算量，本文算法首先利用SLIC 算法将
图像预处理成超像素图像，并以超像素为单位将图像映射为相似度图。然后，将归一化割准则与蚁优化算法相结合，在蚂蚁搜索食物的过程中，以多层图划分的方式将图划分为若干个子图，每一个子图代表最终的图像分割区域，从而完成图像分割。2.1
图像预处理
在CIELab 颜空间，提取颜、亮度、纹理特征作为超像素区域的特征描述。本文将一个超像素s 内所有像素点的a 和b 分量的平均值作为该超像素的颜特征，记为CF s ；将L 分量的直方图统计向量作为亮度特征，记为BF s 。在提取纹理特征时，先使用不同方向不同尺度Gabor 滤波器（图3）对L 分量进行卷积，将卷积值最大的那个方向作为一个像素点的纹理方向，然后将超像素内像素点的纹理方向直方图统计向量作为纹理特征，记为TF s
测绘通报。
图3
三个尺度六个方向的Gabor 滤波器
于是可得到超像素点的描述特征，记为F s =〈CF s ，
BF s ，TF s 〉。在计算颜特征的距离时使用欧氏距离，在计算亮度和纹理特征的距离时使用χ2
距离：
χ2
（h 1，h 2）=12∑
河北科技大学学报Ｒr =0（h 1（r ）－h 2（r ））
2
h 1（r ）+h 2（r ）
·6621·计算机应用研究第32卷
其中：h1、h2表示直方图统计向量；Ｒ表示直方图上界。最终相邻超像素点之间的特征相似度距离为这三个特征分量的加权和，即图的边权值。如图4所示，以超像素为单位构造的图的顶点个数大大减少，同时超像素的边缘能够忠于原图像的边缘，线段越红代表相似度越高
。
(a)超像素边缘(b)以超像素构造的图(c)(b)中黄框部分
图4以超像素为单位构造图
2.2蚁优化多层图划分
蚁优化多层图划分本算法的思想是将图的每一个顶点看做一个连通分量，通过蚁优化算法中蚂蚁迁移演化进行弹性的顶点匹配，随着蚂蚁的爬行相似度高的顶点逐层形成顶点个数多的连通分量从而完成图划分。以2．1节所构建的加权无向图G=（V，E）为蚁的运动环境，图中顶点u、v之间的边e（u，v）的权值w（u，v）为蚁运动的启发式信息。定义每条边被蚂蚁走过的次数（edge visiting degree），记为EVD（e），作为蚂蚁运动后释放的信息素，初始化EVD（e）=0 e∈E。每当一条边被蚂蚁走过一次，这条边的EVD就增加1，信息素挥发则相当于EVD减少1。基于这里定义的启发式信息和信息素信息，本文将蚁优化算法加以改造并用来进行图划分。
蚂蚁在运动过程中，有两个模式：移动（moving）和暂停（staying），并且蚂蚁可以记得一定长度刚走过的路径。假设蚂蚁a在t时刻位于顶点u，那么它会根据顶点u处的局部相似度环境来决定运动状态。局部相似度定义为
ls（u）=max［0，1
|NH（u）|
∑
v∈NH（u）
w（μ，ν）
δ
］
其中：NH（u）表示在u的相邻顶点除去在该蚂蚁记忆中的顶点后的集合，δ为权值归一化除数。ls值越大，则蚂蚁当前所处的环境相似度越高；反之，越低。如果环境相似度高，则鼓励蚂蚁向前移动，否则蚂蚁可能要暂停一下。为了减少对阈值的设定，这里定义蚂蚁的选择移动状态的概率为
p m=［ls（u）
k+ls（u）
］2
其中：k为一个正数，调节局部相似度对蚂蚁运动状态选择的影响。那么，蚂蚁选择暂停状态的概率为
P s=1－P m。
如果蚂蚁选择暂停模式，说明当前顶点可能是图划分的割集所依附的顶点，这时候可以选择清空该蚂蚁的记忆，以便下一次使其有可能回到熟悉的环境中去。如果蚂蚁选择了移动模式，则需要选择下一步要走的边，亦即走向哪一个顶点。这时要综合考虑启发式信息和环境信息素对选择下一步要走哪条边的影响。一方面，倾向于选择权值大的边；另一方面，倾向于选择EVD值大的边。对边e（u，v）的选择概率可定义为
p e（u，v）=
w（u，v）ζEVD（e（u，v））η
∑λ（w（u，λ）ζEVD（e（u，λ））η）
v，λ∈NH（u）
其中：ζ和η分别表示启发式信息和信息素的影响因子。概率最大的那条边将被蚂蚁选择为下一条要走的边。
根据蚂蚁记忆中边的边权相似度来对信息素EVD进行局部更新。假如蚂蚁a的记忆为边集和M，点对集
合MV=｛（x，y）：边e依附于x和y，e∈M｝。如果一只蚂蚁的记忆中边的权值的均值较小或者方差较大，那么这只蚂蚁很可能走过了最小割集中的一条边，这时候需要对这条记忆路径上边的EVD均减去1作为对该条路径的惩罚，EVD最小为0。这相当于是一种局部负反馈。定义惩罚概率为
P n=1－［
mean（w｛MV｝）
mean（w｛MV｝）+var（w｛MV｝）
］2
所有的蚂蚁运动一次（移动或暂停），相当于完成一次迭代。根据边的EVD值是否为0来判断该边是否为当前割集中的一条边。当本次迭代产生的图划分和前一次迭代产生的图划分的NCut值相比增大较多时，所有边的EVD值减去1，但最小为0。这相当于是一种全局正负反馈。当NCut值基本不再变化或其变化小于一定的阈值时，得到全局最优图划分。
2.3分割算法流程（图5）
原图像
SLIC超像素预处理
超像素特征提取
以超像素为单位将原图像映射为加权无向图
利用蚁优化进行多层图划分
否
图划分的NCut值不再变化?
是
将得到的最优图划分映射回原图像
最终分割结果
图5本文分割方法的流程
3实验结果与分析
本文使用BSDS［14］图像分割数据集来对所提分割方法的
有效性进行评估。BSDS中的彩图像尺寸均为321ˑ481或者481ˑ321，而且每幅图像都有对应的若干个人工的标准分割。实验平台为Linux Ubuntu12．10，MATLABＲ2010b，Intel Core i52．6GHz CPU，2GBＲAM。
3.1分割结果可视化展示
图6展示了使用本文算法对一幅图像进行分割的中间结果及最终分割结果。图6（a）表示原图；图6（b）（c）展示了蚁优化多层图划分过程中的两个图划分中间结果所对应的图像分割；图6（d）表示最终的图划分所对应的图像分割结果。对比图6（b） （d）可以发现，较小的分割逐渐被去掉了，印证了本文算法在NCut分割准则下进行图像分割的可行性。
图6本文算法分割的中间结果和最终分割结果展示
(a)原图像(b)分割过程(c)分割过程(d)最终分割结果
图7可视化展示了两幅彩图像的人工标准分割、本文算法的分割结果以及基于谱聚类的归一化切分的分割结果。分割结果中区域显示的是颜的平均值，区域之间以白的边缘相隔。通过观察可以看到，本文算法的分割结果与人工标准分割结果对比，人工标准分割的分割结果的细节更多一些，而本文算法的分割则抽象一些，这是由于人在分割的时候将自身对事物的整体性认识反映出来。基于谱聚类的归一化切分的分割结果虽然没有形成比较小的区域，但是由于受到聚类数的影响，所以产生了过分割现象。
·
7621
·
第4期葛亮，等：基于蚁优化多层图划分的彩图像分割方法
图7图像分割结果可视化对比
(a)测试图像
(b)人工标准分割结果
(c)本文算法的分割结果(d)基于谱聚类的归一化切分的分割结果
3.2分割结果量化评价
为了对分割结果进行科学客观的评价，本文采用常见的
F-measure （F ）［15］来衡量分割结果边缘的正确性，并采用区域
重叠率cover ［16］
、
概率边缘指数（probabilistic rand index ，PＲI ）［17］、信息变化指数（variation of information ，
VoI ）［18］来衡量算法分割结果和人工分割结果之间的区域对应程度。
F-measure 是边缘查准率（precision ，P ）和查全率（recall ，Ｒ）的综合，F-measure 在［0，1］
内取值，值越大，说明分割结果的边缘正确性越高。区域重叠率衡量了两个分割之间的区域对应性。设S 为算法分割出的区域集合，
GS 为人工标准分割的区域集合，那么算法分割结果S 与人工标准分割GS 的区域重叠率记为
cover （S ，GS ）=
1
N ∑Ｒ∈S
|Ｒ|ˑmax O （Ｒ，
GＲ），GＲ∈GS 其中：N 为图像像素点的个数；|Ｒ|为区域Ｒ中像素点的个数；O （Ｒ，GＲ）为两个区域之间的重叠率。
O （Ｒ，GＲ）=
|Ｒ∩GＲ|
|Ｒ∪GＲ|
区域重叠率在［0，1］内取值，值越高说明算法分割结果与
人工标准分割越相近。对于算法分割结果S 和一组人工标准分割｛GS k ｝，
概率边缘指数PＲI 的计算式为PＲI （S ，｛GS k ｝）=
1
T ∑i ＜j ［c ij p ij
+（1－c ij ）（1－p ij ）］其中：c ij 表示像素点对（像素i ∈S 和像素j ∈｛GS k ｝）具有相同的区域标签的事件；p ij 表示事件c ij 发生的概率；T 表示所有像素点对的个数。边缘概率指数的值越大，
说明算法分割与人工标准分割越接近。
信息变化指数VoI 衡量了两个分割之间的平均条件熵，其计算式为
VoI （S ，GS ）=H （S ）+H （GS ）－2I （S ，GS ）
其中：S 和GS 分别表示算法分割结果和人工标准分割结果；H
表示分割的熵，
I 表示两个分割之间的互信息。如果两个分割结果是一致的，
那么VoI 值将是0。VoI 值的上界取决于分割结果中区域的数目。
本文随机选取BSDS 图像数据集中的200幅彩图像，分别利用本文算法和基于谱聚类的归一化切分进行分割，并计算了根据上述评价指标的平均值。表1中列出了本文算法和基
于谱聚类的归一化切分分割结果的F-measure 、区域重叠率、概率边缘指数、
信息变化指数这四种指标的值，其中较好的指标值均为本文算法。
表1
本文算法和基于谱聚类的归一化切分分割结果的评价指标对比
算法指标F cover PＲI VoI time /s 本文算法0．870．650．861．326．2谱聚类归一化切分
0．64
0．45
0．78
2．23
54．3
由表1可以看出，相比于基于谱聚类的归一化切分，本文所提分割方法的边缘正确性得到了很大的提高。在三个区域对应
性程度评价指标上，本文所提分割方法也体现出了优越性。
表1中还给出了分割这200幅图像所用时间的平均值，本
文所提分割方法分割一幅彩图像的平均时间为6．2s ，而基于
谱聚类的归一切分所需时间约为本文算法的10倍，
达到54．3s ，这说明本文所提分割方法速度比基于谱聚类的归一化切分方法
更快。综上所述，本文所提分割方法的有效性得到了验证。
4结束语
本文基于图论的图像分割方法的思想，提出利用蚁优化
算法来优化求解归一化割准则，并将其用来分割彩图像。为了加快图像分割的速度，本文利用超像素生成算法对图像进行
了预处理。本文所提分割方法还体现出了多层分割的特点，这种多层次图像分割丰富了图像分割的过程。通过实验结果的
可视化对比和评价指标分析表明，
利用蚁优化算法求解归一化割准则比利用谱聚类求解归一化割准则的分割结果更准确。参考文献：
［1］侯叶．基于图论的图像分割技术研究［D ］．西安：西安电子科技大
学，
2011．［2］ULＲIKE L V．A tutorial on spectral clustering ［J ］．Statistics and
Computing ，2007，17（4）：395-416．［3］席秋波．基于NCut 的图像分割算法研究［D ］．成都：电子科技大
学，
2011．［4］翟艳鹏，郭敏，马苗，等．遗传算法优化归一化划分准则的图像分
割［
J ］．计算机工程与应用，2010，46（33）：148-157．［5］周逊，郭敏，马苗，等．基于鱼算法优化normalized cut 的图像分
潘恩思
割方法［
J ］．计算机应用研究，2013，30（2）：616-618．［6］TAO Wen-bin ，JIN Hai ，ZHANG Yi-min．Color image segmentation
based on Mean Shift and normalized cuts ［J ］．IEEE Trans on Sys-tems ，2007，37（5）：1382-1389．［7］冯林，孙焘，吴振宇，等．基于分水岭变换和图论的图像分割方法
［J ］．仪器仪表学报，2008，29（3）：649-653．［8］SHI Jian-bo ，MALIK J D．Normalized cuts and image segmentation
［J ］．IEEE Trans on Pattern Analysis and Machine Intelligence ，2000，22（8）：888-905．［9］CHUNG F．Spectral graph theory ［M ］．［S．l．］：American Mathemati-cal Society ，1997．［10］ACHANTA Ｒ，SHAJI A ，SMITH K ，et al．SLIC superpixels compared
to state-of-the-art superpixel methods ［J ］．Journal of Latex Class
Files ，2011，6（1）：92-99．［11］ＲEN C Y ，ＲEID I．gSLIC ：a real-time implementation of SLIC super-pixel segmentation ［Ｒ］．Oxford ：Department of Engineering ，Universi-ty of Oxford ，2011．［12］KATEＲINA T ，PETEＲK ，JUＲIJ S．A distributed multilevel ant colo-nies approach for graph partitioning ［J ］．International Journal of
Bio-Inspired Computation ，
2011，3（5）：286-296．［13］DOＲIGO M ，BIＲATTAＲI M ，STUZLE T．Ant colony optimization ［J ］．
IEEE Computational Intelligence Magazine ，2006，1（4）：28-39．［14］ESTＲADA F J ，JEPSON A D．Benchmarking image segmentation algo-rithms ［J ］．International Journal of Computer Vision ，2009，85
（2）：167-181．
［15］MAＲTIN D Ｒ，FOWLKES C C ，MALIK J．Learning to detect natural
image boundaries using local brightness ，color ，and texture cues ［J ］．IEEE Trans on Pattern Analysis and Machine Intelligence ，2004，26（5）：530-549．［16］AＲBELAEZ P ，MAIＲE M ，FOWLKES C．Contour detection and hie-rarchical image segmentation ［J ］．IEEE Trans on Pattern Analysis ＆
Machine Intelligence ，2011，33（5）：898-916．［17］UNNIKＲISHNAN Ｒ，PANTOFAＲU C ，HEBEＲT M．A measure for
objective evaluation of image segmentation algorithm ［C ］//Proc of IEEE Conference on CVPＲ．2005：34-41．［18］MEILA M．Comparing clustering ：an axiomatic view ［C ］//Proc of In-ternational Conference on Machine Learning．2005：577-584．
·
8621·计算机应用研究第32卷
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议