基于改进PSO的三维Tsallis熵图像分割

吴浩然

(合肥工业大学 数学学院，安徽 合肥 230601)

0 引 言

图像分割就是把图像分成若干个特定的、具有独特性质的区域并提出人们感兴趣目标的技术和过程。现有的图像分割方法主要分以下几类：基于阈值的分割方法、基于区域的分割方法以及基于边缘的分割方法。其中基于阈值的分割方法是最常见的方法，该方法根据图像中目标与背景的灰度值的差异，通过设置一个或几个阈值来将图像分割成多个区域。目前比较成功的阈值方法有聚类方差法、熵方法等[1]。在这之中熵阈值分割方法又因为实现简单且性能稳定而得到了广泛的应用。20世纪80年代，学者们就开始将熵的概念应用在阈值选择上。Pun首先将熵的概念引入图像的阈值分割，提出了最大后验熵法[2]，Kapur等人提出了一维最大Shannon熵阈值法[3]，Li和Lee提出了最小交叉熵阈值法[4]。

上述基于熵的阈值分割法中一般采用的都是一维Shannon熵，但Shannon熵具有广延性，其会忽略两个子系统之间的相互作用，放在图像分割中就是忽略了目标和背景之间的相关性[1]。为了解决这个问题，Tsallis扩展了Shannon熵并提出了Tsallis熵[5]，Tsallis熵具有非广延性，使用Tsallis熵进行图像分割可以取得更好的结果。除此之外，由于一维熵阈值分割法是利用图像的一维直方图进行计算的，这在得到最佳分割阈值的过程中没有利用到图像的空间信息，因此图像分割结果容易受到噪声的干扰，而利用图像的局部空间信息可以在一定程度上改善分割结果[6]，有学者据此引入了像素的邻域灰度信息，提出了多种基于图像二维直方图的熵阈值分割方法，如二维Renyi熵阈值法[7]、二维Tsallis熵阈值法[8]等。扩展的二维方法能较好地抵抗高斯噪声的干扰，但却无法抵抗椒盐噪声的干扰[9]，因此有学者引入了邻域中值提出了三维分割算法，如三维Otsu法[10]、三维Tsallis熵法[11]等。上述三维阈值分割方法都是利用图像的原始灰度，邻域平均灰度，以及邻域中值组成图像的三维直方图，并未利用到图像的梯度信息，这存在着一定的局限性[9]。受文献[9]启发，该文引入了梯度信息，将其与图像像素的邻域均值、邻域中值结合构成图像的三维直方图，并结合Tsallis熵理论提出了三维Tsallis熵阈值分割方法。将提出的新的三维Tsallis熵阈值分割法与该文提出的一种新的改进粒子群优化算法结合进行图像阈值选择，取得了较好的分割结果。由上所述，相对于一维熵阈值分割法，二维熵阈值法进行分割可以取得更好的结果，但同时分割步骤也变得更加繁琐，计算量也变得更大，从而运算时间也变得更长。因此为了提高分割效率，有学者提出了利用元启发式算法结合二维熵来进行阈值选择。与二维熵阈值分割法相比，三维熵阈值分割法的计算量更大，因此该文同样使用元启发式算法对三维熵阈值分割法进行优化以提高分割效率。

启发式算法(heuristic algorithm)是一种基于人的主观经验或自然规律所构造的算法，能够在可接受的计算花费(如计算时间)下给出待解决组合优化问题的一个较优的可行解，但该可行解与目标问题的最优解之间的误差一般无法预计。元启发式算法(meta-heuristic algorithm)是启发式算法的改进，由于元启发式算法较少依赖算法本身组织结构，因此其通用性强、泛化性更好[12]。遗传算法[13]是(genetic algorithm，GA)较早提出来的一种元启发式算法，文献[14]就将遗传算法与二维最大熵法结合进行图像分割，在分割精度明显优于一维最大熵法的情况下分割速度与一维最大熵法基本相同。除此之外，文献[15-16]也都将遗传算法应用于图像分割领域。鲸鱼优化算法[17](whale optimization algorithm，WOA)是一种受鲸鱼社会行为启发的元启发式算法，文献[18]将鲸鱼优化算法与多阈值Otsu法结合进行图像分割，实现了更高的分割精度。除此之外，文献[19-20]也将改进的鲸鱼优化算法与熵阈值法结合进行图像分割。

