基于乌鸦搜索优化算法的多级阈值图像分割方法

康丽锋; 吴锋

doi:10.13718/j.cnki.xsxb.2021.01.007

摘要: 针对传统Kapur熵在多阈值图像分割算法中存在运算量大、计算效率低以及精度不高等问题，提出了一种基于乌鸦搜索优化算法的多级阈值图像分割方法，该方法采用Kapur熵作为计算适应度的目标函数，通过引入乌鸦搜索优化算法求解目标函数最大化时的全局最优问题.实验结果表明：相对于其他方法，本文方法在多个评价指标上都有很好的性能体现，并且本文方法在保证较好分割效果的同时，计算效率明显提升.

Abstract: Aiming at the problems of traditional Kapur's entropy in multi-threshold image segmentation algorithm, such as large computational complexity, low computational efficiency and low precision, a multi-level threshold image segmentation method based on crow search optimization algorithm has been proposed. According to the algorithm, Kapur's entropy has been used as the objective function of computational fitness, and introduces the crow search optimization algorithm to solve the global optimal problem when the objective function is maximized. The experimental results show that compared with other methods, the proposed method has good performance on many evaluation indicators, and the calculation efficiency is obviously improved while ensuring better segmentation effect.

Key words:

全文HTML

图像分割是基于某种分组标准将图像细分成更易于分析内容的过程.对于基于计算机视觉的应用，如面部识别、机器视觉、对象跟踪等领域，图像分割是一项重要的预处理任务^[1].目前，用于图像分割的技术很多，大致可以分为基于边界、基于区域、基于聚类以及基于阈值4类方法^[2-3].基于阈值的方法是最简单、计算效率高且应用最为广泛的图像分割方法之一.阈值技术的主要目的是找出用于图像分割的阈值.在双阈值法中，选择一个阈值将图像分割为目标和背景；而在多级阈值法中，多个阈值被确定，并将图像分割为多个区域.

多阈值选择属于一个优化问题^[4].传统方法采用穷举搜索来获取最佳阈值，计算十分复杂耗时.近年来，由于元启发式技术在解决现实世界中高度非线性和多峰优化问题的突出表现而受到广泛关注，许多研究者提出了一系列应用元启发式技术来获得最优阈值的方法^[5].文献[6]提出了一种基于鲸鱼优化和蛾-火焰优化算法的多级阈值图像分割方法，该方法利用鲸鱼优化和蛾-火焰优化两种自然启发算法来确定多级阈值情况下的最佳阈值，但是该算法的控制参数较多，产生较大的计算复杂度.文献[7]提出了一种基于灰狼优化器的多级阈值处理方法，该算法受到灰狼社交和狩猎行为的启发，利用Kapur熵和Otsu类间方差函数解决多级阈值问题，但是该方法存在收敛精度不够的问题.文献[8]提出了一种基于蛾群算法的多阈值图像分割方法，该元启发式算法通过使用Kapur熵方法来降低最佳阈值的计算复杂度.文献[9]提出了一种基于粒子群优化算法和模糊熵的多级阈值图像分割算法，通过选择香农熵和模糊熵作为优化技术的目标函数，建立了基于粒子群优化算法的多层次阈值分割模型，解决了模型收敛缓慢、计算成本高的问题.上述两种方法有效降低了计算复杂度，提高了收敛速度，但是存在高度依赖于初始控制参数值的问题.文献[10]提出了一种基于改进蜻蜓优化算法的彩色图像分割方法，该方法通过结合蜻蜓算法和差分进化算法，提高了图像阈值技术的准确性和稳定性.

针对大多数优化算法需要大量的控制参数，性能高度依赖于初始控制参数值，传统Kapur熵存在计算效率低的问题，本文提出了一种基于乌鸦搜索优化算法的多级阈值图像分割方法，该方法采用的控制参数较少，从而有效避免了过早收敛的现象.而且，本文采用的Kapur熵比其他熵在测度时获取了更高的平均分数，从而产生了正概率和全局最大熵.

1. 乌鸦搜索算法

