灰度圖像二維交叉熵閾值分割法(投出稿)

1、 MACROBUTTON AcceptAllChangesInDoc 灰度圖像的二維交叉熵閾值分割法 國家自然科學(xué)基金資助（編號：60572133）范九倫 = 1 * GB3 雷博 = 1 * GB3 ， = 2 * GB3 ( = 1 * GB3 .西安郵電學(xué)院信息與控制系, 陜西 西安710061; = 2 * GB3 .西安電子科技大學(xué)電子工程學(xué)院, 陜西 西安710071)摘要：一維Otsu法是一個經(jīng)典的閾值分割方法，遵循該方法的構(gòu)造思想，Li 與 Lee基于交叉熵提出了一個閾值分割方法。本文在解釋和說明Li 與 Lee的方法的基礎(chǔ)上，將其推廣到二維灰度直方圖上，提出了二維交叉熵的圖像

2、分割算法并給出快速遞推公式。與二維Otsu法相比，本文方法能夠更好的適應(yīng)目標(biāo)和背景方差相差較大的情形，是一個有效的閾值分割方法。關(guān)鍵詞：閾值分割；Otsu法；交叉熵中圖分類號： TN911.73 文獻標(biāo)識碼： ATwo-dimensional cross-entropy thresholding segmentation method for gray-level images(FAN Jiu-lun = 1 * GB3 LEI Bo = 1 * GB3 = 2 * GB3 ，) ( = 1 * GB3 .Department of Information and Control, Xian

3、Institute of Post and Telecommunications, ,Xian, Shaanxi 710061,China; = 2 * GB3 . School of Electronic Engineering of Xidian University, Xian Shaanxi 710071, China)Abstract: One-dimensional Otsus method is a classical thresholding segmentation method. Li & Lee proposed a thresholding segmentation m

4、ethod based on cross-entropy following this thought. In this paper, we extend the cross-entropy method to two dimensions and present a fast recursive formula based on the explanation and illustration of Li & Lees method. Compared with the traditional two-dimensional Otsus method, the new method can

5、be better adapted to the cases that the variance between the object and the background is large. It is validated that the new method is an available thresholding selection method. Keywords: threshold segmentation; Otsus method; cross-entropy1 引言圖像分割是圖像分析、理解和計算機視覺中的難點。在圖像分割的諸多方法中，閾值化技術(shù)是一種簡單有效的方法1。Ots

6、u法2是廣泛使用的閾值分割方法之一，Otsu法也稱為最大類間方差法或最小類內(nèi)方差法，等效于一維硬c-均值聚類算法3。Kurita等4在各類方差相等的約束下運用條件相關(guān)混合概率模型對Otsu法進行了解釋，從文3和4的描述可見Otsu法在理論上適用于目標(biāo)和背景方差相差不大的混合正態(tài)分布情形。Otsu法涉及到閾值、目標(biāo)均值和背景均值，如果用與構(gòu)造的二值圖像作為待分割圖像的“理想圖像”，則Otsu法的基本思想是從待分割圖像和“理想圖像”的匹配角度，通過最小化均方誤差來獲得最佳閾值。交叉熵（相對熵、有向散度）描述了兩個概率分布的差異性程度，借用交叉熵并利用Otsu法的基本思想，Li 和 Lee給出了另一

7、個閾值分割方法5。我們6從條件相關(guān)混合概率模型的角度，基于泊松分布對Li 和 Lee的方法進行了解釋，這種解釋使得Li 和 Lee方法的數(shù)學(xué)機理更加清晰，為其更好的使用奠定了堅實的理論基礎(chǔ)。此外我們也給出了Li 和 Lee方法的一種快速迭代算法7。從概率論和數(shù)理統(tǒng)計的知識知道，泊松分布和正態(tài)分布是有密切關(guān)系的，當(dāng)泊松分布的參數(shù)比較大時，可以用均值和方差均為的正態(tài)分布來近似。鑒于Li 和 Lee方法可以用泊松分布進行解釋，我們可以有理由的說，Li 和 Lee方法能更好的適用于灰度圖像中目標(biāo)和背景的方差相差較大的情形。（注：這里假定了圖像中方差較小的部分處于較小灰度值處；方差較大的部分處于較大灰度

