基于莱维飞行麻雀搜索优化的Otsu多阈值图像分割

马卫 朱娴 李微微

摘  要： 群智能算法优化多阈值图像分割策略，易陷入局部最优，搜索精度不高。将莱维飞行扰动策略融入麻雀种群觅食的搜索优化过程，以增加图像分割空间搜索的多样性，从而提高分割精度，避免搜索过程陷入局部最优；同时嵌入Sin混沌搜索机制，改进种群初始化策略，加强搜索性能。最终实现多阈值图像分割的应用性能提升，在保持算法全局寻优能力的基础上大幅度提高收敛速度和求解精度。对经典的图像多阈值分割的实验结果表明，本文方法相比于传统的智能优化策略，在寻优率和分割精度方面提升显著，收敛能力强。

关键词： 多阈值图像分割； 麻雀搜索算法； 莱维飞行扰动； 群智能优化

中图分类号：TP391          文献标识码：A     文章编号：1006-8228（2023）04-77-08

Abstract： The swarm intelligence optimization multi threshold image segmentation strategy is easy to fall into local optimization and the search accuracy is not high. Levy flight disturbance strategy is integrated into the search optimization process of sparrow population foraging to increase the diversity of image segmentation spatial search， so as to improve the segmentation accuracy and avoid falling into local optimization in the search process. At the same time， the Sin chaotic search mechanism is embedded to improve the population initialization strategy and strengthen the search performance. Finally， the application performance of multi threshold image segmentation is improved， and the convergence speed and solution accuracy are greatly improved on the basis of maintaining the global optimization ability of the algorithm. The experimental results of classical multi threshold image segmentation show that compared with the traditional intelligent optimization strategy， this method significantly improves the optimization rate and segmentation accuracy， and has strong convergence ability.

Key words： multi threshold image segmentation; sparrow search algorithm （SSA）; Levy flights disturbance; swarm intelligence optimization

0 引言

圖像分割作为图像处理领域的一类经典难题，吸引了国内外众多学者的广泛关注与深入研究。图像分割方法中的阈值分割策略是一类性能优异、应用广泛的分割方法。阈值分割的核心是通过一定的准则寻找最优的阈值以实现快速、准确分割的目标。阈值分割主要有最大类间方差法，一些学者通过引入群智能优化策略以改进阈值分割从而取得了较好地实验效果。其中，分水岭分割策略引入蚁群算法促进聚类合并解决噪声敏感使得分割过剩的问题，但算法运行时间过长。吕鑫[1，2]等采用麻雀搜索算法与Otsu结合进行图像分割，评价准则为类间方差，从而获得最优的阈值进行图像分割。还有学者采用鸟群算法和麻雀搜索策略的有机融合，改进了搜索机制，利用Kapur熵和类间方差进行阈值求解，以实现图像的多阈值分割。其他一些新提出的群智能优化策略应用于多阈值图像分割也发挥出了较好地分割优势[3-10]。

麻雀搜索算法（Sparrow Search Algorithm，SSA）最早于2020年由学者薛建凯提出，是采用麻雀觅食与反捕食行为进行仿生模拟的一类群智能优化算法。该策略相比于粒子群优化算法（Particle Swarm Optimization，PSO）、灰狼优化算法（Grey Wolf Optimizer，GWO）表现出更优异的搜索性能[11]。但其在搜索过程中仍存在易陷入局部最优，寻优时间过长的不足。所以，本文受布谷鸟搜索（Cuckoo Search，CS）策略[12]的启发，将莱维飞行扰动策略融入麻雀种群觅食搜索的过程中，提出一种改进的基于莱维飞行扰动策略的麻雀搜索算法（Levy Sparrow Search Algorithm，LSSA），以增加图像分割空间搜索的多样性，提高分割精度，避免搜索过程陷入局部最优；同时嵌入Sin混沌搜索机制，改进种群初始化策略，加强搜索性能。最终实现多阈值图像分割的应用性能提升，在保持算法全局寻优能力的基础上大幅度提高收敛速度和求解精度。

1 最大类间方差法（Otsu）

