基于平均中值離差的2維最小誤差閾值分割法

宋 斌，楊恢先*，曾金芳，譚正華，李翠菊

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

引 言

圖像分割是一個經(jīng)典的圖像處理問題，是圖像理解和識別的基礎(chǔ)。在圖像分割的諸多方法中，閾值分割法具有自適應(yīng)分割的特性，且較易實現(xiàn)，因此得到了廣泛的應(yīng)用［1］。經(jīng)過多年研究，國內(nèi)外學(xué)者提出了大量閾值選取方法，其中最大類間方差法(Otsu法)［2］、最大熵法［3］、最小誤差閾值分割法(minimum error threshold segmentation，METS)［4］是閾值分割方法中最為突出的3種方法。2維最大類間方差法［5］分割速度較快、目標(biāo)分割準(zhǔn)確，但對1維直方圖背景和目標(biāo)方差相差較大的圖像易產(chǎn)生閾值偏移，致使分割效果不好，而METS法能有效地克服該缺點，分割效果更為理想。METS法是由KITTLER和ILLINGWORTH［4］假設(shè)理想情況下目標(biāo)與背景的灰度分布服從混合正態(tài)分布，根據(jù)貝葉斯誤差理論推導(dǎo)出的一種重要的閾值分割方法。SEZGIN等人［6］研究對比了多種閾值分割算法，指出分割性能最佳的是METS法。1維METS法不易受目標(biāo)和背景相對大小的影響，但對噪聲較為敏感，對低信噪比圖像分割效果較差。FAN等人［7］將圖像的灰度和均值灰度信息結(jié)合起來，對METS法進(jìn)行了2維推廣，有效地抑制了噪聲的干擾。針對2維METS法計算復(fù)雜度高的問題，F(xiàn)AN等人［7］給出快速遞推算法，把復(fù)雜度由O(L4)降為O(L2);ZHU等人［8］提出了2維METS法的分解算法，把復(fù)雜度由O(L2)降為O(L);WU［9］等人和 ZHANG［10］等人分別將混沌粒子群算法和人工蜂群算法與2維METS法結(jié)合，提高了速度。這些研究雖然有效地加快了算法的分割速度，但對分割效果沒有很好的改善。為改善METS法的分割效果，XUE等人［11］在1維最小誤差閾值分割法中引入平均中值離差(mean absolute deviation from the median，MAD)，圖像分割的魯棒性有一定程度的提高，但該算法對含噪圖像分割效果不理想;LIU［12］等人基于灰度、鄰域均值灰度和鄰域中值灰度提出了3維METS法，較好地解決了噪聲干擾的圖像閾值分割問題，但處理時間遠(yuǎn)大于2維METS法。鑒于中值是比均值更為魯棒的灰度值估計量，作者將中值引入2維METS法，提出一種基于平均中值離差的2維METS法，并對該算法進(jìn)行降維分解，以加快運算速度，預(yù)期對直方圖概率分布呈偏斜分布與重尾分布的含噪圖像有良好分割效果和魯棒性。

1 2維METS法

對于一幅灰度級為L，大小為M×N的數(shù)字圖像，以圖像坐標(biāo)上任意一點(x，y)的灰度值f(x，y)與K×K鄰域(K=3)平均灰度值g(x，y)分別作為2維直方圖的橫縱坐標(biāo)，組成的二元數(shù)組，記作(i，j)。f(x，y)，g(x，y)∈G=［0，1，…，L－1］，該2 維直方圖定義在 1個(L－1)×(L－1)大小的投影平面內(nèi)。設(shè)數(shù)組(i，j)出現(xiàn)的頻率為Cij，相應(yīng)的聯(lián)合概率密度:

圖1a為灰度圖像的2維直方圖，設(shè)圖像分割閾值為(s，t)，如圖1b所示，則2維直方圖的投影平面被直線i=s和j=t分成4個區(qū)域。一般情況下，由于二位直方圖中邊緣與噪聲處于遠(yuǎn)離對角線的區(qū)域，因而可以忽略。即區(qū)域2和4上所有的Pij≈0，背景與目標(biāo)分別位于區(qū)域1和3中。

Fig.1 2-D histogram and region division

對于理想的灰度圖像的2維直方圖，假定閾值(s，t)處有1個2維混合正態(tài)分布:

式中，P0(s，t)，P1(s，t)是先驗概率，P(i，j/0)和P(i，j/1)是兩個2維正態(tài)分布。

2維正態(tài)分布隨機變量(x，y)的概率密度函數(shù)定義為:

式中，μ1，μ2為變量x和y的均值;，為變量x，y的方差;ρ為隨機變量x和y的相關(guān)系數(shù)。先驗概率P0(s，t)，P1(s，t)分別為:

