基于图像阈值分割的改进蜂群算法

霍凤财，孙宝翔，任伟建

(东北石油大学电气信息工程学院，黑龙江大庆163318)

0 引 言

图像阈值分割是目标检测中的关键技术，因其高效、易于实现等特点而被广泛应用。现已提出大量的阈值选取方法，这些方法根据一维直方图或二维直方图及其区域划分方式［1］，结合智能算法寻求不同准则下的最佳阈值［2］，在不同应用领域取得了较好的应用效果。人工蜂群算法(ABC:Artificial Bee Colony)就是这类智能算法中比较典型的算法。该算法是由Karaboga［3］于2005年提出的一种基于蜜蜂群智能搜索行为的随机优化算法。虽然人工蜂群算法的研究和应用只处于初级阶段，但该算法已广泛用于解决各类优化问题，如函数优化［4］、TSP(Tranvelling Salesman Problem)仿真［5］、多目标优化［6］、逻辑推理［7，8］及图像处理［9－11］等。同时，其易于早熟收敛、编码不统一、搜索速度慢等智能算法普遍存在的缺点亦体现出来。

量子计算是信息科学和量子力学相结合的新兴交叉学科，自1994年Shor［12］提出第1个求解大数质因子分解的量子算法和1996年Grover［13］提出随机数据库搜索的量子算法后，量子计算以其独特的计算性能引起了广泛瞩目，迅速成为国际上研究的热点。目前，量子智能算法层出不穷，如量子遗传算法、量子粒子群算法和量子蚁群算法等。大多是在智能算法中吸收了量子计算中的叠加态、相干性和纠缠性，使量子算法突破了传统算法的极限，表现出良好的性能。一些学者提出了量子蜂群(QABC:Quantum Artificial Bee Colony)算法［14，15］，虽然优化效果比单一的蜂群算法有很大改善，但与理想的效果还有一定的差距。

笔者以图像阈值分割为目标，提出了一种改进量子蜂群(IABCQ:Improved Artificial Bee Colony Algorithm Based on Quantum)算法。该算法首先借鉴量子的思想将量子比特概率幅的正弦分量引入到蜂群算法编码中，通过调整相位角更新量子比特概率幅，使蜂群算法中引领蜂向当前最优蜜源的方向移动;然后借鉴量子运算中非门操作将个体的正弦和余弦分量互换，使跟随蜂的蜜源进行互补更新;其次应用蜂群算法中更新个数的限制，使局部优解和不动点进行重新随机获取;最后将该算法应用到图像阈值分割中验证该算法的有效性。

1 图像二维直线交叉熵

设f(x，y)(1≤x≤M，1≤y≤N)为一幅大小为M×N的图像，其灰度变化范围为［0，L－1］，L一般取2n。g(x，y)为图像(x，y)的像素点K×K邻域(K一般取大于1的奇数)平滑处理后的平均灰度，其灰度变化范围也为［0，L －1］。则 f(x，y)与 g(x，y)组成的二元组(i，j)在原图形和平滑图像的概率为p是(i，j)出现的频ij数，显然根据文献［1］在图1中作过垂直于主角线的直线，将二维区域分成两块:C0(T)和C1(T)，分别表示目标和背景。因此，目标和背景出现的概率分别为

图1 二维直线型区域划分Fig.1 2－D Straight linear region division

且满足P0(T)+P1(T)=1。

目标和背景对应的均值向量为

利用f(x，y)和g(x，y)确定其广义二维直线交叉熵

最小化该广义二维直线交叉熵等价于最大化

即获取最优阈值T*，使I(T*)获得最大值。

2 人工蜂群算法

