郭瑞峰+楊柳+彭光宇+袁超峰

摘 要： 閾值分割是眾多圖像分割方法中使用最普遍的一種方法，閾值的求解也是圖像處理的重心。傳統(tǒng)Otsu算法屬于窮舉式的閾值求解方法，需遍歷每個灰度值并計算以其為閾值的類間方差，在此進(jìn)行了大量不必要的計算，可能無法應(yīng)用于某些實時性要求較高的環(huán)境中。對此提出一種快速的Otsu改進(jìn)算法，在引入圖像復(fù)雜度及其相關(guān)性質(zhì)縮小了灰度的搜索范圍，同時在搜索范圍內(nèi)使用了一種快速計算方法，較傳統(tǒng)Otsu算法進(jìn)行了二次加速。實驗結(jié)果證明，該算法較傳統(tǒng)Otsu算法提高了計算速度，且兩種算法的圖像分割結(jié)果相同。

關(guān)鍵詞： 圖像分割； 圖像復(fù)雜度； Otsu算法； 快速計算

中圖分類號： TN911.73?34； TP391.41 文獻(xiàn)標(biāo)識碼： A 文章編號： 1004?373X（2017）20?0042?04

Abstract： Threshold segmentation is one of the most commonly used image segmentation methods， and the solution of threshold is also the focus of image processing. The traditional Otsu algorithm is an exhaustive threshold solution method， which needs to traverse each gray value， calculate the interclass variance taking the gray value as the threshold value， and make a large number of unnecessary calculations. As a result， the traditional Otsu algorithm may not be appropriate to be applied in some environments with high real?time performance requirements. Therefore， an improved fast Otsu algorithm is proposed. The hunting scope of the traversed gray was reduced after importing the image complexity and its related properties. A fast calculation method is used in the scope of the traversed gray， which executes secondary acceleration in comparison with the traditional Otsu algorithm. The experimental results show that this algorithm improves the calculation speed in comparison with the traditional Otsu algorithm， and the image segmentation results of the two algorithms are the same.

Keywords： image segmentation； image complexity； Otsu algorithm； fast calculation

0 引 言

圖像分割是圖像分析中的難點和重點，其目的是要將圖像中感興趣區(qū)域提取出來，以便對分割出的目標(biāo)區(qū)域進(jìn)行分析處理。所以圖像分割也起到了橋梁的作用，一直受到眾學(xué)者極大的關(guān)注。目前傳統(tǒng)分割方法主要分為基于區(qū)域的、基于邊緣的和兩者結(jié)合的圖像分割方法[1]。而閾值分割是圖像分割中一類最早被研究和使用的方法，其具有物理意義明確、效果明顯、易于實現(xiàn)、實時性良好等特點[2]。其中最大類間方差法（Otsu算法）作為一種經(jīng)典閾值法，也被廣泛運用和發(fā)展。且在原算法上又提出基于二維直方圖的二維閾值分割法（二維Otsu）[3?4]和相應(yīng)的三維Otsu[5]算法，雖然比起一維算法，二維算法和三維算法抗噪性更強(qiáng)，不過其計算較一維Otsu算法復(fù)雜，需要消耗更多的時間，可能無法滿足某些對實時性要求較高的工作。文獻(xiàn)[6]所述的快速算法屬于一種迭代算法，雖然計算速度有所提高，但其求得的閾值在某些時候與Otsu算法所求結(jié)果不相同。而文獻(xiàn)[7]的計算結(jié)果和Otsu計算出的閾值也有所不同。

本文在一維Otsu算法基礎(chǔ)上進(jìn)行了改進(jìn)， 基于文獻(xiàn)[8?9]所證明關(guān)于圖像復(fù)雜度和Otsu算法的性質(zhì)，對一維Otsu算法進(jìn)行了簡化，在保證計算精度的同時，提高了閾值計算速度，這可以滿足機(jī)器視覺對于實時性的要求。

1 傳統(tǒng)Otsu算法

Otsu算法是由大津展之[3]在1979年提出的經(jīng)典算法。它是按圖像的灰度特性，將圖像分成了兩部分，可理解為目標(biāo)和背景兩部分，再計算二者的類間方差。若分割后兩部分類間方差越大，則表示構(gòu)成圖像的兩部分的差別越大。因此，使類間方差最大的分割意味著錯分概率最小。