定義圖像目標(biāo)類與背景類的灰度平均值向量μ0(s，t)，μ1(s，t)如下:

對于圖像真實的2維直方圖概率Pij和理想的2維混合正態(tài)分布概率Pij*，使用相對熵來計算，化簡后得到2維METS法閾值函數(shù)J(s，t)的表達(dá)式:

選取的最佳閾值向量(s*，t*)滿足:

2維METS法雖然能克服2維最大類間方差法的閾值偏移問題，但該算法是基于模板匹配的思想推導(dǎo)而來，當(dāng)圖像中目標(biāo)與背景的分布符合正態(tài)分布時，分割效果較好，否則分割效果欠佳［13］。

2 基于平均中值離差的2維METS法及其分解算法

2.1 基于平均中值離差的2維METS法

類似于方差，平均中值離差(MAD)也是一種常用的類內(nèi)離散測度。當(dāng)圖像中目標(biāo)或背景類的直方圖呈現(xiàn)偏斜分布或重尾分布時，中值是比均值更為魯棒的灰度值估計量。XUE等人［11］以平均中值離差作為離散測度，以混合高斯分布模型為基礎(chǔ)，提出的1維基于平均中值離差的最小誤差閾值分割法(簡稱MADMETS)雖引入了中值，分割魯棒性優(yōu)于1維最小誤差法，但該算法基于1維灰度直方圖，僅考慮了圖像的灰度信息，對于噪聲圖像分割效果不理想。

現(xiàn)將1維基于平均中值離差的METS法推廣到2維，以期在獲得較好的分割效果的同時保證對1維直方圖呈偏斜或重尾分布圖像分割的魯棒性。

定義目標(biāo)與背景類對應(yīng)的平均中值離差向量M0(s，t)，M1(s，t)分別為:

式中，M00(s，t)，M10(s，t)為目標(biāo)、背景類對應(yīng)于閾值(s，t)的平均中值離差，M01(s，t)，M11(s，t)為目標(biāo)、背景類對應(yīng)于閾值(s，t)的平均中值離差;Pij為2維直方圖上(i，j)點的概率，xi和xj為灰度級，m00(s，t)，m10(s，t)為目標(biāo)、背景類對應(yīng)于閾值(s，t)的灰度中值，m01(s，t)，m11(s，t)為目標(biāo)、背景類對應(yīng)于閾值(s，t)的鄰域均值灰度中值，即:

式中，C0(s，t)和C1(s，t)分別代表圖像2維直方圖目標(biāo)與背景區(qū)域，由(9)式、(11)式可得到2維基于平均中值離差的最小誤差法準(zhǔn)則函數(shù)J0(s，t)表達(dá)式:

選取的最佳閾值向量(s*，t*)滿足:

為求得最佳閾值(s*，t*)，需要在L×L的投影平面內(nèi)搜尋，并假定圖1b中的區(qū)域1和區(qū)域3為目標(biāo)和背景區(qū)域，因而2維基于平均中值離差的METS法的時間復(fù)雜度為O(L4)，F(xiàn)AN等人［7］采用遞推的方式求取閾值，算法的復(fù)雜度降為O(L2)。

2.2 2維基于平均中值離差的METS法的分解算法

閾值分割算法從1維推廣到2維會大大增加計算復(fù)雜程度，YUE等人［14］將分解思想應(yīng)用于2維灰度圖像閾值選取，通過求解2個1維算法的閾值來代替原始的2維算法的最佳閾值，并從理論上證明了可以得到與原2 維算法相同的閾值。ZHU［8］和 GONG［15］也將該分解方法成功地運用到2維METS法和3維Otsu法中?；谕瑯拥乃枷耄@里提出一種基于分解的2維基于平均中值離差的METS法的快速閾值算法。

由2維直方圖中二元數(shù)組(i，j)的聯(lián)合概率分布Pij，可得像素灰度級邊緣分布Qi和鄰域平均灰度級Rj，將Qi和Rj分別作為像素灰度值i和鄰域平均灰度值j的1維直方圖分布:

假設(shè)2維直方圖中區(qū)域1和區(qū)域3中的概率可以忽略不計，則有:

將(16)式～(22)式代入(13)式中化簡，分離變量i和j，可以得出分解算法最終的分割閾值函數(shù)J*(s，t)表達(dá)式:

式中，只含i的1維閾值函數(shù)J*i(s)與只含j的1維閾值函數(shù)(t)分別如下:

從(23)式～(25)式可以看出，分解算法實現(xiàn)了s與t變量的分離，將2維閾值(s*，t*)的選取轉(zhuǎn)化為了兩個1維閾值s*與t*的求取，算法的時間復(fù)雜性由O(L2)降到了O(L)，降低了運算復(fù)雜程度。圖2為基于分解的2維基于平均中值離差的METS法的快速閾值算法流程圖。