人工蜂群算法是借鉴自然界中蜜蜂群体分工采蜜的方式而提出的一种新型优化算法。蜂群的模型中有3个角色:引领蜂、跟随蜂和侦查蜂。引领蜂、跟随蜂用于蜜源的开采，侦查蜂避免蜜源种类过少，用于蜜源的开拓;引领蜂或观察蜂的数量相当于解的数量，而侦查蜂用来观察是否陷入局部最优。在ABC算法中，食物源的位置代表一个优化问题的可能解，食物源的花蜜数量相当于相关解的适应度。在初始阶段，包含N个体(可能解)的蜂群根据

随机分配到D维搜索领域，其中R为随机数，i=1，…，NP，j=1，…，D。通常初始食物源的位置被设置成优化问题的最优解。初始化后，解的数量受到引领蜂、跟随蜂和侦查蜂搜索进程中最大迭代次数的限制。

在每次迭代中，引领蜂根据记忆的位置(视觉)信息，产生一次位置(解)的修改，并计算新蜜源(新解)的花蜜数量(适应度)。ABC算法利用

寻找附近的食物源。其中i=1，…，NP，k是1，…，NP中的任意一个数，且k≠i;φij是［－1，1］范围内的随机数，在ABC算法中，Xi表示食物源的位置，Vi表示食物源新的可能位置。适应度计算如下

图2 ABC算法流程图Fig.2 ABC algorithm flow chart

其中fi是Vi解的目标函数值。如果Vi的适应度优于Xi的适应度，则蜜蜂记忆新的位置，遗弃旧的位置。所有的引领蜂完成搜索过程后，它们用摇摆舞和观察蜂分享食物源的花蜜和位置信息。

跟随蜂计算所有引领蜂收集的花蜜信息并选择花蜜数量多的食物源。食物源的可能性计算如下

正如引领蜂一样，对于适应度值较高的跟随蜂在记忆中利用式(8)对位置产生一个修正。

在ABC算法中，如果一个位置不能通过预定的圈数，则进一步改进，食物源会被遗弃。一旦Xi被遗弃，其位置通过式(7)被一个新的食物源代替。这项工作由侦查蜂完成，侦查蜂记忆到目前为止获得的最佳解并继续与其他蜜蜂交流蜜源信息。通过预定的圈数MMCN循环进行这些步骤，直到满足循环的结束条件。

为更进一步了解ABC算法，图2给出了算法的程序流程图。

3 量子的改进人工蜂群算法

3.1 新的蜜源初始化方式

在量子计算中，最小的信息单元用量子位表示，量子位又称量子比特，一个量子比特的状态可表示为其中 α和 β称为量子比特的概率幅，满足归一化条件令 α=cos(θ)，β=sin(θ)，量子比特也可以用概率幅表示为［cos(θ)，sin(θ)］T，其中 θ是量子比特的相位。在量子的改进人工蜂群(IABCQ:Improved Artificial Bee Colony based on Quantum)算法中，直接采用量子位概率幅的一个分量作为蜜源位置的编码。根据种群初始化时编码的随机性及量子态概率幅应满足的约束条件，蜜源初始化方法如下

其中 θi，j=2πRrand(0，1)，Rrand为［0，1］之间的随机数;i∈{1，2，…，NP}，j∈{1，2，…，D}，NP为蜜源个数;D为量子维数。

在优化具体问题时，需要进行单位空间与优化问题解空间之间的变换。定义解的上限和下限分别为Xmax，j，Xmin，j，将待优化解从单位空间变换到解空间的位置，定义为

3.2 新的引领蜂蜜源位置更新策略

蜂群记录到目前为止的最优值，并在当前蜜源附近展开邻域搜索，产生一个新位置代替前一位置。标准蜂群算法采用式(8)所示的更新策略，该更新策略中只考虑当前位置与任意相邻位置之间的关系，而实际的更新方式需借鉴当前最优解的信息，同时要具有一定的扩展能力。因此，IABCQ算法中将引领蜂蜜源位置更新转换为量子位概率幅的更新，令^θ为当前搜索到的全局最优解中某量子位的相位，θ为当前解中相应量子位的相位，Δ θ的方向可通过式(14)的sgn A获得［16］。θ0为固定的初始小角度，比如0.05π，c为常数。引领蜂蜜源位置Xi上量子位幅角增量的更新策略为