作为一种非参数类型的图像分割最大类间方差策略最早是1979年由日本学者Otsu提出，该方法利用求解中间方差的最大值从而实现图像的有效分割。

1.1 图像的单阈值分割

Otsu单阈值图像分割原理为：假设待分割的图像表示为I（x，y），图像的大小为H*W，最大灰度级用L表示，取值为256，通常一幅图像的灰度级范围为[0，1，…，L-1]，用Ni表示灰度级为i的像素个数，像素总数N=N1+N2+…+NL-1，灰度级i在图像中出现的概率表示为：

通常单阈值图像分割是设置最优阈值t将目标图像分割为两类，其类别像素的概率表示为式⑵，目标图像总均值表示为式⑶：

1.2 图像的多阈值分割

图像的多阈值分割是对单阈值类别的拓展，若目标图像拟分割为K层，这图像多阈值分割的类间方差[ft]可表示为：

最终，可以得到式⒀，即目标分割图像多阈值的类间方差表示为：

2 麻雀搜索算法

麻雀搜索算法采用麻雀觅食与反捕食行为进行仿生模拟的一类群智能优化算法，其中利用三类麻雀觅食行为：发现者、跟随者和警戒者进行目标寻找以迭代优化搜索。

对于麻雀数量为n的种群位置，有：

评价麻雀种群觅食位置优劣的适应度函数为：

其中，适应度值采用[f（?）]表示。由发现者选择适应度值高的搜索位置，前往觅食，同时为新的发现者提供食物源的方向。发现者的位置变化如下：

