基于群体智能算法的多级图像阈值分割技术的研究

许韫韬，郭 锦，李晓艳，董绵绵，吕志刚，李亮亮

(西安工业大学电子信息工程学院，陕西 西安 710021)

0 引言

图像分割作为图像处理、视觉分析、模式识别中的基本步骤，广泛应用于字符识别、机器视觉、医学图像分析、军事检测等领域。在传统的图像分割算法中，包括基于边缘检测方法、基于区域分割方法、基于阈值分割方法等[1-3]。基于阈值的方法应用最为广泛。然而，随着阈值数量的增加，多阈值分割算法的实时性较差[4]。如何在不影响搜索精度的前提下提高实时性，是该算法研究的热点问题。

粒子群优化算法(PSO)、萤火虫算法(FA)、布谷鸟搜索(CS)算法等群体智能(SI)算法，能够提高优化过程的快速性和稳定性，是解决图像多阈值分割实时性差问题的主要方法，但其搜索精度和实时性有待进一步提高[5-11]。本文提出一种改进的SI算法，采用固定步长搜索策略，以提高群体智能算法在多级阈值上的性能。

1 图像多阈值处理

多级阈值处理的目的是找出一个最佳阈值集T，以将像素分成几个类。多级阈值处理本质上是一种受约束的组合优化问题。

假设在给定图像I中存在L个灰度级，则d阈值将其划分为d+1个类，其可以通过数学描述为

Ck+1={I(i,j)∈I|tk≤I(i,j)≤tk+1-1}

(1)

I(i,j)为像素点(i,j)处的灰度级；tk(k=0,1,2,…,d)表示第k个阈值，同时t0=0,td+1=L,tk∈[0,L-1]。当d=1时，它被称为双级阈值处理，也称为二值化处理。当d≥2时，T=(t0,t1,…,td+1)，显然tk

选择用于双级阈值处理的最佳阈值在计算上并不昂贵，而选择用于多级阈值处理的最佳阈值随着阈值的增加而在指数计算上是昂贵的。通常，阈值处理方法通过优化一些标准函数(也称为目标函数)来搜索最佳阈值。在此，采用类方差(BCV)方法和Kapur熵(KE)方法作为本研究的重点[12-13]。

1.1 类间方差法

类方差法(BCV)之间由Otsu在1979年提出，也称为Otsu方法或最大类间方差方法或最小类内方差方法。BCV的基本思想是最佳阈值将图像分割成具有最大BCV的区段。

(2)

(3)

max(·)表示寻找最大值，式(3)的含义是找出最佳参数T以使函数fBCV(T)最大化。

1.2 Kapur熵方法

熵是不确定性的度量，熵越大，不确定性越大。Kapur的熵(KE)方法也被称为最大熵方法，由Kapur等人在1980年提出。KE的基本思想是较高熵的分布将具有较高的多重性，因此更可能被观察到。

图像的KE可以公式化为

(4)

(5)

2 传统SI算法的多级阈值处理

Yang和Deb以数学方式提出了一种模拟Levy飞行的简单方法，其公式为

(6)

(7)

β和φ为常数；Γ(·)表示伽玛分布；sin(·)代表正弦函数；randn(1,Dim)是一个随机数；Step表示飞行步长值。

在处理基于BCV和KE的多级阈值问题时，不同的SI算法具有不同的迭代机制，分为探索和开发2个阶段，如何以及何时执行2个阶段将导致不同的优化性能。以传统CS算法为例，传统CS算法解决多级阈值问题的流程如图1所示。

图1 传统SI算法解决多级阈值问题的流程

3 改进SI算法的多级阈值处理

尽管传统的SI算法在某些优化问题中表现出良好的性能，但要满足不同特定情况的要求还有很长的路要走，尤其在大多数情况下找不到最优阈值。基于“全局最优解存在于众多局部最优解中”的假设，在传统的SI算法中，采用模式搜索(PS)算法来设计改进策略，以提高SI算法的探索能力，并进一步优化算法性能。

