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

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

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

1 引言

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

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

2.1 二維直方圖的區域斜分

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

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

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

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

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

圖1 二維直方圖及區域劃分

2.2 二維直方圖區域斜分MSD法

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

其中:

目標和背景對應的均值矢量為:

二維斜分MSD準則采用廣義差的形式，即類間方差減去C倍的類內方差為分離性度量，其數學定義為:

式中，C是一個大于零的參數，它的作用是調節類內方差在閾值分割中的作用，從而克服Otsu法當目標與背景面積相差很大時所具有的閾值“偏移”現象，改善分割效果。最佳閾值選為:

2.3 快速遞推算法

對式(13)等號右邊各項經變形整理可得

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

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

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

2)當L－1＜T≤2L－2時，如圖1(d)所示，此時斜線g=－f+T的右上三角部分對應背景，則從(L－1，L－1)點開始遞推計算 ω1(T)、μ1i(T)、μ1j(T)，同理可得到對應ω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上各點相應的值即可，而ω1(T)、μ1i(T)、μ1j(T)和ω0(T)、μ0i(T)、μ0j(T)分別在 T=0，1，…，L－1和 T=2L－2，2L－3，…，L 范圍內可由式(5)、式(9)和已遞推出的變量求得，這樣使得6個變量的搜索次數由(2L－2)減半，相對窮舉算法，計算復雜度從O(L3)降到O(L)，運算量大為減少。

3 實驗結果與分析

仿真實驗結果是在 Matlab2007環境下，Intel Celeron R 1.67 GHz CPU/1.00 GB內存的機器上進行的。

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

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

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

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

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

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

對于其他不同類型的圖像，通過大量實驗同樣可以發現，利用二維斜分MSD法進行閾值分割，隨著參數C在一定范圍內不斷增大，所獲得的閾值T*將不斷減小，當C值變得很大超過一定范圍時這種變化規律將消失而閾值T*會變得很大且不可調節，因此適當選擇C值能獲得較為理想的分割結果。

3.2 不同閾值選取方法的實驗結果比較

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

圖3 四種方法分割結果對比

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

表3 四種方法的運行時間比較 單位:s

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

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

4 結論

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

［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)吳一全，吳文怡，潘喆.基于二維直方圖斜分的最小類內方差閾值分割［J］.儀器儀表學報，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準則函數法［J］.儀器儀表學報，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］.自動化學報，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)王志斌，谷越，李志全.基于最大散度差準則的閾值圖像分割［J］.應用光學，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］.自動化學報，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)張鮮成，申群太，王俊年，等.微粒群算法在二維模糊熵圖像分割中的應用［J］.小型微型計算機系統，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)吳一全，潘喆，吳文怡.二維直方圖區域斜分閾值分割及快速遞推算法［J］.通信學報，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)吳一全，潘喆，吳文怡.二維直方圖區域斜分的最大熵閾值分割算法［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.