基于增强布谷鸟算法的彩色图像多阈值分割

蒲国林，邱玉辉

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

基于增强布谷鸟算法的彩色图像多阈值分割

蒲国林1，邱玉辉2

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

为提高彩色图像多阈值分割的速度和质量，针对布谷鸟算法的缺陷，对每一次莱维飞行结束后，提出一个新的寻优方程进行寻优引导，并对发现概率和步子因子都各提出了一个新的运行方程，以此为基础，提出了一种增强布谷鸟算法（ECS），并以此ECS算法作用于彩色图像多阈值分割中，通过本文所提出算法和标准粒子群算法及标准布谷鸟算法的对比实验表明，本文所提的ECS算法无论在彩色图像分割的主观效果上还是客观效果上都是最好的，完全能运用于实际的多阈值分割中。

彩色图像；多阈值分割；布谷鸟算法；发现概率；步长因子；粒子群算法

图像分割特别是彩色图像分割是数字图像处理的重要步骤，现在已经广泛应用于目标检测、视觉跟踪、场景理解和基于内容的图像检索等方面。图像分割主要有4个类型：基于聚类的方法、基于区域的方法、基于阈值的方法和基于边缘检测的方法。基于阈值的方法简单、高效，并得到了广泛使用。在基于阈值的方法中，随着分割阈值数的增加，分割的目标更接近于真实的子目标，分割效果也越理想，但分割的数据量急剧增加，分割速度也越来越慢，有时候随着分割阈值数的增加分割质量反而降低，主要是由于多维阈值的选择比较。如何寻找最理想的阈值将彩色图像的各个需求子目标分割开来，是研究人员一直以来努力寻求的目标。

随着群体智能算法如粒子群算法［1］、蚁群算法［2］、人工蜂群算法［3］等在各方面的快速发展，在彩色图像分割领域也取得了重要进步［4-5］，但至今为止优秀图像分割算法特别是彩色图像分割算法并不多，各个算法都是在某些方面或某个领域有较好的效果，统一高效的彩色图像分割算法目前还没有。

近年来新出来的布谷鸟算法［6］以参数简单，实现容易，效率较高的优点，已应用在某此方面并取得了进步［7-8］，但布谷鸟算法也存在收敛慢，易陷入局部最优等缺点，本文提出一种增强布谷鸟算法应用于解决彩色图像多阈值分割，增强布谷鸟算法的有效性能，实验表明在彩色图像多阈值分割中取得了较好的效果。

1　Tsallis熵函数的彩色图像分割原理

在熵的图像阈值分割中，Tsallis熵［9］将图像分割为各个子系统后各个图像子系统的概率分布关系比较清楚的表示出来，并且算法较为简单，在有些方面已经得到了较为成功的应用［10-11］。Tsallis熵公式如下：

其中q是待定系数，Pi∈［0，1］代表各个系统的概率，且熵各个子系统熵的关系表示如下：

这个公式分两种情况分别说明了彩色图像和灰度图像的Tsallis熵，假设输入图像的灰度级为G级，各个灰度级像素点的概率分布为P1，P2，P3…PG。

假设A、B分别为图像分割中两个子区域（也可以为前景和目标物），则对应概率公式如下：

这里：

因此对各个子区域，tsallis熵分类如下：

这个最优阈值可以采用较少的计算量用以下公式计算：

其中，

上面公式可以直接到多阈值情况如下：

2　彩色图像布谷鸟算法的多阈值分割

文中以布谷鸟算法对彩色图像的阈值分割进行多阈值寻优，并以Tsallis熵函数［12］作为适应度函数，由于布谷鸟算法本身容易陷入局部最优，收敛速度较慢，故本文提出一种增强布谷鸟算法，并根据最大Tsallis熵函数理论进行多阈值寻优，所求最优解的各个分量即为多阈值最优分割中的各个阈值。

2.1布谷鸟算法

