二維Tsallis熵閾值法中基于粒子群優(yōu)化的參數(shù)選取

林愛(ài)英， 李 輝， 吳莉莉， 昝紅英

(1.河南農(nóng)業(yè)大學(xué) 理學(xué)院 河南 鄭州 450002；2.鄭州大學(xué) 信息工程學(xué)院 河南 鄭州 450001)

0 引言

閾值分割因其簡(jiǎn)單有效而成為廣泛使用的圖像分割方法，人們對(duì)此進(jìn)行了大量研究[1-3].基于熵概念的閾值選取方法,因其良好的信息論背景頗受關(guān)注，其中由Kapur 等[4]較早提出的一維最大Shannon熵閾值法因分割效果較好且實(shí)現(xiàn)簡(jiǎn)單，而成為最具代表性的方法.其后人們基于廣義信息論相繼提出了Renyi熵[5]、Tsallis熵[6-7]等多種熵閾值分割算法，并推導(dǎo)出相應(yīng)的二維算法[8-9]，國(guó)內(nèi)也有許多學(xué)者對(duì)熵閾值分割算法進(jìn)行了相關(guān)的研究[10-11].

通常把Renyi熵和Tsallis熵稱為廣義信息熵，其信息熵中含有參數(shù)，參數(shù)的特殊取值可以得到經(jīng)典的Shannon熵，參數(shù)的合理取值可以獲得比最大Shannon熵閾值法更好的分割性能，但至今其參數(shù)的選取沒(méi)有一個(gè)準(zhǔn)則.針對(duì)Renyi熵，Sahoo等[8]指出對(duì)大部分圖像而言，參數(shù)q取0.7是一個(gè)比較合適的參數(shù)值，而對(duì)于Tsallis熵，Sahoo等[9]指出，參數(shù)q取0.8時(shí)能得到較好的分割結(jié)果.考慮到實(shí)際應(yīng)用中圖像的復(fù)雜性，用一個(gè)固定的參數(shù)值來(lái)選取閾值有其局限性，文獻(xiàn)[12]給出了一維Renyi熵閾值分割法的一種參數(shù)自適應(yīng)選取思路.考慮到在二維灰度直方圖上進(jìn)行閾值選取，能夠利用圖像的更多信息，因此主要研究二維Tsallis熵閾值分割方法中參數(shù)q的自適應(yīng)選擇問(wèn)題.

基于均勻性測(cè)度作為分割圖像質(zhì)量評(píng)價(jià)準(zhǔn)則，作者利用粒子群優(yōu)化搜索方法，提出了一種二維Tsallis熵閾值法中參數(shù)q的選取方法.實(shí)驗(yàn)表明，本文方法可以根據(jù)不同的圖像自適應(yīng)的選取參數(shù)q，獲得較好的圖像分割效果.

1 二維Tsallis熵閾值法

對(duì)于一幅大小為M×N的數(shù)字圖像F，用f(x,y)表示圖像上坐標(biāo)為(x,y)的像素點(diǎn)的灰度值，f(x,y)∈G={0,1,…,L-1}，定義坐標(biāo)為(x,y)的像素點(diǎn)的K×K鄰域的平均灰度值g(x,y)為

(1)

其中,[]表示取整運(yùn)算,K為鄰域?qū)挾龋话闳∑鏀?shù),則g(x,y)∈G={0,1,…,L-1}.

如果用r(i,j)表示相對(duì)應(yīng)的灰度值(f=i)-鄰域灰度值(g=j)對(duì)出現(xiàn)的頻次(0≤r(i,j)≤M·N)，定義p(i,j)是灰度級(jí)-鄰域灰度級(jí)對(duì)出現(xiàn)的概率

(2)

圖1 二維直方圖區(qū)域劃分示意圖

根據(jù)二維直方圖的定義，在閾值(s,t)處將圖像分割成如圖1所示的4個(gè)區(qū)域.其中，對(duì)角線上的兩個(gè)區(qū)域1和2分別對(duì)應(yīng)于目標(biāo)和背景，遠(yuǎn)離對(duì)角線的區(qū)域3和4對(duì)應(yīng)于邊緣和噪聲.一般認(rèn)為在區(qū)域3和4上所有的p(i,j)≈0.