8、值處。若出現(xiàn)相反的情形，只需反色即可。）一維Otsu法對含噪圖像的分割效果不好，為此人們引入了二維灰度直方圖并提出了二維Otsu法8，為了提高運行速度，快速遞推算法也已經(jīng)給出9。近年來有許多基于二維Otsu法的圖像分割方法研究及應(yīng)用10-12。與二維Otsu法的研究成果相對應(yīng)，本文給出Li 和 Lee方法的二維推廣。和理論解釋相對應(yīng)，本文方法對于目標(biāo)和背景方差相差較大的圖像的分割效果優(yōu)于二維Otsu法。因此，本文的方法在一定程度上彌補了Otsu法的不足，是一個有效的閾值分割方法。2 一維交叉熵閾值法我們用來表示一幅大小為的數(shù)字圖像，其中表示圖像中第點的灰度值，。圖像中灰度為的象素點總數(shù)記為，則

9、圖像中每一灰度值出現(xiàn)的概率可表示為 （1）設(shè)閾值將圖像分為目標(biāo)和背景兩類，分別記為 和，則這兩類的先驗概率分別為 （2） （3）背景和目標(biāo)對應(yīng)的均值分別為 （4） （5）我們用表示分割后的二值圖像。則Otsu方法通過衡量待分割圖像與二值化圖像之間的均方誤差來獲取最佳閾值。建立的準(zhǔn)則函數(shù)為最小化 （6）改用灰度直方圖表示，可得簡化表達式 （7）由公式（4）和（5），可將改寫成 （8）于是最小化等價于最大化下式 （9）式（6）描述的是每一象素點上原圖像的灰度值與分割后的灰度值之間的偏差，式（7）描述的是原圖像的灰度直方圖與分割后的灰度直方圖之間的偏差。基于這種認識，運用描述兩個概率分布之間偏差的交

10、叉熵，Li 和 Lee 給出另一個刻畫待分割圖像與二值化圖像之間偏差的閾值分割方法，具體如下：和的交叉熵定義為 （10）改用灰度直方圖表示，可得簡化表達式 （11） 由公式（4）和（5），可將改寫成 （12）于是最小化等價于最大化下式 （13） 將（9）和（13）對比，二者之間有驚人的相似之處，僅有的區(qū)別是式（9）采用的是乘法運算，；而式（13）采用的是對數(shù)運算，。 Otsu法適用于圖像灰度直方圖中目標(biāo)和背景的方差相差不大的正態(tài)混合分布，一般而言對目標(biāo)和背景的方差相差較大的正態(tài)混合分布的分割效果較差。在文6中我們用Poisson分布對Li 和 Lee 提出的交叉熵閾值分割方法進行了解釋，使得對

11、該方法的認識更為深入。由概率論與數(shù)理統(tǒng)計的知識，服從Poisson分布，參數(shù)為的隨機變量記為，那么的均值為，方差為。概率取值為 （14）當(dāng)取值較大時，對泊松分布利用Stirling近似公式 （15）可將Poisson分布轉(zhuǎn)化為正態(tài)分布： （16）即可以認為。這意味著對于服從混合正態(tài)分布，目標(biāo)和背景的方差相差較大的灰度圖像，使用Li 和 Lee 提出的交叉熵閾值分割方法具有一定的合理性。從這一點上講，交叉熵閾值分割方法能夠更好的彌補Otsu法的不足，具有一定的實用價值。3 二維交叉熵閾值分割法一維圖像閾值分割方法常常對含噪圖像的分割效果較差，為此人們提出了在二維灰度直方圖上進行閾值選取。對于一幅