設(shè)一幅圖像有L個灰度級別，以灰度閾值t將圖像分為兩部分，將兩部分分別設(shè)為B0=[0，1，2，…，t]，B1=[t+1，t+2，…，L-1]。設(shè)任意灰度為k的像素出現(xiàn)的概率為[pk]，[pk]=[nkN，]其中N為圖像像素總數(shù)，[nk]為灰度值為k的像素點個數(shù)。圖像總像素均值為[μk=k=0L-1kpk]。目標(biāo)像素（B0）出現(xiàn)的概率記為[ω0（t）]，背景像素（B1）出現(xiàn)的概率記為[ω1（t）]。設(shè)[μ（t）=k=0tkpk]，則目標(biāo)像素灰度均值記為[μ0（t）]，背景像素灰度均值記為[μ1（t）]。endprint

2 改進(jìn)Otsu快速算法

對于傳統(tǒng)的Otsu算法，對所有灰度值進(jìn)行窮舉計算將消耗大量冗余時間，是拉低計算速度的主要原因。因此本文從減少冗余運算為出發(fā)點，在傳統(tǒng)Otsu計算的基礎(chǔ)上，對目標(biāo)圖像的灰度級遍歷范圍進(jìn)行縮減，同時在對縮減后的灰度級范圍內(nèi)使用一種改進(jìn)的Otsu快速算法，在傳統(tǒng)的Otsu算法基礎(chǔ)上進(jìn)行了兩次提速，可以滿足機(jī)器視覺實時性的要求。

2.1 灰度級遍歷范圍的縮小

傳統(tǒng)Otsu算法需要遍歷256個灰度級，本文引用圖像復(fù)雜度的性質(zhì)對所遍歷灰度級范圍進(jìn)行縮減。選用圖像復(fù)雜度作為信息隱藏研究中圖像的度量尺度。首先是因為圖像復(fù)雜度是圖像的客觀屬性；其次，基于圖像的信息隱藏對圖像的紋理、顏色變化等因素敏感，信息隱藏能力和效果隨著圖像紋理的復(fù)雜程度的變化而不同[10]。圖像復(fù)雜度的計算公式為：

[C=-k=1tnklog（nkN）] （7）

式中：C代表圖像復(fù)雜度；t為劃分目標(biāo)和背景區(qū)域的分割閾值；[nk]是灰度值為k的像素點個數(shù)；N為整幅圖像內(nèi)像素點個數(shù)[11]。

由圖像復(fù)雜度的性質(zhì)[12]可知，圖像的整體復(fù)雜度不小于其任意子集的復(fù)雜度，且隨著待分割區(qū)域的減小，圖像灰度值差異的減少，圖像復(fù)雜度會減??；相反的，隨著待分割區(qū)域的增大，圖像灰度值差異的增大，圖像復(fù)雜度會增大。而且在一般的圖像處理經(jīng)驗中，待分割區(qū)域在整圖中所占比例越大，圖像的平均灰度也會越接近最優(yōu)分割閾值。所以由圖像復(fù)雜度，待分割區(qū)域大小的關(guān)系即可對Otsu算法中灰度的遍歷范圍進(jìn)行縮減。即圖像復(fù)雜度越高，待分割區(qū)域所占比例越大，最佳閾值就離平均灰度越接近。設(shè)Tm為圖像平均閾值，[nT]是灰度為Tm的像素數(shù)，[NT]是以閾值為Tm分割區(qū)域內(nèi)像素數(shù)，待分割區(qū)域圖像復(fù)雜度公式為[11]：

式中：L是圖像灰度級數(shù)；q為比例系數(shù)，[0.05≤q≤0.15]。最終灰度級遍歷范圍會在（Tm-[α]，Tm+[α]）之內(nèi)，可見圖像復(fù)雜度越高，[α]越小，傳統(tǒng)Otsu方法的灰度遍歷范圍越小。這樣就從縮小灰度級遍歷范圍的角度出發(fā)，實現(xiàn)了本文快速算法的第一次加速。

2.2 遍歷范圍內(nèi)快速計算

相比于傳統(tǒng)的Otsu算法，本文使用的快速算法大大減少了窮舉次數(shù)，若在相同的灰度級范圍內(nèi)搜索最佳閾值會大大減少計算時間。根據(jù)Otsu準(zhǔn)則的性質(zhì)[8]，在傳統(tǒng)Otsu算法下得到的最佳閾值[t*]滿足如下公式：