乌鸦搜索算法(Crow Search Algorithm，CSA)是基于乌鸦觅食过程而提出的一种智能优化算法^[11]. CSA的工作原理：乌鸦搜索算法由N个个体组成，单个个体在d维环境中的位置可以由矢量表示为x^{i，iteration}={x₁^{i，iteration}，x₂^{i，iteration}，…，x_d^{i，iteration}}，i=1，2，…，N，iteration=1，…，Maxiter，Maxiter表示最大迭代次数.每个个体藏匿食物的位置都由一个记忆值表示，在第itr迭代中，第i只乌鸦在当前获取的最佳隐匿位置可以表示为m^i，itr.此外，每个个体都会记住自己当前的最佳位置.而且个体i在环境中移动，寻找更好的隐藏位置并记住这个位置.如果个体j想要访问其最佳隐藏位置m^j，itr，而其他乌鸦i想要跟随j发现其隐藏位置，这种情况存在两种可能：第一种可能是个体j不知道被跟踪，则乌鸦i发现个体j的食物隐藏位置；第二种可能是是个体j发现乌鸦i在跟踪它，为了保护自己食物不被发现，乌鸦j通过转移位置来欺骗乌鸦i.将这两种情况结合起来，可以得到乌鸦i的新位置.

其中，r_i和r_j取0~1之间的随机数，fl^i，itr表示飞行长度，AP^j，itr表示意识概率.在评估适应度函数之后，使用等式(2)更新每个乌鸦的记忆值.

2. 基于乌鸦搜索算法的多级阈值图像分割

本文提出了一种基于乌鸦搜索优化算法的多级阈值图像分割方法.在此方法中，Kapur熵作为适应度函数，采用乌鸦搜索算法将熵最大化，以达到最佳阈值.多个阈值将图像分为多个类别进行分割，随着阈值数量增加，该方法通过向搜索空间添加更多限制和形式来增加问题的复杂性.

2.1. 基于多级阈值的图像分割

考虑给定图像中存在G级灰度，像素总数为N.令f(i)为第i个强度级的频率，则

第i个强度级的概率由公式(4)给出.

假设有M个阈值，{th₁，th₂，…，th_M}，其中1≤M≤G－1.使用这些阈值，将给定图像划分为M+1个片段，并表示为Class(0)={0，1，…，th₁－1}，Class(1)={th₁，th₁+1，…，th₂－1}和Class(M+1)={th_M－1，th_M－1+1，…，th_M}.多级阈值是一个优化问题，通过最大化目标函数来进行优化.

在多级阈值化中，多个阈值在候选解决方案中被编码.假设种群数量为N，并且种群内的每个个体都由d个阈值组成.因此，解向量SV可以表示为

其中，C_i=[th₁，th₂，…，th_d].

2.2. 基于乌鸦搜索算法的Kapur熵

从物理学的角度，熵代表系统中的无序；在信息论中，熵是数据同质性和数据中是否存在冗余的量度^[12].本文使用的Kapur熵^[13]是一种双层阈值方法，Kapur熵标准进一步扩展可以解决多级阈值问题，并广泛用于多级图像分割中.多阈值问题的Kapur熵方法可以描述为：目标函数可以表示M+1个图像片段的组合熵，即计算每个图像片段的熵并将其求和.

其中，E_i表示第i个图像片段的熵.公式(6)给出了Kapur熵方法的计算公式.

为了获得多级阈值，目标函数最大化的优化问题可以通过公式(7)求得，本文采用乌鸦搜索算法作为优化算法.乌鸦搜索算法只有两个控制参数，飞行长度fl和意识概率AP.意识概率AP用于搜索空间的多样化，飞行长度fl不会在很大程度上影响解决方案，但是正确选择意识概率会极大地影响最终结果.乌鸦搜索算法在探索和开发之间具有更好的平衡，该算法收敛更快，且不会产生过早收敛导致局部最优现象的发生，从而保证了乌鸦搜索算法比其他元启发式优化技术更具优势.

4. 结语

