基于混合ABC-CS算法的彩色图像多阈值分割*

蒲国林　卫洪春　向　伟　邱玉辉

(1.四川文理学院计算机学院　达州　635000)(2.西南大学计算机与信息科学学院　重庆　400715)



基于混合ABC-CS算法的彩色图像多阈值分割*

蒲国林1卫洪春1向伟1邱玉辉2

(1.四川文理学院计算机学院达州635000)(2.西南大学计算机与信息科学学院重庆400715)

摘要将人工蜂群算法中引领蜂和跟随蜂的开采行为融入布谷鸟算法(CS)的每一次莱维飞行结束后进行寻优引导，对发现概率和步子因子也采用了相应新的变异因子随着布谷鸟算法运行而动态改变，以此为基础，提出了一种混合人工蜂群算法的布谷鸟算法(HACS)，并以此HACS算法作用于彩色图像多阈值分割，实验表明，HACS算法有效解决了布谷鸟算法收敛时间较长、精度不高的问题，在彩色图像多阈值分割中取得了较好的效果。

关键词人工蜂群算法; 开采行为; 布谷鸟算法; 发现概率; 步子因子

Class NumberTP391

1引言

彩色图像阈值分割是图像分割和解释的基本过程，也是将图像从背景中分离出来的最为普遍的方法，目前已经应用于多个方面[1～2]，一般情况下是根据一个或多个阈值将图像分离为各个感兴趣的区域，相比256级的灰度图像的阈值分割，彩色图像的多阈值分割能得到更详细的信息，更有效的处理能力，但彩色图像的多阈值分割是一个挑战性的任务，因为随着分割层级的增加，运算代价也会随着增加[3]，彩色图像分割目前主要有基于区域分割的方法、基于边缘分割的方法、基于特征空间的方法、基于梯度阈值的方法等。近年来，出现了许多经典的图像分割技术，但实验证明，这些经典的图像分割技术大多以穷尽搜索最优阈值为特征，比较耗时，为了提高图像分割的质量和速度，也出现了一些令人感兴趣的方法[4～5]，为了得到理想的彩色图像分割结果，最突出的问题是如何选择最合适的阈值问题，在这方面，基于进化和群集的算法在从目标函数中寻找最优解的能力相当优秀，目前这些算法由于能在复杂问题中得到高质量的解而广泛使用，由于这些算法的优势，因而已被广泛使用在图像分割的阈值寻优方面[6～7]，目前研究表明基于群体的算法在多阈值分割问题方面更精确[8]，随着群体智能算法的发展，更多的群体智能算法被应用在图像多阈值分割领域[9～10]，但彩色图像的多阈值分割问题始终存在分割时间过长、分割质量与理想要求有较大差距的问题。

要提高彩色图像分割的质量和速度，本文采用人工蜂群算法[11]和布谷鸟算法[12～13]相结合的方法，并对布谷鸟算法中的发现概率和步长因子也进行了改进。

2混合人工蜂群布谷鸟算法的彩色图像多阈值分割

为解决当前彩色图像多阈值分割中分割清晰度不高、过分割、效率低等缺陷，采用本文提出的HACS混合算法进行彩色图像分割，而效益度(适应度)函数采用Tsallis最小交叉熵函数[14]，此HACS混合算法运用于彩色图像多阈值分割所求得的全局最优解就是所求的一系列最优阈值组合。

2.1布谷鸟算法

布谷鸟算法是一种新的元启发式优化算法，其主要原理是雌性布谷鸟将宿主的蛋推出去而放入自己的蛋，这种行为之所以成功主要在于布谷鸟蛋模仿宿主蛋的行为。通过宿主发现布谷鸟蛋而布谷鸟蛋不断模仿宿主蛋这种行为实际上实现了进化，因为布谷鸟产蛋的时间刚好就是宿主鸟产蛋的时间，在本算法中每有一只布谷鸟蛋就引进一个新解，其目的是用新的有潜力的更好解取代不是很好的解，在简单情况下，每只鸟巢只有一个蛋，在复杂情况下，每只鸟巢可以有多个蛋并代表一系列解，应用这种搜索作为一种优化算法，并采用三个规则[15～16]，其位置变量公式如下：

