基于量子粒子群优化的加权平均倒数熵阈值法参数选取

林爱英， 谷小青， 李富强， 贾树恒, 袁超

(河南农业大学理学院，河南 郑州450002)

阈值分割作为图像分割中的重要方法，因其具有简单、有效、易于实现等优点被广泛应用。阈值分割的关键是如何选取合适的阈值，国内外有许多学者对此已进行了大量的研究[1-6]。在众多的阈值分割方法中，基于信息熵的阈值选取方法因其良好的信息论背景备受关注。PUN[3]首先将信息熵的概念应用于图像分割。KAPUR等[7]通过研究指出了PUN[3]研究中存在的问题，提出一维最大熵阈值法。结合图像空间信息，ABUTALEB[8]将一维最大熵方法推广到二维直方图上，提出二维熵阈值分割方法。其后，人们基于广义信息论相继提出了Renyi熵[9]、Tsallis熵[10]等多种熵阈值分割算法，并推导出相应的二维算法[11-12]。但上述基于信息熵的阈值分割方法存在一个关键问题，最大熵在某些灰度值处存在无定义情况。基于这一原因，吴一全等[13]从信息量需满足的原则出发，定义了倒数熵，给出了一维最大倒数熵阈值选取算法公式，并推广到二维直方图区域。范九伦等[14]把倒数熵概念应用于粗糙集理论中，提出一种倒数粗糙熵阈值分割法，进一步丰富了倒数熵的阈值化方法。

最大倒数熵阈值法解决了熵阈值法中存在的无定义值问题[15]，但其准则函数是对图像中目标和背景的倒数熵取算术平均，这和传统最大熵阈值法的基本思路是一样的，都是基于目标和背景类对分割的影响是对等的假设。对于实际的图像分割，目标和背景对分割所起的作用显然是不同的。鉴于此，作者提出一种对目标和背景倒数熵进行加权平均的新阈值分割方法。为了确定合适的加权值，结合图像质量评价准则——均匀性测度和量子粒子群优化算法对权值进行自适应选取。

1 一维倒数熵的定义及其阈值选取

与之相对应的目标熵(Ho(t))和背景熵(HB(t))分别定义为：

(1)

(2)

最大Shannon熵[7]阈值分割法将目标和背景的信息熵之和作为准则函数，即

H(t)=HO(t)+HB(t)

(3)

(4)

(5)

(6)

倒数熵最优阈值t*选取为：

(7)

2 加权平均倒数熵阈值法

2.1 基于信息熵的阈值分割方法

在上述的基于信息熵的阈值分割方法中，采用的目标函数η1(t)是由KAPUR等[7]提出的目标和背景的信息熵之和，即

η1(t)=HO(t)+HB(t)

(8)

最佳阈值t*通过选取最大化该目标函数来实现，即

(9)

BRINK[16]通过分析二维灰度直方图提出一种对目标熵和背景熵取小的准则函数，该方法通过对背景和目标类中的最小熵进行最大化来寻求最佳分割阈值。基于此，得到另外一种基于信息熵的阈值分割方法，其准则函数η2(t)为：

η2(t)=min(HO(t),HB(t))

最佳阈值t*选取为：

(10)

在实际的图像分割中，KAPUR提出的最大熵阈值法因其对灰度分布的假设最弱，其适应性较强。但在实际情况下其分割效果会比BRINK提出的熵取小法效果差一些[16]。基于此，本研究提出一种能综合最大熵阈值法和熵取小法这2种方法分割性能的新型倒数熵阈值分割法。

2.2 一种新的基于倒数熵的阈值化方法

通过上面对现有的基于信息熵阈值分割方法的分析和比较，本研究提出一种基于倒数熵的加权平均阈值化方法。具体的推导过程如下：

对于任意的2个实函数f1(t)和f2(t)，显然以下的关系成立：

min(f1(t),f2(t))≤mf1(t)+(1-m)f2(t)≤

max(f1(t),f2(t))

(11)

式中：m为权重参数，且0≤m≤1，mf1(t)+(1-m)f2(t)可以看作f1(t)和f2(t)的加权平均。

对于2个非负的函数f′1(t)和f′2(t)，由式(11)可以得出下面的关系式成立：