其中 Δ θi，j为第 i个个体、第 j个量子位的旋转角度。θi，j更新后新个体位置为

由此可见，蜂群个体中通过调整量子位的相位向当前最优相位方向移动，从而调整了量子位概率幅的一个分量，最终体现在蜂群算法是当前引领蜂向当前最优蜜源的方向移动，从而避免了算法搜索的盲目性。

3.3 新的跟随蜂蜜源更新策略

引领蜂采用上述更新策略虽然增强了算法的搜索能力，却降低了算法的开拓特性，导致种群的多样性丢失，最终容易陷入局部优值。跟随蜂对蜜源的选择是通过观察引领蜂的摇摆舞判断蜜源的收益率，并依据收益率大小选择采蜜蜜源。收益率由适应度值表示，选择概率

对每个量子染色体赋予［0，1］之间随机数R，若R ＜Pi，则利用量子非门表示为

采用上面的量子非门操作后，将概率幅正弦分量变换到余弦分量，对量子比特相位而言是进行了角度的互余操作，转换到每个个体的变换域中，相当于进行了互补操作，即跟随蜂的蜜源更新策略为

该更新策略可有效地克服引领蜂更新方式易陷入局部最优的问题，随机动态地将蜜源位置转换到与当前位置互补的位置，从而提升了解空间的多样性。

3.4 侦查蜂随机行为

由于跟随蜂更新策略中，若量子比特的相位为π/4时，无论是概率幅的正弦分量还是余弦分量，对应的数值均相等，即该点为不动点，无论对其进行怎样的非门操作都不能起到更新作用。但在ABC算法中，还有一个控制参数Llimit，用来记录某个蜜源被更新的次数。假定某个蜜源连续经过Llimit次循环后没有得到改善，表明该蜜源陷入局部最优，则该蜜源应被放弃，与该蜜源相对应的蜜蜂也转变为侦查蜂。假设被放弃的蜜源是，则由侦查蜂通过式(11)～式(13)随机行为产生一个新的蜜源代替。从而保证了整个蜂群既具有较好的探索(Exploration)能力又具有较强的开拓(Exploitation)特性。

3.5 改进的量子蜂群(IABCQ)算法步骤

结合上述论述，给出量子思想改进蜂群算法的步骤:

Step1设置算法的控制值，蜜蜂总数2NP，引领蜂和跟随蜂各一半。设置最大循环次数MMCN。判断引领蜂是否陷入局部极值的循环次数Llimit，维数D及搜索范围。

Step2按式(11)～式(13)在搜索区域内随机产生NP个向量，作为蜜源位置，计算适应度函数值，记录当前所有蜜蜂找到的最优蜜源，即全局最优蜜源GlobalMax。对应各NP个引领蜂和跟随蜂，初始化标志向量Tr(i)=0，记录蜜蜂停留同一蜜源的循环次数。

Step3每只引领蜂i按式(14)～式(18)在附近蜜源搜索产生新的蜜源，按待求问题计算适应度函数值，若优于当前蜜源，更新当前引领蜂所在蜜源位置，令 Tr(i)=0，否则更新标志向量 Tr(i)=Tr(i)+1。

Step4按式(19)计算跟随蜂选择蜜源概率，每只跟随蜂i按概率选择蜜源，并转化为引领蜂采蜜，同时按式(20)和式(21)在蜜源附近搜索，产生新的蜜源，按待求问题计算适应度函数值，记录较优蜜源位置，更新向量Tr(i)。

Step5记录当前所有蜜蜂找到的局部最优蜜源Fitness(BestInd)，局部最差蜜源Fitness(WorstInd)。

Step6判断局部最优Fitness(BestInd)是否大于全局最优蜜源GlobalMax，若Fitness(BestInd)大于GlobalMax，用局部最优蜜源更新全局最优蜜源GlobalMax;否则，用全局最优GlobalMax更新局部最差蜜源Fitness(WorstInd)。