(1)

其中，vit+1表示第t+1迭代中第i个鸟窝位置,vit表示第t迭代中第i个鸟窝位置，α表示步长因子，levy(λ)表示莱维飞行因子其公式如下：

(2)

其中λ是分布因子，τ()函数是一个gamma分布函数。

2.2布谷鸟优化算法的改进

在此混合人工蜂群算法和布谷鸟算法的混合算法中，通过将人工蜂群算法中引领蜂和跟随蜂开采方程应用于每一次莱维飞行结束后，并对原人工蜂群算法中引领蜂和跟随蜂的搜索方程进行了改进，其新的搜索方程如下：

BSi,j=BSi,j+α(BSbest,j-BSk,j)+λ(BSm,j-BSi,j)

(3)

其中左边BSi,j表示莱维飞行结束变异后的第i个位置，而等式右边第一个因子BSi,j表示莱维飞行结束后未进行变异前的第i个位置的第j个元素，BSbest,j为此混合算法中搜索得到的当前全局最优解的第j个元素，j∈{1,2,…,N}并且N为此混合算法的种群规模，在此混合算法中各参数i,k,m各异，α和β是随机数，其取值范围分别在[-1,1.5]和[-1,1]之间，同时经过研究发现，布谷鸟算法中步长因子和发现概率对整个布谷鸟算法的效率和收敛精度也有较大影响，根据对布谷鸟算法的运行规律实验观察，发现若步长因子和发现概率前期较大，是有利于全局最优搜索的，而后期的值应当适当减少才有利于局部收敛和全局最优解的求取。故本文对步长因子和发现概率各提出了一个变异因子，使步长因子和发现概率随着此算法的运行而动态变化，其动态变异方程如下：

(4)

方程(4)是步长因子动态变异方程，Tmax、Tmin分别表示当前步长因子的最大值和最小值，i为此混合算法中当前迭代次数。

(5)

方程(5)是本文混合算法中所提出的发现概率变异方程，pmax(t)表示此混合算法中当前代的最大发现概率，pmin(t)表示此混合算法中当前代的最小发现概率，Tmax表示当前最大迭代次数。

2.3本文提出的算法

在本文所提出的HACS算法运用于彩色图像多阈值分割中时，以Tsallis最小交叉熵为适应度函数，所求得的全局最优解的各个解分量就是本文所提算法中所求得最优位置鸟巢中鸟蛋的个数(Tsallis最小交叉熵变量个数)，也就是所求得的彩色图像多阈值分割中全局最优阈值的各个分量分数。

其改进算法如下：

1) 初始化此混合算法中所有参数。

2) 产生初始HACS的种群。

3) 根据HACS算法产生随机解，以Tsallis最小交叉熵计算效益度值。

4) 从当前所得到的全部解中，识别出局部最优解和全局最优解，并开始迭代程序。

5) 在每次莱维飞行结束后采用式(3)寻优，而步长因子和发现概率也分别按式(4)、式(5)计算效益度值，识别出局部最优和全局最优鸟窝位置。

6) 更新种群。

7) 重复前述4)、5)、6)步骤过程，直至满足预定的结束条件为止。

8) 输出得到最终全局最优解的各个解分量，就是所求得彩色图像分割的一系列阈值。

3实验结果与分析

本实验硬件平台为4核3.3GHz，4G内存，以Matlab作为软件平台，为测试本文所提出的改进算法性能，将本实验分为两大部分，第一部分是主观实验部分，以本文所提出HACS算法进行彩色图像多阈值分割的结果图进行主观分析，第二部分是客观实验，从HACS算法、ABC算法、CS算法这三种算法分别对彩色图像多阈值分割的速度和质量进行分析比较。

3.1三种算法在桃花岛图上进行多阈值分割的实验结果图主观效果比较

在本实验中为验证本文所提出HACS算法彩色图像多阈值分割的主观效果，选取了大量素材，进行了大量实验，本实验素材都是从网上或实验室获得，由于篇幅所限，本文只选取了浙江舟山桃花鸟图的三种算法实验结果进行比较分析。下图分别是HACS算法、ABC算法、CS算法的二维、三维、四维实验结果图像。

