基于灰度-梯度二維對稱Tsallis交叉熵的閾值分割

朱 磊，吉 峰，白瑞林

ZHU Lei1,JI Feng2,BAI Ruilin1

1.江南大學 輕工過程先進控制教育部重點實驗室 信息與控制實驗教學中心，江蘇 無錫214122

2.無錫信捷電氣股份有限公司，江蘇 無錫214072

1.Information and Control Experiment Teaching Center, Key Laboratory of Advanced Process Control for Light Industry（Ministry of Education）,Jiangnan University,Wuxi,Jiangsu 214122,China

2.Xinje Electronic Co.,Ltd.,Wuxi,Jiangsu 214072,China

1 引言

圖像分割是機器視覺檢測系統的前期處理技術，其目的是從復雜的背景中分離出感興趣的目標區域，以便后續目標識別。其中，閾值分割是一類簡單實用的圖像分割方法。根據分割的空間特性，可以把閾值分割分為全局閾值和局部閾值兩大類。全局閾值分割法因其實現簡單、實時性較高等特點，得到了廣泛的應用[1-2]。基于信息熵概念（例如最大熵[3]、最小交叉熵[4]、Tsallis 熵等）的閾值分割法是近來研究的熱點。Albuquerque 等[5]首先利用Tsallis 熵的非廣延性，提出帶有調節參數的一維Tsallis 熵閾值分割法，該方法具有較強的普適性且比傳統最大熵更為有效。唐英干等[6]把最小交叉熵與Tsallis 熵相結合，同時考慮目標和背景之間的信息量差異和相關性信息，提出一維最小Tsallis 交叉熵閾值分割法，取得了良好的分割效果。但是基于一維直方圖的方法對背景復雜或者噪聲較強的圖像分割效果往往較差，因此研究人員開始不僅考慮像素點的灰度信息還考慮像素點鄰域的均值、中值等信息，即通過二維直方圖搜尋最佳閾值。Sahoo 等[7]將一維Tsallis 熵閾值分割法拓展到灰度級-平均灰度級二維直方圖上，利用圖像的鄰域空間信息，提高了算法的分割效果，但是二維運算量呈指數上升，難以滿足實時性。為了解決這一問題，朱煒等[8]提出基于粒子群優化算法的二維Tsallis 熵閾值分割法。吳一全等[9]則提出基于斜分策略的二維Tsallis 熵閾值分割法，采用與主對角線垂直的斜線按灰度級與平均灰度級之和大小來進行分割，提高了分割效果，并引入遞推算法加快了運算速度，但此斜分法普遍性不強[10]。唐英干等[11]不僅考慮像素之間的空間鄰域信息，而且考慮了目標和背景之間的相互關系，提出二維Tsallis 交叉熵閾值分割法，并采用粒子群優化算法尋找最佳閾值，大大提高了算法的分割效果和實時性。

然而，二維Tsallis 交叉熵閾值分割法存在著如下不足之處：（1）通過灰度級-平均灰度級直方圖來計算最佳閾值，只考慮了沿主對角線的兩個區域，忽略了其他兩個區域應予考慮的目標點和背景點，勢必影響分割效果，甚至造成錯分；（2）基本粒子群算法搜尋最佳閾值存在后期收斂速度慢和精度低等特點，并且在迭代計算適應度函數時存在著大量冗余計算，因此運行效率仍有待進一步提高。對于第一個問題可以引入其他變量構建二維直方圖，盡可能多地考慮所有的目標點和背景點，提高圖像分割的效果；對于第二個問題可以采用搜索精度更高和速度更快的優化算法，并在計算適應度函數時采用某種快速運算方法，以其降低計算的復雜度。

基于以上考慮，引入梯度變量構建新的二維直方圖，并在一維對稱Tsallis 交叉熵的基礎上導出二維對稱Tsallis 交叉熵閾值選取公式。采用新的灰度-梯度二維直方圖，充分考慮像素之間的鄰域梯度信息，摒棄傳統二維直方圖的近似假設，使圖像分割更為準確，同時縮小遍歷的解空間，提高算法的運行效率。另外，采用基于tent 映射的混沌小生境粒子群優化算法搜尋二維最佳閾值向量，克服基本粒子群算法的缺陷，并在計算適應度函數時引入快速遞推算法，進一步提高了算法的實時性。

