基于ISSA和积分图的二维熵图像多阈值分割快速算法

吴圳桦，唐文艳，吕文阁，陈汝杰，侯梦华，李德源

（1.广东工业大学 机电工程学院，广东 广州 510006；2.深圳市启灵图像科技有限公司，广东 深圳 518114）

智能制造在全球范围内快速发展，已成为制造业重要发展趋势[1]。机器视觉技术因其作为实现智能制造的重要技术[2]，成为了工业自动化领域的关注重点。在机器视觉技术中，图像分割是关键的预处理操作，被广泛应用于工业自动化、在线产品检测、文档图像处理等方面。图像分割的作用是提取出具有独特性质的区域，供后续图像分析、特征提取与模式识别所用。图像阈值化分割是一种传统的最常用的图像分割方法，因其实现简单、性能较稳定而成为图像分割中最基本和应用最广泛的分割方法[3-4]，主要包括大津法、最小误差法以及最大Kapur熵法等分割方法[5]。但是当图像中存在多个目标或多个灰度不同的区域时，使用传统的单阈值分割方法并不能把图像中的目标有效地分割出来，而常见的多阈值分割方法是通过穷举所有阈值来获得图像分割的最佳阈值，随着阈值数的增多，分割算法的计算时间大大增加，不能满足工业使用当中的实时性要求[6]。因此，如何快速且准确地获得最佳阈值成为图像多阈值分割问题的研究重点。

近年来，众多学者把图像多阈值分割问题作为参数最优化问题，将群体智能优化算法或群体智能优化算法的改进算法应用于图像多阈值分割问题的最佳阈值搜索上，降低了最佳阈值的搜索时间。吴亮等[7]使用改进蝴蝶优化算法对Otsu多阈值分割方法进行快速寻优；于洋等[8]提出了一种自适应粒子群优化二维Otsu的阈值分割算法，利用图像的灰度级和邻域灰度级构成二元组，建立二维最大类间方差模型，结合自适应粒子群算法估计出图像最佳阈值；陈恺等[9]分析了二维熵分割原理，将二维熵扩展至多阈值形式，并引入萤火虫算法，提高了最佳阈值的搜索速度。但以上方法对多阈值图像的分割处理时间仍需数秒。

为进一步提升图像二维熵多阈值分割的分割效率，本文尝试引入麻雀搜索算法(Sparrow Search Algorithm, SSA)[10]并对标准麻雀搜索算法进行分析研究，针对其存在的缺陷提出了一种改进麻雀搜索算法(Improved Sparrow Search Algorithm, ISSA)。接着，通过引入积分图方法，降低二维熵多阈值图像分割中总信息熵的运算量，并将总信息熵作为ISSA的适应度函数进行最佳阈值寻优，提出了基于ISSA并结合积分图的二维熵图像多阈值分割快速算法，最后将该算法与穷举法以及基于粒子群优化算法(Particle Swarm Optimization, PSO) 的二维熵方法进行图像分割对比实验。实验结果表明相较于穷举法，本文方法在图像双阈值分割和三阈值分割的速度上分别提升了1 077.76倍和1 317 635.53倍；相较于基于PSO的二维熵方法，本文方法仍取得了6.47倍和4.48倍的速度优势，极大地提升了图像二维熵多阈值分割的分割效率，同时在工业应用场景仍能够获得相同的效果。

1 麻雀搜索算法

麻雀搜索算法是根据麻雀觅食并逃避捕食者的行为而提出的群体智能优化算法[10]。麻雀搜索算法主要模拟了麻雀群觅食的过程。麻雀群觅食过程也是发现者-跟随者模型的一种，同时还叠加了侦查预警机制。在麻雀搜索算法中，每只麻雀的位置代表一个可行解。麻雀种群中的个体被划分为3类，分别肩负不同的觅食职责，其中包括：(1) 发现较好食物的个体作为发现者；(2) 跟随发现者进行觅食活动的跟随者；(3) 在觅食过程中遇到危险进行反捕食行为的侦查者。麻雀种群中的发现者、跟随者以及侦查者的个体数量保持恒定的比例。麻雀种群中的发现者是种群中适应度较高的个体，拥有更广的搜索范围，为跟随者提供觅食方向。跟随者能够发现适应度最高的发现者，跟随发现者的引导，不断更新自身位置以获得更高的适应度。而发现者与跟随者之间的身份是动态变化的，只要跟随者获得更高的适应度，就有机会成为发现者。在觅食过程中，麻雀种群中一定比例的个体作为侦查者，在意识到危险时，会移向安全区作出反捕食行为，以获得更高的适应度。