Step7判断Tr(i)是否大于 Llimit，若 Tr(i)＞Llimit，第 i个引领蜂放弃当前蜜源而成为侦查蜂，按式(11)～式(13)在搜索区域内随机产生蜜源，按待求问题计算适应度函数值。

Step8更新迭代次数t=t+1。若满足当前迭代次数t＞MMCN或收敛精度要求，则搜索停止，输出全局最优位置;否则转Step3。

4 基于阈值分割的量子思想改进蜂群算法

第3节从整体上论述了蜂群算法结合量子思想进行改进的思路并给出了具体的操作步骤，同时将该改进蜂群算法引入到图像的阈值分割中，以体现算法的有效性。算法采用第1节讨论的二维直线交叉熵作为适应度函数，求取其最大阈值以达到图像目标和背景的有效分割。结合图像一维直方图和二维信息熵所体现的二维直方图的特点对具有不同特性的图像进行阈值分割，主要从以下几个方面进行讨论:

1)标准图库中一维直方图具有单峰特点的图像;

2)标准图库中一维直方图具有多峰特点的图像;

3)标准图库中一维直方图具有不规则特点的图像;

4)含噪声且一维直方图具有不规则特点的非标准图像。

从上面的论述及图像分割理论分析可以明确得到:针对标准图库中一维直方图具有双峰特点的图像能实现良好的阈值分割，但对于一维直方图具有多峰值的标准图像和具有噪声特点的非标准图像想利用经典理论实现效果良好的阈值分割还有一定困难。因此，采用笔者提出的算法对具有以上特点的图像分别进行阈值分割，以此验证该算法在图像阈值分割中具有收敛性和有效性。改进算法条件为MMCN=50，NP=60，Llimit=5，θ0=0.05π，c=0.8。用 Matlab2012b实现，在 Intel CoreTMDuo CPU T5470、主频为1.6 GHz、内存为2.0 GByte的笔记本计算机上运行，验证该算法的分割效果。

4.1 对标准图库中的图像进行分割

选取标准图库中具有代表性的 pears.png，coins.png，rice.png和 lena.jpg，其规格尺寸分别为732×486像素，300×246像素，256×256像素和512×512像素，其一维直方图、二维直方图和分割后的图像分别如图3～图6所示。

图3 Pears.png图像分割过程图Fig.3 Pears.png image segmentation figure

这些图像均是在算法验证过程中经常用到的标准图像。从一维直方图中可以看到，这些图像既有单峰、双峰和多峰的特点也有灰度像素分布相对不规则的特性，单纯利用一维直方图的信息很难实现目标和背景的良好分割。图3b所示的pears.png一维直方图，信息内容大部分体现在黑色和白色之间的过渡色中。应用笔者提出的算法，根据图3c所示的二维直方图，获取使二维直线交叉熵最大的阈值T*=238，得到图3d所示分割后图像，分割后图中梨子的斑点和条纹等细节信息都较好地保留下来，达到了在原图中目标和背景的良好分离。图4b是图4a coins.png的一维直方图，尽管从感官上该图形是有两个峰值，但前面的峰值比后面的峰值大很多，若采用一维直方图常用的OTSU算法进行直接分割，易将图像的细节信息误当作背景而分割掉。采用笔者算法，获取二维直线交叉熵的阈值T*=231，从分割后图像中可以看到，左上的硬币内部轮廓信息也完整保留下来。图5a和图6a的图像一维直方图均是多峰图像的代表，获取的阈值分别是T*=250和T*=217，米粒的轮廓和lena的头发等易忽略的内容均以二维直线交叉熵作为适应度函数并利用笔者提出的IABCQ算法进行图像分割。从而可验证，利用笔者算法对标准图库中的图像进行目标和背景分割可取得较好的分割效果，验证了此算法在该类图像分割中的有效性。

