图像分割就是指把图像分成各具特性的区域并提取感兴趣目标的过程，是图像处理到图像分析的关键步骤^[1]，也是计算机视觉的一个基本问题^[2]。图像分割多年来一直得到人们的高度重视，至今已提出了各种各样的分割算法，如基于阈值的分割方法^{[3, 4, 5, 6, 7]}、基于边缘检测的分割方法^{[8, 9]}、基于区域的分割方法^{[10, 11, 12]}、基于图论的分割方法^{[13, 14]}、基于能量泛函的分割方法^{[15, 16]}以及基于机器学习的分割方法^{[17, 18, 19, 20]}等。

基于阈值的分割方法是各类分割算法中简单且广泛采用的方法，其基本思想是用一个或者多个阈值将待分割的图像的灰度级分为多个部分，灰度值在同一类中的像素属于同一个目标^[2]。因此，阈值的选取非常关键，并决定分割的结果。常见的计算阈值的方法主要有最大类间方差法(Otsu算法)^[3]、最大熵法^{[4, 5]}以及最小误差法^[7]等。上述计算阈值方法基本是在满足一定准则下通过解析式求得阈值，例如Otsu算法以目标和背景的类间方差最大或类内方差最小为准则选取阈值。然而，通过解析式求解阈值的计算量和计算复杂度会随着阈值的增加而呈指数增长。因此，一些学者将基于准则函数的阈值求解问题视为以准则函数为目标函数的优化问题，于是出现了一些基于遗传算法^[21]、粒子群优化算法^[22]以及差分算法^[23]等的多阈值方法。得益于经典进化算法能有效求解多阈值问题，一些新颖的仿生算法用于该类问题，并呈现出较好的分割效果^{[24, 25, 26, 27]}。

回溯搜索优化算法(backtracking search optimization algorithm,BSA)是一种新兴的仿生算法，其具有简单的结构，并能有效且快速求解各类函数优化问题^[28]。然而，关于BSA算法的应用研究报道较少，特别是在图像处理及应用领域。因此，借鉴于仿生算法求解多阈值问题的有效性，本文将BSA算法应用于图像分割，提出基于BSA算法的多阈值图像分割。提出的方法将Otsu算法和最大熵法的准则函数视为目标函数，并采用BSA算法分别获取多阈值，实现图像分割。实验说明提出的方法具有更好的性能。

最大类间方差法给予判别分析最小二乘法的原理，其根据图像的灰度特性，将图像分为不同类别，各类之间方差要求最大。假设存在m级灰度的图像P，阈值q将图像的灰度值范围[0,1,…,m-1]分为背景与目标2部分。又设p_i表示灰度值为i出现的概率，则目标部分和背景的概率分别表示为

设λ、λ₁、λ₂分别表示图像、目标和背景的灰度值均值，则可表示为

类间方差可表示为

假设图像P存在a个阈值(q₁,q₂,…,q_a)，式(5)容易扩展多阈值类间方差，可表示为

根据类间最大化准则，可通过计算式(7)获得最佳阈值：

20世纪80年代以来，Shannon信息熵的概念被应用于图像阈值化处理中，其思想是利用图像的灰度分布密度函数定义图像的信息熵，并根据优化准则求得阈值。文献^[4]通过使后验的上限最大化准则确定阈值，而文献^[5]假定目标和背景服从2个不同的概率分布，使得信息熵最大化求得最佳阈值。

假设存在m级灰度的图像P，阈值q将图像的灰度值范围[0,1,…,m-1]分为背景与目标2部分。又设p_i表示灰度值为i出现的概率，则目标和背景表示为式(1)和式(2)，而它们的信息熵则可表示为

Kapur方法^[5]是在图像P的总信息熵最大时，获得最佳阈值，即

同样，式(10)很容易扩展为多阈值最大熵，可表示为

BSA算法是一种新兴的随机优化搜索技术，其结构简单，并且能够有效求解各类优化问题。另外，BSA算法也是基于种群的搜索技术，并且使用一个外部文档维护其历史种群信息以引导种群进化。

当BSA算法用于求解优化问题时，首先在解搜索空间[x_j,min,x_j,max] (j=1,2,…,D)内，通过均匀采样初始化候选解X和历史种群X_old：

与其他进化算法类似，BSA算法使用3个基本的遗传操作：变异、交叉和选择。

BSA算法采用随机变异策略为每个个体生成中间候选个体V_m。该策略能够有效利用历史种群的信息引导算法进化，具体公式为

算法1    交叉策略

输入    变异个体V_m、种群X、种群规模NP、问题维数D、以及混合率mixrate。

输出 候选解T

1)初始化矩阵map_(1:NP,1:D)=1；

2)均匀产生2个[0,1]之间的随机数a和b；

3)if a>b，转入4)，否则转入5)；

4)进行如下操作后转入第6步：

for i=1 to NP

