二维Tsallis熵阈值法中基于粒子群优化的参数选取

林爱英， 李 辉， 吴莉莉， 昝红英

(1.河南农业大学 理学院 河南 郑州 450002；2.郑州大学 信息工程学院 河南 郑州 450001)

0 引言

阈值分割因其简单有效而成为广泛使用的图像分割方法，人们对此进行了大量研究[1-3].基于熵概念的阈值选取方法,因其良好的信息论背景颇受关注，其中由Kapur 等[4]较早提出的一维最大Shannon熵阈值法因分割效果较好且实现简单，而成为最具代表性的方法.其后人们基于广义信息论相继提出了Renyi熵[5]、Tsallis熵[6-7]等多种熵阈值分割算法，并推导出相应的二维算法[8-9]，国内也有许多学者对熵阈值分割算法进行了相关的研究[10-11].

通常把Renyi熵和Tsallis熵称为广义信息熵，其信息熵中含有参数，参数的特殊取值可以得到经典的Shannon熵，参数的合理取值可以获得比最大Shannon熵阈值法更好的分割性能，但至今其参数的选取没有一个准则.针对Renyi熵，Sahoo等[8]指出对大部分图像而言，参数q取0.7是一个比较合适的参数值，而对于Tsallis熵，Sahoo等[9]指出，参数q取0.8时能得到较好的分割结果.考虑到实际应用中图像的复杂性，用一个固定的参数值来选取阈值有其局限性，文献[12]给出了一维Renyi熵阈值分割法的一种参数自适应选取思路.考虑到在二维灰度直方图上进行阈值选取，能够利用图像的更多信息，因此主要研究二维Tsallis熵阈值分割方法中参数q的自适应选择问题.

基于均匀性测度作为分割图像质量评价准则，作者利用粒子群优化搜索方法，提出了一种二维Tsallis熵阈值法中参数q的选取方法.实验表明，本文方法可以根据不同的图像自适应的选取参数q，获得较好的图像分割效果.

1 二维Tsallis熵阈值法

对于一幅大小为M×N的数字图像F，用f(x,y)表示图像上坐标为(x,y)的像素点的灰度值，f(x,y)∈G={0,1,…,L-1}，定义坐标为(x,y)的像素点的K×K邻域的平均灰度值g(x,y)为

(1)

其中,[]表示取整运算,K为邻域宽度，一般取奇数,则g(x,y)∈G={0,1,…,L-1}.

如果用r(i,j)表示相对应的灰度值(f=i)-邻域灰度值(g=j)对出现的频次(0≤r(i,j)≤M·N)，定义p(i,j)是灰度级-邻域灰度级对出现的概率

(2)

图1 二维直方图区域划分示意图

根据二维直方图的定义，在阈值(s,t)处将图像分割成如图1所示的4个区域.其中，对角线上的两个区域1和2分别对应于目标和背景，远离对角线的区域3和4对应于边缘和噪声.一般认为在区域3和4上所有的p(i,j)≈0.

由图1可知，利用二维直方图中任意阈值矢量(s,t)对图像进行分割，可将图像分成目标和背景两类区域，分别记为C0和C1，则这两类的先验概率分别为：

(3)

(4)

满足P0(s,t)+P1(s,t)≈1.

(5)

(6)

(s*,t*)=arg max[Hq(s,t)],0≤s,t≤L-1.

(7)

分割后二值图像fT(x,y)的取值为

(8)

一般的，b0取0，b1取255.

如何选取式(7)中的参数q是二维Tsallis熵阈值分割方法的难点，至今尚无明确的解决方案.文献[12]给出了一维Renyi熵阈值分割法的一种参数自适应选取方法，作者受此启发主要研究二维Tsallis熵方法中参数q的自适应选择问题.理论上讲，参数q的取值范围在(0,+∞)，为了获得最优的q值，这里采用粒子群算优化法(particle swarm optimization,PSO)对其进行优化搜索.

2 基于PSO的自适应参数选取

2.1 PSO优化算法

