一种求解图像分割问题的限速-离散蜂群优化算法

周 逊，郭 敏，马 苗

(陕西师范大学计算机科学学院，西安 710062)

1 概述

基于图论的图像分割是当前图像分割领域一个热点问题。该方法将整幅图像看作一幅无向带权图，图像中每一个像素对应图中一个节点，边上的权值代表像素的近似关系，利用最小剪切准则得到图像最佳分割。文献［1 -2］综合考虑分割后子图的内部相似度和子图之间的相似度，提出的Normalized Cut 准则是一种规范化的准则，有效避免了出现歪斜分割区域。由设计复杂性可知，归一化图像分割权值矩阵构造的计算量非常大。文献［3］通过加入先验知识得到优质分割结果;文献［4］利用分水岭算法对图像进行预处理，有效地降低了权值计算维度。由于最小化Ncut 值是NP-hard 问题，文献［2］提出谱聚类算法，将问题转换为求解特大矩阵的第二小特征值，得到了Ncut 值的近似解。近年来，群智能优化算法在求解组合优化问题时显示出其独特的优势，文献［5］利用粒子群算法对非线性约束问题进行优化，减少了多重制冷系统中的能源消耗;文献［6］采用鱼群优化算法对灰色理论中的GM(1，1)模型参数进行优化;文献［7］利用细菌觅食算法求解任何尺寸的矩形微带天线的谐振频率问题。

蜂群优化算法［8］具有控制参数少、易于实现、计算简洁等优点，文献［9］将蜂群算法用于MESFET 的小信号模型参数的提取，在时间和质量上效果较佳;文献［10］将蜂群算法优化与混沌搜索相结合在PID控制调整中得到应用。但蜂群算法求解归一化图像分割问题时存在早熟收敛、长期停滞等缺点，一直制约其在该领域发展。本文提出一种限速-离散蜂群优化算法(Speed-limiting Discrete Artificial Bee Colony Algorithm，SLDABC)，用于解决归一化的彩色图像分割问题，该算法将标准蜂群优化算法离散化，在离散域上求解问题，重新定义了蜂群位置的变换方式;增加速度的定义，并引入一个对速度限制的过程;同时，自适应地调整个体蜂速度更新因子，增加了种群的多样性。

2 归一化彩色图像分割方法

2.1 归一化图像分割

无向带权图每个边有权值ω(i，j)，ω(i，j)表示像素i 和像素j 之间的相似度，通过删去某些边将图分成2 个点集，使得A∪B=V，A∩B=Ø，被删去的边的权值总和称为割cut。

由于其容易划分出孤立点，Shi 和Malik 提出一种规范化的分割方法，归一化分割描述如下:

其中，asso(A，V)表示A 中节点与图G 中所有节点之间的联系程度;asso(B，V)表示B 中节点与图G 中所有节点之间的联系程度。可以看出Ncut 值越小，划分的结果越好。

2.2 图像预处理

彩色图像颜色信息量非常大，通常认为每个像素是由R，G，B 3 个颜色分量组成。若以像素点构造权值矩阵必然造成非常大的计算量，为了减少计算量，本文针对彩色图像的3 个颜色分量通道分别做模糊C 均值处理，每个颜色分量通道分别聚类为c 个最大相似区域IR，IG，IB，取IR，IG，IB的交集将图像分为n 块最大相似区域，再以n 块最大相似区域构造权值矩阵。

3 基于SLDABC 的归一化彩色图像分割方法

3.1 标准蜂群算法原理

标准蜂群算法(Artificial Bee Colony Algorithm，ABC)［11］利用蜜蜂的采蜜行为进行空间搜索，每个食物源的位置代表优化问题的一个可行解，食物源的花蜜量作为可行解的适应度值，蜜蜂寻找最优食物源的过程即是寻找最优解的过程。ABC 算法随机产生N 个食物源，每个食物源对应一个引领蜂。当所有的引领蜂完成搜索后，跟随蜂则根据一定概率选择一个食物源进行采蜜。劣质食物源对应的引领蜂变为侦察蜂，随机寻找新的食物源。引领蜂产生新的邻域位置和侦察蜂搜索新的食物源的公式分别为:

