基于改进麻雀搜索算法的多阈值图像分割

2021-01-26慕晓冬

系统工程与电子技术 2021年2期

吕鑫, 慕晓冬, 张钧

(1. 火箭军工程大学作战保障学院, 陕西西安 710025; 2. 北京遥感设备研究所, 北京 100854)

0 引言

图像分割是图像处理的关键环节,其目的是从图像中提取出感兴趣的目标区域[1]。阈值分割作为一种简单有效的分割方法,被广泛应用于各领域的图像处理,主要包括最大类间方差法和Kapur熵等分割方法。常见阈值分割方法采取穷尽搜索进行图像多阈值分割,计算时间长,局限性大,如何快速准确地找到最佳阈值成为阈值分割的关键。

随着群智能优化算法的兴起和发展,由于其具有全局寻优和收敛速度快等特点,被广泛应用于图像分割,起到了减少分割时间和提高分割精度的作用。Akay[2]将粒子群优化(particle swarm optimization, PSO)算法和人工蜂群(artificial bee colony, ABC)算法应用到多阈值图像分割,选择Kapur熵和Otsu作为适应度函数来搜索阈值以获取最佳分割效果。Yao[3]将优良点集应用到灰狼优化(grey wolf optimization, GWO)算法,并将最大熵作为目标函数进行全局优化,具有良好的全局收敛性和鲁棒性,有效避免了陷入局部最优,同时应用到多阈值图像分割,分割阈值更加稳定,分割质量更高。Wang[4]将莱维飞行引入樽海鞘群算法(salp swarm algorithm, SSA1),分别使用Kapur熵、Otsu和Renyi熵作为适应度函数进行全局寻优,表现出良好的搜索能力和开拓能力,多阈值图像分割更优,并定量分析了Kapur熵分割结果优于其他两种方法。其他将群智能优化算法[5～9]应用到多阈值图像分割也均表现出良好的分割性能。

薛建凯和沈波于2020年开发的麻雀搜索算法[10](sparrow search algorithm, SSA)是一种模拟麻雀觅食行为和反捕食行为的新型群智能优化算法。SSA能够取得比PSO、GWO等算法更好的寻优性能,但是其运行时间较长,且仍存在陷入局部最优的缺陷。所以,结合鸟群算法[11](bird swarm algorithm, BSA)的思想设计改进麻雀搜索算法(improved sparrow search algorithm, ISSA),以此来缩短算法运行时间,并提高其搜索能力和开拓能力,取得更好的全局寻优性能。同时,将Otsu和Kapur熵作为ISSA的目标函数进行阈值寻优,并对比Otsu和Kapur熵两种方法的优劣性。最后,将ISSA与现有的分割方法展开多组对比实验,验证ISSA在分割性能上的提升。实验结果表明,ISSA能更稳定、准确、高效地找到最佳阈值,综合性能更优。

1 ISSA

1.1 SSA

在自然界中,麻雀作为群居鸟类,聪明且记忆力强,种群内部存在明显的分工,一部分麻雀负责寻找食物并为整个种群提供觅食区域和方向,剩余麻雀则利用前者来获取食物。同时,当有麻雀意识到危险时,会及时发出警报信号,整个种群会立刻做出反捕食行为。

在SSA中,每只麻雀位置对应一个解。麻雀在觅食时存在3种行为:① 作为发现者寻找食物;② 作为加入者跟随发现者觅食;③ 作为侦察者决定种群是否放弃食物。其中,发现者和加入者之间可互相转换,但比例保持恒定,发现者一般占到种群的10%～20%。发现者作为觅食的引导者,搜索范围广,通过记忆不断更新自身位置,以获得食物来源。而加入者则跟随发现者不断进行觅食,以获取更高的适应度。但由于随时存在捕食者的威胁,种群会随机选取10%～20%的麻雀作为侦察者进行监视,以便在捕食者出现时及时提醒整个种群做出反捕食行为。

发现者位置更新如下：

(1)

式中,MaxCycle表示算法的最大迭代次数;α为(0,1]之间的均匀随机数;Q是服从标准正态分布的随机数;L表示1×d的矩阵,且元素均为1;R2∈[0,1]和ST∈[0.5,1]分别表示预警值和安全值。

加入者位置更新如下：

(2)

侦察者位置更新如下:

(3)

1.2 SSA的改进

BSA是Meng等人于2015年受鸟群飞行、觅食和警戒行为启发而提出的群智能算法,具有良好的稳定性。飞行行为中发现者和加入者的位置更新公式分别是

(4)

(5)

式中,randn(0,1)表示均值为0,标准差为1的高斯随机分布;FL∈[0,2]代表加入者跟随生产者寻找食物的概率;k属于发现者。

由于SSA中发现者在R2

故将SSA中发现者位置更新公式改进为

(6)