发现者的位置更新公式为

式中：i termax为算法的最大迭代次数；α 为 ( 0,1]之间的均匀随机数；Q为一个服从标准正态分布的随机数；R2为 预警值，是[0,1]之间的一个均匀随机数；T为安全阈值，取值范围为[0.5,1.0]。

跟随者位置更新公式为

侦查者的位置更新公式为

2 改进麻雀搜索算法

2.1 方差线性递减的高斯扰动

由式(1)可知在SSA中，当R2

图1 发现者位置变化趋势Fig.1 Change trend of discoverer's position

为解决麻雀搜索算法在迭代过程之中，因发现者所有维度有向原点靠拢或跳跃的趋势所造成的全局搜索能力不高的问题，本文采用方差线性递减的高斯扰动策略，即去除式(1)中R2T时的更新策略修改为方差线性递减的高斯扰动策略，使得该算法在迭代初期发现者群体具有一定的个体多样性，并且在算法迭代的后期具备较强的局部搜索能力。改进后的发现者位置更新公式为

式中：n ormrnd(0,sigma)为 期望值为0，方差为s igma 的高斯分布。 s igma 值在迭代过程中线性地减小，其表达式为

式中：tmax为最大允许迭代次数，t为当前迭代次数；sstart和send分别为初始的方差取值和迭代到最大迭代次数的方差取值。设待优化问题目标函数的定义域为 [a,b]，为使算法在迭代初期具有一定的个体多样性，根据正态分布的 3σ 原则，sstart的取值为

send应取一个较小的值，使得算法在迭代后期具备较强的局部搜索能力。由于该优化算法针对最佳阈值搜索任务进行改进，并且考虑到阈值的取值为整数，因此将种群个体位置进行四舍五入取整，得到当前种群个体位置所对应的阈值取值，且根据正态分布的 σ 原则令send=1，使得算法在迭代的后期，发现者在一定的概率下仍然具有跳出当前位置的能力。

2.2 随机步长移动策略

从式(2)中可以看出，在迭代过程中，当i>n/2时，跟随者各维度位置的值为一个标准正态分布随机数与一个以自然常数e为底数的指数函数的乘积。即此时跟随者总是在原点周边区域进行搜索。当i≤n/2时，跟随者的迭代公式可简化为

式中：r andi([0,1])表 示[0,1]中的随机整数。显然，在迭代过程中，跟随者在全维度地向最优位置移动，种群多样性较低，算法容易陷入局部最优。

为解决以上问题，本文提出随机步长移动策略，将算法中发现者的位置更新公式改进为

式中：r and 表示0到1之间的均匀随机数；u和l分别为最大步长因子和最小步长因子。由式(8)可知，跟随者位置的每一维度以(l,u)之间的随机步长向最优位置移动，可通过设置步长因子的值调节跟随者的移动速度。

改进的麻雀搜索算法流程为：

步骤1：初始化，包括初始化种群的规模N，发现者的个数PNum，跟随者的个数FNum，最大步长因子u，最小步长因子l，最大迭代次数tmax，并按均匀分布初始化各麻雀个体的位置。

步骤2：计算每只麻雀的适应度fi，得到当前最优适应度和最优位置。

步骤3：选取适应度最优的前PNum个麻雀个体作为发现者，选取适应度最优的前FNum个麻雀个体，并排除前PNum个麻雀个体作为跟随者，最后剩余的作为侦察者，并分别根据式(4)、(8)以及式(3)更新发现者、跟随者以及侦察者的位置。

步骤4：根据各麻雀个体所处的位置重新计算适应度值finew。当finew>fi时，表明迭代后的个体优于上一代的个体，则用迭代后的个体替代上一代的个体，否则保持原个体不变。

