二維直方圖斜分最大散度差閾值分割算法

楊恢先，李 淼，譚正華，翟云龍，張建波

(1.湘潭大學(xué)材料與光電物理學(xué)院，湖南湘潭411105;2.湘潭大學(xué)信息工程學(xué)院，湖南湘潭411105)

1 引言

在圖像處理和計算機(jī)視覺中，圖像分割是一項(xiàng)基本且關(guān)鍵的技術(shù)，而諸多圖像分割方法中，閾值法是一種簡單有效的方法［1］，其關(guān)鍵是如何選取閾值，經(jīng)過多年研究，國內(nèi)外學(xué)者提出了大量閾值選取方法，如最大熵法［2］、最大相關(guān)性法［3］、最小誤差法［4］、最大類間方差法［4］(又稱 Otsu 法)，其中 Otsu法以目標(biāo)和背景之間的類間方差作為分離性準(zhǔn)則，對多類圖像分割效果好且計算簡單，成為實(shí)際中常用的方法。然而，當(dāng)圖像中目標(biāo)和背景的面積相差很大或者信噪比低時，Otsu法會出現(xiàn)閾值“偏移”問題而不能實(shí)現(xiàn)有效分割［5］，有學(xué)者僅從類內(nèi)散度出發(fā)提出新的閾值分割方法［6］，但又因沒有兼顧類間散度分割效果依然不理想。針對Otsu法存在的問題，文獻(xiàn)［7］通過引入模式識別中Fisher準(zhǔn)則提出了Fisher準(zhǔn)則閾值法，該方法同時考慮了類間方差和類內(nèi)方差在數(shù)據(jù)分離性中的作用，使其分割結(jié)果受目標(biāo)面積大小的影響較小，但類內(nèi)方差矩陣可能的奇異性以及類內(nèi)方差在分離性中的作用是固定的使得該算法不穩(wěn)定。文獻(xiàn)［8］對Fisher準(zhǔn)則作了必要的修正，并基于新的鑒別準(zhǔn)則設(shè)計了最大散度差分類器，文獻(xiàn)［9］將最大散度差分類的思想運(yùn)用到圖像分割中，提出了最大散度差閾值法，該方法不僅考慮了類間方差和類內(nèi)方差，而且可以避免Fisher準(zhǔn)則所面臨的類內(nèi)方差矩陣的奇異性，同時還能調(diào)節(jié)參數(shù)來改變類內(nèi)方差在分離性中的作用。然而一維最大散度差法(簡稱一維MSD法)同眾多典型一維閾值分割法一樣，沒有考慮圖像局部空間信息，當(dāng)圖像光照不均勻或受到噪聲干擾時難以取得好的分割結(jié)果，劉建莊首次提出基于二維直方圖的Otsu法［10］，很好解決了這一問題，同時也使基于二維直方圖的分割算法成為近年研究的熱點(diǎn)，有學(xué)者提出基于二維直方圖的群集智能算法［11］，還有學(xué)者提出基于二維直方圖的改進(jìn)閾值分割輸出函數(shù)的閾值算法［12］，這些算法或提高了圖像分割的準(zhǔn)確性，或降低了算法的運(yùn)算時間。這里提出一種基于二維直方圖區(qū)域斜分的最大散度差閾值法(簡稱二維斜分MSD法)，以期待獲得更好的分割結(jié)果以及更少的運(yùn)算時間。

2 二維直方圖斜分的MSD閾值分割法

2.1 二維直方圖的區(qū)域斜分

設(shè)圖像尺寸為M×N，圖像灰度級為L，相應(yīng)的像素鄰域均值灰度的灰度級也是L，f(x，y)為圖像在(x，y)點(diǎn)的灰度值，g(x，y)為以 (x，y)為中心k×k鄰域內(nèi)的平均灰度值，其中 g(x，y)的表達(dá)式為:

以f(x，y)和g(x，y)組成的二元組(i，j)來定義二維直方圖，直方圖中任意一點(diǎn)的聯(lián)合概率密度定義為p(i，j)，它表示二元組(i，j)發(fā)生的頻率，則:

式中，cij是(i，j)出現(xiàn)的頻數(shù)，0≤i，j≤L －1。圖 1(a)為一幅圖像的二維直方圖。