同时,SSA中的加入者在全维度向最佳位置靠近时,虽然能够达到快速收敛的效果,但是减少了种群多样性,算法容易陷入局部最优。而BSA中的加入者是以一定概率向发现者靠拢,既保证了全局收敛,又不失种群多样性,有效跳出局部最优。故改进SSA中加入者的位置更新公式如下：

(7)

ISSA的简单流程为

步骤 1初始化；

步骤 2计算麻雀种群个体适应度;

步骤 3得到当前最佳位置,最差位置和最差适应度;

步骤 4根据式(6)、式(7)和式(3)依次更新发现者、加入者和侦察者的位置信息;

步骤 6若算法达到最大迭代次数,则算法寻优结束,否则转到步骤3。

图1 发现者搜索策略Fig.1 Search strategy of producers

2 基于ISSA的多阈值图像分割

2.1 多阈值分割

多阈值分割就是按照某一准则在待分隔图像f(x,y)中寻找一组阈值[t1,t2,…,tn](n>0),并将其分割成n+1部分的过程。Otsu和Kapur熵是两种常见的多阈值分割准则。

Otsu是由日本学者大津于1979年提出的一种全局自适应阈值选取方法[12]。对于一幅灰度级在[0,1,…,L-1]的给定图像(L常取256),灰度级为i的像素个数为ni,像素总数为N,则图像中每一部分的灰度均值表示为

(8)

(9)

⋮

(10)

则此时图像的类间方差表示为

σ=ω0(u0-uT)2+ω1(u1-uT)2+…+ωn(un-uT)2

(11)

当阈值向量满足式(12)时,即为最佳阈值,可表示为

(12)

基于Kapur熵的阈值化方法就是利用熵量化的值衡量图像中包含的信息,使图像分割后目标区域熵和背景区域熵的和最大化[13]。则基于Kapur熵准则的分割图像各部分熵值如下所示:

水法确立了流域与区域相结合的水资源管理体制，太湖流域管理局把建立流域与区域联合执法机制作为贯彻水法的重要举措，通过主动与地方开展联合巡查、专项联合执法检查活动以及重大水事违法案件联合查处与监督等工作，总结好的经验与做法，于2005年印发《太湖流域“一湖两河”水行政执法联合巡查制度》，该制度包含了联合巡查、定期磋商、案件处理、案件督办、培训与交流等流域与区域合作机制，并在《太湖流域管理条例》立法中得到进一步拓展与细化。

(13)

(14)

⋮

(15)

此时,图像灰度值的Kapur熵定义为

f([t1,t2,…,tn])=H0+H1+…+Hn

(16)

分割图像的最佳阈值向量满足下式：

(17)

2.2 基于ISSA的多阈值分割算法

假设对图像进行n维阈值分割,则解向量为T=[t1,t2,…,tn],其取值为正整数且满足0

步骤 1读取待分割图像f(灰度图像)。

步骤 2求读入图像的灰度直方图。

步骤 3ISSA参数初始化。包括种群规模NP,算法的最大迭代次数MaxCycle,发现者个数pNum,侦察者个数sNum,欲分割阈值数n等。

步骤 4麻雀种群初始化。麻雀个体位置表示图像分割的阈值向量,其为从小到大顺序排列的像素灰度值组合,每个向量的分量取值范围为[0,255],且为整数。

步骤 5根据式(11)或式(16)计算种群中所有麻雀的适应度值,得到当前最佳适应度的麻雀个体。

步骤 6执行ISSA算法。

步骤 7若算法达到预设最大迭代次数MaxCycle或最佳适应度持续保持在迭代总数的10%,则算法寻优结束,并返回最佳适应度的麻雀位置信息,即为最佳阈值分割向量;否则跳转至步骤5。

步骤 8利用得到的最佳阈值分割向量对灰度图像进行分割,输出分割后的图像g。

图2 所提分割算法流程图Fig.2 Flow chart of the proposed segmentation algorithm

3 实验结果与分析

为验证ISSA的算法性能,设计了基准函数对比实验,基于ISSA的图像多阈值分割实验和图像多阈值分割对比实验。基准函数对比实验旨在验证改进算法的通用性能提升。基于ISSA的图像多阈值分割实验旨在检验ISSA应用于图像多阈值分割的可行性,同时对比了基于Otsu和Kapur熵多阈值分割方法的优劣。图像多阈值分割对比实验旨在验证基于ISSA的图像多阈值分割方案对比现有多阈值分割方法的优越性。文中实验均基于Windows7 64位操作系统,2.50 GHz CPU和4 GB内存的PC机,Matlab R2015a开发软件。

3.1 基准函数对比实验

为验证ISSA的搜索能力和开发能力,本文采用4种不同类型的测试函数,如表1所示。

表1 基准函数

函数F1～F4具有不同的特征[14]:F1单峰变量可分离(unimodal and variables separable, UVS)、F2单峰变量不可分离(unimodal and variables non-separable, UVN)、F3多峰变量可分离(multimodal and variables separable, MVS)、F4多峰变量不可分离(multimodal and variables non-separable, MVN)。实验中算法的通用参数设置为:种群规模NP=30,最大迭代次数MaxCycle=100,发现者个数pNum和侦察者个数sNum均取NP的20%。