2 基于灰度-梯度二維對稱Tsallis交叉熵的閾值分割

2.1 灰度-梯度二維直方圖

設一幅大小為M×N圖像的灰度級f(x,y)取0,1,…,L-1，采用8鄰域模板濾波得到平均灰度級g(x,y)。傳統的二維直方圖都是由灰度級f(x,y)和平均灰度級g(x,y)構建而成。如圖1（a）所示，主對角線區域0 和區域1 分別對應目標點和背景點；而區域2 和區域3 對應邊緣點及噪聲點。基于該傳統直方圖的二維Tsallis 交叉熵閾值分割法假設二維直方圖中遠離主對角線的分量近似為0，即忽略區域2 和3 這兩個部分的目標點和背景點。這樣的二維直方圖必然會丟失少量或者部分目標點和背景點。若采用灰度-梯度直方圖及其區域劃分方式可以彌補這一缺陷，提高分割閾值的準確性。如圖1（b）所示，橫坐標為像素的灰度級與平均灰度級的均值，即為[f(x,y)+g(x,y)]/2，縱坐標則取該像素的鄰域梯度，這里用像素灰度級和平均灰度級的絕對差|f(x,y)-g(x,y)|表示。可見，這種二維直方圖既對噪聲圖像有平滑作用，又可以使圖像邊緣及細節分割的更加準確。若用h(i,j)表示該二元組([f(x,y)+g(x,y)]/2=i,|f(x,y)-g(x,y)=j|)出現的頻數，則發生的聯合概率為：

圖1 傳統與灰度-梯度二維直方圖

{p(i,j)}即為灰度-梯度二維直方圖。這里M×N為圖像的總像素點數；i=0,1,…,H；j=0,1,…,W，H和W分別為最大的平均值和最大鄰域梯度。

若(t,s)是待選取的閾值向量，(t,s)把灰度-梯度二維直方圖劃分為四部分，如圖1（b）所示。區域0 和區域1 的鄰域梯度較小，即灰度級與平均灰度級相近，因此分別對應目標點和背景點；區域2 和區域3 的鄰域梯度較大，即灰度級與平均灰度級相差較大，因此對應邊緣點及噪聲點。如圖1（c）所示，為Lena 圖像的灰度-梯度二維直方圖，在區域0 和1 存在聯合概率高峰，因目標點和背景點的鄰域梯度較小，數量在圖像中占較大比例；區域2 和3 則存在聯合概率低谷，因邊緣點和噪聲點的鄰域梯度較大，數量在圖像中占較小比例。可見，這種新的灰度-梯度二維直方圖比傳統直方圖更加全面地考慮了背景類和目標類的內部點，可以提高分割的效果，而鄰域梯度的最大值W往往遠小于最大灰度級L-1，所以遍歷的解空間大大縮減，可以進一步提高了算法的運行效率。

2.2 對稱Tsallis交叉熵的閾值分割

將新的灰度-梯度直方圖運用到對稱Tsallis 交叉熵閾值選取中，導出算法的相關計算公式。設(t,s)為灰度和梯度構成的閾值向量，二維直方圖1（b）中區域0（目標類）和區域1（背景類）的概率分別為po(t,s) 和pb(t,s)，則

式中，t為灰度（均值）分割閾值，s為鄰域梯度分割閾值，且0 ≤t≤H，0 ≤s≤W。區域0 和區域1 的均值向量μo(t,s)和μb(t,s)分別為：

將文獻[12]中一維對稱Tsallis 交叉熵的準則函數推廣到二維，則基于灰度-梯度直方圖的二維對稱Tsallis交叉熵的閾值選取準則函數Φ(t,s)為：

其中參數q通常取0.8 最佳，準則函數Φ(t,s)越小，分割前后圖像之間的差異性就越小。當二維對稱Tsallis 交叉熵達到最小時，取得最佳閾值向量(t*,s*)，即