12、的數(shù)字圖像，我們用表示圖像上坐標(biāo)為的像素點的灰度值，表示圖像上坐標(biāo)為的像素點的鄰域的平均灰度值，的定義如下： （17） 其中表示取整運算。K為鄰域?qū)挾?，一般取奇?shù)。從的定義可以看出，如果圖像的灰度級為，那么相應(yīng)的像素鄰域平均灰度的灰度級也為，和組成的二元組記為。在此基礎(chǔ)上定義圖像的二維直方圖，該二維直方圖定義在一個大小的正方形區(qū)域上，其橫坐標(biāo)表示圖像像元的灰度值,縱坐標(biāo)表示像元的鄰域平均灰度值。直方圖中任意一點的值定義為，它表示二元組發(fā)生的頻率。由下式確定 （18） 其中是出現(xiàn)的頻數(shù)，。圖1根據(jù)二維直方圖的定義，假設(shè)在閾值處將圖像分割成四個區(qū)域，如圖1所示。其中，對角線上的兩個區(qū)域1和2分別對

13、應(yīng)于目標(biāo)和背景，遠離對角線的區(qū)域3和4對應(yīng)于邊緣和噪聲8-9。一般認為在區(qū)域3和4上所有的。由圖1可知，利用二維直方圖中任意閾值矢量對圖像進行分割，可將圖像分成目標(biāo)和背景兩類區(qū)域，分別記為 和，則這兩類的先驗概率分別為 （19） （20）滿足 （21）目標(biāo)和背景對應(yīng)的均值矢量分別為 （22） （23）二維直方圖上總的均值矢量為 （24）我們用表示原圖像在灰度值處的概率，用表示鄰域平均圖像在灰度值處的概率，那么， （25） （26）用和分別表示原圖像在閾值為時目標(biāo)和背景的先驗概率，和分別表示原圖像在閾值為時目標(biāo)和背景的均值。那么 （27） （28） （29） （30）用和分別表示鄰域平均圖像在閾

14、值為時目標(biāo)和背景的先驗概率，和分別表示鄰域平均圖像在閾值為時目標(biāo)和背景的均值。那么 （31） （32） （33） （34）對于原圖像，在閾值為時的交叉熵分割方法的準(zhǔn)則函數(shù)為 （35）對于鄰域平均圖像，在閾值為時的交叉熵分割方法的準(zhǔn)則函數(shù)為 （36）因此，在二維直方圖上建立的以為閾值點的準(zhǔn)則函數(shù)為 （37）最佳閾值取為： （38）注意到，由于 （39）鑒于是常數(shù)，因此，最佳閾值也可選為 （40） 4 快速遞推算法和二維Otsu法一樣，用窮舉搜索的方法得到二維交叉熵閾值的計算量很大，不能滿足實時性的要求。為此本節(jié)給出二維交叉熵閾值法的遞推算法。我們記，。那么 （41） （42） （43） （44）

15、具體的遞推過程如下： （45） （46） （47） （48） （49） （50） （51） （52） （53） （54） （55） （56）用以上快速遞推公式，每次計算不必都從(0,0)開始，將計算復(fù)雜度從降低到，大大節(jié)省了計算時間。同時快速遞推的過程還減少了計算過程所需的存儲空間，提高了算法的效率。如果不使用遞推公式，的所有值一直需要保留在存儲空間中，而使用快速算法不需要保留中間結(jié)果，這樣可以節(jié)省存儲空間提高算法效率。5 實驗結(jié)果及分析仿真實驗是在Matlab6.5環(huán)境下，在奔騰4、2.8GHz CPU和256M內(nèi)存微處理器上進行的。在實驗中，采用兩幅圖像：SAR圖像和加了均值為0、方差為0

16、.005的高斯噪聲的細菌圖像，尺寸分別為340340，178178。我們分別采用一維Otsu法、二維Otsu遞推算法、一維交叉熵法以及本文給出的二維交叉熵遞推算法進行了比較。在二維灰度直方圖的構(gòu)造時取。 （a）原圖 (b) 二維直方圖 (c) 一維Otsu法 (d) 二維Otsu法 (e) 一維交叉熵法 (f) 二維交叉熵法 圖2 SAR圖像的分割結(jié)果 （a）原圖 (b) 二維直方圖 (c) 一維Otsu法 (d) 二維Otsu算法 (e) 一維交叉熵法 (f) 二維交叉熵法圖3 細菌圖像分割結(jié)果SAR圖像的實驗結(jié)果如圖2所示。從圖2（b）可見，目標(biāo)和背景的方差相差較大。從圖2（c）（f）可見