图1　桃花岛原图及ABC算法的多阈值分割实验结果图

图1是ABC算法的实验结果图，从横向来看，图1(b)～(d)图的分割效果中，(d)图分割效果最好，(b)效果最差，(c)图的分割效果居中，在(d)图的桃花岛图中远处天上的云层、远处及近处的山和图前面的亭式建筑都一定程度分割出来了，而(b)图无论是云层、远山及近山、近处亭式建筑分割得都不太清楚。纵向来看，图2是CS算法的分割结果图，其分割效果比ABC好些，而图3的HACS算法的分割效果从整体来看是最好的。在相同维数情况下，如都在二维、三维、四维情况下，HACS算法比ABC算法和CS算法的分割效果都好，在图3(d)图中，天上的云层、远处的山及近处的山，近处的亭式建筑甚至亭式建筑后面的树都分割得比较清楚，明显比图2(d)、图1(d)效果要好。

图2　桃花岛原图及CS算法的多阈值分割实验结果图

图3　桃花岛原图及HACS算法的多阈值分割实验结果图

3.2HACS算法、ABC算法、CS算法多阈值分割实验结果的客观分析

本实验中为了对本文所提出的HACS算法的多阈值分割结果进行客观分析，采用HACS算法和标准ABC算法以及标准CS算法进行对比实验，以Tsallis最小交叉熵函数为适应度函数，采用阈值、分割时间、均一度[17]作为评价指标，对应3.1部分的实验结果图，分别给出了三种算法对应的二阈值、三阈值、四阈值指标数据，具体指标数据如表1。

从表1三种算法的实验指标数据来看，在运行时间方面，在同为二维阈值的情况下，HACS算法的运行时间是CS算法运行时间的76.91%，而ABC算法的运行时间是CS算法运行时间的77.42%。在同为三维阈值的情况下，HACS算法的运行时间是CS算法的运行时间的81.70%,而ABC算法的运行时间是CS算法的运行时间的86.87%。在同为四维阈值的情况下，HACS算法的运行时间是CS算法的运行时间的80.74%，而ABC算法的运行时间是CS算法运行时间的88.59%。因而无论从二维、三维、四维阈值分割的情况来看，HACS算法的运行时间都是最短的，在均一度方面，每一种算法随着阈值数的增加，其分割质量明显变好，而三种算法中，无论从相同阈值数来看，还是从整体分割情况来看，HACS算法的分割质量都是最好的，另外本实验中还知道ABC算法运行时间比CS算法运行时间短，这说明ABC算法的多阈值分割速度比CS算法快。

表1　HACS、ABC、CS三种算法的实验指标数据比较

4结语

彩色图像多阈值分割一直以来是研究的难题，本文通过将人工蜂群算法和布谷鸟算法相结合实现两种算法的优势互补，将此混合算法和人工蜂群算法、布谷鸟算法以Tsallis最小交叉熵作为适应度函数进行彩色图像多阈值分割的对比实验，实验结果表明本文所提出的人工蜂群布谷鸟混合算法在彩色图像分割的无论主观效果还是客观效果，都是最好的。

参 考 文 献

[1] N. Paragios, R. Deriche. Geodesic active contours and level sets for the detection and tracking of moving objects[J]. IEEE Trans. Pattern Anal. Mach. Intell,2000,22(3):266-280.

[2] T. Zhang, D. Freedman. Tracking objects using density matching and shape priors[C]//Proceedings of IEEE International Conference on Computer Vision,2003(2):1056-1062.

[3] Dey, S., Saha, I., Bhattacharyya, S., et al. Multi-level thresholding using quantum inspired meta-heuristics[J]. Knowledge-Based Systems,2014,67:373-400.

[4] Manikandan, S., Ramar, K., Willjuice, I. M., et al. Multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm[J]. Measurement,2014,47:558-568.

[5] Dirami, A., Hammouche, K., Diaf, M., et al. Fast multilevel thresholding for image segmentation through a multiphase level set method[J]. Signal Processing,2013,93(1):139-153.

[6] Liu, Y., Mu, C., Kou, W., et al. Modified particle swarm optimization-based multilevel thresholding for image segmentation[J]. Soft Computing,2015,19(5):1311-1327.