图4 Coins.png图像分割过程图Fig.4 Coins.png image segmentation figure

图5 Rice.png图像分割过程图Fig.5 Rice.png image segmentation figure

图6 Lena.jpg图像分割过程图Fig.6 Lena.jpg image segmentation figure

4.2 对含噪声的非标准图像的分割

上节利用IABCQ算法对标准图库中的几类图像进行分割，标准图像尽管具有不同的信息特征，但离实际应用还有一定差距。在工业现场中应用得最多的是工程图纸，该类图纸图像典型的特征就是线条细，噪声多，而且大多有蓝色背景。这里选取图7a所示的工程图纸，对其进行图像分割，进一步验证该算法在这类图纸中应用的有效性。

从图7b可知，一维直方图大部分信息在白色区域，背景和噪声部分起主导作用，线条信息易被忽略。采用IABCQ算法和二维直线交叉熵对适应度函数进行图像分割，首先利用二维直线交叉熵中3×3的模板对图7a所示的原图进行有效去噪，生成图7c所示的二维直方图;然后利用IABCQ算法快速获取最优阈值T*=312;最后对原图进行理想的分割，其分割效果如图7d所示。由此可见，将该算法应用到工程图纸图像克服了图纸本身背景和噪声的影响，实现了目标从整个图纸的有效分离。从而验证了该算法对工程图纸图像进行分割的有效性以及对噪声的鲁棒性。

图7 工程图纸图像分割过程图Fig.7 Engineering draw's image segmentation figure

4.3 算法性能验证

尽管前面验证了算法的有效性，但算法收敛速度和其他性能指标仍制约着算法应用的前景。为了测试算法性能优劣，选取基本蜂群算法与IABCQ算法对上述测试图像在相同的参数和测试环境下随机运行50次，测得各算法对上述不同图像分割得到的最优值，最差值，平均值，方差和平均运行时间如表1所示。

表1 算法性能指标比较Tab.1 Algorithms'performance comparison

由表1中对比数据可以看到，笔者提出的IABCQ算法的性能指标明显优于基本ABC算法。在相同的迭代次数下，基本ABC算法由于其更新策略是在个体之间进行随机选取，出现局部最优的情况;而IABCQ算法是利用更新策略集中向当前全局最优解汇集的方式，使算法均能获得全局最优解。从平均运行时间上分析，IABCQ算法的收敛速度要明显快于基本ABC算法。总之，笔者提出的IABCQ与基本ABC算法相比，该算法具有良好的收敛速度和对各类图像阈值分割中良好的稳定性和抗噪声能力。

5 结语

笔者针对蜂群算法收敛速度慢、容易陷入局部最优解等缺点，提出了一种改进的量子蜂群算法。该算法中融合了量子思想和蜂群算法获取最优解的机理，将该算法应用到图像阈值分割中，通过不同类型的图像和算法比较结果表明，该算法具有快速的收敛能力以及快速、平稳、准确地对不同图像获取分割阈值的能力，为实现图像目标和背景的良好分割提供了理论依据和应用验证。

［1］范九伦，雷博.灰度图像的二维交叉熵直线型阈值分割法［J］.电子学报，2009，37(3):476－480.FAN Jiulun，LEI Bo.Two－Dimensional Cross－Entropy Linear－Type Threshold Segmentation Method for Gray－Level Images［J］.Acta Electronica Sinica，2009，37(3):476－480.

［2］LINYI LI，DEREN LI.Fuzzy Entropy Image Segmentation Based on Particle Swarm Optimization ［J］.Progress in Natural Science，2008，18(9):1167－1171.

［3］KARABOGA D.An Idea Based on Honey Bee Swarm for Numerical Optimization［R/OL］.Kayseri:Erciyes University，Engineering Faculty，Computer Engineering Department［2014－06－08］.http://www.docin.com/p－773016019.html.