粒子群优化算法[21](particle swarm optimization，PSO)是由Kennedy和Eberhart于1995年提出的一种基于群体智能的元启发式优化算法，由于操作简单、收敛速度快而得到了广泛的应用，文献[22]就将PSO与二维最大Tsallis熵结合进行阈值选择，取得了较好的结果。虽然PSO算法收敛速度快，但仍存在早熟收敛的问题,并且具有种群多样性随迭代数增加下降过快、有可能不收敛到全局最优解等缺点，这将会导致分割阈值选取不够精确，从而图像分割精度较低。因此有学者通过不断改进这些元启发式算法以获得更好的效果。该文通过修改粒子群优化算法的粒子迭代方式，得到了一种在低维环境下可以有效避免局部最优的改进粒子群优化算法，然后将其与三维Tsallis熵结合对图像进行分割，取得了更好的分割精度。

1 三维Tsallis熵的图像分割原理

1.1 二维Tsallis熵阈值分割

取图像自身的灰度值以及对应的邻域平均灰度值构造二维直方图，如图1所示。

图1 二维直方图

在图1中，(s,t)为假设的阈值向量，可以看出，向量(s,t)将上图分割为四个部分，其中区域A和B表示目标或背景，区域C和E表示边界点或噪声。

则目标和背景两类的二维Tsallis熵分别为：

(1)

(2)

式中，L为图像灰度级，q为待定系数，其代表了Tsallis熵的非广延性，文中q取0.8。由此可得图像总的二维Tsallis熵为：

(3)

以上公式为文献[8]和文献[23]的工作。

1.2 三维Tsallis熵分割原理

假设f为大小M×N、灰度级为L的一幅图像，用f(x,y)表示位于图像(x,y)处的像素点的灰度值，g(x,y)表示以(x,y)为中心的3×3的像素邻域的平均灰度值。在此基础上再设h(x,y)为以(x,y)为中心的3×3邻域灰度中值，z(x,y)为以(x,y)为中心的3×3邻域的梯度值。其中梯度的计算如下所示：

z(x,y)=9|f(x,y)-g(x,y)|

(4)

该文则将g(x,y)、h(x,y)与z(x,y)三个元素作为三维Tsallis熵的组成部分构成三维直方图，如图2所示。

图2 三维直方图

由图2可以看出，假设的三个阈值(s,t,q)将图中像素划分为8个部分。其中区域0，1，2，3位于梯度阈值q的下方，即位于该区域的灰度值梯度较小，这表示该区域的像素之间灰度值变化不大，所以一般认为目标与背景位于该区域。反之区域4，5，6，7的梯度值则较大，这表示该区域像素之间灰度值变化较大，一般认为边缘和噪声位于该区域。因为位于目标或背景的灰度值比较相似，因此位于目标或背景的像素点处的邻域平均灰度值与中值则会非常接近，从而在区域0，1，2，3中，位于对角线处的区域0，1便代表背景和目标(假设区域0为背景，区域1为目标)，区域2，3则因为像素点很少而可以忽略不计。与之同理，边缘和噪声点主要出于区域4，5之中，区域6，7则可以忽略不计。其中区域4中的边缘信息为背景区域向目标区域过度的边缘信息，区域5为目标区域向背景区域过度的边缘信息[9]。

每个像素对(i,j,k)出现的联合概率为：

(5)

式中，rijk表示像素对(i,j,k)出现的次数。则区域0，1，4，5的联合密度分别为：

(6)

(7)

(8)

(9)

则根据上述公式以及上节的Tsallis熵公式可得区域0，1，4，5的三维Tsallis熵分别为：

(10)

(11)

(12)

(13)

据上所述，该文将区域0，4作为背景，1，5作为目标，根据Tsallis熵的定义，提出了以下图像总的熵的公式：

(14)

只需求出式(14)最大值即可得到最优阈值，在求得最优阈值(s*,t*,q*)之后按以下公式对图像进行分割：

(15)

由上文所述，图像的背景与目标均处于阈值q*以下，所以公式(15)未利用到阈值q*。

2 改进粒子群优化算法

2.1 粒子群优化算法

(16)

(17)

式中，d为粒子的某一个维度。c1和c2为加速度系数，二者通常情况下都取2，R1(t)与R2(t)为[0,1]之间的随机数。ω为惯性权重，通常是随着迭代次数的增加而线性减小，最大值一般取ωmax=0.9，最小值一般取ωmin=0.4，ω的公式如下：

(18)

式中，Max_iter为最大迭代次数。

2.2 综合学习改进粒子群优化算法

如式(16)、(17)所示，在粒子群优化算法中，每次迭代每个粒子都只向当前位置，自身的历史最优位置pbesti以及所有粒子所发现的全局历史最优位置gbest进行学习，这导致粒子在更新时其余粒子信息使用不足[25]。且每当有粒子陷入局部最优时，由于gbest的存在，其他粒子都会向该粒子学习，这将会导致算法陷入局部最优。因此为了避免算法陷入局部最优，该文引入了综合学习策略[26]并同时修改PSO中粒子的学习方式，使粒子在更新时尽量减少其对gbest的依赖并增加对其他粒子信息的使用。