二維直方圖區(qū)域斜分:采用與主對角線垂直的一條線段g=－f+T(T為閾值，0＜T≤2L)將直方圖分成0區(qū)和1區(qū)兩個部分(如圖1(c)、1(d)所示)，這兩部分所在的點(diǎn)分別歸為目標(biāo)和背景兩類，按圖像灰度級與鄰域均值灰度級之和的大小分割圖像，像元的歸類方式為:

其中，fT(x，y)表示分割后的圖像。相比二維直方圖區(qū)域直分模式在計算最佳閾值向量時沒有考慮像素灰度級和鄰域均值灰度級相差較大的點(diǎn)(如圖1(b)中的A點(diǎn)和B點(diǎn))，以及忽略了在對角線附近靠近閾值向量的一些區(qū)域的概率分布(如圖1(b)中陰影部分)，二維直方圖區(qū)域斜分模式采用與主對角線垂直的斜線進(jìn)行閾值分割，計算閾值時考慮了所有區(qū)域，提高了二維閾值分割的準(zhǔn)確性，并已被成功應(yīng)用到二維 Otsu法［13］、二維最大熵法(簡稱二維MET 法)［14］、二維最小誤差法［15］等閾值法中。

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

2.2 二維直方圖區(qū)域斜分MSD法

在圖1(c)、1(d)中斜線g=－f+T將二維直方圖分成了對應(yīng)于目標(biāo)及背景的0類和1類，目標(biāo)和背景出現(xiàn)的概率分別為ω0(T)和ω1(T):

其中:

目標(biāo)和背景對應(yīng)的均值矢量為:

二維斜分MSD準(zhǔn)則采用廣義差的形式，即類間方差減去C倍的類內(nèi)方差為分離性度量，其數(shù)學(xué)定義為:

式中，C是一個大于零的參數(shù)，它的作用是調(diào)節(jié)類內(nèi)方差在閾值分割中的作用，從而克服Otsu法當(dāng)目標(biāo)與背景面積相差很大時所具有的閾值“偏移”現(xiàn)象，改善分割效果。最佳閾值選為:

2.3 快速遞推算法

對式(13)等號右邊各項(xiàng)經(jīng)變形整理可得

由式(13)、式(16)、式(17)可將類內(nèi)方差整理為:

因此，從式(12)、式(19)、式(14)以及式(6)、式(7)可知求最佳閾值時需要計算 ω0(T)、ω1(T)、 μ0i(T)、 μ0j(T)、 μ1i(T)、 μ1j(T)、δTi(T)、δTj(T)，用窮舉搜索的方法得到二維斜分MSD法最佳閾值的計算量很大，顯然不能滿足實(shí)時性要求，為此這里給出快速遞推公式以進(jìn)一步優(yōu)化算法。對同一幅圖像，μTi(T)、μTj(T)、δTi(T)和δTj(T)是固定的，所以只要計算 ω0(T)、ω1(T)、μ0i(T)、μ0j(T)、μ1i(T)、μ1j(T)就可以由目標(biāo)函數(shù)式(14)求得最佳閾值，推導(dǎo)公式見以下兩種情況:

1)當(dāng)0＜T≤L－1時，如圖1(c)所示，此時斜線g=－f+T的左下三角部分對應(yīng)目標(biāo)，可以從(0，0)點(diǎn)開始遞推計算 ω0(T)、μ0i(T)、μ0j(T)，而ω1(T)、μ1i(T)、μ1j(T)可通過式(5)、式(9)求得。

2)當(dāng)L－1＜T≤2L－2時，如圖1(d)所示，此時斜線g=－f+T的右上三角部分對應(yīng)背景，則從(L－1，L－1)點(diǎn)開始遞推計算 ω1(T)、μ1i(T)、μ1j(T)，同理可得到對應(yīng)ω0(T)、μ0i(T)、μ0j(T)。

采用以上遞推算法，每一次計算J(T)都無需重新計算 ω0(T)、μ0i(T)、μ0j(T)和 ω1(T)、μ1i(T)、μ1j(T)，只要分別利用前面得出的ω0(T－1)、μ0i(T－1)、μ0j(T－1)和ω1(T－1)、μ1i(T－1)、μ1j(T－1)再加上直線段g=－f+T上各點(diǎn)相應(yīng)的值即可，而ω1(T)、μ1i(T)、μ1j(T)和ω0(T)、μ0i(T)、μ0j(T)分別在 T=0，1，…，L－1和 T=2L－2，2L－3，…，L 范圍內(nèi)可由式(5)、式(9)和已遞推出的變量求得，這樣使得6個變量的搜索次數(shù)由(2L－2)減半，相對窮舉算法，計算復(fù)雜度從O(L3)降到O(L)，運(yùn)算量大為減少。

