一種改進的一維Otsu快速算法

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

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

關鍵詞： 圖像分割； 圖像復雜度； Otsu算法； 快速計算

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

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

1 傳統(tǒng)Otsu算法

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

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

2 改進Otsu快速算法

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

2.1 灰度級遍歷范圍的縮小

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

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

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

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

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

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

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

利用這三條性質(zhì)即可進行最佳閾值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ù)重復之前步驟搜索出滿足[f1（t）]=[f2（t）]的t值，最后將所有滿足式（10）的t值分別代入[σ2b（t）]，使得其最大的t值即為所求。這種快速算法減少了待搜索灰度范圍內(nèi)的冗余計算次數(shù)，避免了逐一搜索，進而實現(xiàn)了本文快速算法的第二次加速。

2.3 改進算法計算流程

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

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

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

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

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

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

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

2.4 算法耗時分析

運算量越大會導致計算耗時越長，降低圖像處理速度，影響機器視覺的實時性。運用傳統(tǒng)Otsu方法計算圖像最佳閾值，需要計算[ω0（t）]，[μk]，[μ（t）]和[σ2b（t）]，其中[μk]=[μ（L-1）]。記計算一次[μ（t）]所耗時為y0，計算一次[ω0（t）]耗時為y1，且[ω0（t）]和[μ（t）]均可遞推得到結果，故計算時間遠小于[σ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）可知，計算圖像復雜度[CTm]需2次乘法運算，計算[α]需要4次乘法1次減法運算，總共需進行6次乘法和1次減法運算，總耗時記為y3，則y3<2y2。記每次計算[f1（t）]耗時為y4，由式（11）可知計算[f1（t）]時需要3次乘法3次減法，因為乘法計算耗時通常大于加法計算耗時，故y4

3 實驗與結果

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

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

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

4 結 語

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

參考文獻

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

[2] 吳一全，孟天亮，吳詩婳.圖像閾值分割方法研究進展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ī)學體數(shù)據(jù)中四面體化方法的研究進展[J].計算機應用研究，2011，28（10）：3615?3622.

[5] 龔劬，倪麟，唐萍峰，等.改進的三維Otsu圖像分割快速算法[J].計算機工程與應用，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ì)分析[J].電子學報，2009（12）：2716?2719.

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

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

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

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