不失一般性，考虑以下最小化问题：

minf=f(x)

(19)

在综合学习策略中，粒子在更新时，每个维度都会向不同的粒子学习。具体规则如下所述：在粒子更新时，粒子的每个维度都会对应生成一个随机数，然后将随机数与学习概率Pc进行比较，若随机数较大，则粒子该维度将之从自身pbest的对应维度进行学习。若学习概率Pc更大，粒子该维度则向其他粒子对应的维度进行学习，而学习的对象则通过竞争选择而来。竞争选择的具体规则如下所述：首先随机选择两个粒子，然后比较这两个粒子的历史最优值(将两个粒子的pbest带入评价函数求得的适应值)，选择适应值较好的一个将其pbest对应的维度当成粒子更新时某个维度的学习对象。

受综合学习策略的启发，该文提出了综合学习改进粒子群优化算法(comprehensive learning improved particle swarm optimization，CLIPSO)，具体原理如下：首先，将粒子按行组为一个矩阵，每个粒子为一行，行顺序随机确定，然后将所有粒子按标准PSO的迭代规则迭代一次。这之后位于矩阵第一行的粒子先按照PSO的迭代法则更新自身位置，即该粒子的学习对象为自身历史最优位置pbesti与全局历史最优位置gbest，然后剩下的粒子按照矩阵的行顺序从上往下依次更新位置，但这些粒子的学习对象与第一个粒子不同，它们在更新位置之前会生成一个随机数，然后将该随机数与事先设定的学习概率Pc(文中Pc取0.8)进行比较，若学习概率较大，则粒子只向自身的历史最优值pbesti进行学习。反之若随机数较大，则在该粒子上方随机挑选两个粒子，再对这两个粒子的当前适应值进行对比，选择较优的粒子作为当前更新位置的粒子的学习对象，其中i={2,3,…,N}。

在上述CLIPSO的迭代步骤中，除了位于矩阵第一行的粒子会向全局历史最优值gbest学习外，其余粒子均不会向gbest学习，虽然这会避免粒子被gbest吸引而轻易地陷入局部最优，但由于粒子是随机分布的且在算法开始的时候粒子矩阵的行顺序也是随机确定的，因此粒子在迭代过程中可能会缺少全局信息，从而导致算法收敛速度变慢。该文将所有粒子都更新过一次位置之后迭代一次，然后每隔一定的迭代次数(设为m代)，就对所有的粒子整体进行一次PSO迭代以获取全局最优信息，文中m取15。

CLIPSO具体的迭代公式如下：

(20)

(21)

(22)

式中，2≤i≤N,1≤j

3 CLIPSO实验与分析

3.1 实验准备

为了验证综合学习改进粒子群优化算法的寻优能力以及跳出局部最优的能力，使用了5个经典的测试函数来验证CLIPSO的性能。这5个测试函数中，f1为单峰函数，其余为多峰函数，所有函数解空间均设为2维，各函数参数如表1所示。

表1 函数参数

续表1

3.2 对比结果与分析

在这一部分，将CLISPO与PSO本体以及量子粒子群优化算法(quantum-inspired particle swarm optimization，QPSO)[27]、遗传算法、鲸鱼优化算法在五个测试函数上的测试结果进行比较。所有算法均使用相同的种群大小40和最大迭代次数7 500。每个算法都在测试函数上运行30次，然后取平均值。实验环境为：Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz。RAM 8.00 GB，Windows10操作系统，MatlabR2016a。运行结果见表2。

表2 各算法在测试函数上的比较

表2中，mean表示算法运行30次所得结果的平均值，min表示这30次结果中的最优值，max表示这30次结果中的最差值，std表示这30次结果的标准差，time表示算法运行的时间。由表2数据可以发现，CLIPSO在这5个基准函数上的平均表现比较优异。在单峰函数f1上，CLIPSO、QPSO、WOA每次都可以发现函数的最优值，同时PSO与GA则多次陷入了局部最优。在函数f2上，CLIPSO多次陷入了局部最优，但在该函数上只有WOA算法每次都达到了全局最优。在函数f3上，只有CLIPSO每次都能收敛到全局最优值，其余算法均不同程度地陷入了局部最优。在函数f4上，CLIPSO与QPSO、WOA均能次次达到全局最优，PSO与GA算法则多次陷入了局部最优。在函数f5上，所有算法均陷入了局部最优，但CLIPSO所能达到的效果最接近全局最优值。由此可以得知，CLIPSO可以在一定程度上避免局部最优。但从表中也可以看出，CLIPSO的运行时间要长于其他算法，这也是未来需要改进的方向。