步骤5:若算法的迭代次数达到最大迭代次数，则算法结束，否则跳转到步骤3。

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

3.1 二维熵多阈值分割方法

基于一维直方图可分离判据的阈值分割方法在图像信噪比下降时，图像的分割质量急剧下降[11]。因此出现了一些利用图像的二维直方图进行阈值分割的方法[12-13]，其中就包括二维熵的阈值分割方法。可将二维熵阈值分割方法扩展为二维熵多阈值分割方法。

二维熵多阈值分割方法的原理为：假设一幅尺寸为M×N的待分割图像f(x,y)(1 ≤x≤M,1 ≤y≤N)，利用尺寸为n×m的滤波核对其进行均值滤波获得邻域平均图像g(x,y) ，两图像的灰度级均为0 ,1,···,L，L的取值一般为255。设r(i,j)为 图像f(x,y)中灰度级为i且 图像g(x,y) 中 灰度级为j的像素对数。定义r(i,j)所对应的联合概率密度为

如此得到了一个关于pij的二维直方图，如图2所示。设分割阈值为(t,s),则二维直方图被分割为4个区域，其中区域1和区域3代表目标区域和背景区域，区域2和区域4代表边缘和噪声。

图2 二维直方图Fig.2 Two-dimensional histogram

图3 多阈值二维直方图Fig.3 Two-dimensional multi-threshold histogram

区域1和区域3的概率分别为

区域1与区域3的总信息熵为[14]

式中：

最大二维熵则是要获得最佳阈值(t∗,s∗)，使得

令

式中：k=1,2,···,n+1 且定 义t0+1=s0+1=0 ，tn+1=sn+1=L。

3.2 积分图

通过二维直方图计算总信息熵H时运算量巨大，如式(17)及式(18)所示，对于每对阈值(tk,sk)均要做累加计算，且随着阈值数量的增多，二维熵多阈值分割方法的计算复杂度呈指数级增长。为尽可能地提高最佳阈值的搜索速度，本文采用Viola等[15]提出的积分图方法来降低总信息熵H的运算量。分别对pk及hk生成对应的积分图，如图4所示，其中：

图4 pk 及 hk对应的积分图Fig.4 Integral diagram corresponding to pk and hk

运用积分图，可将式(17)和式(18)的计算简化为：

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

设分割图像的阈值向量T为[t1,t2,···,tn,s1,s2,···,sn]， 其中0

步骤1：读取待分割灰度图f。

步骤2：根据灰度图f求得二维直方图。

步骤3：根据步骤2中的二维直方图求得pk和hk对应的积分图。

步骤4：初始化麻雀种群，其中每个麻雀个体的位置代表一个阈值向量，并利用积分图及根据式(16)、式(21)和式(22)计算所有麻雀个体的适应度值。

步骤5：利用改进麻雀搜索算法对阈值向量进行寻优迭代，直至达到最大迭代次数。

步骤6：通过使用寻优得到的最优阈值对待分割图像进行阈值分割，输出分割后的图像。

流程图如图5所示。

图5 分割算法流程图Fig.5 Flow chart of segmentation algorithm

5 实验结果与分析

5.1 基准函数对比实验

通过设计基准函数对比实验来验证改进算法的性能提升，设计二维熵图像多阈值分割对比实验来验证基于改进麻雀搜索算法的二维熵多阈值分割方法在运行速度上的优越性。本文实验均基于Windows1064位操作系统，CPU为Intel(R)Core(TM)i5-4210 M和16 GB内存的PC机，实验软件为Matlab R2018a。

为测试改进麻雀搜索算法的搜索能力，本文采用4个不同特征的基准测试函数作为实验对象，如表1所示。表1中特征“U”代表该函数是单峰函数，函数在定义域内没有局部极值，只有全局最优解；特征“M”代表函数是多峰函数，多峰函数相对于单峰函数具有多个局部极值，用于检验算法的全局搜索能力；特征“S”代表函数是可分离的，即该函数可由N个单变量函数之和表示；特征“N”代表函数是不可分离的，与可分离函数相对，不可分离函数变量之间存在复杂的关系，因此此类函数的寻优较为困难[16]。实验中算法的通用参数分别设置为：种群的规模N=50， 最大迭代次数tmax=100，发现者、跟随者及侦查者的比例为2:7:1。