利用這三條性質(zhì)即可進(jìn)行最佳閾值t*的快速搜索。概括地說，這種快速搜索就是要分別從所要遍歷的灰度范圍的兩端，即范圍內(nèi)的首個灰度和末尾灰度值分別開始搜索使得[f1（t）]=[f2（t）]的所有t值。在此過程中，把所要遍歷的范圍分成了若干個小區(qū)間，利用性質(zhì)，直接就能判斷出每個小區(qū)間是否有滿足式（10）的t值，并且記錄這個t值，若有惟一t值使得式（10）成立，此t值即為所求的最佳閾值；若有兩值t1，t2分別滿足式（10），則在（t1，t2）范圍內(nèi)繼續(xù)重復(fù)之前步驟搜索出滿足[f1（t）]=[f2（t）]的t值，最后將所有滿足式（10）的t值分別代入[σ2b（t）]，使得其最大的t值即為所求。這種快速算法減少了待搜索灰度范圍內(nèi)的冗余計算次數(shù)，避免了逐一搜索，進(jìn)而實現(xiàn)了本文快速算法的第二次加速。

2.3 改進(jìn)算法計算流程

運用本文算法進(jìn)行最佳閾值求解計算過程如下：

（1） 計算圖像的平均閾值Tm，計算以Tm為閾值分割的目標(biāo)區(qū)域的圖像復(fù)雜度[CTm]，結(jié)合式（8）、式（9）計算出[α]，得出所要搜索的灰度范圍（Tm-[α]，Tm+[α）]。并依照定義計算[μk]，[μ（t）]和[ω0（t）]。

（2） 從Tm-[α]開始搜索滿足[f1（t）]=[f2（t）]的t值。若[f1（t）]>[f2（t）]，令[d=f1（t）-f2（t）]，當(dāng)[ω0（t+d）<1]，則t=t+d，否則t=t+1。將新得出的t值再重新返回進(jìn)行比較計算，直到搜索出滿足[f1（t）]=[f2（t）]的t值，使t1=t，結(jié)束搜索。

（3） 從Tm+[α]開始搜索滿足[f1（t）]=[f2（t）]的t值，若[ω0（t）]=1，則使t=t-1。當(dāng)[ω0（t）]<1并有[f1（t）]<[f2（t）]時，使[d=f1（t）-f2（t）]，t=t-d。將新得到的t值再重新計算比較，直至搜索出使[f1（t）]=[f2（t）]成立的t值，使t2=t，結(jié)束搜索。

（4） 比較t1與t2，若t1和t2相等，此時交點惟一，則t1（t2）即為所求最佳閾值，求解結(jié)束；否則繼續(xù)步驟（5）和步驟（6）。

（5） 若t1[≠]t2，則繼續(xù)以（t1，t2）為區(qū)間返回步驟（2）重新搜索，并記錄所有使得[f1（t）]=[f2（t）]成立的t值。

（6） 將不同t值代入[σ2b（t）]計算，則使其最大的t值即為最佳閾值。

2.4 算法耗時分析

運算量越大會導(dǎo)致計算耗時越長，降低圖像處理速度，影響機(jī)器視覺的實時性。運用傳統(tǒng)Otsu方法計算圖像最佳閾值，需要計算[ω0（t）]，[μk]，[μ（t）]和[σ2b（t）]，其中[μk]=[μ（L-1）]。記計算一次[μ（t）]所耗時為y0，計算一次[ω0（t）]耗時為y1，且[ω0（t）]和[μ（t）]均可遞推得到結(jié)果，故計算時間遠(yuǎn)小于[σ2b（t）]計算時間。記計算一次[σ2b（t）]的時間記為y2，由式（6）可知需要計算4次乘法和2次加法。傳統(tǒng)Otsu的總計算時間可記為L（y0+y1）+Ly2。

運用本文算法同樣需先計算[ω0（t）]，[μk]，[μ（t）]，可知每算一次消耗時間y0+y1。記減小灰度搜索范圍后灰度數(shù)為l，則此部分耗時為l（y0+y1）。由式（8）和式（9）可知，計算圖像復(fù)雜度[CTm]需2次乘法運算，計算[α]需要4次乘法1次減法運算，總共需進(jìn)行6次乘法和1次減法運算，總耗時記為y3，則y3<2y2。記每次計算[f1（t）]耗時為y4，由式（11）可知計算[f1（t）]時需要3次乘法3次減法，因為乘法計算耗時通常大于加法計算耗時，故y4