由圖1可知，利用二維直方圖中任意閾值矢量(s,t)對(duì)圖像進(jìn)行分割，可將圖像分成目標(biāo)和背景兩類區(qū)域，分別記為C0和C1，則這兩類的先驗(yàn)概率分別為：

(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)中的參數(shù)q是二維Tsallis熵閾值分割方法的難點(diǎn)，至今尚無(wú)明確的解決方案.文獻(xiàn)[12]給出了一維Renyi熵閾值分割法的一種參數(shù)自適應(yīng)選取方法，作者受此啟發(fā)主要研究二維Tsallis熵方法中參數(shù)q的自適應(yīng)選擇問(wèn)題.理論上講，參數(shù)q的取值范圍在(0,+∞)，為了獲得最優(yōu)的q值，這里采用粒子群算優(yōu)化法(particle swarm optimization,PSO)對(duì)其進(jìn)行優(yōu)化搜索.

2 基于PSO的自適應(yīng)參數(shù)選取

2.1 PSO優(yōu)化算法

PSO算法最早由Eberhart 等[13]提出，是一種基于鳥(niǎo)類覓食的隨機(jī)群體搜索過(guò)程.設(shè)在n維解空間中，有N個(gè)粒子組成一個(gè)群落，第i個(gè)粒子的位置為Xi=(xi1,xi2,…,xin)，“飛翔”速度為Vi=(vi1,vi2,…,vin).前者表示問(wèn)題的解，將Xi帶入一個(gè)目標(biāo)函數(shù),可以計(jì)算出其適應(yīng)值，根據(jù)適應(yīng)值的大小衡量Xi的優(yōu)劣；后者表示粒子從當(dāng)前位置移動(dòng)到下一個(gè)位置的速度大小.求解時(shí)首先對(duì)粒子群的位置和速度進(jìn)行初始化，然后通過(guò)迭代方式在解空間中尋找最優(yōu)解.假設(shè)第i個(gè)粒子迄今為止搜索到的最優(yōu)位置為Pi=(Pi1,Pi2,…,Pin)，稱為個(gè)體最優(yōu)極值，整個(gè)粒子群迄今為止搜索到的最優(yōu)位置為G=(g1,g2,…,gn)，稱為全局極值.基本PSO采用式(9),(10)對(duì)粒子操作[14]

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

(9)

Xi=Xi+Vi,

(10)

其中，慣性因子ω是非負(fù)數(shù)；學(xué)習(xí)因子c1和c2是非負(fù)常數(shù)；r1和r2是介于(0,1)之間的隨機(jī)數(shù).迭代中止條件根據(jù)具體問(wèn)題一般選為最大迭代次數(shù)或粒子群迄今為止搜索到的最優(yōu)位置滿足預(yù)定最小適應(yīng)閾值.基本PSO算法需要用戶確定的參數(shù)少、操作簡(jiǎn)單，使用比較方便，但是它容易陷入局部極小點(diǎn).研究者們提出了自適應(yīng)調(diào)整的策略，即隨著迭代的進(jìn)行，線性地減小ω的值.作者采用這種改進(jìn)的自適應(yīng)PSO算法來(lái)進(jìn)行優(yōu)化搜索.

2.2 自適應(yīng)PSO參數(shù)選取

在文獻(xiàn)[8]中指出，Renyi熵的參數(shù)q在(0,1)之間，并建議q取經(jīng)驗(yàn)值0.7，不能隨著圖像的不同而改變，這在一定程度上就失去了參數(shù)熵的優(yōu)勢(shì).在文獻(xiàn)[9]中分析了參數(shù)q對(duì)Tsallis熵閾值分割的影響，但沒(méi)有給出參數(shù)q的選取方法.根據(jù)文獻(xiàn)[12]，作者通過(guò)PSO優(yōu)化搜索算法對(duì)參數(shù)q在其取值空間進(jìn)行全局尋優(yōu)，以均勻性測(cè)度函數(shù)UM作為適應(yīng)度函數(shù)對(duì)q閾值進(jìn)行評(píng)價(jià)，自適應(yīng)地找出最優(yōu)的參數(shù)q及相應(yīng)的分割閾值.