本文提出一种基于乌鸦搜索优化算法的多级阈值图像分割方法，解决了传统Kapur熵在多阈值图像分割算法中存在计算复杂度高，计算时间过长的问题.该方法将多级阈值处理视为优化过程，并使用CSA的搜索功能和Kapur熵作为目标函数，其主要优点是使用较少的参数，从而避免了因过早收敛而发生局部最优的情况.通过基准图像集测试，本文算法在多个评价指标上的性能明显优于其他分割算法，而且具有极高的计算效率和适用度.

参考文献 (13)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

方法	阈值等级
方法	2	4	8	16	32
MFO^[6]	1.56	5.67	21.24	205.58	2 399.38
GWO^[7]	1.48	5.62	20.89	202.50	2 396.10
MSA^[8]	2.00	5.98	21.64	210.60	2 408.09
IDA^[10]	1.96	6.02	22.45	212.67	2 435.55
本文算法	1.35	5.38	20.32	200.53	2 348.44

[1]	吴禄慎, 程伟, 王晓辉.应用模拟退火粒子群算法优化二维熵图像分割[J].计算机工程与设计, 2019, 40(9): 2544-2551.
[2]	de Oliveira P V, Yamanaka K. Image Segmentation Using Multilevel Thresholding and Genetic Algorithm: An Approach[C]//2018 2^nd International Conference on Data Science and Business Analytics (ICDSBA). Changsha: IEEE, 2018.
[3]	RAHKAR FARSHI T, DEMIRCI R, FEIZI-DERAKHSHI M R. Image Clustering with Optimization Algorithms and Color Space[J]. Entropy, 2018, 20(4): 296-313. doi: 10.3390/e20040296
[4]	LI J F, TANG W Y, WANG J, et al. Multilevel Thresholding Selection Based on Variational Mode Decomposition for Image Segmentation[J]. Signal Processing, 2018, 147: 80-91. doi: 10.1016/j.sigpro.2018.01.022
[5]	Xuejun WU. Review of Theory and Methods of Image Segmentation[J]. Agricultural Biotechnology, 2018, 7(4): 136-141.
[6]	AZIZ M A E, EWEES A A, HASSANIEN A E. Whale Optimization Algorithm and Moth-Flame Optimization for Multilevel Thresholding Image Segmentation[J]. Expert Systems with Applications, 2017, 83: 242-256. doi: 10.1016/j.eswa.2017.04.023
[7]	KHAIRUZZAMAN A K M, CHAUDHURY S. Multilevel Thresholding Using Grey Wolf Optimizer for Image Segmentation[J]. Expert Systems with Applications, 2017, 86: 64-76. doi: 10.1016/j.eswa.2017.04.029
[8]	ZHOU Y Q, YANG X, LING Y, et al. Meta-heuristic Moth Swarm Algorithm for Multilevel Thresholding Image Segmentation[J]. Multimedia Tools and Applications, 2018, 77(18): 23699-23727. doi: 10.1007/s11042-018-5637-x
[9]	李红蕾, 王翊. Bregman全散度水平集图像分割方法[J].计算机应用研究, 2020, 37(6): 1916-1920.
[10]	XU L, JIA H M, LANG C B, et al. A Novel Method for Multilevel Color Image Segmentation Based on Dragonfly Algorithm and Differential Evolution[J]. IEEE Access, 2019, 7: 19502-19538. doi: 10.1109/ACCESS.2019.2896673
[11]	孔显, 马晓珂.基于非归一化直方图的GrabCut图像分割算法改进[J].计算机应用研究, 2020, 37(5): 1549-1552.
[12]	雷翔霄, 欧阳红林, 肖乐意, 等.基于等价三维熵与鲸鱼优化算法的图像分割研究[J].计算机工程, 2019, 45(4): 217-222.
[13]	RAJA N S M, RAJINIKANTH V, FERNANDES S L, et al. Segmentation of Breast Thermal Images Using Kapur's Entropy and Hidden Markov Random Field[J]. Journal of Medical Imaging and Health Informatics, 2017, 7(8): 1825-1829. doi: 10.1166/jmihi.2017.2267

留言板