［4］刘勇，马良.函数优化的蜂群算法［J］.控制与决策，2012，27(6):886－890.LIU Yong，MA Liang.Bees Algorithm for Function Optimization ［J］.Control and Decision，2012，27(6):886－890.

［5］胡中华，赵敏.基于人工蜂群算法的TSP仿真［J］.北京理工大学学报，2009，29(11):978－982.HU Zhonghua，ZHAO Min.Simulation on Traveling Salesman Problem(TSP)Based on Artificial Bees Colony Algorithm［J］.Transactions of Beijing Institute of Technology，2009，29(11):978－982.

［6］OMKAR S N，SENTHILNATH J，RAHUL KHANDELWAL，et al.Artificial Bee Colony for Multi－Objective Design Optimization of Composite Structures［J］.Applied Soft Computing，2010(11):489－499.

［7］李林菲，马苗.基于ABC算法的逻辑推理题快速求解方法［J］.计算机技术与发展，2011，21(6):125－127.LI Linfei，MA Miao.Artificial Bee Colony Algorithm Based Solution Method for Logic Reasoning ［J］.Computer Technology and Development，2011，21(6):125－127.

［8］HSIN－CHIH WANG，WANG Yucheng，MEN－SHEN TSAI.Performance Comparisons of Genetic Algorithm and Artificial Bee Colony Algorithm Applications for Localization in Wireless Sensor Networks［C］∥System Science and Engineering 2010 International Conference.Wuhan，China:［s.n.］，2010:469－474.

［9］YE Zhiwei，ZENG Mengdi.Image Enhancement Based on Artificial Bee Colony Algorithm and Fuzzy Set［C］∥International Symposium on Information Engineering and Electronic Commerce(IEEC).Wuhan，China:［s.n.］，2011:127－130.

［10］肖永豪，余卫宇.基于蜂群算法的图像边缘检测［J］.计算机应用研究，2010，27(7):2748－2750.XIAO Yonghao，YU Weiyu.Bee Colony Algorithm for Image Edge Detection［J］.Application Research of Computers，2010，27(7):2748－2750.

［11］何志明，马苗.基于灰色关联分析和人工蜂群算法的图像匹配方法［J］.计算机技术与发展，2010，20(10):79－81.HE Zhiming，MA Miao.Fast Image Matching Approach Based on Grey Relational Analysis and Artificial Bee Colony Algorithm［J］.Computer Technology and Development，2010，20(10):79－81.

［12］SHOR P W.Algorithms for Quantum Computation:Discrete Logarithms and Factoring［C］∥Proc of the 35th Annual Symp on Foundations of Computer Science.New York，USA:IEEE Computer Society Press，1994:124－134.

［13］GROVER L K.A Fast Quantum Mechanical Algorithm for Database Search［C］∥Proc of the 28th Annual ACM Symp on Theory of Computing.New York，USA:ACM Press，1996:212－219.

［14］高洪元，曹金龙.量子蜂群算法及其在认知频谱分配中的应用［J］.中南大学学报:自然科学版，2012，43(12):4743－4749.GAO Hongyuan，CAO Jinlong.Quantum－Inspired Bee Colony Optimization Algorithm and Its Application for Cognitive Radio Spectrum Allocation ［J］.Journal of Central South University:Natural Science Edition，2012，43(12):4743－4749.

［15］易正俊，何荣花，侯坤.量子位Block坐标的量子人工蜂群优化算法［J］.计算机应用，2012，32(7):1935－1938.YI Zhengjun，HE Ronghua，HOU Kun.Quantum Artificial Bee Colony Optimization Algorithm Based on Bloch Coordinates of Quantum Bit［J］.Computer Applications，2012，32(7):1935－1938.

［16］李盼池，宋考平，杨二龙.一种基于相位编码的量子遗传算法［J］.信息与控制，2010，39(6):681－685.LI Panchi，SONG Kaoping，YANG Erlong.A Quantum Genetic Algorithm Based on Phase Encoding ［J］.Information and Control，2010，39(6):681－685.