均勻性測(cè)度是用來(lái)評(píng)價(jià)分割方法性能的一個(gè)指標(biāo).一個(gè)區(qū)域內(nèi)的均勻性與區(qū)域內(nèi)的方差成反比，區(qū)域均勻性越好，其灰度分布越集中.均勻性測(cè)度可計(jì)算為[15]

(11)

其中，Ri表示分割后的第i個(gè)區(qū)域，i=1,2，Ai表示區(qū)域Ri中的像素總個(gè)數(shù)，C是歸一化參數(shù).最優(yōu)的q取值為

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

(12)

以式(12)作為PSO算法的適應(yīng)度函數(shù)，可以根據(jù)不同的圖像，在q的變化空間內(nèi)自適應(yīng)地搜索參數(shù)q的取值，從而進(jìn)一步確定圖像的分割閾值.對(duì)于Tsallis熵而言，參數(shù)的維數(shù)為1.一般的，粒子的個(gè)數(shù)根據(jù)實(shí)際應(yīng)用不同進(jìn)行選取，選取N=10個(gè)粒子來(lái)進(jìn)行搜索，參數(shù)空間取(0,1)可以滿足要求[7].自適應(yīng)PSO搜索參數(shù)的具體步驟如下.

步驟1：粒子群初始化 對(duì)于PSO算法需要確定的參數(shù)有：

①粒子的初始位置X及初始速度V：由于每一個(gè)粒子代表一組參數(shù)，第i個(gè)粒子的初始位置為xi，在(0,1)區(qū)間隨機(jī)選取粒子的初始位置.初始速度可以從初始位置中得到，這里選vi=rand(0,1).一般的，為了避免粒子飛行過(guò)快，飛過(guò)全局最優(yōu)值，需要設(shè)定粒子的最大速度.粒子速度變化范圍為[-Vmax,Vmax]，Vmax=0.15.

②學(xué)習(xí)因子c1和c2：取c1=2.8，c2=1.3.

③慣性因子ω：慣性因子對(duì)PSO算法的性能有很大的影響，采用自適應(yīng)調(diào)整慣性因子的方法來(lái)控制PSO的整體搜索效率.初始慣性因子選為1.0，隨著迭代次數(shù)的增加，慣性因子線性地減小，如式(13)所示，

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

(13)

其中，ωmax和ωmin分別為權(quán)重的最大和最小值.一般的，ωmax=0.95，ωmin=0.4，iter為迭代次數(shù)，取iter= 30.

步驟2： 計(jì)算每個(gè)粒子的適應(yīng)度值 對(duì)于第i個(gè)粒子，首先利用(7)式計(jì)算二維Tsallis熵(q=xi)，選取圖像最佳閾值；然后利用(12)式計(jì)算對(duì)應(yīng)第i個(gè)粒子的適應(yīng)度值.重復(fù)上述過(guò)程計(jì)算所有粒子的適應(yīng)度值.

步驟3： 對(duì)于每個(gè)粒子，將其適應(yīng)值與所經(jīng)歷過(guò)的最好位置的適應(yīng)值進(jìn)行比較，如果更好，則將其作為粒子的個(gè)體歷史最優(yōu)值，用當(dāng)前位置更新個(gè)體歷史最好位置.

步驟4： 對(duì)每個(gè)粒子，比較它的適應(yīng)度值和群體所經(jīng)歷的最好位置的適應(yīng)度值，如果更好，更新最好位置.

步驟5： 根據(jù)(9)和(10)式調(diào)整粒子的速度和位置.

步驟6： 如果達(dá)到結(jié)束條件(足夠好的位置或最大迭代次數(shù))，則結(jié)束，否則轉(zhuǎn)步驟2.

3 結(jié)果與分析

