文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.2016.12.028
中文引用格式： 徐超，黃風(fēng)華，毛政元. 一種改進(jìn)的二維Otsu閾值分割算法[J].電子技術(shù)應(yīng)用，2016，42(12)：108-111.
英文引用格式： Xu Chao，Huang Fenghua，Mao Zhengyuan. An improved two-dimensional Otsu thresholding segmentation method[J].Application of Electronic Technique，2016，42(12)：108-111.
0 引言
圖像分割是將圖像劃分為一組子區(qū)，使得每個(gè)子區(qū)的內(nèi)部都具有某種同質(zhì)性、而任意兩個(gè)相鄰的子區(qū)間則不具備此種同質(zhì)性的過(guò)程。它是涉及計(jì)算機(jī)視覺(jué)、圖像分析和模式識(shí)別等領(lǐng)域的重要研究?jī)?nèi)容[1]，歷經(jīng)數(shù)十年的發(fā)展，各類(lèi)文獻(xiàn)中提出的圖像分割方法已經(jīng)形成了復(fù)雜的譜系[2-3]，閾值分割法是其中的一個(gè)分支，因其實(shí)現(xiàn)簡(jiǎn)單、執(zhí)行效率高而被廣泛運(yùn)用。日本學(xué)者OTSU N于1978年提出的Otsu算法被稱(chēng)之為最大類(lèi)間方差法[4]，是目前閾值分割法的主流算法之一，分割效果良好[5]。但傳統(tǒng)的一維Otsu法僅僅考慮了圖像的灰度信息，而未充分考慮圖像的空間信息，因此當(dāng)圖像直方圖沒(méi)有出現(xiàn)明顯的雙峰時(shí)，利用該方法進(jìn)行分割會(huì)出現(xiàn)信息丟失現(xiàn)象。
為此，劉健莊等人提出了二維Otsu法，利用圖像灰度值和鄰域平均灰度值作為兩個(gè)維度進(jìn)行閾值分割，使其抗噪性得到了提升，但是同樣提高了計(jì)算的復(fù)雜度[6]；在此基礎(chǔ)上，Gong Jian等人提出了二維Otsu的快速分割算法，將原算法時(shí)間復(fù)雜度從O(L4)降低到O(L2)[7]；范九倫等人提出二維Otsu曲線算法，將閾值范圍限制在主對(duì)角線與次對(duì)角線之間，有效地降低了算法的時(shí)間復(fù)雜度[8]；汪海洋等人提出了改進(jìn)的二維Otsu閾值分割算法，通過(guò)遞歸的方式創(chuàng)建查找表，減少大量冗余的計(jì)算過(guò)程，降低計(jì)算量[9]；Wu Chengmao等人通過(guò)求取多元函數(shù)極值的方法構(gòu)建迭代算法，降低了時(shí)間開(kāi)銷(xiāo)和存儲(chǔ)空間開(kāi)銷(xiāo)[10]；江禹生等人利用遺傳算法來(lái)快速獲取二維Otsu閾值算法的近似最優(yōu)閾值，唐英干等人則利用粒子群算法來(lái)優(yōu)化二維Otsu法的分割閾值，但是這種優(yōu)化算法容易過(guò)早地收斂而陷入到局部最優(yōu)的結(jié)果中，并且算法的代碼量過(guò)大[11-12]。
為了進(jìn)一步降低二維Otsu閾值分割算法的計(jì)算量同時(shí)提高其分割效果，本文利用分解的思想，將二維Otsu最佳閾值(s，t)分解為兩個(gè)一維Otsu最佳閾值s和t。同時(shí)，在獲取一維Otsu最佳閾值過(guò)程中，引入了類(lèi)內(nèi)方差概念，并提出一種改進(jìn)的最佳閾值判別函數(shù)，從而得到最佳閾值s和t。
1 二維Otsu閾值分割算法
傳統(tǒng)的二維Otsu算法主要是利用圖像鄰域中心灰度值與其鄰域均值構(gòu)成的二維直方圖來(lái)進(jìn)行分割，因此具有良好的抗噪性，其原理如下：
設(shè)一幅圖像f(x，y)的大小為M×M，其灰度級(jí)為L(zhǎng)(0，1，2，…，L-1)，它的鄰域均值圖像g(x，y)(以3×3鄰域均值作為該像素灰度值)灰度級(jí)也為L(zhǎng)(0，1，2，…，L-1)，由此形成一個(gè)二元組：像素的灰度值i和其鄰域灰度均值j。設(shè)灰度值為i且鄰域灰度均值為j的像素?cái)?shù)為fij，圖像像素總數(shù)為N，則對(duì)應(yīng)的聯(lián)合概率密度pij可定義為：
假設(shè)給定一個(gè)門(mén)限向量(s，t)，s為灰度閾值，t為鄰域灰度均值閾值，可以將圖1所示的正方形分割為I、II、III、IV 4個(gè)區(qū)域。由于圖像目標(biāo)或者背景內(nèi)部像素點(diǎn)之間的相關(guān)性很強(qiáng)，像素點(diǎn)的灰度值和其鄰域灰度均值十分接近；而在目標(biāo)和背景邊緣處或者噪聲部分，它的灰度值與其鄰域灰度均值差異明顯。因此，圖1中I代表的是背景部分，III代表的是目標(biāo)部分，II和IV分別代表邊緣和噪聲部分。假設(shè)圖像目標(biāo)和背景分別用C0和C1表示，則它們出現(xiàn)的概率分別為：
大多數(shù)情況下，遠(yuǎn)離對(duì)角線的概率較小，即邊緣點(diǎn)和噪聲點(diǎn)的概率很小，可忽略不計(jì)。因此可以假設(shè)：w0+w1=1；uT=w0u0+w1u1。
定義圖像類(lèi)間離散度矩陣為：
最佳閾值為tr(Sb)取得最大時(shí)的(s，t)。
2 改進(jìn)的快速二維Otsu算法
為了降低二維Otsu算法復(fù)雜度以及提高分割效果，本文提出一種改進(jìn)的快速二維Otsu算法。該算法將傳統(tǒng)的二維Otsu算法分解為兩個(gè)一維Otsu算法，即原圖像f(x，y)獲取一個(gè)閾值s，它的鄰域均值圖像g(x，y)獲取一個(gè)閾值t。從計(jì)算機(jī)的角度上看，分別求解兩個(gè)閾值以代替原來(lái)二維Otsu算法的閾值，這種方法不但降低了算法時(shí)間復(fù)雜度，而且降低了計(jì)算機(jī)的存儲(chǔ)空間。另外，傳統(tǒng)的二維Otsu算法以及一些改進(jìn)的二維Otsu算法的閾值判別函數(shù)只考慮目標(biāo)與背景之間的方差大小，即類(lèi)間方差越大，分割效果越好。然而，這些算法并未考慮目標(biāo)或背景內(nèi)的內(nèi)聚性，即目標(biāo)類(lèi)和背景類(lèi)內(nèi)部像素具有較強(qiáng)的相關(guān)性。因此，本文綜合考慮類(lèi)間方差和類(lèi)內(nèi)方差的概念，提出一個(gè)新的閾值判別函數(shù)。
定義1 設(shè)閾值s將一組離散的數(shù)據(jù)分成了兩類(lèi)，定義其類(lèi)間方差為：
式中，u0、u1分別代表目標(biāo)類(lèi)和背景類(lèi)的均值，w0、w1分別代表目標(biāo)類(lèi)和背景類(lèi)的概率。因此，sp值越大，即類(lèi)間方差越大，目標(biāo)類(lèi)和背景類(lèi)區(qū)分就越明顯，分割效果越好。
定義2 設(shè)閾值s將一組離散的數(shù)據(jù)分成了兩類(lèi)，pi表示i出現(xiàn)的概率，u0、u1分別表示兩類(lèi)的均值，w0、w1分別表示兩類(lèi)的概率，則這組數(shù)據(jù)兩類(lèi)的類(lèi)內(nèi)方差分別表示：
顯然，sw表示這組數(shù)據(jù)兩類(lèi)類(lèi)內(nèi)的內(nèi)聚性，其值越小，分割效果越好。
為了進(jìn)一步考慮類(lèi)間方差和類(lèi)內(nèi)方差這兩個(gè)因素，即類(lèi)間方差越大，類(lèi)內(nèi)方差越小，所得到的分割效果越好。因此，本文提出一個(gè)新的判別函數(shù)，即類(lèi)間類(lèi)內(nèi)方差比值法：
S=sp/sw (13)
則最優(yōu)閾值滿足S*=argmax{S}，其對(duì)應(yīng)的灰度值則為最佳閾值。類(lèi)似可求得鄰域均值圖像g(x，y)的最佳閾值t，該方法避免了在L×L維進(jìn)行窮舉遍歷，只需要在兩個(gè)長(zhǎng)度為L(zhǎng)的空間內(nèi)尋找最佳閾值即可，從而降低了計(jì)算量，減少計(jì)算機(jī)所需存儲(chǔ)空間。算法步驟如下：
(1)初始閾值范圍計(jì)算
由于圖像目標(biāo)灰度必然高于大量背景的均值，因此將初始閾值的下限設(shè)定為圖像灰度均值m，實(shí)驗(yàn)也證實(shí)了該結(jié)論。另外由于圖像目標(biāo)灰度必然不高于圖像最大灰度值，因此將初始閾值的上限設(shè)定為圖像最大灰度值n。
(2)最佳閾值求取
為了進(jìn)一步降低運(yùn)算時(shí)間，本文將二維圖像灰度矩陣轉(zhuǎn)換為一維矩陣(1，L)，并根據(jù)式(9)、式(12)分別求取圖像類(lèi)間方差sp、類(lèi)內(nèi)方差sw，進(jìn)而根據(jù)式(13)得到最佳閾值s，同樣可以求得鄰域均值圖像g(x，y)的最佳閾值t。
(3)分割圖像
利用上一步得到的閾值(s，t)分割圖像，并將其二值化。
3 實(shí)驗(yàn)結(jié)果
為了驗(yàn)證本文算法的可行性和有效性，將它與傳統(tǒng)二維Otsu算法、快速二維Otsu算法進(jìn)行比較。實(shí)驗(yàn)環(huán)境為：Win8.1專(zhuān)業(yè)版，IntelCore(TM) i5-3570 CPU @ 3.40 GHz，RAM 4.00 GB，MATLAB R2012b。
在實(shí)際應(yīng)用環(huán)境中，獲取到的圖像背景一般較為復(fù)雜并且信噪比較低。為了驗(yàn)證本文算法的分割效果，以rice圖像、lena圖像、學(xué)生合照作為樣本數(shù)據(jù)，選擇目前閾值法中效果較好的傳統(tǒng)二維Otsu算法、快速二維Otsu算法與本文算法進(jìn)行實(shí)驗(yàn)對(duì)比，結(jié)果如圖2～圖4所示。表1為本文算法與傳統(tǒng)二維Otsu法、快速二維Otsu法針對(duì)各樣本數(shù)據(jù)的運(yùn)算時(shí)間。
上述實(shí)驗(yàn)所用的lena圖像大小為512×512，rice圖像大小為256×256,學(xué)生合照大小為768×1 024。從表1可知，在上述實(shí)驗(yàn)環(huán)境下，本文算法時(shí)間復(fù)雜度遠(yuǎn)低于文獻(xiàn)[6]和文獻(xiàn)[9]的算法，處理時(shí)間大為降低。就分割效果而言，本文綜合考慮類(lèi)間方差和類(lèi)內(nèi)方差(即類(lèi)間的離散測(cè)度信息和類(lèi)內(nèi)的內(nèi)聚性)得到的分割結(jié)果抗噪性和目標(biāo)內(nèi)聚性均優(yōu)于傳統(tǒng)二維Otsu算法與快速二維Otsu算法。圖2(d)的上半部分沒(méi)有出現(xiàn)圖2(b)與圖2(c)中的細(xì)微噪聲顆粒，而下半部分米粒的完整性也更好；圖3(d)中分割出來(lái)的頭發(fā)和柱子內(nèi)部更具飽和性；圖4(d)中漢字和學(xué)生眼睛、鼻子、嘴巴等目標(biāo)更能清晰地識(shí)別出來(lái)。
4 結(jié)論
為了進(jìn)一步降低二維Otsu算法復(fù)雜度、提高分割質(zhì)量，本文提出了改進(jìn)的二維Otsu算法。根據(jù)本文算法與其他同類(lèi)算法處理相同樣本圖像的實(shí)驗(yàn)結(jié)果表明，本文提出的算法在分割效果和算法復(fù)雜度兩個(gè)方面都具有明顯提高。另外，將本文的算法思想擴(kuò)展到三維甚至高維Otsu算法時(shí)，算法復(fù)雜度不會(huì)明顯提高。如何集成Otsu與其他同類(lèi)算法得到更佳的分割效果，是后續(xù)研究要解決的問(wèn)題。
參考文獻(xiàn)
[1] 岡薩雷斯.數(shù)字圖像處理[M].第三版.北京：電子工業(yè)出版社，2011.
[2] BHARGAVI K，JYOTHI S.A survey on threshold based segmentation technique in image processing[J].International Journal of Innovative Research and Development，2014，3(12)：234-238.
[3] TANEJA A，RANJAN P，UJJLAYAN A.A performance study of image segmentation techniques[C].Reliability，Infocom Technologies and Optimization(ICRITO)(Trends and Future Directions)，2015 4th International Conference on.IEEE，2015：1-6.
[4] OTSU N.A threshold selection method from gray-level histograms[J].Automatica，1975，11(285-296)：23-27.
[5] SEZGIN M.Survey over image thresholding techniques and quantitative performance evaluation[J].Journal of Electronic Imaging，2004，13(1)：146-168.
[6] 劉健莊，栗文青.灰度圖像的二維Otsu自動(dòng)閾值分割法[J].自動(dòng)化學(xué)報(bào)，1993，19(1)：101-105.
[7] Gong Jian，Li Liyuan，Chen Weinan.A fast recursive algorithm for two-dimensional thresholding[C].Signal Processing，1996，3rd International Conference on.IEEE，1996，2：1155-1158.
[8] 范九倫，趙鳳.灰度圖像的二維Otsu曲線閾值分割法[J].電子學(xué)報(bào)，2007，35(4)：751-755.
[9] 汪海洋，潘德?tīng)t，夏德深.二維Otsu自適應(yīng)閾值選取算法的快速實(shí)現(xiàn)[J].自動(dòng)化學(xué)報(bào)，2007，33(9)：968-971.
[10] Wu Chengmao，Tian Xiaoping，Tan Tieniu.Fast iterative algorithm for 2D Otsu thresholding method[J].PR&AI，2008，21(6)：746-757.
[11] 江禹生，宋香麗，任晶晶.基于遺傳算法的二維Otsu算法改進(jìn)[J].計(jì)算機(jī)應(yīng)用研究，2010，27(3)：1189-1191.
[12] 唐英干，劉冬，關(guān)新平.基于粒子群和二維Otsu方法的快速圖像分割[J].控制與決策，2007，22(2)：202-205.