模式搜索算法由Hooke和Jeeves于1961年提出，也被称为Hooke-Jeeves方法。PS的基本思想是找出一系列越来越接近最小函数值的点。PS从初始基点开始，选择基于轴的搜索方向进行探索性移动和模式移动。基于轴的探索移动可以提供一种策略来执行基点周围的精细搜索，同时模式移动也被认为是某种摆脱局部策略。模式搜索算法的模拟过程如图2所示。

图2 PS算法工作过程示意

在模式搜索算法中，“∶=”表示将右侧表达式获得的值赋给左侧变量，其流程如下：

a.设定基点x1∈RD，D轴方向包括e1,e2,…,eD，初始步长为ρ，加速因子α≥1，减速比τ∈(0,1)，最小步长ρmin>0，同时设定y1=x1,k=1，i=1。

b.如果f(yi+ρ×ei)

c.如果f(yi-ρ×ei)

d.如果i

e.如果f(yD+1)

f.设定xk+1=yD+1,y1=xk+1+α×(xk+1-xk)，同时k∶=k+1，i=1，然后跳转到步骤b。

g.如果ρ≤ρmin停止迭代，得到点xk；否则设定ρ∶=τ×ρ，y1=xk，xk+1=xk，同时k∶=k+1，i=1跳转到步骤b。

在解决基于BCV的CS算法多级阈值问题时，使用固定步长模式搜索算法，重新寻找群体全局历史最优解附近的解，从而提高SI算法的局部性能。这种改进的SI算法，称为改进的模式搜索(IPS)算法。

多级阈值处理本质上是一个受约束的组合优化问题，得到的可行解基本都是近似解。基于固定步长的IPS算法，可以提高局部搜索精度，增强其局部收敛性，能够对可行解的逐步精细搜索，进而找到最优阈值。IPS算法在每次迭代中或许会增加SI算法的复杂度，但在搜索方向上有较强的指导作用，特别是在群体全局历史最佳解决方案周围进行了精细搜索，从而改进SI算法的优化性能。改进SI算法解决多级阈值问题的流程，如图3所示。

图3 改进SI算法解决多级阈值问题的流程

4 实验仿真与结果分析

本文以PSO、FA和CS 3种传统SI算法以及改进的SI算法IPS进行比较，并在2幅图像中进行了实验。以KE和BCV作为适应度目标函数的阈值标准，首先采用穷举搜索方法得到离线性能分析的最优解，测试图像及其标准灰度直方图，如图4所示。

图4 测试图像与标准灰度直方图

然后利用SI算法寻找实验图像的阈值，每个实验中的探索阈值数量为2～5，由于SI算法具有随机性，因此对于每幅图像和每个d值都进行50次的仿真实验，表1中列出了由BCV和KE方法穷举搜索提供的最佳阈值及其相应的最佳目标函数值。

表1 穷举搜索得到最佳阈值和函数值

为了公平比较，相同大小的群体40(CS被设置为20，因为它们在每次迭代中评估目标函数2次)并且为所有算法设置最大迭代次数200。除了常见的控制参数外，其他参数对其性能也有很大影响，需要反复试验来确保每个算法获得相对较好的结果。对于PSO算法，惯性重量w=0.5，认知和社会成分c1=c2=2，最大速度限制为vmax=5；对于FA算法，β0=0.8，γ=1，α=0.006，Sk=Gend-Gstart，其中Gend和Gstart分别表示测试图像的最大(终点)和最小(起点)的非零灰度值；对于CS算法，β=3/2，Pa=0.25。

在大多数情况下，每种SI算法运行50次得到的最佳阈值彼此非常接近，尤其是当阈值数量很小时，因此考虑采用SI算法在50次运行中获得的最差阈值来显示视觉差异。而对于视觉差异不是那么显着的，需要进行量化的比较研究。对于第1幅图和第2幅图分别进行基于BCV方法和基于KE方法的群体智能算法阈值分割，并通过每种算法的阈值均值、方差、平均收敛时间以及搜索成功率评估算法的综合性能。均值可用于评估比较算法的搜索精度，方差可用于评估比较算法的稳定性，平均收敛时间可用于评估比较算法的收敛速度，搜索成功率可用于预测算法在何种程度上可以找到最优的概率阈值。