3 實(shí)驗(yàn)結(jié)果與分析

仿真實(shí)驗(yàn)結(jié)果是在 Matlab2007環(huán)境下，Intel Celeron R 1.67 GHz CPU/1.00 GB內(nèi)存的機(jī)器上進(jìn)行的。

3.1 參數(shù)C取不同值對圖像閾值分割效果的影響

事實(shí)上，同一維MSD法一樣，二維斜分MSD法應(yīng)用在圖像閾值分割中的一大特點(diǎn)在于，算法不僅同時考慮了類間方差和類內(nèi)方差在分離性中的作用，而且可以通過調(diào)節(jié)參數(shù)C來改變類內(nèi)方差在分離性中的作用，因此要使圖像分割取得好的效果必須對參數(shù)C選擇合適的值?，F(xiàn)通過一幅典型紅外圖像car(圖2(a))來說明參數(shù)C在取不同值時對圖像閾值分割效果的影響，圖2(b)～(d)給出了二維斜分Otsu法、二維斜分MET法、一維MSD法的分割結(jié)果用以進(jìn)行比較，因限于篇幅二維斜分MSD法僅給出了C依次取0.90、1.01、1.05和1.20時所得的分割結(jié)果，如圖2(e)～(h)所示，圖2(j)為不同C值的二維直方圖區(qū)域劃分情況，圖2(g)繪出了C從0.6到1.55之間以0.05為間隔的閾值變化趨勢，各方法得到的最佳閾值如表1所示。

圖2 紅外圖像car對于不同閾值法的分割結(jié)果比較及二維MSD法二維直方圖區(qū)域劃分解析

表1 不同方法取得的閾值比較

從圖2(i)可以看到，這幅紅外圖像的二維直方圖沒有明顯的雙峰，近似為單峰，顯然其代表的目標(biāo)與背景的面積和方差相差很大，由二維斜分Otsu法得到的閾值偏向了較大的那個峰，不能進(jìn)行有效分割(如圖2(b))，同時二維斜分MET法也沒能有效分割目標(biāo)與背景(如圖2(c))，一維MSD法在調(diào)節(jié)參數(shù)C到一個合適值后，類內(nèi)方差在分類中起到調(diào)節(jié)作用，其分割結(jié)果比較理想(如圖2(d))。

在圖2(j)中，可以看出沿主對角線附近背景的概率分布十分集中且比例很大，而目標(biāo)的概率分布零星分散且比例很小，圖2(g)可以觀察到當(dāng)參數(shù)C逐漸增大時，二維斜分MSD法所獲得的閾值逐漸減小，這使得在圖2(j)中區(qū)域劃分線段g=－f+T將從上向下平移，C值取較小時(如C=0.90)T*值較大，此時屬于目標(biāo)的很多點(diǎn)被錯分到左下角背景區(qū)域一起，體現(xiàn)為分割結(jié)果目標(biāo)car信息不完整且輪廓?dú)埲?如圖2(e))，C值增大到一個合適值(如C=1.01)時，g=－f+T平移到可以很好的將絕大部分目標(biāo)和背景的點(diǎn)劃分到各自對應(yīng)的區(qū)域，此時將獲得比較理想的分割結(jié)果(如圖2(f))，而當(dāng)C值繼續(xù)增大(如C=1.05)時，g=－f+T繼續(xù)向下平移，這時屬于背景部分的點(diǎn)將被錯分到線段右上部分的目標(biāo)區(qū)域，分割結(jié)果體現(xiàn)為目標(biāo)car周圍開始出現(xiàn)屬于背景的虛假信息(如圖2(g))，如果C再增大(如C=1.20)這種區(qū)域錯分將更加嚴(yán)重，分割結(jié)果也會變得更為不理想(如圖2(h))。