4 基于三维最大Tsallis熵的图像分割实验

4.1 实验准备

为了验证CLIPSO结合三维Tsallis熵的分割精度，对Lena、Camera这两张图片进行了加噪处理，然后将CLIPSO结合三维Tsallis熵对这些图片进行分割并将分割结果与CLIPSO结合二维Tsallis熵对这些图片的分割结果进行对比。实验中CLIPSO种群数设置为20，最大迭代次数设置为100。实验环境为：Intel(R) Core(TM)i7-6700HQ CPU @2.60 GHz，RAM 8.00 GB，Windows10操作系统，MatlabR2016a。分割用的图片如图3所示。

图3 分割用图像

4.2 三维Tsallis熵与二维Tsallis熵分割结果对比

本节将CLIPSO分别结合二维Tsallis熵与三维Tsallis熵对Lena、Camera两张图片以及它们的加噪图片进行分割，操作环境如上所述，图片的分割结果如图4和图5所示。

图4 Lena分割结果对比

在图4、图5中，位于每张图片下方的是图片分割的时间与阈值，图(a)是原图的分割结果，图(b)是添加了高斯噪声的分割结果，图(c)是添加了椒盐噪声的分割结果，图(d)是添加了混合噪声的分割结果。

由图4可以看出，在图4(a)上，CLIPSO结合三维Tsallis熵的方法清晰地将人脸分割了出来，但CLIPSO结合二维Tsallis熵的方法却无法完全将人脸与背景分离。在图4(b)上，二者表现相同但效果较差。在图4(c)上，二维Tsallis熵方法的分割结果存在着大量的噪声点，而三维Tsallis熵的分割结果则只有少量的噪声点。在图4(d)上，二维Tsallis熵与三维Tsallis熵的分割结果均存在着噪声点，但三维Tsallis熵的分割图片上的噪声点要明显少于二维Tsallis熵分割图片上的噪声点。

在图5中，二维Tsallis熵与三维Tsallis熵均清晰的分割出了目标与背景，但二维Tsallis熵在添加了图5(b)上的分割结果中存在着少量的噪声点，在图5(c)上的分割结果中存在着大量的噪声点，在图5(d)上的分割结果中则几乎整张图片都布满了噪声点。与此相反，三维Tsallis熵的所有分割结果几乎没有区别，仅在添加了混合噪声的图片上存在着极少的噪声点。

图5 Camera分割结果对比

虽然总体来说三维Tsallis熵阈值分割法可以有效地避免噪声干扰，但其分割时间却远远大于二维Tsallis熵。这是因为三维Tsallis熵阈值分割法代码的时间复杂度要远远大于二维Tsallis熵阈值分割法代码的时间复杂度。为了解决三维熵阈值分割法的时间复杂度过大的问题，文献[9-10]都提出了三维熵的递推公式以减小算法的时间复杂度。而该文选择采用元启发式算法来优化三维Tsallis熵阈值分割法，虽然最终分割时间仍远大于二维Tsallis熵阈值分割法，但与文[9]提到的三维OTSU法相比，分割时间约为其一半。与同样是文献[9]提出的利用递推公式的三维Renyi熵阈值分割法相比，分割时间则与之相近。

5 结束语

由于二维Tsallis熵阈值分割法难以抵抗部分噪声的干扰，通过引入图像的邻域均值、邻域中值以及梯度信息构建了三维直方图，并将其与Tsallis熵理论结合提出了一种三维Tsallis熵阈值分割方法。实验表明，与二维Tsallis熵阈值分割方法相比，三维Tsallis熵阈值分割法可以有效地抵抗各种噪声的干扰。

为了更精确地进行图像分割，提出了一种新的改进粒子群优化算法：综合学习改进粒子群优化算法，将其与前面提出的三维Tsallis熵结合进行图像分割。实验表明，综合学习改进粒子群优化算法可以在低维环境下有效地避免陷入局部最优，且其与三维Tsallis熵结合可以更精确地进行图像分割。

虽然综合学习改进粒子群优化算法与三维Tsallis熵结合可以更精确地分割图像，三维熵阈值分割方法的时间仍然要远远高于二维熵阈值分割方法，因此在后续的改进中，可以尝试将综合学习改进粒子群优化算法中穿插的PSO替换成其他更快的PSO变体，或引入如文献[10]所述的三维熵递推公式，也许可以加快图像的分割速度。