一种基于Levy-人工蜂群的三维Otsu阈值分割算法*

黄翠玲，孔韦韦，李 萌，呼亚萍

(1.西安邮电大学 计算机学院，西安 710121；2.陕西省网络数据分析与智能处理重点实验室，西安 710121)

0 引 言

图像分割技术是计算机视觉和数字图像处理领域中的一项重要研究内容，其主要目标是将图像目标与背景按照某种规则分开来，目前已被广泛应用于遥感[1]、军事[2]、气象[3]、医疗[4]等方面。

在众多图像分割方法中，基于阈值的分割方法占有十分重要的地位。其中，日本学者Otsu[5]提出的一维Otsu算法以目标和背景的类间方差为准则，计算复杂度较低，并能在一般情况下取得较好的分割性能。然而，当该算法用于含噪图像的分割任务时效果并不理想。在此基础上，二维Otsu分割算法[6]综合利用了图像像素点与其邻域空间的相关信息，当作用于低对比度、低信噪比的目标分割时，二维Otsu算法具有较理想的分割效果，但其对象区域和背景区域上的概率和近似为1的假设不够普遍。为此，文献[7]提出了一种基于三维Otsu算法的阈值分割算法，通过限定迭代空间和搜索空间，并用布谷鸟搜索算法进行寻优，但该方法对于椒盐噪声的图像仍然存在错分的问题。徐青等[8]提出了新的基于分解直方图的三维Otsu分割算法，能够满足一定的实时性，但分解技术使得目标及背景部分都有不少错分，分割效果不够理想。刘思言[9]提出了一种直方图区域合并算法，在每次迭代中减少一个阈值，并挑选出相邻区域进行合并，直到达到符合要求的阈值数目。姜圣涛等[10]利用自适应差分进化算法选取阈值分割所需要的最佳参数，把参数带入广义模糊熵的补函数进而得到图像的阈值。文献[11]提出了基于白顶帽规模的粗麻布血管增强滤波器和多阈值Otsu方法，开发了一种三维Otsu混合分割方法，解决了强度不均匀的问题。文献[12]提出了一种基于三维Otsu和多尺度图像表示的阈值分割算法，使用多数表决规则将分割结果加以合并以获得最终分割结果。高扬等[13]提出了一种改进的人工蜂群算法来处理图像分割问题，能够取得开发和探索的平衡，但其更适合解决多级图像分割问题，普遍性不够。

综上所述，传统三维Otsu算法在一维Otsu算法的基础上改进，由于维度的增加，时间复杂度也大幅增加。在此背景下，本文为了提高三维Otsu算法的运算效率，提出了一种通过Levy-人工蜂群算法进行寻优的算法，从而获取到最佳阈值。仿真实验结果表明，该算法能够有效降低计算复杂度以及阈值获取的时间，分割后的图像效果也更为理想。

1 三维Otsu算法

三维Otsu算法利用原图像、邻域平滑图像及邻域中值图像构成了三维直方图，具有一定的抗噪性，其原理如下：假设一幅图像的尺寸为M×N，灰度级为L，f(x,y)为像素点(x,y)的灰度值，g(x,y)为像素点(x,y)的邻域均值，h(x,y)为像素点(x,y)的邻域中值，则g(x,y)与h(x,y)的灰度级也为L。g(x,y)和h(x,y)分别定义为

(1)

(2)

式中：med表示中值，k×k为邻域大小。

将任一像素点(x,y)的f(x,y)、g(x,y)以及h(x,y)构成一个三元组(i,j,k)，并将该三元组定义为三维直方图。显然，该三维直方图对应一个尺寸为L×L×L的正方体区域，如图1(a)所示，其三个坐标分别表示图像像素点的灰度值、邻域均值及邻域中值。设mijk为像素点(i,j,k)出现的频数，则(i,j,k)出现的频率pijk由下式确定:

(3)

设分割阈值为(s,t,q)，其将三维直方图分为8个部分，如图1(b)～(d)所示。其中，区域0和1分别代表图像的背景和目标，区域2～7 表示图像边界附近的边缘和噪声。由于边界区域的像素点远小于图像背景与目标区域的像素点，因此可假设目标和背景区域的概率和近似为1。

