基于改进人工蜂群算法的多阈值图像分割

李鑫鑫,刘群锋

(东莞理工学院 计算机学院,广东 东莞 523808)

0 引 言

图像的分割技术在图像处理方面起着至关重要的作用,是图像分析和识别的首要任务[1]。图像分割指的是将目标图像处理成多个具有独特性质的区域并提取出对使用者有用的或者感兴趣的部分的技术[2]。图像的阈值分割是根据图像的局部或者全局信息来确定分割阈值,包括单阈值分割和多阈值分割,在实际的生活中,多阈值的分割应用更为广泛[3]。图像的多阈值选取方法包括最大类间方差[4]、最小交叉熵[5]和Tsallis熵[6]等。

智能优化算法为图像多阈值分割技术提供了一种十分有效的方式,愈来愈多的研究者将智能优化算法与阈值选取方法相结合来得到质量较好的分割图像。吴禄慎等人[7]将教与学搜索策略和模拟退火机制引入布谷鸟算法,提出了基于改进布谷鸟算法的多阈值灰色图像的分割。高扬等人[8]分析并研究了基于改进的人工蜂群算法(Artificial Bee Colony Algorithm,ABC)的阈值分割方法,将其应用在了图像分割问题上,实验结果表明改进的人工蜂群算法在高维分割图像问题上有很好的性能和稳定性。徐朗等人[9]将蜻蜓算法与差分进化算法结合,提出了一种基于改进的蜻蜓算法(Improved Dragonfly Algorithm,IDA)的彩色图像多阈值分割技术,实验证明,与其他算法相比,该算法得到的分割阈值最优,且分割出的图像质量较好。S. Pare等人[10]提出基于蝙蝠算法的多阈值分割技术用于分割彩色的卫星图像。Mahajan等人[11]提出了基于樽海鞘群算法(Salp Swarm Algorithm)的多阈值分割技术,并将第二类模糊熵作为适应度函数进行计算得到最佳阈值。

上面提到的算法都能够有效地得到图像分割的阈值,但是大部分都不能保证图像分割后的质量。提高图像分割后的质量是一个非常重要的问题,因此,该文提出了一种基于改进的ABC算法(Improved ABC,IABC)的多阈值图像分割方法。ABC算法具有鲁棒性强、精度高等优点,但其自身具有过早收敛、局部搜索能力差的缺点[12]。为了能够弥补ABC算法的缺陷,该文利用DIRECT算法全局收敛并能够快速定位到最优值区域的特点,为ABC算法选择良好的种群,种群经过数代演化后得到的最优解会返回到DIRECT算法的分割区域中并指导DIRECT的分割,再次为ABC算法选取更好的种群,循环这个过程直到满足算法的停止条件。将IABC算法得到的图像分割结果与多种算法得到的结果进行比较,实验数据表明该算法得到的分割后的图像质量更好。

1 阈值分割方法

本节主要介绍了阈值的分割方法——最大类间方差。

最大类间方差是一种无参数、无监督的自动阈值选择的方法[4],也被称为OTSU方法。假设I是一幅拥有M×N个像素的图像,[0,1,…,L-1]表示图像I有L个灰度级别,[th1,th2,…,thk-1]表示由算法找到的k-1个阈值。ni表示第i个灰度级在图像中的个数,那么图像I灰度级的概率分布是:

(1)

(2)

k-1个阈值将图像分为了C1,C2,…,Ck类,则第Ci类出现的概率为:

(3)

第Ci类的平均灰度值为:

(4)

第Ci类的方差为:

σi=ωi(μ0-μ)2,i=1,2,…,k

(5)

被分割后图像的类间方差为:

(6)

由以上分析可得到Otsu方法的目标函数为:

(7)

2 基于改进人工蜂群算法的多阈值图像分割

本节在分析了ABC算法以及DIRECT算法后,提出了IABC算法并简要论证了IABC算法的全局收敛性,随后提出了基于IABC算法的阈值分割技术。

2.1 人工蜂群算法

ABC算法[13]是模仿蜂群采蜜行为的一种智能优化算法。人工蜂群算法包含三种蜜蜂,(a)雇佣蜂:去食物源采蜜;(b)观察蜂:根据雇佣蜂采回花蜜的数量(目标函数的适应值)选择食物源;(c)侦察蜂:当花蜜的数量不再上升时,侦察蜂会重新随机选择一个食物源给雇佣蜂。

ABC算法主要分为四个阶段。第一个阶段(初始化阶段):初始化种群数量SN,雇佣蜂种群的初始位置{xi},i∈[1,2,…,SN/2];第二阶段(雇佣蜂阶段):雇佣蜂将返回蜂巢,与观察蜂分享信息后返回到食物源位置,根据表达式(8)寻找新的食物源位置。

(8)