其中，xi，j(i=1，2，…，N，j=1，2，…，D)是一个食物源;xk，j是xi，j附近的一个食物源;Φ 和φ 是［-1，1］之间的随机数。

ABC 算法求解连续域约束数值优化问题能够得到很好的结果，但是它是一种新型的随机优化算法，其研究刚刚起步，求某些特定问题时限制了蜂群的多样性，算法容易早熟，且其求解离散域的约束优化问题需要重新定义算法的参数与运算公式，使得求解问题的质量下降。针对上述问题，本文提出了一种限速-离散蜂群算法(Speed Limited-Disperse Artificial Bee Colony Algorithm，SLDABC)来解决归一化彩色图像分割问题。

3.2 SLDABC 算法

SLDABC 算法以标准离散蜂群优化算法为基础，给出了速度与惯性权重的定义，引入自适应惯性权重调整模式控制算法的收敛，设定限速模型来控制种群的多样性。

3.2.1 速度和惯性权重的定义

定义1 个体蜂速度的大小决定该个体蜂在空间中运动的趋势，间接决定着个体蜂的下一个位置。Vi=(vi，1，vi，2，…，vi，D)，其中，vi，k(k=1，2，…，D)为第i 个个体蜂在D 维解空间的速度。通过速度的变化控制位置的变化。

定义2 惯性权重是控制个体蜂的以前速度及相互之间的位置差异对当前速度的影响比重。

惯性权重的调控影响到算法的收敛速度及算法的稳定性。

3.2.2 离散化蜂群算法速度的表达

将标准蜂群算法离散化，Xi(xi，1，xi，2，…，xi，D)表示第i 个个体蜂在D 维解空间的位置，xi，k(k=1，2，…，D)的取值为0 或1;Vi=(vi，1，vi，2，…，vi，D)表示第i 个个体蜂在D 维解空间的速度和分别表示第i 个个体蜂在第m 次迭代中的位置及速度;w1，w2表示惯性权重。

本文提出的离散蜂群优化算法的新的速度更新公式为:

其中，r 为［0，2］间的随机数。

3.2.3 自适应惯性权重调整机制

标准蜂群算法个体蜂的搜素空间随着迭代进化而收缩，导致只有当优化问题的全局最优值在初始搜索空间时，算法才有可能找到解，使得最优解能否找到非常依赖初始化的群体。本文算法设计了一个动态权重调整机制，由个体蜂自身的适应度确定其动态权重，计算方式如下:

其中，fit(Xi)表示第i 个个体蜂在位置Xi处的适应度值;mean(fit(X))，max(fit(X))，min(fit(X))分别表示本次迭代过程中个体蜂平均、最大、最小适应度值。个体蜂的速度是决定其位置的关键因素，初始种群中个体蜂的速度波动较大，适应度值波动也较大，由于惯性权重由本次迭代的适应度值的mean(fit(X))，max(fit(X))和min(fit(X))决定，使得算法在前期的时候偏向于在全局搜索，当逐渐找到全局最优区域时，个体蜂的速度波动较小，使得算法偏向于在局部区域搜索调整解，本文提出这一自适应权重调整机制使得算法的稳定性及收敛速度得到了较大的提高。

3.2.4 限速-离散蜂群算法模型设计

归一化图像分割是二元标号问题，函数需要在二进制空间内使得个体蜂的位置趋向判别为0 或1，当速度vi，k越大时，位置xi，k则更容易被选择为1;反之则容易被选择为0。即由个体蜂速度决定一个范围在［0，1］之间的概率选择参数s:若s 接近1，则个体蜂的位置更加趋近于选择1;反之，则个体蜂的位置更加趋近于选择0。文献［12］提出使用Sigmoid函数求参数s，公式如下:

本文算法设定一个限制速度vSL，当个体蜂的速度超过限制速度，则对其进行特定变换，减缓s趋向于1 和0，使得其能够全方位在解空间中搜索可能的解，有效找到最优局部解空间。具体操作如下:

速度的限制是为了使位置的变化富有多样性，使群体多样化。由公式可以看出，当 vi，k＞vSL时，s减缓趋向于1 的速度;当vi，k＜(-vSL)时，s 则减缓趋向于0 的速度。这样个体蜂的状态更加容易得到改变，防止了个体蜂停滞不前，使其在更大的范围内去搜索解，种群变得多样化。表1 给出了特定限制速度下的s 的取值范围。