表1 基准测试函数Table 1 Benchmark functions

标准麻雀搜索算法和改进麻雀搜索算法在4个基准测试函数上的收敛曲线如图6所示,从图中可以看出改进后的麻雀搜索算法在F1上表现出了更优的收敛精度；在F2上表现出了更优的全局搜索能力；在F3上表现出更优的收敛速度；在F4上表现出与标准麻雀搜索算法相似的寻优能力。

图6 基准函数收敛图Fig.6 Convergence graph of benchmark function

为避免实验结果的随机性，定量分析改进后算法的寻优性能，标准麻雀搜索算法(SSA)和改进麻雀搜索算法(ISSA) 对表1中的4个基准函数各独立运行30次，选取运行结果中的最差值、最优值、平均值和标准差作为对比指标进行比较，如表2所示。

表2 算法性能比较Table 2 Comparison of performance among different algorithms

从寻优结果的比较中可发现，在F1上，ISSA极大地提高了寻优精度；在F2上SSA没有能够搜寻到最优解，体现了ISSA相较于SSA在全局搜索能力上的提升；在F3和F4上，ISSA相较于SSA,其寻优结果的标准差更低，表现出了更好的寻优稳定性，具有更高的寻优能力。

5.2 基于改进麻雀搜索算法的二维熵多阈值图像分割方法实验

本文实验选取了Lenna图、Camera man图、Rice图以及工业生产当中的齿轮图和刹车盘图分别进行基于改进麻雀搜索算法的二维熵多阈值图像分割方法的单阈值分割、双阈值分割以及三阈值分割。算法的参数设置为：种群的规模N=50，最大迭代次数tmax=30 ，最大步长因子u=1.7，最小步长因子l=0.3，发现者、跟随者及侦查者的比例为1:8:1。分割后的图像如图7所示。图7中，齿轮图包含多个待分割的齿轮目标，在单个刹车盘工件上同时存在多个灰度不同的区域，对此类图像进行单阈值分割往往不能得到理想的分割结果。利用本文方法对齿轮图像进行双阈值分割，可正确分割出所有的齿轮目标。而刹车盘图像灰度不同的区域较多，采用三阈值分割方可获得理想的分割结果。

图7 分割结果Fig.7 Segmentation results

5.3 对比实验

为验证本文方法的优越性，将其与基于粒子群优化算法(Particle Swarm optimization，PSO) 的二维熵分割方法进行对比实验。基于粒子群优化算法(PSO) 的二维熵分割方法是直接利用粒子群优化算法对图像的二维熵最优阈值进行寻优的方法。

以上2种算法对前述5幅原始图像进行分割实验，分割后的阈值与计算时间如表3所示。由表3可知，相较于基于PSO的二维熵方法，本文方法在双阈值分割及三阈值分割中取得了6.47倍及4.48倍的速度优势。将改进麻雀搜索算法应用在二维熵图像多阈值分割上，提高了图像分割的速度。

表3 两种算法的结果对比Table 3 Comparison of the results between two algorithms

6 结论

本文针对图像二维熵多阈值分割时存在的计算量过大，计算时间过长的问题，提出了基于ISSA并结合积分图的二维熵图像多阈值分割快速算法。首先，引入麻雀搜索算法(SSA)并对该算法的算法性能进行分析研究，针对SSA存在的全局搜索能力差、容易陷入局部最优解的缺点，提出了基于方差线性递减的高斯扰动策略和随机步长移动策略的ISSA。相较于SSA，ISSA在4种不同类型的基准函数上表现出更优的寻优能力。接着，通过引入积分图方法，降低总信息熵的运算量，最终提出了基于改进麻雀搜索算法并结合积分图的二维熵图像多阈值分割快速算法。最后，使用该方法与基于PSO的二维熵方法进行图像分割对比实验，实验结果表明，相较于基于PSO的二维熵方法，本文方法仍取得了6.47倍和4.48倍的速度优势，提升了图像二维熵多阈值分割的分割效率。