其中，当前迭代数表示为t，[Xt+1i，j]表示种群中第i只麻雀在第j维度上的位置，i=1，2，…，n，j=1，2，…，d，d是搜索空间的维数，[itermax]为常数，表示最大迭代次数，[α∈（0，1]]表示随机数。Q表示服从正态分布的一个随机数。预警参数[R2]取值范围为[R2∈[0，1]]，安全参数[ST]的取值范围[ST∈[0.5，1]]，L是一个[1×d]的矩阵向量，所有元素值为1。当满足条件[R2

加入者的位置更新公式如下：

其中，[Xp]为发现者获得的最优位置，[Xworst]表示当前迭代全局的最差位置，A为一个[1×d]的矩阵向量，向量中的元素随机选择1或-1进行赋值，并且满足条件[A+=AT（AAT）-1]，当满足条件[i>n/2]时，说明第i个适应度值较低的加入者获取食物失败，此时转移觅食搜索。

警戒者约占种群规模的10%-20%，常常表示能敏锐发觉有危险的麻雀。警戒者的初始位置表示为：

其中，[Xbest]为当前迭代中全局最优位置，常数[ε]为一个最小值，步长控制参数[β]服从正态分布，随机值K取值范围在-1～1之间，[fw]为全局最差适应度值、[fg]为全局最优适应度值，[fi]为当前麻雀个体的适应度值。

3 改进麻雀搜索算法

3.1 莱维飞行搜索机制

随着仿生学的不断发展，模拟布谷鸟巢寄生行为的布谷鸟搜索算法应运而生。生物学研究表明，布谷鸟利用孵育寄生的方式繁衍后代，表现为产卵寄生于其他宿主鸟巢，由其他宿主鸟帮助其孵化和育雏。其选巢位置的变化正好体现出莱维飞行的搜索特性。

布谷鸟搜索算法是将布谷鸟寻窝产卵的搜索机制形成理论，基于莱维飞行搜索机制形成搜索算法。算法约定三条规则：①每只布谷鸟每次只产卵一个，并随机选择寄生巢来孵化；②在随机选择的一组寄生巢中，保留最好的寄生巢到下一代；③寄生巢的数量固定，一个寄生巢的宿主鸟按一定的概率发现外来寄生卵。在该三条规则的约束下，宿主鸟可以将产卵抛出，或放弃该鸟巢以新建巢。

布谷鸟寻窝搜索的路径和位置更新公式如式⒆所示，通過莱维飞行生成新的搜索位置：

其中，[xti]表示第i个鸟窝在第t代的鸟窝位置，[δ>0]为步长大小，通常设置[δ=1]。式（19）表现为一个随机行走过程，该随机行走过程即为一个马尔可夫链，位置更新结果受于当前位置在式（19）的第一项和转移概率第二项的影响。[]表示点对点乘法，[Levy（λ）]是一个随机搜索路径，其随机步长表现为一个[Levy]分布。

3.2 莱维飞行扰动策略

根据一些生物学家对鸟类和昆虫类的觅食轨迹的研究发现，一些生物飞行轨迹中直线部分出现频率与Levy分布基本相似，表现为莱维飞行的特点。莱维飞行搜索策略对于种群个体独立、求解空间位置随机且稀疏分布时，搜索效果较好。莱维飞行是随机行走（random walk）的一类，行走步长符合一个重尾的稳定分布，常常可以看到较短距离的搜索与相对较长距离的行走交错。在仿生群智能优化算法中采用莱维飞行搜索机制，可以有效地增加搜索空间的探寻范围、提高群体搜索的多样性，往往使搜索算法跳出局部最优变为可能。

在布谷鸟搜索算法中，采用莱维飞行产生随机步长，这种步长变化多样，在其搜索过程中，步长越大，越容易搜索到全局最优解，搜索精度则相应减弱，易产生不稳定的震荡现状；如果步长较小，搜索速度下降，搜索精度会显著增强。因此，采用莱维飞行产生步长具有遍历性和随机性，缺点是自适应能力不够，而SSA算法恰好弥补了这一不足，利用发现者-跟随者-警戒者的模型机制，协调好全局寻优能力和局部求解精度之间的矛盾，从而加强麻雀搜索算法的全局搜索能力和局部求解精度。

构建莱维飞行步长扰动策略受CS算法启发，对于扰动步长的定义，其计算公式如下：

3.3 改进的麻雀搜索搜索策略

3.3.1 初始化混沌搜索机制

本文对传统的麻雀搜索算法进行了初始化搜索策略的改进。利用Sin混沌模型以初始化种群分布，以此来增加种群搜索的多样性。

3.3.2 LSSA算法步骤

LSSA算法的步骤如下：

Step1 参数设置：设置麻雀种群规模数n，初始化麻雀发现者数量PD，警戒者数量SD，设置寻食步数计数器[t=0]，最大寻食迭代次数为MCN。

Step2 初始化种群：在搜索区域内按式（26）混沌搜索机制产生n个向量[Xi（i=1，2，…，n）]，计算适应度值，记录适应度值的最佳和最差个体位置。

Step3 发现者搜索：根据式⒃进行发现者位置搜索更新。

Step4 加入者搜索：根据式⒄进行加入者位置搜索更新。

Step5 警戒者搜索：根据式⒅进行警戒者位置搜索更新。

Step6 适应度值计算位置更新：比较当前最优值[ymin]与min全局最优值，若有[ymin

Step7 莱维飞行机制：随机生成一个数rnd，根据概率[pi]，如果[rnd

Step8 更新迭代次数[t=t+1]，若满足当前迭代次数[t>MCN]，则搜索停止，输出全局最优位置[Xg]和搜索结果[f（Xg）]，否则转Step3继续执行。

4 实验结果与分析

4.1 实验设计与参数设置

为了测试本文所提改进策略的性能，本文选用了8副经典图像进行多阈值图像分割测试，如图1所示，其中4副为常用的具有代表性的测试图像，4副为伯克利经典彩色图像。为了验证本文提出的算法的有效性，选择了近年來新提出的布谷鸟搜索算法（Cuckoo Search，CS），蝗虫优化算法（Grasshopper Optimization Algorithm，GOA）[13]、鲸鱼优化算法（Whale Optimization Algorithm，WOA）[14]、蜻蜓算法（Dragonfly Algorithm，DA）[15]、灰狼优化算法（Grey Wolf Optimizer，GWO）[16]和麻雀搜索算法（Sparrow Search Algorithm，SSA）与本文改进的麻雀搜索算法 （Levy Sparrow Search Algorithm，LSSA）进行实验测试。实验设备的硬件条件为CPUIntel（R） Core（TM）i5-8400 2.80GHz，8G内存，实验仿真软件采用Matlab R2016a。实验评价的方式采用峰值信噪比和结构相似性进行量化比较，这两种评价方式的阐述如下。

⑴ 峰值信噪比

PSNR（Peak Signal to Noise Ratio）为峰值信噪比，是一种评价图像的客观标准，常用于最大值信号和背景噪音之间的一类失真衡量指标。PSNR值越高表明图像失真越小，多阈值分割效果好。PSNR衡量的计算公式为：

其中，RMSE（Root Mean Square Error）为原图像[Ii，j]与分割后图像[I（i，j）]间的均方根误差。[M×N]表示图像的尺寸大小。

⑵ 结构相似性

SSIM（Structural Similarity Index）表示结构相似性的一类评价两幅图像相似程度的指标。SSIM使用的两副图像中，一副为无失真的原始图像，另一副为分割后的图像，取值越高说明结构相似性越好。SSIM结构相似性衡量的计算公式为：

其中，[μx]和[μy]表示图像[Ii，j]和[I（i，j）]的均值，[δ2x]和[δ2y]为图像[Ii，j]和[I（i，j）]的方差，[c1=（k1L）2]和[c2=（k2L）2]为保持稳定性的常数，L为像素值的动态范围，[k1]，[k2]取值分别为0.01和0.03。

为了实验比较的公平性，所有算法最大迭代次数为200，种群规模为30，各个算法的参数设置见表1。其中SSA算法中ST表示预警值，PD为发现者的比例参数，SD为意识到有危险麻雀的比重。CS算法中Pa为发现外来卵的概率；DA算法中s为分离权重、a为对齐权重、c为凝聚权重、f为猎物权重因子、天敌权重因子e根据迭代次数动态调整。WOA和GWO算法中参数a的值从2到0线性下降，A和C为表示系数。

4.2 图像多阈值分割实验结果

为了验证算法LSSA的性能，实验测试了改进策略在图像多阈值分割的可行性和有效性，利用群智能优化策略进行最优阈值的迭代搜索，获取PSNR、SSIM、最优适应度值，分割时间，分割阈值等实验测试评价结果并与其他智能优化算法进行了比较，结果示于表2～表3。图2中以Cameraman图像为例给出了五个阈值的基于Otsu的LSSA算法多阈值分割效果图，图3给出了基于Otsu的智能优化算法Baboon六阈值分割效果图，图4为基于Otsu的智能优化算法Horses三阈值分割效果图，图2～图4体现了较好的分割效果。

表2中给出了基于Otsu的CS、GOA、WOA、DA、GWO、SSA和LSSA算法的多阈值图像分割的适应度值，其中阈值范围从2至6分别实验，表格中黑色加粗的数值为最优实验结果，表3中测试了基于各群智能优化算法应用在多阈值图像分割领域的PSNR和SSIM评价值，本文所提LSSA算法表现出较好的实验效果。

4.3 实验结果分析

基于Otsu的实验对比结果表明，LSSA相比较于CS、GOA、WOA、DA、GWO和SSA算法，能够搜索到较好地适应度值，表现出更加稳定的寻优性能，PSNR和SSIM值更优。所以，从表2～表3可以看出，LSSA应用在多阈值图像分割领域，分割的性能更优，搜索精度更高，算法表现出较好地稳定性能，鲁棒性强。从时间上看，本文所提算法由于增加了莱维飞行搜索机制，时间上略有提升，但LSSA算法取得了更优异的搜索性能，有一定的应用价值。

综上所述，本文所提LSSA算法在多阈值图像分割上的应用，搜索精度好，分割的质量高，有较好地寻优搜索性能，在多阈值分割方面表现出较好地稳定性。

5 结束语

本文针对多阈值图像群智能优化分割易陷入局部最优，求解精度不高等问题，采用全局寻优能力强的莱维飞行机制融入麻雀搜索算法，同时结合改进种群Sin混沌初始化的搜索机制，形成基于莱维飞行扰动策略的麻雀搜索算法，以增加图像分割空间搜索的多样性，从而提高分割精度，避免搜索过程陷入局部最优。最终实现多阈值图像分割的应用性能提升，在保持算法全局寻优能力的基础上大幅度提高收敛的速度和求解精度。对经典的图像多阈值分割的实验结果表明，本文所提的LSSA方法相比于传统的智能优化策略，在寻优率和分割精度方面提升显著，收敛能力强，有一定的应用价值。

参考文献（References）：

[1] 吕鑫，慕晓冬，张钧.基于改进麻雀搜索算法的多阈值图像分割[J].系统工程与电子技术，2021，43（2）：318-327

[2] 吕鑫，慕晓冬，张钧，等.混沌麻雀搜索优化算法[J].北京航空航天大学学报，2021，47（8）：1712-1720

[3] YueX， ZhangH. Modified hybrid bat algorithm with genetic crossover operation and smart inertia weight for multilevel image segmentation[J].Applied Soft Computing，2020，90（5）：10615

[4] 程玉柱，李赵昡，余伟.基于布谷鸟搜索的路面裂缝图像检测算法[J].传感器与微系统，2019，38（8）：136-138，142

[5] 刘鑫晶，刘彦隆，徐鑫鑫.细胞膜机制萤火虫算法优化多阈值Otsu图像分割[J].小型微型计算机系统，2020，41（2）：410-415

[6] Santhos K A， Kumar A， Bajaj V， et al. McCulloch' salgorithm inspired cuckoo search optimizer based mammographic image segmentation[J].Multimedia Tools and Applications，2020，79（7）

[7] 黄毅英，黄河清.基于自适应布谷鸟搜索算法的Tsallis熵阈值图像分割[J].西南师范大学学报（自然科学版），2020，45（5）：127-133

[8] Zhi H， Liu S. Gray image segmentation based on fuzzy c-means and artificial bee colony optimization[J]. Journal of Intelligent and Fuzzy Systems，2020，38（12）：1-9

[9] Liu H， Sun Y， Sun N， et al. Just noticeable difference color space con-sistency spectral clustering based on firefly algorithm for image segmentation[J]. Evolutionary Intelligence，2020（12）：1-10

[10] 陈瑶，陈思.动态权重的蝙蝠算法在图像分割中的应用研究[J].计算机工程与应用，2020，56（14）：207-215

[11] Xue J K， Shen B. A novel swarm intelligence optimization approach：sparrow search algorithm[J].Systems Science &Control Engineering An Open Access Journal，2020，8（1）：22-34

[12] YangXS， DebS. Cuckoo search via Levy Flights[C].Proc.of World Congress on Nature&Biologically Inspired Computing （NaBic 2009），2009：210-214

[13] Saremi S， Mirjalili S， Lewis A. Grasshopper Optimization Algorithm： Theory and application[J].Advances in Engineering Software，2017，105（MAR.）：30-47

[14] Mirjalili S， Lewis A. The Whale Optimization Algorithm[J].Advances in Engineering Software，2016，95：51-67

[15] Mirjalili S. Dragonfly algorithm： a new meta-heuristic optimization technique for solving single-objective， discrete，and multi-objective problems[J].Neural Computing and Applications，2016，27（4）：1053-1073

[16] 张晓凤，王秀英.灰狼优化算法研究综述[J].计算机科学，2019，46（3）：30-38

*基金项目：江苏省高校自然科学基金（No.17KJB520013）； 江苏省高校哲学社会科学研究项目（No.2020SJA0794，No.2021SJA0782）； 江苏省高校“青蓝工程”学术带头人项目； 国家文化和旅游部文化艺术职业教育和旅游职业教育提质培优行动计划“双师型”师资培養扶持项目（No.2021TZPYSS）； 江苏省社科应用研究精品工程课题（No.22SYB-117）； 江苏省职业改革研究课题（No.ZYB601）；科研创新团队资助项目（No.2021KYTD04）

作者简介：马卫（1983-），男，江苏东台人，博士，副教授，主要研究方向：群智能优化、进化计算和计算机视觉。