表1 限制速度下s 的取值范围

分析实验时间和实验效果，当vSL取2 时，综合分析结果较好。

3.2.5 适应度函数

SLDABC 算法中可将归一化图像分割的分割值Ncut 作为适应度值，适应度函数即为式(2)，显然当适应度值越小时指导图像分割的效果越好。同时为防止蜂群在搜索过程中抛弃最佳蜜源，导致不必要的耗时。本文设定一个公告板来记录蜂群在迭代搜索中达到的最优位置及所在位置的适应度值。

3.3 算法描述

本文设定蜂群数量为n，最大迭代次数为m，具体算法步骤如下:

Step1初始化:随机生成n 个个体蜂。

Step2算法迭代:

(1)利用式(2)计算每个个体蜂的fit(Xi)，if fit(Xi)＞maxfit(X)，将得到的最优适应度值fit(X)和其所在位置状态Xi记录到公告板中。

(2)利用式(10)控制速度变化对位置变化影响的幅度，通过式(5)进行速度更新，式(6)和式(7)进行惯性权重更新，通过一定概率选择个体蜂进行跟随，计算新的fit(Xi)，if fit(Xi)＜max fit(X)，则max fit(X)=fit(Xi)，同时记录到公告板中;iffit(Xi)≥max fit(X)，则max fit(X)=max fit(X)。

(3)对Step2 循环迭代，直至达到最大迭代次数或者达到理论最佳适应度值。

Step3结果输出:结合最优fit(Xi)及个体蜂最优位置指导分割图像。

4 仿真结果与分析

为了验证本文算法的可行性及高效性，分别从收敛性、求解质量、算法耗时3 个方面进行仿真实验，并与鱼群优化算法及粒子群优化算法进行了比较。为了体现本文算法的优越性，采用相同硬件环境:Microsoft Windows 7 Professional，CPU 为Intel Core 2.2 GHz，RAM 大小为2 GB。采用相同的随机数据，设定种群数量n 为100、最大迭代次数m 为100，对2 幅大小均为256×256 的彩色图像进行测试。

实验1 算法收敛性比较

图1、图2 分别是图像sunshade 与图像pilot 运用粒子群优化算法(DPSO)、鱼群优化算法(DAFO)、标准蜂群优化算法(DABC)及SLDABC 算法求解图像分割的迭代收敛比较。

图1 图像sunshade 运用不同算法求解分割的迭代收敛比较

图2 图像pilot 运用不同算法求解分割的迭代收敛比较

由图1、图2 可以看出，DPSO、DAFO 与DABC 算法在局部最优解停留时间过长，搜索全局最优值缓慢，这是因为DPSO 算法、DAFO 算法与DABC 算法随机搜索时变化较少且当搜索到局部最优解时较难跳出所致。而SLDABC 算法采用了自适应的权值调整模式，根据自身及群体的适应度有目的变化，同时由于SLDABC 算法采用了限速模型，使得算法即使搜索到局部最优也很容易摆脱，继续向全局最优靠近。

实验2 算法分割效果比较

图像分割的好坏，肉眼判断是最直接的评价标准。图3、图4 分别是图像sunshade 与图像pilot 的原图及不同算法求解的分割效果。

彩色图像sunshade 颜色信息量比较丰富，DPSO算法对颜色信息判别能力欠缺，将较大的地面区域划分为背景。图像pilot，由于其背景和前景的差别不大，DAFO 算法与DABC 算法对前景和背景某些差别不大的地方造成误判，DAFO 算法将一部分蓝天区域划分成了背景区域，DABC 算法飞机顶部及飞行员影子划分欠佳。SLDABC 算法能够有效识别图像所包含的信息，对前景和背景的区分明确，细节处理到位，准确地分割图像，效果明显优于DPSO、DAFO及DABC 算法。

图3 图像sunshade 运用不同算法的分割效果

图4 图像pilot 运用不同算法的分割效果

实验3 Ncut 值及耗时比较