利用上述提出的自適應(yīng)PSO參數(shù)選取方法，對(duì)二維Tsallis熵閾值法中的參數(shù)進(jìn)行選取，通過(guò)對(duì)大量不同類型的灰度圖像進(jìn)行的閾值分割實(shí)驗(yàn)發(fā)現(xiàn)，相對(duì)于參數(shù)q取固定值的分割方法[9](q取0.8)，自適應(yīng)PSO參數(shù)選取方法的分割結(jié)果更為準(zhǔn)確，目標(biāo)和背景邊緣及噪聲點(diǎn)的錯(cuò)分大為減少.現(xiàn)給出其中4幅圖像兩種算法分割的實(shí)驗(yàn)結(jié)果(圖2～圖5)，相應(yīng)的分割閾值及參數(shù)q的取值列于表1.

圖2 cameraman圖像及分割結(jié)果

圖3 moon圖像及分割結(jié)果

圖4 航拍圖像及分割結(jié)果

圖5 rose圖像及分割結(jié)果

表1 兩種方法的分割閾值及參數(shù)q取值比較

從圖2(c)，圖3(c),圖4(c),圖5(c)可以看出，基于PSO優(yōu)化的自適應(yīng)參數(shù)選取法能使分割后的圖像區(qū)域的內(nèi)部均勻、邊界形狀更準(zhǔn)確、細(xì)節(jié)特征更清晰.這是因?yàn)楸疚牡姆指罘椒ɑ趫D像分割評(píng)價(jià)準(zhǔn)則—均勻度測(cè)試準(zhǔn)則，致使目標(biāo)和背景邊緣及噪聲點(diǎn)的錯(cuò)分大為減少的緣故；從圖2(b)～圖4(b)可以看出，固定參數(shù)選取的分割方法已經(jīng)不能有效地把目標(biāo)和背景分割開(kāi)來(lái)，出現(xiàn)了大量的錯(cuò)分點(diǎn)；從圖5可以看出，盡管兩種方法都能取得比較好的分割結(jié)果，但本文的方法在目標(biāo)和背景邊緣處分割效果更好.由表1可以看出，參數(shù)q在(0,1)區(qū)間變化時(shí)，確實(shí)可以取得最佳的分割閾值.

4 結(jié)論

作者針對(duì)二維Tsallis熵閾值法中參數(shù)q的選取問(wèn)題，以圖像分割效果評(píng)價(jià)準(zhǔn)則—均勻度測(cè)試準(zhǔn)則為適應(yīng)性函數(shù)，利用PSO 優(yōu)化搜索算法，在q的變化空間內(nèi)進(jìn)行優(yōu)化搜索，根據(jù)具體的圖像自適應(yīng)地選取參數(shù)q，從而得到合適的分割閾值，這種方式更適合圖像分割問(wèn)題的要求.在實(shí)際工程應(yīng)用中，遇到的圖像比較復(fù)雜，如果對(duì)所有圖像都使用相同的參數(shù)q，必然是不合適的.因此，從理論上來(lái)看，結(jié)合圖像本身的信息，自適應(yīng)的選取參數(shù)的方法可以更好地發(fā)揮參數(shù)熵的優(yōu)勢(shì)，本文的實(shí)驗(yàn)結(jié)果也驗(yàn)證了這一觀點(diǎn).

[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] 閆成新,孫亮.圖像過(guò)渡區(qū)直接提取與分割快速算法[J].鄭州大學(xué)學(xué)報(bào):理學(xué)版,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].信號(hào)處理,2009,25(4): 665-668.

[11] 張毅軍,吳雪菁,夏良正.二維圖像閾值分割的快速遞推算法[J].模式識(shí)別與人工智能,1997,10(3):259-264.

[12] 雷博,范九倫.一維Renyi 熵閾值法中參數(shù)的自適應(yīng)選取[J].光子學(xué)報(bào),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] 章毓晉.圖像分割評(píng)價(jià)技術(shù)分類和比較[J].中國(guó)圖象圖形學(xué)報(bào),1996,1(2): 151-158.