基于灰度-梯度直方圖的二維對稱Tsallis 交叉熵閾值分割法求解二維最佳閾值向量，其優點在于不僅考慮了目標和背景之間的信息量差異，使分割前后圖像之間的誤差最小，而且考慮了相關性信息，使類內灰度更加均勻，因此提高了分割的準確性。但是從上面準則函數公式Φ(t,s)可以看出，該方法和基于傳統二維直方圖的Tsallis 交叉熵閾值分割法同樣具有較高的計算復雜度。因此，本文引入快速遞推算法對其相關量進行計算，以此減少其運算量。

從上述公式（5）、（7）以及（8）可知，實際需要計算的相關量為以及。由于涉及的相關量較多，在此以po(t,s)和αoi(t,s)兩個量為例給出快速遞推計算公式。

對于每次計算po(t,s)和αoi(t,s)兩個量可以利用前面已經得到的po(t-1,s)和αoi(t-1,s)以及當前的ps(t)和αs(t)，而ps(t)和αs(t)是通過計算每一列值累加算出，總共H+1 列，不用每次重新逐點計算。類似地，可以遞推計算以及。通過這樣的快速遞推計算，可以降低目標準則函數的計算復雜度，提高了算法的運行效率。

3 對稱Tsallis 交叉熵的閾值分割的混沌小生境粒子群優化算法

粒子群算法是模擬鳥集群飛行覓食行為的群智能演化方法，它能夠以較大概率搜索到目標函數的全局最優解。設在n維搜索空間中，向量Xi=(xi1,xi2,…,xin)表示為第i個粒子位置，向量Vi=(vi1,vi2,…,vin)表示為第i個粒子速度。對稱Tsallis 交叉熵準則函數Φ(t,s)作為評價粒子優劣的適應度函數，迭代搜索整個解空間。在迭代搜索過程中，粒子通過兩個最優解更新當前的位置和速度，設Pi(k)為粒子i的歷史最優解，Pg(k)為當前粒子群的全局最優解。基本粒子群算法的位置和速度迭代公式如下：

其中，k為迭代次數；c1和c2為學習因子，一般取c1=c2=2；r1和r2為（0，1）上的隨機數；w為慣性因子，它對粒子的全局和局部搜索能力有著較大的影響，因此本文采用線性遞減方式來調節慣性因子：

其中，kmax為最大迭代次數，設最大慣性因子wmax=0.95，最小慣性因子wmin=0.40，迭代時粒子速率取值范圍為[Vmin,Vmax]，Vmin=Vmax=10。

上述基本粒子群算法雖簡單，但是容易陷入局部最優解，難以保證收斂到全局最優解。此外基本粒子群算法還存在著后期搜索精度低和收斂速度慢等缺陷。為了彌補基本粒子群算法這一缺陷，結合小生境進化策略與混沌變異的隨機性和遍歷性，以提高搜索的精度以及速度。小生境進化策略是把粒子群分為幾個子種群，通過子種群之間的歐式距離來控制其競爭，形成各個子種群局部極值同步搜索，避免粒子的早熟；同時在搜索過程中引入混沌變異，使粒子快速跳出局部極值。由于tent 映射具有相對較高的尋優效率，因此本文采用基于tent映射的混沌小生境粒子群優化算法搜尋二維最佳閾值向量。tent映射方程表示為：

由于上述tent 映射存在小周期點和不穩定點的不足，當達到小周期點(0.2,0.4,0.6,0.8) 或者不穩定點(0,0.25,0.50,0.75)時，再次采用如下擾動方程：

其中，λ為收縮因子，e為粒子群的進化代數，u為控制收縮速度，一般取2。

基于tent 映射的混沌小生境粒子群優化算法搜尋二維最佳閾值向量步驟如下：

步驟1初始化混沌小生境粒子種群。隨機產生K個粒子（本文取12），并把這些粒子分成C（本文取4）個子種群，粒子位置是像素灰度和梯度構成的向量，粒子速度在[Vmin,Vmax]范圍內隨機產生。

步驟2根據式（5）計算每個粒子的適應度函數值，該適應度函數值由快速遞推算法計算得到，然后找出每個小生境種群中的最優粒子和全局最優粒子。

步驟3計算兩個子種群最優個體之間的歐式距離D。當D＜R（R為小生境半徑，本文取）時，對小生境最優個體的適應度函數值低者置零，并對置零和最劣粒子重新初始化，直至任意兩個小生境最優個體之間的距離D≥R。