其中,xij表示食物源xi在第j维度的位置,k∈[1,2,…,SN]和rij∈[-1,1]是随机数。第三阶段(观察蜂阶段):观察蜂会依概率:

(9)

选择需要观察的雇佣蜂,其中f(xi)表示食物源xi的函数值,即花蜜的数量,观察蜂会根据式选择食物源的位置,使用贪婪策略选择是否更新食物源位置;第四阶段(侦察蜂阶段):当雇佣蜂带回花蜜的数量处于停滞状态时,侦察蜂会随机指定一个新的食物源给雇佣蜂。

其中,食物源表示目标函数可行解,对应的花蜜数量表示目标函数的适应值,通常雇佣蜂的数量与观察蜂的数量相同,为种群数量的一半。

2.2 DIRECT算法

DIRECT算法[14]是一种确定性算法,在初始阶段能够很快找到目标函数最优解所在的区域[15]。然而,刘[16]发现,将DIRECT算法运用在目标函数线性校正前后,性能有非常大的不同,于是提出了具有鲁棒性的DIRECT算法。该文将使用刘提出的DIRECT算法。

DIRECT算法主要包含三个主要操作,选择潜在最优超矩形(Potential Optimal Hyperrectangle,POH),在POH中抽去样本点和分割POH。抽样操作:假设POH的最长边为δ,表示最长边的维度的集合,c为POH的中心,在的每一个维度上进行抽样,其中ei是一个第i个元素为1的单位向量;分割操作:优先选择最小值所在的维度被分割成三等分;POH的区域选择:假设分割后所得到的超矩形的集合为,ci和σi表示第i个超矩形的中心和大小,fmin表示当前函数的最小值,如果存在一个常数γ>0满足:

(10)

则矩形j是一个POH,其中ε>0是给定的常数。

图1表示的是DIRECT算法的迭代过程,在第一次迭代时,选择整个搜索空间作为POH,并对其最长边所在的维度进行抽样,对最优解所在的维度进行三等分。第二次迭代与第三次迭代重复选择、抽样、分割三个步骤直到停止条件被满足。

DIRECT算法的步骤如下:

第一步:将搜索空间初始化为一个单位超矩形,记作c1为这个超矩形的中心,fmin=f(c1);

第二步:识别潜在最优矩形S;

第三步:选择矩形j∈S;

第四步:对矩形j进行采样,确定分割超矩形的方式,并更新fmin;

第五步:S=S-{j},如果S≠∅,返回第三步;

第六步:满足循环条件则返回第二步,否则停止。

图1 DIRECT算法的迭代过程

2.3 基于改进人工蜂群的多阈值图像分割方法

2.3.1 改进的人工蜂群算法

IABC算法首先执行DIRECT算法,根据2.2节的分析,DIRECT算法不仅能够很快地找到最优解所在的区域,而且每次迭代之后至少能够生成5个可行解,足以形成一个种群并进行种群的演化,也就是说,DIRECT算法可以为ABC算法提供一个非常好的种群。ABC算法在经过一定次数的迭代后,将生成的最优解返回到DIRECT算法的分割区域中并将区域进行分割,不断进行种群选择和种群进化直到满足停止条件。其中ABC算法得到的最优解的加入破坏了DIRECT算法三等分分割原则,这时应遵循采样点在超矩形中心这一原则对分割区域进行分割。IABC算法的步骤如下:

第一步:初始化种群;

第二步:若迭代次数大于1,执行第三步,否则执行第四步;

第三步:从现有的解中采用完全随机选择方法选择一组种群作为初始种群,执行ABC算法,得到最优解并返回到分割区域中,对该区域进行分割;

第四步:选择POH,并对其进行采样和分割;

第五步:若满足停止条件则停止,否则继续执行第二步。

Johns等人[14]在论文中论述了DIRECT算法的收敛性——如果目标函数是连续的,则DIRECT算法保证可以找到函数的全局最优值。通过论文[14]中的论述过程可知,根据POH的区域选择的规则即表达式(10)可推出在每一次迭代的过程中至少有一个最大的超矩形会成为POH,因此每一个超矩形在有限次迭代过程中都会被分割。由于每一个超矩形都会在有限迭代次数内被分割,在有限次迭代过程中,每一个超矩形的大小都会小于一个任意的σ(σ>0),这意味着,超矩形采样的点都会落在某个采样点的σ邻域内。因此,DIRECT算法是全局收敛的。

根据改进的ABC算法的过程可知,在DIRECT的分割区域加入了由种群进化得到的一个最优解,最优解的加入意味着使得DIRECT算法能够提前分割这些区域,对DIRECT算法中POH的选择以及采样都不造成任何影响,因此IABC算法也是一种全局收敛的算法。

2.3.2 基于改进的人工蜂群的多阈值图像分割方法