[7] Zhang, J., Li, H., Tang, Z., et al. An improved quantum inspired genetic algorithm for image multilevel thresholding segmentation[J]. Mathematical Problems in Engineering,2014:1-12.

[8] Kurban, T., Civicioglu, P., Kurban, R., et al. Comparison of evolutionary and swarm based computational techniques for multilevel color image thresholding[J]. Applied Soft Computing,2014,23:128-143.

[9] Zhang, Y., Wu, L. Optimal multi-level thresholding based on maximum Tsallis entropy via an artificial bee colony approach[J]. Entropy,2011,13(4):841-859.

[10] Agrawal, S., Panda, R., Bhuyan, S., et al. Tsallis entropy based optimal multilevel thresholding using cuckoo search algorithm[J]. Swarm and Evolutionary Computation,2013,11:16-30.

[11] D. Karaboga. An Idea Based on Honey Bee Swarm for Numerical Optimization[R]. Kayseri: Erciyes University,2005.

[12] Afzalan E, Joorabian M. An improved cuckoo search algorithm for power economic load dispatch[J]. International Transactions on Electrical Energy Systems,2015,25(6):958-975.

[13] M. Basu, A. Chowdhury, Cuckoo search algorithm for economic dispatch[J]. Energy,2013,60(1):99-108.

[14] 唐英干,邸秋艳,关新平,等.基于最小Tsallis交叉嫡的阈值图像分割方法[J].仪器仪表学报,2008,29(9):1868-1872.

TANG Yinggan, GUAN Xinping, Liu Fucai, et al. thresholding image segmentation method based on minimum Tsallis cross entropy[J]. Chinese Journal of Scientific Instrument,2008,29(9):1868-1872.

[15] Yang XS, Deb S. Multiobjective cuckoo search for design optimization[J]. Comput Oper Res,2013,40:1616-24.

[16] Abd-Elaziz AY, Ali ES. Cuckoo search algorithm based load frequency controller design for nonlinear interconnected power system[J]. Int J Electric Power Energy Syst,2015,73:632-43.

[17] TANG Kezong, YUAN Xiaojing, SUN Tingkai, et al. An improved scheme for minimum cross entropy threshold selection based on genetic algorithm[J]. Knowledge-based Systems,2011,24(8):1131-1138.

收稿日期:2016年1月6日,修回日期:2016年2月19日

基金项目:国家自然科学基金(编号：61152003);国家档案局科技项目(编号：2014-X-65);四川省教育厅重点项目(编号：16ZA0353);四川省教育厅资助科研项目(编号：15ZB0323);四川文理学院智能计算与物联网工程技术中心资助。

作者简介:蒲国林,男,博士,副教授,研究方向：人工智能、数字图像处理。卫洪春,男,硕士,讲师,研究方向：图形图像处理。向伟,男,硕士,讲师,研究方向：软件工程、智能计算。邱玉辉,男,教授,博士生导师,研究方向：人工智能。

中图分类号TP391

DOI:10.3969/j.issn.1672-9722.2016.07.029

Color Image Multi Threshold Segmentation Based on Hybrid ABC-CS Algorithm

PU Guolin1WEI Hongchun1XIANG Wei1QIU Yuhui2

(1. School of Computer Science, Sichuan University of Arts and Science, Dazhou635000)(2. College of computer and Information Science, Southwest University, Chongqing400715)

AbstractThe behaviors of employed bees, onlooker bees in artificial bee colony algorithm are introduced into every time after the end of flight Levi of cuckoo search(CS) algorithm to optimized guiding, the discovery probability and the pace factor are also using the corresponding new variation factors, and change with cuckoo algorithm operation. Based on this, a hybrid artificial bee colony algorithm and cuckoo search algorithm (HACS) is proposed, and the HACS algorithm is used for color image segmentation. Experimental results show, the HACS algorithm can effectively solve the cuckoo algorithm long convergence time, lower accuracy. Good results have been achieved in the color image multi threshold segmentation.

Key Wordsartificial bee colony algorithm, mining behavior, cuckoo algorithm, detection probability, step factor