步驟4按式（11）至（13）對所有小生境最優個體進行tent映射的混沌迭代變異，重新計算其適應度函數值，若大于原適應度函數值，則更新當前最優個體的位置。

步驟5按式（9）和式（10）更新每個粒子的位置和速度。

步驟6當達到最大迭代次數，得到最佳閾值進行圖像分割；否則返回步驟2。

4 實驗結果及分析

為了驗證算法的有效性，本文針對大量各種典型圖像進行了仿真實驗，并將本文方法分別與基于灰度級-平均灰度級直方圖的二維Tsallis 交叉熵法、二維斜分對稱Tsallis交叉熵法[12]以及最近提出的二維Otsu 準分法[14]在分割效果和運行時間上進行對比。這里，算法的硬件運行環境為Intel Pentium?CPU E6700 3.2 GHz，2 GB內存，軟件編程語言為Matlab2011b。

選取五幅圖像加以說明，這五幅圖像分別為米粒圖像（257×257）、辣椒圖像（200×200）、建筑圖像（600×600）、火焰圖像（309×226）以及紅外圖像（210×192）。如圖2～6所示，從上至下依次是原始圖像、文獻[11]的分割結果、文獻[12]的分割結果、[14]的分割結果以及本文方法的分割結果。相應的分割閾值向量和運行時間見表1。

圖2 原始圖像

圖3 文獻[11]分割結果

圖4 文獻[12]分割結果

圖5 文獻[14]分割結果

圖6 本文分割結果

（1）圖像分割效果對比。對于背景光照不均勻的多目標米粒圖像，二維Tsallis 交叉熵法和二維Otsu 準分法雖然較為準確地分割出了下半部分目標，但是在上半部分都存在著嚴重的錯分，抗噪性能較差，從而無法識別米粒目標，二維斜分對稱Tsallis 交叉熵法卻丟失了下方米粒目標，而本文方法準確得分割出了各個米粒，分割效果較好；對于背景較為復雜的辣椒圖像，二維Tsallis交叉熵法和二維斜分對稱Tsallis 交叉熵法分割出了較大的辣椒目標，但是局部較小辣椒目標分割效果不佳，二維Otsu 準分法優于上述方法，但是前景中的較大辣椒目標邊緣分割不夠準確，而本文方法對辣椒邊緣分割更加準確，特別是對局部小目標的辣椒；對于灰度分布不均勻的建筑圖像，二維Tsallis 交叉熵法分割效果不好，在墻壁上產生了大面積的錯分，二維Otsu 準分法效果有所改善，但是在圖像上方產生陰影，同時圖像右側的墻壁并未有效地分割出來，而二維斜分對稱Tsallis 交叉熵法和本文方法比較準確地分割出了房屋的邊界，不足之處在于瓦片紋理未能分割出來；對于模糊的火焰圖像，二維Tsallis 交叉熵法丟失了左上方火焰目標，且對火焰的邊緣分割不夠準確，二維斜分對稱Tsallis 交叉熵法和二維Otsu 準分法分割效果相對較為優秀，而本文方法對火焰的分割更為精確；對于紅外小目標圖像，二維Tsallis交叉熵法和二維斜分對稱Tsallis 交叉熵法均未能準確提取出圖像中的人物，存在大量的誤分現象，二維Otsu準分法分割效果較差，產生大面積陰影部分，而本文方法十分準確地提取出了三個人物目標，分割效果良好。從上述實驗得出，本文方法在分割性能上有著明顯的優勢，尤其是對米粒、紅外等這樣的小目標圖像。

（2）運行時間對比。在本文測試中，基于灰度級-平均灰度級直方圖的二維Tsallis 交叉熵法采用粒子群算法搜尋二維最佳閾值向量，其迭代次數為50 次，而經過多次運行，本文基于tent 映射的混沌小生境粒子群優化算法僅需迭代20 次就可以搜尋到全局最優解。由表1可以看出，本文方法的運行時間比基于傳統直方圖的二維Tsallis 交叉熵法運行時間提高了30 倍，比二維斜分對稱Tsallis 交叉熵法快了1 倍左右，比二維Otsu 準分法快了至少40%以上。可見本文方法在實時性方面有很明顯的優勢。這是因為：（1）在灰度-梯度二維直方圖中，鄰域梯度的最大值與最大灰度級相比很小，大大縮減了解空間的搜索范圍；（2）采用了混沌小生境粒子群優化算法，提高了閾值搜索的速度。同時，快速遞推算法在迭代計算適應度函數中降低了計算的復雜度，使得算法的實時性進一步提高。