4.1 基于BCV的阈值处理

使用PSO、FA、CS和IPS优化BCV方法，实质上是优化方程(3)的目标函数。为了直观地了解比较算法的分段差异，当阈值数为5时，给出了用分段阈值标记的分段图像和灰度级直方图，如图5所示。均值和方差结果、平均收敛时间和搜索成功率结果分别如表2、表3和表4所示。

图5 基于BCV方法的不同SI算法d=5时的图像和直方图

表2 基于BCV方法的不同SI算法搜索均值与方差

表3 基于BCV方法的SI算法搜索平均收敛时间

表4 基于BCV方法的SI算法搜索成功率

分析仿真结果可知：当直方图中没有更多更突出的峰值，会导致BCV方法函数空间出现更多次有解，从而影响算法的性能；当d=2时，所有算法都具有相同的性能，并在50次运行中找到最佳结果；通常情况下IPS算法的收敛速度要比其他算法快，而当d值变大时，PSO算法简单迭代机制和搜索处理有助于其更快的收敛速度；随着阈值数量的增加，优化问题的复杂性增加，因此问题处理起来要困难得多。每种算法的优化性能变差，例如当d=5时，所有算法都不能在50次重复实验中以100%的概率找到最优结果。

综上所述，考虑到搜索精度，稳定性，收敛速度和成功搜索率，并且4个评估指标具有相同的权重，可以对基于BCV方法的比较算法的综合性能排序为：IPS>CS>PSO>FA。

4.2 基于KE的阈值处理

使用PSO、FA、CS和IPS优化KE方法，实质上是优化方程(5)的目标函数。重复4.1中的仿真实验，分段阈值标记的分段图像和灰度级直方图，如图6所示。均值和方差结果、平均收敛时间和搜索成功率结果分别如表5、表6和表7所示。

图6 在基于KE方法的不同SI算法下d=5时的图像和直方图

表5 基于KE方法的不同SI算法搜索均值与方差

表6 基于KE方法的SI算法搜索平均收敛时间

表7 基于KE方法的SI算法搜索成功率

观察表5～表7中的数据，并比较基于BCV方法的多级阈值处理中的相应结果，可以类似于BCV方法得出结论：首先，当阈值数量较小时，所有原算法都具有相似的优化性能，随着阈值数量的增加，优化性能会逐渐下降；其次，如果直方图不同，则优化性能也不相同；此外，在阈值数d分别为2、3和4时，IPS算法具有较快的收敛速度，而当d=5时，PSO的收敛速度明显比其他比较算法快；最后，IPS算法搜索多级阈值的成功率要优于其他算法。

同时，通过分析表5～表7，对基于KE方法的比较算法的综合性能排序为：IPS>CS>PSO>FA。

5 结束语

随着阈值数量的增加，传统的阈值处理方法已不能满足实时应用的要求。目前，结合具有强大优化能力的群体智能算法，基于一定的标准找到最优阈值成为研究的热点。在分析群体智能算法和模式搜索算法的机理后，提出了基于模式搜索策略的IPS算法，以提高群体智能算法在多级阈值上的性能。该策略是应用步长固定模式搜索算法，在每次迭代中重新利用群体智能算法的全局历史最佳解决方案。在基于BCV方法和KE方法的多级阈值处理中，对比PSO、FA、CS和IPS 4种算法的搜索精度，稳定性，收敛速度和成功搜索率进行了比较研究。

结果表明，当使用不同的阈值标准时，群体智能算法的性能不同。应用所提出的策略后，IPS算法不仅具有良好的全局探索和局部优化，而且在基于BCV方法和KE方法的多级阈值处理方面具有优越的综合性能。