min(f′1(t),f′2(t))≤mf′1(t)+(1-m)f′2(t)≤f′1(t)+f′2(t)

(11′)

式中：0≤m≤1为权重参数，mf′1(t)+(1-m)

f′2(t)可以看作f′1(t)和f′2(t)的加权平均。

(12)

(13)

由式(12)和以上的分析可以看出，当m=0.5时，加权平均倒数熵阈值法就成为最大倒数熵阈值法，当m=0或m=1时，加权平均倒数熵阈值法就成为倒数熵取小法。进一步分析表明，本文提出的加权平均倒数熵阈值分割法的思路同样适用于Shannon熵、Renyi熵、Tsallis熵阈值分割法，所以本文提出的分割方法可看作是对信息熵阈值分割法的一个补充，熵取小法和最大熵阈值法可看作本研究提出的熵阈值法的特例。

（1984年1月6日讲座，全文略有删节。吴培华教授提供讲座录音，史悠整理，刘祥安教授审阅，在此特申谢忱！）

3 权重参数m的自适应选取

如何选取合适的权重参数m是使用加权平均倒数熵阈值法对图像进行分割的关键。这里采用量子粒子群优化(Quantum-behaved Particle Swann Optimization，QPSO)算法，以均匀性测度[15]作为图像分割质量评价指标，对权重参数m在(0,1)区间进行自适应选取。均匀性测度主要用来衡量区域内的一致性，区域内的均匀性与该区域内的方差成反比，区域内的方差越小，则均匀性测度越大，图像分割效果越好。

假设阈值t将图像分为目标和背景2个不同的区域，分别记为Ri，i= 1, 2，则均匀性测度UM(t)定义为：

(14)

最佳权重参数m*可选为：

(15)

由于m可取(0,1)内的任意实数，穷举搜索算法无法实现，因此采用QPSO优化算法来寻找其最优解。

3.1 基本粒子群优化算法

粒子群优化(Particle Swann Optimization，PSO)算法最早源于对鸟类群体觅食行为的研究，通过模拟鸟群的捕食行为来实现优化问题的求解，它最先由文献[17]提出。PSO算法将每个粒子看作是在多维搜索空间中的一个没有质量和体积的微粒，并在搜索空间中以一定的速度飞行，通过不断迭代趋近于最优解。PSO算法的迭代方程如下：

Vi=ωVi+c1r1(Pi-Xi)+c2r2(Gbest-Xi)

(16)

Xi=Xi+Vi

(17)

式中：惯性因子ω为非负数；2个学习因子c1和c1为非负常数；r1和r2为相互独立的介于(0, 1)之间的随机数；Xi和Vi分别为种群中粒子i的位置和速度；Pi为第i个粒子的最优位置；Gbest为群体中所有粒子的最佳位置。

迭代终止条件通常是根据实际问题设置的最大迭代次数，或粒子群进行搜索时寻找到的满足预先设定的最小适应阈值的最优位置。

3.2 量子粒子群优化算法

在基本PSO算法中，粒子是在经典力学的状态下沿着确定的轨迹飞行，因此粒子搜索的空间是一个有限的区域，因而不能保证一定找到全局最优解。文献[18]将量子理论引入经典PSO算法，提出了一种全局收敛的量子粒子群优化(QPSO)算法。该方法对整个PSO算法的搜索策略进行了改变，其迭代方程中不再需要速度向量，仅需要粒子的位置向量，使得迭代方程的形式更简单，参数更少，因而更容易控制。通过蒙特卡罗随机模拟的方式可得到粒子的位置方程，具体的QPSO算法迭代方程如下：

p=aPi+(1-a)Gbest

(18)

(19)

(20)

(21)

式中：a和u为(0,1)区间的随机数；N为粒子的数目；D为粒子的维数；Pi为第i个粒子的最佳位置；Gbest为群体中所有粒子的最佳位置；p为每个粒子的势中心点；mbest为Pi的均值；β为收缩扩张系数，它是QPSO算法中的一个非常重要的参数。

β随迭代次数从1线性减小到0.5，第t次迭代时的β一般可取为[18]：

(22)

式中：Maxiter为算法的最大迭代次数。

QPSO算法可由以下几个步骤实现：