3 實驗與結(jié)果

實驗硬件采用2.53 GHz CPU 4 GB內(nèi)存的電腦，運用Matlab 2013b進(jìn)行算法編程，對程序二次執(zhí)行后進(jìn)行計時。兩組實驗分別運用Otsu方法和改進(jìn)算法進(jìn)行閾值計算。分別對兩算法的計算速度和計算精確度進(jìn)行對比驗證。實驗結(jié)果說明，本文提出的算法較傳統(tǒng)Otsu算法耗時更少，同時保持了相同的精確度。

實驗1：分別對4幅像素大小不同的灰度圖運用兩種算法進(jìn)行閾值求解，如圖1所示。兩種算法的運算時間見表1，圖像分割結(jié)果如圖2所示。

由表1數(shù)據(jù)可知，圖2（a）改進(jìn)算法用時為傳統(tǒng)算法的38.2%，圖2（b） 改進(jìn)算法用時為傳統(tǒng)算法的29.7%， 圖2（c）和圖2（d）用時分別為傳統(tǒng)算法的47.0%和45.7%。因此改進(jìn)算法在時間性能上強(qiáng)于傳統(tǒng)Otsu算法。由圖2分割結(jié)果可以看出，運用改進(jìn)算法對不同圖像進(jìn)行分割均得到良好效果。

4 結(jié) 語

本文針對傳統(tǒng)Otsu算法對窮舉式的運算過程存在大量冗余計算這一缺點，在傳統(tǒng)Otsu算法上進(jìn)行了改進(jìn)。實驗結(jié)果表明本文算法不但保證了計算準(zhǔn)確性，同時減少了計算時間，為提高圖像分割速度，進(jìn)而對提高機(jī)器視覺的實時性提供了新方法。

參考文獻(xiàn)

[1] 許新征，丁世飛，史忠植，等.圖像分割的新理論和新方法[J].電子學(xué)報，2010（2A）：76?82.

[2] 吳一全，孟天亮，吳詩婳.圖像閾值分割方法研究進(jìn)展20年（1994—2014）[J].數(shù)據(jù)采集與處理，2015，30（1）：1?23.

[3] PIETRONI N， GANOVELLI F， CIGNONI P， et al. Splitting cubes： a fast and robust technique for virtual cutting [J].Visual computer， 2009， 25（ 3）： 227?239.

[4] 周筠，樊曉平，廖志芳，等.醫(yī)學(xué)體數(shù)據(jù)中四面體化方法的研究進(jìn)展[J].計算機(jī)應(yīng)用研究，2011，28（10）：3615?3622.

[5] 龔劬，倪麟，唐萍峰，等.改進(jìn)的三維Otsu圖像分割快速算法[J].計算機(jī)工程與應(yīng)用，2014（6）：171?174.

[6] 趙于前，楊元，王琨.基于模糊集理論的迭代多值化圖像分割[J].光電子·激光，2009（10）：1403?1409.

[7] HUANG D Y， WANG C H. Optimal multi?level thresholding using a two?stage Otsu optimization approach [J]. Pattern recognition letters， 2009， 30（3）： 275?284.

[8] 許向陽，宋恩民，金良海.Otsu準(zhǔn)則的閾值性質(zhì)分析[J].電子學(xué)報，2009（12）：2716?2719.

[9] 何志勇，孫立寧，陳立國.Otsu準(zhǔn)則下分割閾值的快速計算[J].電子學(xué)報，2013（2）：267?272.

[10] 錢思進(jìn)，張恒，何德全.基于圖像視覺復(fù)雜度計算的分類信息隱藏圖像庫[J].解放軍理工大學(xué)學(xué)報（自然科學(xué)版），2010（1）：26?30.

[11] 董忠言，蔣理興，王俊亞，等.基于圖像復(fù)雜度的一維Otsu改進(jìn)算法[J].計算機(jī)科學(xué)，2015，42（z1）：171?174.

[12] 高振宇，楊曉梅，龔劍明，等.圖像復(fù)雜度描述方法研究[J].中國圖象圖形學(xué)報，2010，15（1）：129?135.endprint