IABC算法将OTSU方法作为目标函数,即表达式(7),得到最优阈值对图像进行分割。图2是基于改进的ABC算法的多阈值分割图像方法的流程。

图2 多阈值图像分割方法的流程

3 实验结果与分析

本节主要围绕改进的人工蜂群算法在图像分割方面的实验展开论述,详细说明了实验的设置以及评价指标和实验结果的分析等。为了说明算法的优劣,在保证图像大小、种群大小、函数评估次数等都相同的前提下,将本实验得到的结果与ABC算法[13]、IDA算法[9]和AHHO算法[17]得到的结果相比较。

3.1 实验设置

在本节中,将表达式(7)作为目标函数,但根据问题的属性,该目标函数是离散问题,在实验中,首先将目标函数的变量做连续化处理,即使得阈值的取值范围为[0,255],且目标函数为fOTSU(xi)=fOTSU(⎣xi」)。随后使用2.3节提出的彩色图像多阈值分割方法分割四幅大小均为481×321×3的RGB图片,如图3所示(依次为horse.jpg、lake.jpg、pig.jpg、stone.jpg,图片来自于伯克利分割数据集[18])。本实验在“Linux 3.10.0”系统上的“Matlab 2020b”软件上进行。由于随机性的存在,对每幅图像,对OTSU方法运行30次再求平均值。实验的参数如表1所示。

图3 RGB图片 表1 参数设置

参数值函数评估次数15 000种群大小30种群迭代次数50观察蜂数量15雇佣蜂数量15停滞界限100

3.2 图像分割质量评价指标

为了评估图像分割算法的优劣,文中采取了三个图像质量评价指标,即峰值信噪比(Peak Signal-to-Noise Ratio,PSNR)、结构相似性(Structural Similarity Index,SSIM)和特征相似性(Feature Similarity index,FSIM)[19]。

PSNR用于验证原始图像I与分割后的图像K之间的相似性,其表达式为:

(11)

(12)

其中,MSE是原始图像I与处理后的图像K之间的均方误差(Mean Square Error),Iij和Kij表示对应图像的第i行第j列的像素值。

SSIM是用于比较原始图像与分割后图像之间结构的相似性,也就是图像中相邻像素之间的关系,其表达式为:

(13)

其中,μI和μK分别是原始图像与分割后图像像素的均值,σI和σK对应的是图像的标准差,σIK表示的是原始图像I与分割后图像K像素之间的协方差,λ1和λ2是常数。

FSIM用于比较图像之间的特征相似性,即相位一致性(Phase Congruency,PC)和梯度的特征(Gradient Magnitude,G)[19],表达式如下:

(14)

(15)

SL(x)=SPC(i)·SG(i)

(16)

(17)

其中,PCm(i)=max{PCI(i),PCK(i)}。

这三种指标有一个共同点,即求得的值越大,表示由分割得到的图像质量越高。

3.3 实验数值结果与分析

表2展示了文中算法与ABC算法、IDA算法以及AHHO (Altruistic Harris Hawks’ Optimization)算法得到的实验数据结果,比较数据包括算法运行30次之后得到的平均PSNR、平均SSIM和平均FSIM。黑色加粗的数值表示文中算法与其他三种算法相比较得到的较好的值。

表2 实验结果比较

从表2中可以看出,以OTSU为目标函数时,使用文中算法得到的图像阈值分割结果要远远好于其他三种算法得到的结果;当以PSNR为评价指标时,文中算法要远好于其他三个算法,即使用IABC对图像进行分割后的质量与原图像相似性高;当以SSIM作为图像的质量评价标准时,从实验的比较结果看,文中算法在lake.jpg图像上表现最差,在pig.jpg图像上表现最好;当以FSIM作为图像的质量评价标准时,在大多数情况下,IABC算法分割得到的图片与原图片的特征最相似。

图4是图像的分割结果,由于篇幅原因,仅给出基于改进的人工蜂群的多阈值图像方法的实验结果。结合表2和图4可以发现,当k值较低时,得到的分割图像细节较少,图像的质量也相对较差,当k值较大时,图像细节越多,图像的质量也越好,越接近未被分割的图像。

图4 基于改进的人工蜂群的多阈值图像分割方法的实验可视化结果 (从左向右分别是k-1=4,6,8,10所对应的结果)

4 结束语

首先对阈值分割的国内外研究进行了一个梳理,并在前人的基础上,提出了一种基于IABC的多阈值彩色图像分割方法,并简要证明了IABC算法的全局收敛性。首先,将DIRECT算法的分割过程与ABC算法联系起来,使得DIRECT算法能够为人工蜂群算法提供足够好的初始种群,再将OTSU作为目标函数,以提高图像被分割后的质量。确定了图像分割的阈值后,对分割后的图像与原始图像使用了三个评价指标,即PSNR、SSIM和FSIM,对结果进行分析,结果证明了该算法的优越性。