Fig.2 Flowchart of 2-D METS method based on mean absolute deviation from the median

3 實驗結(jié)果與分析

仿真實驗是在 Core 2，2.1GHz，2GB 內(nèi)存的機器上進(jìn)行的，編程環(huán)境為MATLAB R2012a。為驗證算法的有效性，對多幅圖像進(jìn)行了處理，均獲得了比較滿意的結(jié)果;為了與其它算法進(jìn)行比較，給出4幅含噪實驗圖像:boat，tank，moon與coin。各圖像的1維直方圖如圖3所示，直方圖的橫縱坐標(biāo)分別表示圖像的灰度級與相應(yīng)灰度級的像素點的頻數(shù)。boat與tank的1維直方圖概率分布是較為典型的偏斜分布，moon與coin的1維直方圖概率分布是較為典型的重尾分布。

分別采用1維基于平均中值絕對差的最小誤差閾值分割法(1-D MAD-METS)［10］、2維最大類間方差法(2-D Otsu)［14］、2 維最小誤差閾值分割法(2-D METS)改進(jìn)算法［7］和2維基于平均中值離差的最小誤差閾值分割法(2-D MAD-METS)對實驗圖像分割對比，4種算法的最佳分割閾值如表1所示。

Fig.3 1-D histogram of the image

Table 1 Comparison of threshold value of different methods

從視覺效果上，由圖4的實驗結(jié)果可知，1維MAD-METS法對于噪聲的抑制最差，2維Otsu法、2維METS法抗噪聲能力要優(yōu)于1維MAD-METS法，對目標(biāo)背景噪聲的抑制比2維MAD-METS法差，且2維MAD-METS法對目標(biāo)輪廓分割得更為平滑。

Fig.4 Threshold segmentation results of images

對偏斜分布圖像boat和tank的分割，2維METS法和2維MAD-METS法分割結(jié)果的邊緣輪廓準(zhǔn)確性和對背景噪聲的抑制優(yōu)于2維Otsu法，2維 MADMETS法對背景噪聲的抑制和分割目標(biāo)邊緣平滑性要更優(yōu)于2維METS法，能更準(zhǔn)確干凈地分割出目標(biāo);對重尾分布圖像moon與coin的分割，2維Otsu法和2維MAD-METS法對圖像中噪聲的抑制優(yōu)于2維METS法，2維MAD-METS法對于分割目標(biāo)邊緣輪廓準(zhǔn)確性更優(yōu)于2維Otsu法，能夠較為準(zhǔn)確地分割出目標(biāo)的邊緣和輪廓，對噪聲也有較好的抑制。

圖像分割效果好壞一般由人進(jìn)行主觀評判，但也很有必要對不同算法分割結(jié)果進(jìn)行定量的客觀評價?，F(xiàn)引入?yún)^(qū)域間灰度對比度(gray-level constrast，GC)與區(qū)域內(nèi)部均勻性(uniformity within region，UM)對4種算法的分割效果進(jìn)行定量評價。

圖像分割把圖像分割成若干區(qū)域，對相鄰接的兩個區(qū)域，它們各自平均灰度f1與f2，定義GC表達(dá)式為:

GC值越大，說明區(qū)域間差距越明顯，圖像的分割質(zhì)量也就越好。

UM用來描述圖像分割中各區(qū)域內(nèi)部特性的均勻程度，定義UM表達(dá)式為:

式中，Ri表示分割圖中的第i個區(qū)域，Ai為區(qū)域面積，C為歸一化參量。UM值越大，表示分割后得到的目標(biāo)與背景區(qū)域內(nèi)部區(qū)域一致性越好，圖像分割質(zhì)量越好。

表2和表3中分別給出了4種算法分割結(jié)果的區(qū)域間對比度與區(qū)域內(nèi)部均勻性參量，進(jìn)一步說明了2維MAD-METS法對概率分布直方圖呈偏斜分布和重尾分布的圖像具有比2維Otsu法和2維METS法具有更準(zhǔn)確的分割效果和更好的魯棒性。

Table 2 Comparison of grey-level of different methods

Table 3 Comparison of uniformity measurement of different methods

表4中給出了4種算法的時間代價對比，由于2維MAD-METS法中離散測度(MAD)的求取比2維Otsu法與2維METS法中離散測度(方差值)的求取更為復(fù)雜，因而時間代價略大于2維Otsu法與2維METS法。

Table 4 Comparison of time cost of different methods/s