SSA和ISSA在4个基准函数上的收敛曲线如图3所示,从图中可以看出ISSA在收敛速度和收敛精度上均优于SSA。

图3 基准函数收敛图Fig.3 Convergence graphs of the benchmark function

由于ISSA搜索策略具有随机性,为定量分析其性能,分别在4个基准函数上独立运行30次,得到寻优结果的最劣值、最优值、平均值、标准差和平均运行时间,并与SSA算法运行结果进行比较,如表2所示。从寻优结果可以得出,ISSA较SSA在寻优精度上整体提升了44.20%,稳定性整体提升了47.37%,同时平均运行时间整体减少了7.90%,表现出优良的寻优性能。

3.2 基于ISSA的图像多阈值分割实验

为检验基于ISSA的多阈值图像分割算法的可行性,实验选取阈值分割中经典的Cameraman图、Lena图、Butterfly图和Baboon图作为测试图像,并基于Otsu和Kapur熵两种分割准则依次进行双阈值、三阈值、四阈值和五阈值图像分割。

表2 算法性能比较

算法实验参数设置为:种群规模NP=30,最大迭代次数MaxCycle=500,个体上下界取[0,255],维数dim依次取2、3、4和5,发现者个数pNum和侦察者个数sNum均取NP的20%。

为了客观精确地评价分割算法的稳定性和多阈值图像分割效果,对每幅图像独立运行30次,并采用标准差STD和峰值信噪比PSNR作为评价标准[15],分别如下所示：

(18)

(19)

式中,NI是独立运行次数(NI=30);bfi是第i次运行的最佳适应度;μ是适应度bf的平均值；MSE表示大小为m×n的原始图像f和分割后图像g的均方误差，可表示为

(20)

分别将类间方差和Kapur熵作为ISSA的目标函数,测试阈值个数n取2、3、4和5时实验结果,记录最佳分割阈

值、PSNR和STD值,如表3和表4所示。由表3和表4的结果可以看出,除却Cameraman图四阈值分割结果,其余分割结果中PSNR值和STD值均与阈值个数成正比。同时Otsu方法得到的PSNR值普遍高于Kapur方法,但Kapur方法的稳定性普遍优于Otsu方法。

表3 基于Otsu方法的分割结果

表4 基于Kapur方法的分割结果

为直观了解基于ISSA的多阈值图像分割结果,图4和图5分别显示了基于Otsu多阈值分割准则和Kapur熵多阈值分割准则的图像分割结果。从分割结果可以看出,ISSA在Otsu和Kapur两种方法下进行多阈值图像分割,随着阈值个数的增加,图像分割结果中细节更清晰,信息更完整,分割质量更高。

比较ISSA基于Otsu方法和Kapur方法的分割结果,对Otsu和Kapur独立运行30次得到的PSNR值在显著性

水平为5%的情况下做Wilcoxon符号秩检验。建立假设:

H0:两种方法的PSNR值之间没有差异。

H1:两种方法的PSNR值之间存在显著差异。

秩和检验结果如表5所示,从检验结果可以看出,P值均小于0.05,则拒绝H0,接受H1,两种方法的PSNR值之间存在显著差异,同时Otsu方法在图像分割中表现更好,能够获得更高的PSNR值,且不具偶然性。

表5 Wilcoxon符号秩检验

图4 基于Otsu方法的多阈值分割效果图Fig.4 Multi-threshold segmentation effect graphs based on Otsu method

图5 基于Kapur方法的多阈值分割效果图Fig.5 Multi-threshold segmentation effect graphs based on Kapur method

3.3 图像多阈值分割对比实验

设计本文算法与GWO、SSA1和ABC的对比实验,验证本文算法在图像多阈值分割上的性能。为保证实验的公平性,同时保证各算法优化效果最佳,且尽量达到稳定收敛,对4种算法的通用参数设置同第3.2节。同时,ABC中的交叉系数cr=0.6,邻域搜索未发生改变的最大次数Limit=50,蜜源数目foodNumber=15。

4种算法分别基于Otsu和Kapur两种方法进行图像多阈值分割,结果如表6和表7所示。

基于Otsu的对比结果可以看出,ISSA相较GWO、SSA1和ABC算法,100%能够得到更大的类间方差,且稳定性表现最优。同时,79.17% ISSA能够取得更高的PSNR值。基于Kapur的对比结果可以看出,ISSA相较其他算法,在稳定收敛的基础上,95.83%能够取得更大的熵值,79.17% PSNR值最优。综上所述,ISSA应用在多阈值图像分割上,分割精度更高,分割质量更好,算法稳定性更强,综合分割性能最优。

为了更好地反映4种算法的收敛情况,绘制出4幅图像分割过程的收敛曲线,由于篇幅原因,仅给出4幅图像基于Otsu的五阈值分割收敛曲线,如图6所示。