图1 图像的三维直方图

令图像背景和目标对应的两个区域分别为C0与C1，则C0与C1对应的概率p0、p1可以分别表示为

(4)

(5)

与二维Otsu算法类似，可以采用sB作为trsB(i,j,k)为类间的离散度测度，即

trSB(i,j,k)=

(6)

(i*,j*,k*)=maxtrSB(i,j,k) 。

(7)

2 改进算法的三维Otsu算法

2.1 人工蜂群算法原理

人工蜂群(Artificial Bee Colony,ABC)算法具有较快的收敛速度。该算法将人工蜂群分为引领蜂、跟随蜂和侦察蜂三类。在搜索过程中，引领蜂和跟随蜂负责搜索新蜜源，即寻找最优解，而侦察蜂负责观察是否陷入局部最优，若陷入局部最优则随机搜索其他新蜜源。每个蜜源代表一个可能解，蜜源的花蜜量代表相应解的质量。

2.2 Levy飞行模型

Levy飞行是法国数学家莱维(Levy)提出的一种概率分布，已证实自然界的很多动物觅食轨迹遵从Levy分布，Levy飞行服从Levy分布。Levy飞行是一种频繁的短距离与偶尔的长距离之间的运动轨迹，能够加强信息的交互，避免搜索过程陷入局部最优[14]。Levy飞行如下式:

Levy～u=t-λ，1<λ≤3。

(8)

由式(8)可以看出，Levy基本上形成了具有幂律步长分布且尾巴较重的随机游走过程。 Levy可以最大化提高未知的、大型环境的搜索效率。Levy分布的随机步长如下:

(9)

式中：

(10)

(11)

假设β=1.5，l=50，起点为(0,0)，连续100步，Levy飞行轨迹如图2所示。

图2 Levy飞行轨迹图

由图2可以看出，在Levy的飞行中，短距离深入和偶尔的长距离行走交替发生，因此搜索的部分解靠近局部最优值，从而加快了搜索速度；搜索的另一部分解远离局部最优值，可以避免算法陷入局部最优。

2.3 改进人工蜂群算法

ABC算法的具体步骤如下：

Step1 初始化各个参数，确定搜索范围，并且按照式(12)随机产生初始解：

(12)

Step2 引领蜂在蜜源附近按式(13)进行领域搜索产生新蜜源:

Xij′=Xij+R(Xij-Xkj) 。

(13)

式中：R为[0,1]间的随机数。

Step3 跟随蜂根据引领蜂分享的蜜源信息，按照式(14)计算概率：

(14)

解的适应度函数为

(15)

式中：fi为解的函数值。

Step4 跟随蜂依据概率Pi选择解或者蜜源，跟随蜂在蜜源i附近根据式(13)产生一个新蜜源，并计算该位置下适应度函数值。

Step5 比较引领蜂和跟随蜂搜索的蜜源的花蜜数量大小，其中引领蜂、蜜源位置由花蜜数量较优的解来表示。

Step6 判断是否有放弃的解，若有则相应侦察蜂替换为引领蜂，侦察蜂根据式(13)随机搜索新的食物源。

Step7 记录到目前为止最好的新蜜源。

Step8 判断新确定的蜜源、跟随蜂、引领蜂位置是否满足循环终止条件，如果满足，循环结束，输出最佳蜜源位置，即最优分割阈值；否则，返回Step 2继续搜索。

在经典的人工蜂群算法中，种群的初始化位置是随机的，如式(12)所示。该方法虽然简单，但算法的求解效率会降低，且算法易陷入局部最优的问题。因此为了解决该问题，本文算法在原始算法的蜜源位置更新操作中引入了Levy飞行机制和改进的位置更新方法，进一步提高了蜂群算法的全局搜索能力。Levy飞行机制会产生随机跳跃和方向上的极速变化，能够扩展搜索空间，并有效避免蜂群算法陷入局部最优。

(16)

(17)

本文提出的人工蜂群优化的三维Otsu图像分割算法是基于灰度阈值实现的图像分割；人工蜂群算法采用轮盘赌方式迭代搜索新蜜源，该方式具有更多的随机性，并评价Levy飞行路径对应的最大类间方差，获得最佳分割阈值。算法流程图如图3所示。