布谷鸟算法是一个新的元启发式优化算法，此算法受到布谷鸟种群通过将自己的蛋放到其他种群鸟儿鸟窝中的育雏寄生行为的启发而产生，当宿主发现了这些布谷鸟蛋后，可能会将这些蛋扔出去或抛弃这个鸟巢而建一个新的鸟巢，CS算法将布谷鸟种群这种育雏行为和一些鸟儿的莱维飞行行为相结合并理想化这种行为，使之成为一种独立的算法，用来解决许多约束优化问题。其位置变量公式如下：

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

2.2布谷鸟优化算法的改进

为了提高布谷鸟算法的收敛速度，在每一次莱维飞行结束后，进行寻优引导。

其中SPi，j为当前位置的第j个元素，SPbest，j为当前最优位置的最j个元素，j∈｛1，2，…D｝并且j为问题的维度，i，j，n互不相等，g为高斯变异因子，λi，j∈［0，1.5］的随机数，βi，j∈［-1，1］的随机数，通过此搜索方程，可以在每一次莱维飞行结束后，加强引导，以促进算法向最优位置搜索，同时通过高斯变异因子将陷入局部最优的粒子跳出局部最优。

同时在布谷鸟算法中，步长因子和发现概率对布谷鸟算法的收敛也是至关重要，通过对粒子群算法和人工蜂群算法以及其他群体智能的研究，结合实验，我们对步长因子和发现概率各提出了一个新的公式如下：

上两式中，Sa，min，Sa，max分别表示步长因子的最小和最大值，fmax，fmin分别表示发现概率的最大和最小值，t，tmax分别表示当前迭代次数和最大迭代次数，m1，m2为控制因子，m1∈［0，1］，m2∈［π，10］，采用上面两式，可以保证搜索前期莱维飞行距离远，寻优能力较强，这样可以避免早熟现象，而后期局部寻优能力较强，加快收敛。

2.3本文提出的算法

文中提出的增强布谷鸟算法运用于彩色图像多阈值分割过程中，每个鸟巢中鸟蛋的个数就是此彩色图像分割中的阈值个数，也就是本文采用的适应度函数中Tsallis熵函数的变量个数，所求的全局最优解对应的就是彩色图像分割中全局最优阈值。

其改进算法如下：

1）初始化布谷鸟算法产生N只鸟窝（即n个初始解）及相关初始参数如发现概率、步长因子、最大迭代次数等，本实验中步长因子的最小值、最大值分别为Sa，min=0.000 5和Sa，max= 0.5，发现概率的最大值和最小值分别为fmax=0.5和fmin=0.001，最大迭代次数tmax为300，控制因子m1，m2分别取为m1=0.6，m2=6。

2）根据本改进布谷鸟算法选择相应的搜索边界（上界和下界本文中上界设为256，下界设为1）。

3）以Tsallis熵函数作为适应度函数，根据搜索方程及本文提出的步长因子公式（10）和发现概率公式（11），产生随机解。

4）当不满足停止条件时，进行莱维随机飞行，每次莱维飞行结束至下次飞行前，运用方程（9）进行寻优引导，并计算出当前Tsallis熵函数值。

5）当前适应度值（熵函数值）与当前最优适应度值比较，若当前对应的适应度值更优，则取代当前最优值，将当前适应度值作为全局最优值，并产生一个新的鸟窝。

6）以当前发现概率发现质量差的鸟窝时，该鸟窝被抛弃，建立新的鸟窝。

7）保留当前最优解。

8）根据当前最优解得到当前全局最优阈值。

3　实验结果与分析

本实验基于MATLAB平台，硬件配置为CPU3.4 GHz四核，内存4 G，分两部分，第一部分是主观实验，通过本文算法和粒子群及标准布谷鸟算法以Tsallis熵函数为适应度函数对多张图像进行分割对比实验，第二部分是客观实验，通过对3种算法的彩色图像分割时间和质量进行比较。

3.13种算法在以Tsallis熵函数为适应度值时的彩色图像分割结果比较

本实验部分的实验图像素材来源于实验室或从网络中下载，由于篇幅本文选择了基于三亚大东海的图像，3种算法分别在三亚大东海实验图像中进行二维、三维以及四维阈值分割，本实验项目是一个机器视觉项目的子项目，目的是为了准确分割出图中的各个对象以便能对各个目标对象进行自动分类识别，以下是分割实验结果图像。

