一種改進(jìn)的二維Otsu閾值分割算法*

徐 超，黃風(fēng)華，毛政元

（1.福州大學(xué) 福建省空間信息工程研究中心，福建 福州 350002；2.福州大學(xué) 空間數(shù)據(jù)挖掘與信息共享教育部重點(diǎn)實(shí)驗(yàn)室，福建 福州 350002；3.福州大學(xué) 地理空間信息技術(shù)國(guó)家地方聯(lián)合工程研究中心，福建 福州 350002；4.福州大學(xué) 陽(yáng)光學(xué)院，福建 福州 350015）

一種改進(jìn)的二維Otsu閾值分割算法*

徐 超1，2，3，黃風(fēng)華1，4，毛政元1，2，3

（1.福州大學(xué) 福建省空間信息工程研究中心，福建 福州 350002；2.福州大學(xué) 空間數(shù)據(jù)挖掘與信息共享教育部重點(diǎn)實(shí)驗(yàn)室，福建 福州 350002；3.福州大學(xué) 地理空間信息技術(shù)國(guó)家地方聯(lián)合工程研究中心，福建 福州 350002；4.福州大學(xué) 陽(yáng)光學(xué)院，福建 福州 350015）

Otsu算法，也被稱(chēng)之為最大類(lèi)間方差算法，是實(shí)現(xiàn)閾值分割的經(jīng)典算法之一。二維 Otsu算法是一維 Otsu算法的推廣，它充分考慮了圖像的灰度信息和空間鄰域信息，可以有效濾除噪聲影響，但是同樣存在著運(yùn)算量大、時(shí)效性差的問(wèn)題。對(duì)此提出了一種改進(jìn)的二維Otsu快速閾值分割算法，先將二維Otsu算法分解為兩個(gè)一維Otsu算法，并集成類(lèi)間和類(lèi)內(nèi)方差信息構(gòu)造了一種新的閾值判別函數(shù)，同時(shí)通過(guò)降維，進(jìn)一步降低計(jì)算量。實(shí)驗(yàn)結(jié)果表明，該算法在時(shí)間效率與分割效果兩方面明顯優(yōu)于傳統(tǒng)的二維Otsu算法與快速二維Otsu算法。

閾值分割；二維Otsu；類(lèi)間方差；類(lèi)內(nèi)方差

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)的概率分別為：

圖1 二維直方圖的平面投影

對(duì)應(yīng)兩類(lèi)的均值向量為：

則二維直方圖總的均值向量為：

大多數(shù)情況下，遠(yuǎn)離對(duì)角線的概率較小，即邊緣點(diǎn)和噪聲點(diǎn)的概率很小，可忽略不計(jì)。因此可以假設(shè)：w0+w1=1；uT=w0u0+w1u1。

定義圖像類(lèi)間離散度矩陣為：

離散度矩陣的秩為：

通過(guò)化簡(jiǎn)可以將式(6)改寫(xiě)為：

最佳閾值為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)間方差為：

將式(9)化簡(jiǎn)，得：

式中，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)方差分別表示：

則兩者類(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)方差比值法：

則最優(yōu)閾值滿(mǎn)足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è)版，Intel?Core(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í)間。

圖2 rice圖像分割效果

圖3 lena圖像分割效果

圖4 學(xué)生合照分割效果

上述實(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)。

表1 3種算法處理不同樣本的運(yùn)算時(shí)間比較(單位：s)

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)題。

[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.

An improved two-dimensional Otsu thresholding segmentation method

Xu Chao1，2，3，Huang Fenghua1，4，Mao Zhengyuan1，2，3
(1.Provincial Spatial Information Engineering Research Center，F(xiàn)uzhou University，F(xiàn)uzhou 350002，China；2.Key Laboratory of Spatial Data Mining and Information Sharing of Ministry of Education，F(xiàn)uzhou University，F(xiàn)uzhou 350002，China；3.National Engineering Research Centre of Geospatial Information Technology，F(xiàn)uzhou University，F(xiàn)uzhou 350002，China；4.Yango College，F(xiàn)uzhou University，F(xiàn)uzhou 350015，China)

Otsu algorithm，also called the method of maximum classes square error，is one of classical methods for image threshold segmentation.As generalization of 1D Otsu algorithm,2D Otsu algorithm fully considers information of both the image gray and the neighborhood relationship among pixels,thus it is able to filter noise effectively.However,it is time consuming because of its huge amount of calculation.Concerning the problem,this article presents an improved fast 2D Otsu segmentation algorithm,which further cuts down the amount of computation by decomposing the original 2D Otsu algorithm into two 1D Otsu algorithm,constructing a new threshold recognition function through integrating inter-class variance with intra-class variance,and reducing dimension.Experiment results show that the improved method is superior to the other two methods in terms of segmentation efficiency and effect.

threshold segmentation；2D Otsu；inter-class variance；intra-class variance

TN911.73

A

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.

2016-04-12)

徐超（1991-），男，碩士，主要研究方向：遙感影像變化檢測(cè)、時(shí)空序列分析。

黃風(fēng)華（1982-），男，博士，副教授，主要研究方向：遙感與 GIS應(yīng)用、數(shù)據(jù)挖掘。

毛政元（1964-），男，博士，教授，博士生導(dǎo)師，主要研究方向：時(shí)空序列分析、地表變化檢測(cè)、信息化管理與信息服務(wù)。

國(guó)家自然科學(xué)基金項(xiàng)目（41501451）