對于其他不同類型的圖像，通過大量實(shí)驗(yàn)同樣可以發(fā)現(xiàn)，利用二維斜分MSD法進(jìn)行閾值分割，隨著參數(shù)C在一定范圍內(nèi)不斷增大，所獲得的閾值T*將不斷減小，當(dāng)C值變得很大超過一定范圍時這種變化規(guī)律將消失而閾值T*會變得很大且不可調(diào)節(jié)，因此適當(dāng)選擇C值能獲得較為理想的分割結(jié)果。

3.2 不同閾值選取方法的實(shí)驗(yàn)結(jié)果比較

為驗(yàn)證二維斜分MSD算法及其快速遞推的有效性，對多幅圖像進(jìn)行閾值分割實(shí)驗(yàn)，并將分割結(jié)果與二維斜分 Otsu 法［10］、二維斜分 MET 法［11］、一維MSD法［9］的進(jìn)行比較。現(xiàn)選出其中4幅圖像Cameraman、Tank、Columbia、Coin 作為示例進(jìn)行比較說明，這4幅圖像都疊加了均值為0、方差為0.01的高斯噪聲。對于一維MSD法和二維斜分MSD法，為了能讓這兩種方法獲得較為滿意的分割效果，這里將二者的參數(shù)C分別設(shè)置為C=100，C=1。實(shí)驗(yàn)對比結(jié)果如圖3所示，相應(yīng)的最佳閾值和運(yùn)行時間所表2和表3所示。

圖3 四種方法分割結(jié)果對比

表2 四種方法的最佳閾值比較

表3 四種方法的運(yùn)行時間比較 單位:s

分割性能效果方面，由圖3可以看到，這四種方法中二維斜分MSD法的分割結(jié)果更準(zhǔn)確、抗噪聲能力更穩(wěn)健，例如Cameraman圖像草地上的噪聲去除得更加干凈;Tank圖像中坦克上的輪子和五角星輪廓都更清晰;Columbia圖像中盡管建筑物受光照不均但其前面階梯部分的圖像細(xì)節(jié)仍能保持清晰準(zhǔn)確;Coin圖像硬幣上頭像的邊緣輪廓更清晰。其余三種方法，一維MSD法的分割結(jié)果在圖像邊緣細(xì)節(jié)、內(nèi)部均勻性方面比二維Otsu法的要好，而二維斜分Otsu法在抗噪聲方面比一維MSD法的要顯著，二維斜分MET法的分割結(jié)果和抗噪聲能力最不理想。

運(yùn)行時間方面，分析表3可以看到，三種二維閾值分割方法由于考慮了空間鄰域信息，算法復(fù)雜性增加，耗時比一維MSD法的要大，但二維斜分MSD法相比二維斜分Otsu法和二維斜分MET法而言花費(fèi)的時間要少一些，約為它們遞推算法運(yùn)算時間的80% ～90%，可以滿足實(shí)時處理要求。

4 結(jié)論

提出了一種二維直方圖區(qū)域斜分的最大散度差閾值法，該方法摒棄了一些常用二維閾值分割法中認(rèn)為二維直方圖中反對角線區(qū)域概率和近似為零的假設(shè)，通過調(diào)節(jié)參數(shù)C改變類間方差和類內(nèi)方差在分類中的作用，能夠在保證去噪效果的同時有效克服二維斜分Otsu法的閾值偏移問題。參數(shù)C在一定范圍內(nèi)的不斷增大將使得所獲閾值T*隨之不斷減小，在具體應(yīng)用時對于不同類型的圖像，適當(dāng)選擇C值能獲得比現(xiàn)有幾種常見二維閾值法更準(zhǔn)確的圖像分割結(jié)果。在導(dǎo)出二維斜分MSD法閾值選取公式的同時給出了其快速遞推算法，降低了算法復(fù)雜性，提升了運(yùn)算效率。

［1］ Sezgin M，Sankur B.Survey over image thresholding techniques and quantitative performance evaluation［J］.Journal of Electronic Imaging，2004，13(1):146 －165.

［2］ P D Sathya，R Kayalvizhi.Amended bacterial foraging algorithm for multilevel thresholding of magnetic resonace brain images ［J］.Measurement，2011，44(10):1828－1848.

［3］ Yen J C.Chang F J，Chang S Y.A new criterion for automatic multilevel thresholding［J］.IEEE Trans.on Image Processing，1995，4(3):370 －378.