图1　三亚大东海原图及PSO算法的二维、三维、四维分割实验结果图

图2　三亚大东海原图及标准CS算法的二维、三维、四维分割实验结果图

图3　三亚大东海原图及增强CS（ECS）算法的二维、三维、四维分割实验结果图

从图1至图3的分割结果来看，3种算法在相同维数进行分割时，无论是二维分割、三维分割还是四维分割，图3的分割效果是最好的，这表明本文提出的ECS算法和其他两种算法相比在彩色图像多阈值分割时效果是最好的，在同为二维分割时，PSO算法分割效果最差，在沙滩的分割上有许多杂色粒子像素块存在，而我们的目标是分割出沙滩区域，在PSO这种分割中，就出现了过分割现象，远处的椰树及建筑分割模糊，近处的休息椅子许多没有分割出来。CS算法明显要好些，ECS算法的分割效果最好，其近沙滩分割比较清晰，而PSO分割时出现了不同的像素斑块过分割现象。同为三维和四维图像分割时，同样PSO算法效果最差，ECS分割效果最好。在ECS的四维分割时，无论是远处的建筑还是椰树其分割都比较清楚，甚至天上的云层形状也分割得比较清晰，近处沙滩的边缘轮廓也比较清楚分割出来。

3.23种算法多阈值分割实验的客观数据指标比较

本实验部分以基于粒子群算法、布谷鸟算法以及本文中提出的ECS算法，以Tsallis熵函数为适应度函数，其实验评价指标包括3种算法在3种阈值情况下Tsallis熵的最优目标值比较如表1所示，结构相似性SSIM［13］和特征相似性FSIM［14］值比较如表2和表3所示，分割时间、质量均一度的比较如表4所示，其中图像质量均一度［15］计算公式如下：

式中T表示阈值的个数，Rj表示分割区域j，gmax，gmin，ui分别表示图像对应区域中的最大灰度值，最小灰度值，以及对应区域j的灰度均值，而gi表示像素i的灰度值，M表示一个给定图像中像素的总体数量。

表1　3种算法使用Tsallis Entropy的最优目标值比较

表2　3种算法使用Tsallis entropy的SSIM值比较

表3　3种算法使用Tsallis entropy的FSIM值比较

表4　3种算法的阈值、运行时间及均一度比较

如上述表1至表4所示，表1从全局最优适应度值即全局最优阈值的角度说明，ECS算法具有全局最优目标值就是说具有最优分割阈值，表2的结构相似性（SSIM）和表3特征相似性（FSIM）从图像的结构、相位及梯度方面说明了图像分割后失真程度或错分率，并且从表2和表3还可以看出本文提出的ECS算法所分割图像无论在二阈值、三阈值还是四阈值情况下，其失真程度或错分率都是最低的，而PSO失真度或错分率都是最高的，CS算法居中。从分割的时间来看，在同为二维阈值时，CS算法的分割时间是PSO算法分割时间的92%，ECS算法的彩色图像分割时间是CS算法分割时间的86%，在同为三维阈值分割时，CS算法是PSO算法时间的90%，ECS算法是PSO时间的74%。在同为四维阈值分割时，CS算法分割时间是PSO算法分割时间的85%，ECS算法的分割时间是PSO算法分割时间的67%。因此无论从不同算法的相同阈值分割还是同一种算法的不同分割阈值的分割时间来看，ECS算法的分割时间都是最少的，CS算法所用时间居中，PSO算法所用时间最多，在均一度方面，按照均一度原理，图像分割后的均一度越高，说明图像分割质量越好。从表4来看，很明显，在同一种算法中，随着阈值分割数的提高，分割质量也随着提高，在不同阈值分割时，本文提出的ECS算法的均一度相对来说，都是最高的，因此说明本文提出的算法其多阈值分割质量是有明显提高的。

4　结束语

本文为了提高彩色图像多阈值分割的速度和改进彩色图像多阈值分割的效果，对现在比较优秀的布谷鸟算法的寻优方式、发现概率和步长因子都进行了改进，以此改进的ECS算法运用于彩色图像分割中，并与标准PSO算法和CS算法进行了对比实验，实验说明本文提出的ECS算法无论是分割速度还是分割效果都是最好的。

