龔劬,倪麟,唐萍峰,葉劍英,廖武忠
重慶大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,重慶 401331
改進的三維Otsu圖像分割快速算法
龔劬,倪麟,唐萍峰,葉劍英,廖武忠
重慶大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,重慶 401331
針對三維Otsu圖像分割算法運算量大和圖像細節(jié)分割不夠準(zhǔn)確的問題,提出一種改進的三維Otsu圖像分割算法。該算法基于灰度-鄰域平均灰度-梯度的新的三維特征模型,構(gòu)建三維直方圖;將三維Otsu分解為三個一維Otsu;在同時考慮類間距離和類內(nèi)距離的基礎(chǔ)上,提出一種新的最大散度差準(zhǔn)則。實驗結(jié)果表明,該算法不僅可以取得較好的分割效果,而且計算量較小,比三維Otsu閾值分割遞推算法快900倍左右。
圖像分割;Otsu;三維直方圖;閾值
圖像分割是指將一幅圖像分解為若干個互不交疊的、有意義的、具有相同性質(zhì)的區(qū)域[1-2]。它是圖像工程中的重點和熱點,也是計算機視覺中的難題。至今,提出的分割算法已有上千種,其中最經(jīng)典的方法就是基于灰度閾值的分割方法。閾值分割利用了圖像中所要提取的目標(biāo)和背景在灰度上的差異,把圖像視為不同灰度級的目標(biāo)和背景兩類區(qū)域的組合,選擇合適的閾值以確定圖像中每個像素應(yīng)屬于目標(biāo)還是背景的區(qū)域。Otsu法[3]因計算簡單、實時性高等優(yōu)點被廣泛使用[4-6]。但是,Otsu法只使用了灰度信息,而沒有考慮空間鄰域信息,抗噪性較弱。為此,人們利用圖像像素與其鄰域之間存在一定相關(guān)性的這一空間信息,推導(dǎo)出了相應(yīng)的二維算法[7-8]及三維算法[9-11]。相對于一維Otsu算法,二維算法和三維算法取得了較好的分割效果。但是,對于邊緣細節(jié)的處理,以及一些強噪聲的抑制上,二維算法的處理效果也不夠好。而目前的三維Otsu算法[9-11]均是基于灰度-鄰域平均灰度-鄰域中值的三維直方圖,但是中值會破壞掉圖像中大量的高頻邊緣細節(jié)信息,使得圖像變得模糊不清,特別對一些細節(jié)多,如點、線、尖頂細節(jié)較多的圖像不宜使用中值方法[12],否則會使得分割不夠準(zhǔn)確。因此,為了抑制噪聲,又盡量凸顯以及還原圖像中的細節(jié)并減小算法的計算量,本文把像素的梯度作為第三維加入到三維Otsu算法中,提出一種改進的三維Otsu圖像分割快速算法。經(jīng)過多次實驗表明,該算法不僅可以取得較好的分割效果,而且計算量較小,比三維Otsu閾值分割遞推算法快900倍左右。
在文獻[9]中,景曉軍等利用原始圖像、鄰域平均圖像以及鄰域中值圖像聯(lián)合直方圖,提出了三維Otsu算法。該方法不僅充分利用了圖像像素點的信息,而且還考慮到了鄰域圖像像素點以及鄰域中值圖像像素點的空間相關(guān)信息,具有很好的抗噪性。三維Otsu算法在文獻[9]中有詳細敘述,在此不再贅述。
3.1 基于灰度-鄰域平均灰度-梯度的三維直方圖
目前傳統(tǒng)三維Otsu算法中一般采用鄰域中值作為第三維,雖然有利于噪聲抑制,但是弱化了圖像的邊緣和細節(jié)等信息。因此,本文從考慮抑制噪聲和增強圖像的邊緣和細節(jié)出發(fā),將三維直方圖的第三個分量改為像素點的梯度。梯度運算實際上是一種非線性銳化濾波器,能夠使邊緣和輪廓線模糊的圖像變得清晰,并使其細節(jié)清晰[12]。這里梯度算法選擇了對灰度漸變和噪聲較多的圖像處理較好的Sobel算子。該算子的計算公式如下:
式中,f(m,n)表示像素點(m,n)處的灰度,▽fm(m,n)、▽fn(m,n)分別表示橫、縱坐標(biāo)方向的一階微分,G[f(m,n)]表示梯度。為了提高最佳閾值選取的速度以及后文處理的方便,將其范圍壓縮至[0,255]以內(nèi)。
3.2 分解的灰度-鄰域平均灰度-梯度三維Otsu算法
3.3 最大散度差準(zhǔn)則
由于本文已經(jīng)成功地將三維分解為三個一維即將三維Otsu遞推算法的計算復(fù)雜度從O(L3)降到了O(L),所以在求取最佳閾值時,就放在一維的Otsu中求取最佳閾值,這樣算法的計算復(fù)雜度就為O(L),可大幅度地提高計算速度,提高算法的實用性。
傳統(tǒng)三維Otsu算法和加權(quán)的三維Otsu算法的類間散度函數(shù)都只考慮目標(biāo)類和背景類的類間距離,也就是說類間距離越大,分割的效果越好。然而,上述的兩個算法都沒有考慮到目標(biāo)類和背景類的每個類自身像素的分類信息,也就是說沒有考慮類內(nèi)距離。因此,本文同時考慮類間距離和類內(nèi)距離,最大散度差準(zhǔn)則以廣義散度差[13-14]即類間距離減去C倍的類內(nèi)距離作為數(shù)據(jù)的可分離性度量,并且可以通過調(diào)節(jié)參數(shù)C來改變類內(nèi)距離在分離性中的作用。
定義3.1設(shè)用值s將一組離散的數(shù)據(jù)分為了兩類,對于這兩個類,定義其類間距離為:
其中μ1(s),μ0(s)是對應(yīng)各自類別元素均值??梢钥闯?,sb(s)越大,類間距離就越大,目標(biāo)和背景就分得越開,分割效果就越好。
定義3.2設(shè)用值s將一組離散的數(shù)據(jù)分為了兩類,Pi是數(shù)據(jù)i出現(xiàn)的概率,W0(s)和W1(s)分別是兩類所占的概率,μ0(s)和μ1(s)是對應(yīng)的兩類的均值,那么這兩類的類內(nèi)距離分別為:
兩類的總體類內(nèi)距離為:
那么最大散度差準(zhǔn)則的數(shù)學(xué)形式就定義為:
當(dāng)G(s)取最大值所對應(yīng)的灰度級即為所求的最佳閾值s0,即s0=argmax{} G(s)。
3.4 快速實現(xiàn)方法
為了驗證本文算法的有效性和可行性,實驗選取了一幅普通圖像、兩幅Berkeley segmentation dataset[15]里的人物圖像、一幅VOC dataset里的摩托車圖像,并與文獻[3,8,10-11]的算法進行了比較。實驗環(huán)境為Windows XP操作系統(tǒng),系統(tǒng)配置1.96 GB內(nèi)存,3.19 GHz,Matlab 7.5.0(R2007b)。這里的VOC數(shù)據(jù)庫是來自于名叫Mark Everingham,University of Oxford的一位學(xué)者。
參數(shù)的選取是本文關(guān)鍵的步驟,對分割的結(jié)果有著重要影響。在本文中,參數(shù)的選取是根據(jù)具體的圖像,通過實驗數(shù)據(jù),分析不同圖像的類間距離和類內(nèi)距離而得到的。本文通過大量的實驗觀察發(fā)現(xiàn),參數(shù)取值為10或者在10的左右分割較好。從以上實驗結(jié)果可以看出,本文提出的基于灰度-鄰域平均灰度-梯度直方圖的三維Otsu算法分割效果可以達到甚至優(yōu)于遞推的三維Otsu圖像分割算法[10]和加權(quán)的三維Otsu算法[11]。在圖1中,它是對輪胎圖像的分割。文獻[3,8,10-11]算法的分割效果都不是很理想,提取出來的輪胎都包括了部分背景;而本文算法巧妙地將輪胎從背景中分離出來,并且輪胎內(nèi)部細節(jié)和輪廓較為清晰,這是其他幾個算法都不能達到的效果。圖2中的摩托車圖像選自于VOC dataset圖像分割測試集,本文算法的優(yōu)勢在于將前輪的影子給正確地分割成了背景,且摩托車的輪廓更為清晰。圖3是Berkeley segmentation dataset里的一幅人物圖像,可以看出,其他的幾個算法效果都相當(dāng),都未能較好提取出人物目標(biāo),大部分背景都錯分成了目標(biāo);而本文算法卻將人物目標(biāo)大致從背景中分割出來。圖4是Berkeley segmentation dataset里的一幅女孩圖像,本文算法成功地將女孩頭部和背景分割開來,圖像右側(cè)的背景分割也更為理想,這是其他幾個算法都不具有的分割效果。表1給出了各個算法的運算時間比較。
圖1 輪胎圖像的分割效果(參數(shù):C1=6,C2=6,C3=6)
圖2 摩托車圖像的分割效果(參數(shù):C1=6,C2=6,C3=8)
圖3 人物運動圖像的分割效果(參數(shù):C1=10,C2=10,C3=10)
圖4 女孩圖像的分割效果(參數(shù):C1=10,C2=6,C3=10)
表1 各個算法的運算時間比較s
從分割圖像自身的特點出發(fā),本文提出一種基于灰度-鄰域平均灰度-梯度直方圖的三維Otsu圖像分割快速算法。該算法不僅能較好地保留圖像邊緣和細節(jié)信息,而且還更能準(zhǔn)確地將圖像目標(biāo)和背景分割開來,大大提高了分割的準(zhǔn)確性。需要指出的是,對于不同的圖像,由于三維Otsu方法每一維在圖像分割中所起的作用不同,如何自適應(yīng)地確定三個參數(shù),使得分割的效果更佳將是繼續(xù)研究的問題。
[1]岡薩雷斯.數(shù)字圖像處理[M].2版.北京:電子工業(yè)出版社,2003:460-521.
[2]姚敏.數(shù)字圖像處理[M].北京:機械工業(yè)出版社,2006:243-253.
[3]Otsu N.A threshold selection method from gray-level histograms[J].IEEE Transactions on Systems,Man and Cybernetics,1979,9(1):62-66.
[4]Farrahi M R,Cheriet M.A multi-scale framework for adaptive binarization of degraded document images[J].Pattern Recognition,2010,43(6):2186-2198.
[5]Yang Wenzhu,Li Daoliang,Zhu Liang,et al.A new approach for image processing in foreign fiber detection[J].Computers and Electronics in Agriculture,2009,68(1):68-77.
[6]Chung Kuo-liang,Tsai Chia-lun.Fast incremental algorithm for speeding up the computation of binarization[J].Applied Mathematics and Computation,2009,212(2):396-408.
[7]劉健莊,栗文青.灰度圖像的二維Otsu自動閾值分割法[J].自動化學(xué)報,1993,19(1):101-105.
[8]岳峰,左旺孟,王寬全.基于分解的灰度圖像二維閾值選取算法[J].自動化學(xué)報,2009,359(7):1022-1027.
[9]景曉軍,李劍峰,劉郁林.一種基于三維最大類間方差的圖像分割算法[J].電子學(xué)報,2003,31(9):1281-1285.
[10]范九倫,趙鳳,張雪峰.三維Otsu閾值分割方法的遞推算法[J].電子學(xué)報,2007,35(7):1398-1402.
[11]呂燕,龔劬.加權(quán)三維Otsu方法在圖像分割中的應(yīng)用[J].計算機應(yīng)用研究,2011,28(4):1576-1579.
[12]劉直芳.數(shù)字圖像處理與分析[M].北京:清華大學(xué)出版社,2006:79-85.
[13]宋楓溪,張大鵬,楊靜宇,等.基于最大散度差鑒別準(zhǔn)則的自適應(yīng)分類算法[J].自動化學(xué)報,2006,32(4):541-549.
[14]宋楓溪,程科,楊靜宇,等.最大散度差和大間距線性投影與支持向量機[J].自動化學(xué)報,2004,30(6):890-896.
[15]Arbelaez P,Maire M,F(xiàn)owlkes C,et al.Contour detection and hierarchical image segmentation[J].IEEE TPAMI,2011,33(5):898-916.
GONG Qu,NI Lin,TANG Pingfeng,YE Jianying,LIAO Wuzhong
College of Mathematics&Statistics,Chongqing University,Chongqing 401331,China
Aiming at the weakness of image detail and the huge calculation of the three-dimensional Otsu,an improved three-dimensional Otsu image segmentation algorithm is presented.A three-dimensional histogram based on gray level-average gray level-gradient is built.The original three-dimensional Otsu algorithm is decomposed into three one-dimensional Otsu algorithms.Based on the one-dimensional Otsu algorithm,a novel maximum scatter difference discriminant criterion is proposed.The criterion considers simultaneously both between-class distance and within-class distance.The experimental results show that the proposed algorithm does not only get satisfactory segmentation result,but also improves the calculation speed,which spends 900 times less than the recursive algorithm for the three-dimensional Otsu method.
image segmentation;Otsu;three-dimensional histogram;threshold
A
TP391.41
10.3778/j.issn.1002-8331.1204-0563
GONG Qu,NI Lin,TANG Pingfeng,et al.Improved fast three-dimensional Otsu image segmentation algorithm. Computer Engineering and Applications,2014,50(6):171-174.
中央高校基本科研業(yè)務(wù)費基金資助項目(No.CDJXS11100032)。
龔劬(1963—),女,博士,教授,主要研究方向:圖像處理和小波分析;倪麟(1987—),男,碩士研究生,主要研究方向:圖像處理;唐萍峰(1987—),男,碩士研究生,主要研究方向:模式識別和圖像處理;葉劍英(1987—),女,碩士研究生,主要研究方向:圖像處理;廖武忠(1986—),男,碩士研究生,主要研究方向:圖像處理。E-mail:nilin871124@163.com
2012-05-02
2012-08-03
1002-8331(2014)06-0171-04
CNKI網(wǎng)絡(luò)優(yōu)先出版:2012-09-06,http://www.cnki.net/kcms/detail/11.2127.TP.20120906.0855.007.html