17、，基于交叉熵的方法總體上優(yōu)于Otsu法，而二維交叉熵法獲得了最好的分割效果，將河流與背景區(qū)分開來。細菌圖像的實驗結(jié)果如圖3所示。從圖3（b）可見，目標(biāo)和背景的方差相差較大。從圖3（c）（f）可見，基于交叉熵的方法總體上優(yōu)于Otsu法，而二維交叉熵法獲得了最好的分割效果。綜合圖2和圖3的實驗結(jié)果，對于目標(biāo)和背景的方差相差較大的灰度圖像，交叉熵法的分割性能優(yōu)于Otsu法，而二維交叉熵法的分割效果是最好的。這說明二維交叉熵法能更好的處理目標(biāo)和背景的方差相差較大的情形。表1 四種算法的運行時間及閾值比較（s）SAR圖像細菌圖像運行時間(s)閾值運行時間(s)閾值一維Otsu法0.411060.4111

18、6一維交叉熵法0.40950.4395二維Otsu遞推算法0.88（102, 115）0.62(118, 127)二維交叉熵遞推算法1.68(70,87)0.92(96, 103)表1給出了四種方法在運行時間和閾值上的比較，由表1可以看出，一維Otsu方法和一維交叉熵方法耗時較少。二維交叉熵方法和二維Otsu方法耗時較多。這是由于二維算法的復(fù)雜性大，計算量大，但由表1所示的時間可以看出這并不影響二維閾值化方法的實用性。6 結(jié)論一維交叉熵閾值法提出的思想和一維Otsu法是相同的，二者在表述上有相似之處。本文通過分析一維交叉熵閾值法的理論基礎(chǔ)，將其推廣到二維情形。為了提高運行速度，給出了遞推算法。

19、實驗表明交叉熵閾值法能夠更好的適應(yīng)目標(biāo)和背景方差相差較大的情況，而二維交叉熵閾值法在抑制噪聲方面的效果是較好的。因此，本文提出的二維交叉熵閾值法是一個有效的圖像分割算法。參考文獻1 Sahoo P K, Soltani S, Wong A K C, Chen Y C. A survey of thresholding techniquesJ, Computer Vision, Graphics and Image Processing, 1988,41:233-260.2 N.Otsu, A thresholding selection method from gray-level histo

20、grams J, IEEE Trans. System Man Cybernetic.1979,9:6266.3 Kittler J, Illingworth J, On threshold selection using clustering criteriaJ, IEEE Trans. System Man Cybernetic.1985,15(5):652655.4 Kurita T, Otsu N, Abdelmalek N. Maximum likelihood thresholding based on population mixture models J, Pattern Re

21、cognition,1992,25(11): 1231-1240.5 Li C H, Lee C K. Minimum cross entropy thresholdingJ. Pattern Recognition,1993,26(4): 6176256 Jiu-Lun Fan. Notes on Poisson distribution-based minimum error thresholdingJ. Pattern Recognition Letters 19(1998):4254317 吳成茂、范九倫，基于交叉熵閾值法的快速迭代算法J.計算機應(yīng)用與軟件，2007，Vol.24 No

22、 6:68 Wu Cheng-mao, Fan Jiu-lun. Rapid Iterating thresholding algorithm based on mulual entropyJ. Computer Applications and Software. 2007，Vol.24 No 6:688 劉健莊, 粟文青. 灰度圖像的二維Otsu自動閾值分割法J. 自動化學(xué)報, 1993, 19(1): 101-105.Liu Jian-Zhuang, Li Wen-Qing. The automatic thresholding of gray-level pictures via two-dimensional Otsu methedJ.Acta Automatica Sinica.1993, 19(1): 101-105.9 唐英干,劉冬, 關(guān)新平. 基于粒子群和二維Otsu方法的快速圖像分割J. 控制與決策，2007，Vol.22 No.2: 202205Tang Ying-gan, Liu Dong, Guan Xin-ping. Fast image segmentation based on particle sw