［4］ Jinghao Xue，Yujin Zhang.Ridler and Calvard’s，Kittler and Illingworth’s and Otsu’s methods for image thresholding［J］.Pattern Recognition Letters，2012，33(6):793 －797.

［5］ XU Xiangyang，XU Shengzhou，JIN Lianghai，et al.Characteristic analysis of otsu threshold and its applications［J］.Pattern Recognition Letters，2011，32(7):956－961.

［6］ WU Yiquan，WU Wenyi，PAN Zhe.Minimum within-class variance thresholding based on two-dimensional histogram oblique segmentation［J］.Chinese Journal of Scientific Instrument，2007，29(12):2644 －2655.(in Chinese)吳一全，吳文怡，潘喆.基于二維直方圖斜分的最小類內(nèi)方差閾值分割［J］.儀器儀表學(xué)報，2007，29(12):2644－2655.

［7］ CHEN Guo.The fisher criterion function method of image thresholding［J］.Chinese Journal of Scientific Instrument，2003，24(6):564 －567.(in Chinese)陳果.圖像閾值分割的Fisher準(zhǔn)則函數(shù)法［J］.儀器儀表學(xué)報，2003，24(6):564 －567.

［8］ SONG Fengxi，CHENG Ke，YANG Jingyu，et al.Maximum scatter difference，large margin linear projection and support vector machines［J］.Acta Automatica Sinica，2004，30(6):890 －896.(in Chinese)宋楓溪，程科，楊靜宇，等.最大散度差和大間距線性投影與支持向量機(jī)［J］.自動化學(xué)報，2004，30(6):890－896.

［9］ WANG Zhibin，GU Yue，LI Zhiquan.Threshold image segmentation based on maximum scatter difference discriminant criterion［J］.Journal of Applied Optics，2010，31(3):403 －405.(in Chinese)王志斌，谷越，李志全.基于最大散度差準(zhǔn)則的閾值圖像分割［J］.應(yīng)用光學(xué)，2010，31(3):403 －405.

［10］ LIU Jianzhuang，LI Wenqing.Automatic thresholding using the Otsu algorithm based on the two-dimentional grey image［J］.Acta Automatica Sinica，1993，19(1):101 －105.(in Chinese)劉健莊，栗文青.灰度圖像的二維Otsu自動閾值分割法［J］.自動化學(xué)報，1993，19(1):101 －105.

［11］ ZHANG Xiancheng，SHEN Quntai，WANG Junnian，et al.Application of particle swarm optimization in 2D fuzzy entropy image segmentation［J］.Journal of Chinese Computer Syetems，2008，29(5):959 －962.(in Chinese)張鮮成，申群太，王俊年，等.微粒群算法在二維模糊熵圖像分割中的應(yīng)用［J］.小型微型計算機(jī)系統(tǒng)，2008，29(5):959 －962.

［12］ YANG Jinlong，ZHANG Guangnan，LI Shuzhong，et al.Study of image segmentation algorithm based on two-dimensional histogram［J］.Laser ＆ Infrared，2008，38(4):400 －403.(in Chinese)楊金龍，張光南，厲樹忠，等.基于二維直方圖的圖像分割算法研究［J］.激光與紅外，2008，38(4):400－403.

［13］ WU Yiquan，PAN Zhe，WU Wenyi.Image thresholding based on two-dimensional histogram oblique segmentation and its fast recurring algorithm［J］.Journal on Communications，2008，29(4):77 －84.(in Chinese)吳一全，潘喆，吳文怡.二維直方圖區(qū)域斜分閾值分割及快速遞推算法［J］.通信學(xué)報，2008，29(4):77 －84.

［14］ WU Yiquan，PAN Zhe，WU Wenyi.Maximum entropy image thresholding based on two-dimensional histogram oblique segmentation［J］.PR＆AI，2009，22(1):162 － 168.(in Chinese)吳一全，潘喆，吳文怡.二維直方圖區(qū)域斜分的最大熵閾值分割算法［J］.模式識別與人工智能，2009，22(1):162－168.

［15］ ZHANG Xinming，LI Zhenyun，SUN Yinjie.Fast image thresholding with minimum error based on 2－d oblique segmentation［J］.Electronics Optics ＆ Control，2012，19(6):8 －12.(in Chinese)張新民，李振云，孫印杰.快速二維直方圖斜分最小誤差的圖像閾值分割［J］.電光與控制，2012，19(6):8－12.