表1 四種算法的閾值向量和運行時間

（3）圖像分割質量評價。本文采用均勻性測度作為衡量圖像分割結果的性能評價標準。在閾值分割中，均勻性測度是衡量兩個區域內部的均勻性程度，其大小在一定程度上反映了閾值分割方法的優劣，認為測度越大，分割效果越好。基于灰度級-平均灰度級的二維Tsallis 交叉熵法和二維Otsu 準分法的二維閾值向量采用向量中較小的一個作為關鍵閾值，對其進行均勻性測度的計算，而本文灰度-梯度二維對稱Tsallis 交叉熵閾值分割法采用閾值向量中的第一個為關鍵閾值。四種算法相應的均勻性測度位于表2，在表中可以看出從評價準則角度可以得出本文方法優于其他三種方法，同時也說明了該方法使得類內的灰度更加均勻。

表2 四種算法的均勻性測度

5 結論

本文提出的基于灰度-梯度二維對稱Tsallis 交叉熵的閾值分割法充分利用了鄰域像素的灰度信息，也考慮了與邊緣輪廓相關的鄰域梯度信息，在一定程度上彌補了傳統灰度級-平均灰度級直方圖的近似錯分問題，并且通過混沌小生境粒子群優化算法在迭代計算適應度函數值時，引入快速遞推算法，提高了實時性。仿真結果表明，本文方法不僅提升了算法的實際分割效果，而且提高了算法的運行效率，因此該方法具有較高的實用價值。此外，本文方法還可以推廣到其他二維閾值分割方法中中去。為了進一步滿足實際應用，實現對非均勻光照、灰度分布不均勻圖像的有效分割還可以將該方法引入到局部閾值法中，這是下一步的研究工作。

[1] 張新明，黨留群，鄭延斌，等.一種改進的二維最小交叉熵圖像分割方法[J].光電工程，2010，37（11）：103-109.

[2] Fan Jiulun，Lei Bo.A modified valley-emphasis method for automatic thresholding[J].Pattern Recognition Letters，2012，33（6）：703-708.

[3] Kapur J 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 Process，1985，29（3）：273-285.

[4] Brink A D，Pendock N E.Minimum cross-entropy thresold selection[J].Pattern Recognition，1996，29（1）：179-188.

[5] 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.

[6] 唐英干，邸秋艷，關新平，等.基于最小Tsallis交叉熵閾值圖像分割方法[J].儀器儀表學報，2008，29（9）：1868-1872.

[7] Sahoo P K，Arora G.Image thresholding using two-dimensional Tsallis-Havrda-Charvát entropy[J].Pattern Recognition Letters，2006，27（6）：520-528.

[8] 朱煒，徐玉如，秦再白.一種新的基于二維Tsallis 熵的閾值分割方法[J].計算機工程與應用，2007，43（27）：54-58.

[9] 吳一全，潘喆，吳文怡.二維直方圖斜分Tsallis-Havrda-Charvát熵圖像閾值分割[J].光電工程，2008，35（7）：53-58.

[10] 吳一全，張金礦.二維直方圖θ-劃分Tsallis 熵閾值分割算法[J].信號處理，2010，26（8）：1162-1168.

[11] 唐英干，邸秋艷，趙立興，等.基于二維最小Tsallis 交叉熵的圖像閾值分割方法[J].物理學報，2009，58（1）：9-15.

[12] 吳一全，沈毅，剛鐵，等.基于二維對稱Tsallis交叉熵的小目標圖像閾值分割[J].儀器儀表學報，2011，32（10）：2161-2167.

[13] 賈東立，張家樹.基于混沌變異的小生境粒子群算法[J].控制與決策，2007，22（1）：117-120.

[14] 張新明，孫印杰，鄭延斌.二維直方圖準分的Otsu 圖像分割及其快速實現[J].電子學報，2011，39（8）：1778-1784.