［1］Kennedy J，Eberhart R C.Particle swarm optimization［C］// Proceedings of the 1995 IEEE International Conference on Neural Networks.Piscataway，NJ，Perth，IEEE service center，1995:1942-1948.

［2］Salima Ouadfel，Mohamed Batouche.An efficient ant algorithm for swarm-based image clustering［J］.Computer Science，2007（3）3:162-167.

［3］Karaboga D.An idea based on honey bee swarm for numerical optimization.Technical Report，Erciyes University，Engineering Faculty［J］.Computer Engineer-ing Department，2005.

［4］Liu Y，Mu C，Kou W，et al.Modified particle swarm optimization-based multilevel thresholding for image segmentation［J］.Soft Computing，2014:1-17.

［5］Huang P，Cao H，Luo S.An artificial ant colonies approach to medical imagesegmentation Comput［J］.Methods Progr. Biomed，2008，92（1）:267-273.

［6］Basu M，Chowdhury A.Cuckoo search algorithm for economic dispatch［J］.Energy，2013，60（1）:99-108.

［7］Valian E，Mohanna S，Tavakoli S.Improved cuckoo search algorithm for global optimization［J］.Int.J.Comunications and Information Technology，2014，1（1）:31-34.

［8］Yang X S，Deb S.Cuckoo search via Levy flights，Proceedings of the world congress on nature and biologically inspired computing Coimbatore［J］.NABIC，2009（4）:210-214.

［9］尹诗白，赵祥模，王卫星，等.递推人工蜂群的模糊划分熵多阈值分割算法［J］.西安交通大学学报，2012，46（10）:72-77.

［10］邸秋艳.基于Tsallis熵的阈值图像分割方法研究［D］.燕山大学，2009.

［11］Sathya P D，Kayalvizhi R.PSO-based Tsallis thresholding selection procedure for image segmentation［J］.International Journal of Computer Applications，2010，5（4）:39-46.

［12］Portes DE Albuquerque M，Esquef I A，et al.Image thresholding using Tsallis entropy［J］.Pattern Recognition Letters，2004，25（9）:1059-1065.

［13］庞建新，张荣，张晖，等.图像结构失真的编码质量评价［J］.中国图象图形学报，2009，14（8）:1560-1568.

［14］ZHANG Lin，ZHANG Lei，MOU Xuan-qin，et al.FSIM:a feature similarity index for image quality assessmen［J］.IEEE Trans on Image Processing，2011，20（8）:2378-2386.

［15］TANG Ke-zong，YUAN Xiao-jing，SUN Ting-kai，et al.An improved scheme for minimum cross entropy threshold selection based on genetic algorithm［J］.Knowledge-based Systems，2011，24（8）:1131-1138.

A color image multi threshold image segmentation method based on enhanced cuckoo algorithm

PU Guo-lin1，QIU Yu-hui2
（1.School of Computer Science，Sichuan University of Arts and Science，Dazhou 635000，China；2.College of Computer and Information Science，Southwest University，Chongqing 400715，China）

In order to improve the speed and quality of color image segmentation，aiming at the limitation of the cuckoo algorithm，every time after the end of the Lévy flight，a new optimization seeking equation is proposed，and the discovery probability and the pace factor are respectively proposed a new operating equation.Based on this，proposed an enhanced cuckoo algorithm（ECS），and the ECS algorithm is based on the multi threshold segmentation of color image.Through the comparison of the proposed algorithm（ECS），the standard PSO algorithm and the standard CS algorithm，the ECS algorithm is the best of both subjective and objective results，fully able to be applied to the actual multi threshold segmentation.

color image；multi-threshold segmentation；cuckoo algorithm；detection probability；step factor；particle swarm optimization

TN 911.73

A

1674－6236（2016）12-0009-05

2016-02-22稿件编号：201602092

国家自然科学基金（61152003）；四川省教育厅资助科研项目（15ZB0323）

蒲国林（1971—），男，四川宣汉人，博士研究生，副教授。研究方向：人工智能，数字图像处理。