PSO算法最早由Eberhart 等[13]提出，是一种基于鸟类觅食的随机群体搜索过程.设在n维解空间中，有N个粒子组成一个群落，第i个粒子的位置为Xi=(xi1,xi2,…,xin)，“飞翔”速度为Vi=(vi1,vi2,…,vin).前者表示问题的解，将Xi带入一个目标函数,可以计算出其适应值，根据适应值的大小衡量Xi的优劣；后者表示粒子从当前位置移动到下一个位置的速度大小.求解时首先对粒子群的位置和速度进行初始化，然后通过迭代方式在解空间中寻找最优解.假设第i个粒子迄今为止搜索到的最优位置为Pi=(Pi1,Pi2,…,Pin)，称为个体最优极值，整个粒子群迄今为止搜索到的最优位置为G=(g1,g2,…,gn)，称为全局极值.基本PSO采用式(9),(10)对粒子操作[14]

Vi=ω·Vi+c1·r1·(Pi-Xi)+c2·r2·(G-Xi),

(9)

Xi=Xi+Vi,

(10)

其中，惯性因子ω是非负数；学习因子c1和c2是非负常数；r1和r2是介于(0,1)之间的随机数.迭代中止条件根据具体问题一般选为最大迭代次数或粒子群迄今为止搜索到的最优位置满足预定最小适应阈值.基本PSO算法需要用户确定的参数少、操作简单，使用比较方便，但是它容易陷入局部极小点.研究者们提出了自适应调整的策略，即随着迭代的进行，线性地减小ω的值.作者采用这种改进的自适应PSO算法来进行优化搜索.

2.2 自适应PSO参数选取

在文献[8]中指出，Renyi熵的参数q在(0,1)之间，并建议q取经验值0.7，不能随着图像的不同而改变，这在一定程度上就失去了参数熵的优势.在文献[9]中分析了参数q对Tsallis熵阈值分割的影响，但没有给出参数q的选取方法.根据文献[12]，作者通过PSO优化搜索算法对参数q在其取值空间进行全局寻优，以均匀性测度函数UM作为适应度函数对q阈值进行评价，自适应地找出最优的参数q及相应的分割阈值.

均匀性测度是用来评价分割方法性能的一个指标.一个区域内的均匀性与区域内的方差成反比，区域均匀性越好，其灰度分布越集中.均匀性测度可计算为[15]

(11)

其中，Ri表示分割后的第i个区域，i=1,2，Ai表示区域Ri中的像素总个数，C是归一化参数.最优的q取值为

q*=arg max[UM(t(q))],q>0.

(12)

以式(12)作为PSO算法的适应度函数，可以根据不同的图像，在q的变化空间内自适应地搜索参数q的取值，从而进一步确定图像的分割阈值.对于Tsallis熵而言，参数的维数为1.一般的，粒子的个数根据实际应用不同进行选取，选取N=10个粒子来进行搜索，参数空间取(0,1)可以满足要求[7].自适应PSO搜索参数的具体步骤如下.

步骤1：粒子群初始化 对于PSO算法需要确定的参数有：

①粒子的初始位置X及初始速度V：由于每一个粒子代表一组参数，第i个粒子的初始位置为xi，在(0,1)区间随机选取粒子的初始位置.初始速度可以从初始位置中得到，这里选vi=rand(0,1).一般的，为了避免粒子飞行过快，飞过全局最优值，需要设定粒子的最大速度.粒子速度变化范围为[-Vmax,Vmax]，Vmax=0.15.

②学习因子c1和c2：取c1=2.8，c2=1.3.

③惯性因子ω：惯性因子对PSO算法的性能有很大的影响，采用自适应调整惯性因子的方法来控制PSO的整体搜索效率.初始惯性因子选为1.0，随着迭代次数的增加，惯性因子线性地减小，如式(13)所示，

ω(t+1)=ωmax-(ωmax-ωmin)·t/iter,

(13)

其中，ωmax和ωmin分别为权重的最大和最小值.一般的，ωmax=0.95，ωmin=0.4，iter为迭代次数，取iter= 30.

步骤2： 计算每个粒子的适应度值 对于第i个粒子，首先利用(7)式计算二维Tsallis熵(q=xi)，选取图像最佳阈值；然后利用(12)式计算对应第i个粒子的适应度值.重复上述过程计算所有粒子的适应度值.

步骤3： 对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置.

步骤4： 对每个粒子，比较它的适应度值和群体所经历的最好位置的适应度值，如果更好，更新最好位置.

步骤5： 根据(9)和(10)式调整粒子的速度和位置.

步骤6： 如果达到结束条件(足够好的位置或最大迭代次数)，则结束，否则转步骤2.

3 结果与分析