Step 1：粒子群初始化。对于QPSO 算法，需要初始化的参数有2类：(1)粒子群的规模N、粒子的维数D和最大迭代次数Maxiter；(2)每个粒子的初始位置x。由于参数m是一维的，故粒子群的维数D=1，粒子的个数随机选取，这里选取N=10个粒子，最大迭代次数Maxiter选取为50。每个粒子代表一组参数，第i个粒子的初始位置为xi，其中xi=rand(0,1)。

Step 2：计算10个粒子的适应度值。对于第i个粒子，利用式(13)计算加权平均倒数熵(m=xi)，选取图像最佳阈值；然后再利用式(15)计算对应第i个粒子的适应度值。重复上述过程计算所有粒子的适应度值。

Step 3：将每个粒子的当前适应度值与其所经历过的历史最好位置的适应值进行比较。如果更好，则用当前位置更新个体历史最好位置，反之，保持原来个体历史最好位置不变。

Step 4：将每个粒子的当前适应度值和群体所经历的历史最好位置的适应度值进行比较。若更好，更新群体历史最好位置，反之，保持不变。

Step 5：根据式(20)或式(21)进行粒子位置的更新。

Step 6：根据最大迭代次数或足够好的粒子位置，判断算法是否终止，如果终止条件满足的话，则结束，否则，转Step 2。

4 实验结果与分析

通过对大量不同类型的图像分别进行实验，来说明本文方法的有效性。现选取其中的4幅图像对实验结果加以说明。这4副不同类型的图像分别是普通Lena、光照不均匀Number、局部细节特征较多Cameraman和医学CT图像，如图1所示。图2给出了最大Shannon熵、Kapur最大倒数熵法、Brink倒数熵取小法及本文提出的加权平均倒数熵算法(Weighed Average Reciprocal Entropy, WARE)的分割结果。表1列出了这4种方法的分割阈值及加权平均倒数熵算法中权重参数m的取值。

图1 原图Fig.1 Original images

(a) 最大Shannon熵分割结果

(b) Kapur最大倒数熵法分割结果

(c) Brink倒数熵取小法分割结果

(d) 加权平均倒数熵法分割结果

由图2(a) 的分割结果可以看出，除了普通Lena图像，对于光照不均匀的车牌图像、背景局部细节特征较多的Cameraman图像和医学CT图像，传统的最大Shannon熵方法已经失效，不能对图像实现有效的分割。

由图2(b)和图2(c)可以看出，Kapur最大倒数熵法、Brink倒数熵取小法和传统Shannon法一样，除了对普通Lena图像能够取得比较好的分割效果外，对其他3种不同特征的图像均已失效。而加权调和平均倒数熵阈值法(图2(d)所示)由于充分考虑了目标和背景倒数熵的不同权重，对这几种不同特征的图像都能获得较好的分割效果。

对比普通Lena图像的分割结果，结合表1可以看出，本文提出的加权平均法在权重参数m=0.408 1时，取得最佳阈值t=117，其结果与Kapur法、Brink法和Shannon法的分割效果基本相同。而从光照不均匀的Number图像、局部细节特征较多的Cameraman图像和医学CT图像的分割结果来看，Kapur倒数熵法、Brink倒数熵取小法和最大Shannon熵法已全部失效，不能有效地把目标从图像中提取出来。相反地，因充分考虑到目标和背景类的先验熵对分割作用的不同影响，用加权平均代替算术平均的方法可取得令人满意的分割结果。这也表明，本文提出的加权平均倒数熵法对实际图像的分割具有更好的适应性，可以推广到其他熵阈值的分割方法中。

表1 4种方法的分割阈值Table 1 Comparison of segmentation thresholds by 4 methods

5 结论

本文通过分析传统最大熵阈值分割算法定义域的局限性及目标和背景类对图像分割所起的不同作用，提出了一种基于倒数熵进行加权平均的新型阈值分割算法。该阈值分割法的准则函数是目标和背景信息倒数熵的加权平均。同时，为了寻求最优的权重参数m，采用图像分割均匀性评价准则并结合量子粒子群优化算法进行全局寻优来寻找权重值。大量的实验结果表明，本文提出的加权平均倒数熵方法，能根据实际的图像对权重参数进行自适应选取，比传统熵阈值法能获得更好的分割结果，更具有普遍实用性。