文獻(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ì)性的過程,。它是涉及計(jì)算機(jī)視覺、圖像分析和模式識(shí)別等領(lǐng)域的重要研究?jī)?nèi)容[1],,歷經(jīng)數(shù)十年的發(fā)展,,各類文獻(xiàn)中提出的圖像分割方法已經(jīng)形成了復(fù)雜的譜系[2-3],閾值分割法是其中的一個(gè)分支,,因其實(shí)現(xiàn)簡(jiǎn)單,、執(zhí)行效率高而被廣泛運(yùn)用。日本學(xué)者OTSU N于1978年提出的Otsu算法被稱之為最大類間方差法[4],,是目前閾值分割法的主流算法之一,,分割效果良好[5]。但傳統(tǒng)的一維Otsu法僅僅考慮了圖像的灰度信息,,而未充分考慮圖像的空間信息,,因此當(dāng)圖像直方圖沒有出現(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閾值分割算法,,通過遞歸的方式創(chuàng)建查找表,,減少大量冗余的計(jì)算過程,降低計(jì)算量[9],;Wu Chengmao等人通過求取多元函數(shù)極值的方法構(gòu)建迭代算法,,降低了時(shí)間開銷和存儲(chǔ)空間開銷[10];江禹生等人利用遺傳算法來快速獲取二維Otsu閾值算法的近似最優(yōu)閾值,,唐英干等人則利用粒子群算法來優(yōu)化二維Otsu法的分割閾值,,但是這種優(yōu)化算法容易過早地收斂而陷入到局部最優(yōu)的結(jié)果中,并且算法的代碼量過大[11-12],。
為了進(jìn)一步降低二維Otsu閾值分割算法的計(jì)算量同時(shí)提高其分割效果,,本文利用分解的思想,將二維Otsu最佳閾值(s,,t)分解為兩個(gè)一維Otsu最佳閾值s和t,。同時(shí),在獲取一維Otsu最佳閾值過程中,,引入了類內(nèi)方差概念,,并提出一種改進(jìn)的最佳閾值判別函數(shù),從而得到最佳閾值s和t,。
1 二維Otsu閾值分割算法
傳統(tǒng)的二維Otsu算法主要是利用圖像鄰域中心灰度值與其鄰域均值構(gòu)成的二維直方圖來進(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è)門限向量(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,。
定義圖像類間離散度矩陣為:
最佳閾值為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è)閾值以代替原來二維Otsu算法的閾值,這種方法不但降低了算法時(shí)間復(fù)雜度,,而且降低了計(jì)算機(jī)的存儲(chǔ)空間,。另外,傳統(tǒng)的二維Otsu算法以及一些改進(jìn)的二維Otsu算法的閾值判別函數(shù)只考慮目標(biāo)與背景之間的方差大小,,即類間方差越大,分割效果越好,。然而,,這些算法并未考慮目標(biāo)或背景內(nèi)的內(nèi)聚性,即目標(biāo)類和背景類內(nèi)部像素具有較強(qiáng)的相關(guān)性,。因此,,本文綜合考慮類間方差和類內(nèi)方差的概念,提出一個(gè)新的閾值判別函數(shù),。
定義1 設(shè)閾值s將一組離散的數(shù)據(jù)分成了兩類,,定義其類間方差為:
式中,u0,、u1分別代表目標(biāo)類和背景類的均值,,w0、w1分別代表目標(biāo)類和背景類的概率,。因此,,sp值越大,即類間方差越大,,目標(biāo)類和背景類區(qū)分就越明顯,,分割效果越好。
定義2 設(shè)閾值s將一組離散的數(shù)據(jù)分成了兩類,,pi表示i出現(xiàn)的概率,,u0、u1分別表示兩類的均值,,w0,、w1分別表示兩類的概率,則這組數(shù)據(jù)兩類的類內(nèi)方差分別表示:
顯然,,sw表示這組數(shù)據(jù)兩類類內(nèi)的內(nèi)聚性,,其值越小,分割效果越好。
為了進(jìn)一步考慮類間方差和類內(nèi)方差這兩個(gè)因素,,即類間方差越大,,類內(nèi)方差越小,所得到的分割效果越好,。因此,,本文提出一個(gè)新的判別函數(shù),即類間類內(nèi)方差比值法:
S=sp/sw (13)
則最優(yōu)閾值滿足S*=argmax{S},,其對(duì)應(yīng)的灰度值則為最佳閾值,。類似可求得鄰域均值圖像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)分別求取圖像類間方差sp、類內(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專業(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í)間大為降低。就分割效果而言,,本文綜合考慮類間方差和類內(nèi)方差(即類間的離散測(cè)度信息和類內(nèi)的內(nèi)聚性)得到的分割結(jié)果抗噪性和目標(biāo)內(nèi)聚性均優(yōu)于傳統(tǒng)二維Otsu算法與快速二維Otsu算法。圖2(d)的上半部分沒有出現(xiàn)圖2(b)與圖2(c)中的細(xì)微噪聲顆粒,,而下半部分米粒的完整性也更好,;圖3(d)中分割出來的頭發(fā)和柱子內(nèi)部更具飽和性;圖4(d)中漢字和學(xué)生眼睛,、鼻子,、嘴巴等目標(biāo)更能清晰地識(shí)別出來。
4 結(jié)論
為了進(jìn)一步降低二維Otsu算法復(fù)雜度,、提高分割質(zhì)量,,本文提出了改進(jìn)的二維Otsu算法。根據(jù)本文算法與其他同類算法處理相同樣本圖像的實(shí)驗(yàn)結(jié)果表明,,本文提出的算法在分割效果和算法復(fù)雜度兩個(gè)方面都具有明顯提高,。另外,將本文的算法思想擴(kuò)展到三維甚至高維Otsu算法時(shí),,算法復(fù)雜度不會(huì)明顯提高,。如何集成Otsu與其他同類算法得到更佳的分割效果,是后續(xù)研究要解決的問題,。
參考文獻(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] 汪海洋,,潘德爐,夏德深.二維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.