图3 算法流程图

该算法实现过程简单，参数较少，结合Levy飞行策略，能避免算法陷入局部最优的问题。同时，该算法适合处理分辨率高的图像，算法时间复杂度明显减小，能够避免存储空间的浪费，并且抗噪性大大提升，算法可以较快地找到最佳阈值。

3 仿真实验

3.1 实验条件

为了验证本文算法的可行性和有效性，Matlab R2018b软件上进行实验，实验平台为Windows 8.1，64位操作系统，4 GB内存。

首先选取Benchmarks测试函数的常用函数对本文算法及传统三维Otsu算法进行寻优性能测试。实验中用到的测试函数，如表1所示。为了保证实验的公平性，考虑到算法随机性对实验结果的影响，将本文算法及传统三维Otsu算法分别运行10次。将实验中的参数进行设定，蜂群总数为100，循环次数为1 000，limit为100，优化参数的空间为[-500,500],两种算法下测试函数的平均值如表2所示。

表1 Benchmarks测试函数

表2 算法测试结果

通过对比两种算法下测试函数的平均值可以得知，本文算法收敛性更好，其求解精度比传统三维Otsu算法好，性能也略优于传统三维Otsu算法，寻优能力也更强，尤其是Sphere函数和Griewank函数在分割精度与稳定性方面有很大的提升。

3.2 主观评价结果

为验证本文算法的分割效果，实验选取Lena、man、Plane、Kids、Boat 5幅含噪图像，显示Lena实验结果，将本文算法与文献[10]算法、遗传算法以及传统三维Otsu算法进行对比。分割结果如图4所示。

图4 Lena图像分割结果

从直观视觉效果来看，文献[10]算法分割图像其轮廓相对清晰，但噪声去除较为粗糙；三维Otsu算法噪声处理结果较为明显，但容易出现图像边缘信息保存不完整的现象；遗传算法在边缘信息保存方面优于三维Otsu算法，但在大噪声点易产生阶梯效应；与上述三种算法相比，本文算法分割得到的图像区域一致性较好，图像更清晰，并且图像的抗噪性也更好，能够将图像与背景更好地分割出来。

3.3 客观评价结果

为了定量地评价各优化算法在图像分割精度方面的能力，本文对各算法的均方误差(Mean Square Error,MSE)和峰值信噪比(Peak Signal-to-Noise Ratio,PSNR)指标进行比较，其结果如表3和表4所示。首先，本文算法的MSE数值略小于其他优化算法，其得到的分割误差更小，分割效果相对较好；其次，本文算法PSNR数值高于另外两种算法，说明分割图像的失真程度更低，更接近于原图像。由表3和表4不难看出，各优化算法数值上差别不大，但本文算法相对于其他算法仍有一定优势，因此可以得出，本文算法的分割精度更高，获得的分割效果更好。

表3 不同算法MSE值对比

表4 不同算法PSNR值对比

3.4 分析与讨论

为了进一步评价几种算法及本文算法在阈值分割方面的性能，本文对不同算法程序运行时间进行了比较与分析。为了保证数据的公平性，每组实验均进行5次，并取其平均值作为本实验结果的数据。各算法的平均运行时间如表5所示。

表5 各算法平均运行时间

由表5可以看出，本文算法在平均运行时间方面比其他几种算法都要低，充分表明本文算法在分割图像复杂度方面有很大的优越性，更适用于实时性更高的场合。

4 结束语

针对三维Otsu算法分割效率低的问题，本文采用Levy飞行对人工蜂群算法进行优化，加强了各人工蜂间的信息交互能力，且收敛速度更快；并将三维Otsu算法与之结合，提出了一种基于人工蜂群优化的三维Otsu算法，有效降低了阈值分割时间复杂度。与传统三维Otsu算法相比，本文算法得到的分割图像精度更高，提高了运行效率，可为后续的目标检测、识别等做更有效的准备。如何针对三维Otsu算法进行更好的优化将是下一阶段需要研究的主要问题。