2維MAD-METS法中的離散測度MAD考慮了像素鄰域內(nèi)的中值信息，比采用與均值信息有關(guān)的方差作為離散測度的2維Otsu法和2維METS法更為魯棒，較好地克服了2維Otsu法的對目標(biāo)與背景方差較大、圖像分割出現(xiàn)的閾值偏移和2維METS法對目標(biāo)與背景分布為非正態(tài)分布而分割效果不佳的缺點。2維MAD-METS法雖然采用了分解降維的思想加快運算速度，但因為中值的求取比均值的求取要花費更多的時間代價，因而分割速度較2維Otsu法和2維METS法慢。

4 結(jié)論

針對2維METS法對直方圖概率分布呈偏斜分布和重尾分布圖像分割效果魯棒性不理想且1維基于平均中值離差的METS法抗噪性差的問題，在2維METS法的基礎(chǔ)上引入中值，用平均中值離差取代2維METS法中的方差，提出2維基于中值離差的METS法。實驗結(jié)果表明，2維基于中值離差的METS法對直方圖概率分布呈偏斜分布和重尾分布圖像能更好地將目標(biāo)區(qū)和背景區(qū)及噪聲劃分開，分割結(jié)果目標(biāo)輪廓更為準(zhǔn)確，相較于2維Otsu法和2維METS法，具有更為穩(wěn)健的抗噪性和更理想的分割魯棒性。同時，文中還對2維基于中值離差的最小誤差法進(jìn)行了分解降維，將算法復(fù)雜度從O(L4)降到O(L)，但由于算法中對中值的求取，花費了較大的時間代價，將在以后的研究中加以改進(jìn)。

［1］ DIRAMI A，HAMMOUCHE K，DIAF M，et al.Fast multilevel thresholding for image segmentation through a multiphase level set method［J］.Signal Processing，2013，93(1):139-153.

［2］ MOGHADDAM R F，CHERIET M.AdOtsu:An adaptive and parameterless generalization of Otsu’s method for document image binarization［J］.Pattern Recognition，2012，45(6):2419-2431.

［3］ SATHYA P D，KAYALVIZHI R.Amended bacterial foraging algorithm for multilevel thresholding of magnetic resonace brain images［J］.Measurement，2011，44(10):1828-1848.

［4］ KITTLER J，ILLINGWORHT J.Minimum error thresholding ［J］.Pattern Recognition，1986，19(1):41-47.

［5］ GONG J，LI L Y，CHEN W N.Fast recursive algorithms for two-dimensional thresholding［J］.Pattern Recognition，1998，31(3):295-300.

［6］ SEZGIN M，SANKUR B.Survey over image thresholding techniques and quantitative performance evaluation［J］.Journal of Electronic Imaging，2004，13(1):146-168.

［7］ FAN J L，LEI B.Two-dimensional extension of minimum error threshold segmentation method for gray-level images［J］.Acta Automatica Sinica，2009，35(4):386-393(in Chinese).

［8］ ZHU D Q，JING L Q，BI R S，et al.Improvement algorithm of minimum-error thresholding segmentation method［J］.Opto-Electronic Engineering，2010，37(7):107-113(in Chinese).

［9］ WU Y Q，ZHANG X J，WU Sh H，et al.Two-dimensional minimum error thresholding based on chaotic particle swarm optimization or decomposition［J］.Journal of Zhejiang University(Engineer Science E-dition)，2011，45(7):1198-1205(in Chinese).

［10］ ZHANG X M，F(xiàn)ENG W H，HE W T，et al.Two-dimensional minimum error thresholding method nased on the artificial bee colony algorithm［J］.Journal of Guangxi University(Natural Science Edition)，2013，38(5):1126-1133(in Chinese).

［11］ XUE J H，TITTERINGTON D M.Median-based image thresholding［J］.Image and Vision Computing，2011，29(9):631-637.

［12］ LIU J，YU Z B，JIN W D.Three dimentional minimum error threshold algorithm and its fast recursive mathod［J］.Journal of Electronics ＆ Information Technology，2013，35(9):2073-2080(in Chinese).

［13］ CUI T Y，LIU W P，ZHANG N.Algorithms and performance comparison of automatic thresholdingsegmentation for forest regions in remote sensing image［J］.Journal of Computer Applications，2010，30(12):3269-3273(in Chinese).

［14］ YUE F，ZUO W M，WANG K Q.Decomposition based two-dimensional thresholdalgorithm for grayimages［J］.Acta Automatica Sinica，2009，35(7):1022-1027(in Chinese).

［15］ GONG Q，NI L，TANG P F，et al.Fast three-dimensional Otsu image segmentation algorithm based on decomposition［J］.Journal of Computer Applications，2012，32(6):1526-1528(in Chinese).