随机生成系列u=permuting(1:D)；

均匀生成1个[0,1]的随机数c；

处理map_{(i,1:mixrate×c×D))}=0;

end for

5)进行如下操作：

for i=1 to NP

均匀生成1个[0,D]的随机整数d；

处理map_(i,d)=0;

end for

6)T=V_m;

7)进行如下操作：

for i=1 to NP

for j=1 to D

if map_(i,j)=1 then T_(i,j)= P_(i,j);

end for

end for

另外，BSA算法采用2种选择操作。第一种选择操作用于更新历史种群的信息，其完全随机下接收当前种群信息，可概括为

应用BSA算法求解多阈值问题，其实质是将多阈值准则作为目标函数，采用BSA算法搜索最优阈值，具体步骤如算法2所示。

算法2    基于BSA算法的多阈值图像分割

输入    种群规模NP、问题维数D(阈值数目)、混合率mixrate、最大迭代次数MaxIteration。

输出    最佳阈值q

1)采用式(12)初始化种群X和历史种群X_old；

2)初始化迭代计数器iter=1；

3)if iter>MaxIteration，转入11);

4)执行第1种选择操作，即执行式(14)更新历史种群；

5)执行变异操作，即执行式(13)；

6)执行交叉操作获得T，即执行算法1；

7)采用式(7)或者式(11)评价T；

8)根据X和T的适应值，采用第2种选择操作获得下一代种群X。

9)获得当前最优阈值q；

10)iter=iter+1，转入3)；

11)输出最优阈值q。

为了分析BSA算法的多阈值图像分割性能，本文采用文献^[25]中的Camera、Lena、Pepper以及Baboon等4幅图像作为待分割图像见图1，其中，每幅图像的大小为256×256。

图 1 测试图像Fig. 1 Test images

图选项

另外，图像峰值信噪比(peak signal to nose ratio,PSNR)作为性能指标，其中PSNR公式^[24]如下：

在实验中，各算法针对每幅图像独立运行30次。每次独立运行中，最大迭代数MaxIteration为160，种群大小NP为20。

表1给出了与基于传统优化算法的多阈值Otsu(MOT)^[29]比较的实验结果。MOT中的适应值是将MOT中的阈值带入式(7)求得。表2列出与基于细菌算法(bacterial foraging algorithm,BFA)的Otsu多阈值^[25]和带惯性权重PSO算法^[30]的Otsu多阈值的实验结果。其中，PSO算法的最大和最小惯性权重分别为0.9和0.4；BFA算的参数见文献^[25]。另外，图2给出各算法求解的PSNR随Otsu阈值数的变化趋势。

图 2 PSNR随Otsu阈值变化的趋Fig. 2 The trend of PSNR change with Otsu threshol

图选项

从表1可知，采用BSA算法求解的阈值使得适应值都优于MOT的所得适应值；另外借助于PSNR，BSA算法也优于MOT。上述结果说明了BSA算法以Otsu的最大类间准则为目标函数求解多阈值是可行的，而且获得较好的性能。

从表2可以看出，与BFA算法比较，BSA算法求解的多阈值在目标函数适应值以及PSNR上都明显较优。另外，与PSO算法比较，在各测试图像的2和3个阈值上，BSA算法求解的多阈值与PSO算法求解的多阈值是相同的，然而在4和5个阈值上，PSO算法获得稍微较好的目标函数适应值，但是BSA算法却获得较好的PSNR。总体而言，BSA算法的多阈值与带惯性权重PSO算法的多阈值性能是相同的。图2同样说明了随阈值数的增加，BSA算法求解的PSNR趋势总体上是最好的。

表3给出了不同仿生算法求解Kapur多阈值的比较结果，其中参数与4.1节相同。

从表3可以看出，BSA算法求解的目标函数适应值上完全优于BFA算法求解的目标函数适应值，而且借助于PSNR性能，BSA算法也优于BFA算法。另外与PSO算法比较，BSA算法求解的目标函数适应值基本上相似，但借助于PSNR，BSA算法的多阈值法总体上优于PSO算法的多阈值法。

图3给出各仿生算法求解的PSNR随Kapur阈值数的变化趋势。从图3可以看出，在多数的图像上，BSA求解的PSNR随Kapur阈值数的变化趋势优于其他2种算法。

图 3 PSNR随Kapur阈值变化的趋势Fig. 3 The trend of PSNR change with Kapur threshold

图选项

本文将BSA算法应用于图像分割，提出BSA算法求解的多阈值图像分割。提出方法将Otsu方法和Kapur方法的求多阈值准则函数作为目标函数，应用BSA算法求解，并实现图像分割。仿真结果说明BSA算法求解的多阈值图像分割是可行的，与其他的BFA算法和PSO算法求解的多阈值分割方法比较，本文提出的方法具有较好的性能。下一步工作将提出方法应用于更多的图像测试，包括遥感图像以及医学影像等。