利用上述提出的自适应PSO参数选取方法，对二维Tsallis熵阈值法中的参数进行选取，通过对大量不同类型的灰度图像进行的阈值分割实验发现，相对于参数q取固定值的分割方法[9](q取0.8)，自适应PSO参数选取方法的分割结果更为准确，目标和背景边缘及噪声点的错分大为减少.现给出其中4幅图像两种算法分割的实验结果(图2～图5)，相应的分割阈值及参数q的取值列于表1.

图2 cameraman图像及分割结果

图3 moon图像及分割结果

图4 航拍图像及分割结果

图5 rose图像及分割结果

表1 两种方法的分割阈值及参数q取值比较

从图2(c)，图3(c),图4(c),图5(c)可以看出，基于PSO优化的自适应参数选取法能使分割后的图像区域的内部均匀、边界形状更准确、细节特征更清晰.这是因为本文的分割方法基于图像分割评价准则—均匀度测试准则，致使目标和背景边缘及噪声点的错分大为减少的缘故；从图2(b)～图4(b)可以看出，固定参数选取的分割方法已经不能有效地把目标和背景分割开来，出现了大量的错分点；从图5可以看出，尽管两种方法都能取得比较好的分割结果，但本文的方法在目标和背景边缘处分割效果更好.由表1可以看出，参数q在(0,1)区间变化时，确实可以取得最佳的分割阈值.

4 结论

作者针对二维Tsallis熵阈值法中参数q的选取问题，以图像分割效果评价准则—均匀度测试准则为适应性函数，利用PSO 优化搜索算法，在q的变化空间内进行优化搜索，根据具体的图像自适应地选取参数q，从而得到合适的分割阈值，这种方式更适合图像分割问题的要求.在实际工程应用中，遇到的图像比较复杂，如果对所有图像都使用相同的参数q，必然是不合适的.因此，从理论上来看，结合图像本身的信息，自适应的选取参数的方法可以更好地发挥参数熵的优势，本文的实验结果也验证了这一观点.

[1] Lee S U,Chung S Y.A comparative performance study of several global thresholding techniques for segmentation[J].Computer Vision,Graphics and Image Processing,1990,52(2): 171-190.

[2] Shaoo P K,Soltani S,Wong A K C.A survey of thresholding techniques[J].Computer Vision,Graphics and Image Processing,1988,41(2): 233-260.

[3] 闫成新,孙亮.图像过渡区直接提取与分割快速算法[J].郑州大学学报:理学版,2006,38(4): 74-77.

[4] Kapur N,Sahoo P K,Wong A K C.A new method for gray-level picture thresholding using the entropy of the histogram[J].Computer Vision,Graphics,and Image Processing,1985,29(3):273-285.

[5] Sahoo P K,Wilkins C,Yeage J.Threshold selection using Renyi’s entropy[J].Pattern Recognition,1997,30(1): 71-84.

[6] Tsallis C.Nonextensive physics: a possible connection between generalized statistical mechanics and quantum group[J].Physics Lett A,1994,195(5/6):329-334.

[7] Portes de Albuquerque M,Esquef I A,Gesualdi Mello A R.Image thresholding using Tsallis entropy[J].Pattern Recognition Letters,2004,25(9):1059-1065.

[8] Sahoo P K,Arora G.A thresholding method based on two-dimensional Renyi’s entropy[J].Pattern Recognition,2004,37(16):1149-1161.

[9] Sahoo P K,Arora G.Image thresholding using two-dimensional Tsallis-Havrda-Charvat entropy[J].Pattern Recognition Letters,2006,27(6): 520-528.

[10] 吴一全,潘喆.二维Tsallis-Havard-Charvat熵值分割的快速递推算法[J].信号处理,2009,25(4): 665-668.

[11] 张毅军,吴雪菁,夏良正.二维图像阈值分割的快速递推算法[J].模式识别与人工智能,1997,10(3):259-264.

[12] 雷博,范九伦.一维Renyi 熵阈值法中参数的自适应选取[J].光子学报,2009,38(9): 2439-2442.

[13] Eberhart R C,Kermedy J.A new optimizer using particles swarm theory[C]//Proceedings of Sixth International Symposium on Micro Machine and Human Science.Nagoya,1995: 39-43.

[14] Eberhart R C,Shi Y H.Tracking and optimizing dynamic systems with particle swarms[C]//Proceedings of the Congress on Evolutionary Computation.Seoul,2001: 94-100.

[15] 章毓晋.图像分割评价技术分类和比较[J].中国图象图形学报,1996,1(2): 151-158.