根据Normalized Cut 求解方式，可以看出Ncut值越小，指导分割的图像越好，Ncut 值是判定图像分割效果优劣的理论依据。表2 是DPSO、DAFO、DABC 及SLDABC 算法求解分割时的Ncut 值及耗时比较，为了方便比较，表2 列出的运行时间都是优化算法迭代求解的耗时。

表2 不同算法求解时的Ncut 值及耗时比较

由表2 数据可知，SLDABC 算法在数据上都要优于DPSO 算法和DAFO 算法。SLDABC 算法通过对个体蜂速度的限制使得其对初始种群的依赖较小，使个体蜂迅速脱离局部解空间，在更大的范围内搜索最优解，增加了达到全局最优解的可能性，同时缩短了算法运行时间。

5 结束语

基于图论的图像分割已经成为图像分割领域的一个热点研究方向，是图像理解、图像分析、模式识别等领域中的关键。本文以标准蜂群算法为基础，提出改进蜂群算法SLDABC，算法主要特点如下:(1)将标准蜂群离散化，定义蜂群速度，得到新的离散位置定义，利用智能优化算法有效解决了NP-hard问题;(2)针对智能优化算法容易局部收敛，将速度进行了限制，并设计了限速函数，求得的解的质量有较大提高;(3)在蜂群位置变化的过程中增加了自适应权重策略，动态改变和确定个体蜂当前的速度，有利于提高算法收敛速度;(4)为防止算法在迭代过程中舍弃最优解，设定一个公告板用来保存算法在迭代过程中寻找到的最优解。实验结果表明，SLDABC 算法在解决归一化彩色图像分割问题上效果好且耗时少。

［1］Shi Jianbo，Malik J.Normalized Cuts and Image Segmentation ［C］//Proc.of IEEE CS Conf.on Computer Vision and Pattern Recognition.［S.1.］:IEEE Press，1997:731-737.

［2］Shi Jianbo，Malik J.Normalized Cuts and Image Segmentation［J］.IEEE Transactions on Pattern Analysis Machine Intelligence，2000，22(8):888-905.

［3］Xu Linli，Li Wenye，Dale S.Fast Normalized Cut with Linear Constraints［C］//Proc.of IEEE Conference on Digital Object Identifier.［S.1.］:IEEE Press，2009:2866-2873.

［4］Liu Haitao，Wang Yinlong，Yao Huifen.A New Normalized-cut Image Segmentation Algorithm Based on Watershed Transform ［J］.Applied Mechanics and Materials，2012，235(1):45-48.

［5］Beghi A，Cecchinato L，Cosi G，et al.A PSO-based Algorithm for Optimal Multiple Chiller Systems Operation［J］.Applied Thermal Engineering，2012，32(1):31-40.

［6］Lin Zhensi，Zhang Qishan，Liu Hong.Parameters Optimization of GM(1，1)Model Based on Artificial Fish Swarm Algorithm［J］.Theory and Application，2012，2(2):166-177.

［7］Gollapudi S，Pattnaik S，Bajpai O，et al.Bacterial Foraging Optimization Technique to Calculate Resonant Frequency of Rectangular Microstrip Antenna［J］.International Journal of RF and Microwave Computer-Aided Engineering，2008，18(4):383-388.

［8］Karaboga D，Basturk B.On the Performance of Artificial Bee Colony Algorithm［J］.Applied Soft Computing，2008，8(1):687-697.

［9］Sabat S L，Udgata S K，Abraharm A.Artificial Bee Colony Algorithm for Small Signal Model Parameter Extraction of MESFET［J］.Engineering Applications of Artificial Intelligence，2010，23(1):689-694.

［10］Yan Gaowei，Li Chuangqin.An Effective Refinement Artificial Bee Colony Optimization Algorithm Based on Chaotic Search and Application for PID Control Tuning［J］.Journal of Computational Information Systems，2011，7(9):3309-3316.

［11］张超群，郑建国，王 翔.蜂群算法研究综述［J］.计算机应用研究，2011，28(9):3201-3214.

［12］Kennedy J，Eberhart R C.A Discrete Binary Version of the Particle Swarm Algorithm［C］//Proc.of IEEE International Conference on Computational Cybemetics and Simulation.Washington D.C.，USA:IEEE Computer Society，1997:4104-4108.