基于最大類間方差的改進圖像分割算法

丁曉峰，何凱霖

（電子科技大學成都學院 計算機系，四川 成都611731）

0 引 言

在車牌識別、目標跟蹤等諸多研究領域，圖像閾值分割 處 理［1，2］是 其 中 的 關 鍵 步 驟，常 用 的 方 法 為Ostu 法［3］。目前，隨著研究的深入，圖像分割技術有了較快發展，其中基于灰度直方圖統計的圖像分割法［4］最為典型，成為目前圖像分割的基本方法。因為單純的閾值分割法并不適用全部圖像，所以學者創造性地把該方法和其它分割技術聯合在一起。目前，圖像閾值分割算法的種類很多，如固定門限閾值算法［5］、自適應門限閾值算法［6］、最大熵法［7］和Ostu法等幾種。Ostu法又稱為最大類間方差法，該方法具有穩定性強、準確性大的優點，但Ostu法在整個灰度級遍歷上求最大類間方差，運算復雜，對于視覺檢測等要求高、技術精的應用場所，Ostu法不再適合。

本文在Ostu算法的基礎上通過提高其效率，加快圖像閾值分割的速度，改進的Ostu法具有更高的使用價值。

1 傳統算法缺陷的機理研究

根據實際需要把自然圖像劃分為所需的不同區域或部分就是圖像分割的過程。根據實際利用的分割模型，側重的特征類型，傳統的分割算法種類繁多。另外，經實驗研究，不同的方法具備不同的使用條件，并呈現出各自的優勢。分割技術大部分是從圖像的像素為突破口，實現對應的目標。目前，常用的分割方法分為邊緣檢測法、譜和空間分類法、區域生長法和灰度等級閾值法等幾種類別［8－11］。其中，應用廣泛的灰度閾值法，它是把像素灰度進行分類，實現對圖像的分割；邊緣檢測法應用也較為廣泛，它是通過識別圖像內物體輪廓進而求出圖像的邊界實現容易，效果優勢顯著；區域生長法是根據圖像的灰度、紋理、形狀、尺寸等特征把性質基本一致的鄰近點進行歸納，組成不同的區域，它是一種從圖像中提取實體的序貫分割法。

廣泛應用的灰度閾值分割算法是基于閾值化技術的應用，通過對像素灰度做種類的劃分，實現對圖像的有效劃分與分割。該方法有一個應用前提即圖片內的像素點灰度級相鄰但也存在差別的情況。所以該方法的關鍵是要取定恰當的閾值。

該方法在原始階段，均依靠二值化方法來進行相關求解。實踐證明，其優勢為方便、簡潔而易懂。在遇到直方圖的兩峰值明顯的情況時，用該方法來求解具有明顯的優勢。處理方法為：選擇在凹谷點處的灰度級T 值，當作此時的門限值進行求解，設μ（i，j）為掃描點二值化圖像的灰度值，則

對于當出現直方圖為雙峰值的情況，根據上述公式處理后可知，實驗對象和背景對應的灰度級數分別為1和0，從而完成了對象分割與容量壓縮的任務。如果兩者的差別較小，對應的圖像不存在雙峰現象，依據上述的把凹谷點處的灰度值當做閾值大小不再合適，因此固定門限法不再適用，應該另尋它法。由此可知，本方法具有不完美的地方歸納如下：當對出現對比度不明顯的圖片進行處理時，處理效果不好；如果峰值較多，精度無法保證。

自適應門限閾值確定方法能夠很好的解決固定門限二值化存在的問題和不足。其中，引言中所描述的Otsu法是二值化算法中的重要組成部分，占據著很高的地位和作用。該算法以閾值的準確選取為基礎，有時可能出現分割的出發點不為最優的情況，在分割效果來看，卻是穩定和理想的。具體操作步驟說明如下：

定義 規格為M×N 自然圖像某一點的灰度值是f（x，y），取值范圍是 ［0，L－1］，對應的級數大小取L，圖像中出現灰度數為k的像素點的概率大小用p（k）表示，所以

取對應的閥值大小是t，初始圖像可以拆分成目標（第一區域）與背景（第二區域）兩部分，以｛f（x，y）≤t｝表示目標部分，用｛t＜f（x，y）＜L｝代指背景部分，所以：

第一區域比例

第二區域比例

目標均值

背景均值

總均值

式中：X，X0，Xp分別表示待評草原生態安全物元的量值、經典域物元的量值范圍以及節域物元的量值范圍。ρ(X,X0)表示點X與x0=[a0,b0]的距離，ρ(X,Xp)表示點X與xp=[ap,bp]的距離。

Otsu法求出的圖像最佳閾值的公式為

可以用另一種形式理解Otsu法：μ、μ0（t）與μ1（t）分別為整幅圖像、第一區域和第二區域對應的中心灰度數。若使實驗效果盡可能優良，必須讓拆分出的第一區域和第二區域與圖像中心的距離盡可能大，也就是（μ0（t）－μ）2與（μ1（t）－μ）2數值盡可能變大。上面描述的Outs算法，它是使用灰度值來表示對應圖像內的第一區域和第二區域。

Otsu算法是在整個灰度級上進行最佳閾值的搜索，針對每一個灰度值求類間方差大小，運算量大，速度慢。因此文獻 ［3］對該方法進行了完善，具體做法是首先對待解圖片灰度平均值 （T）進行量化，以數值T 為分水嶺，圖像劃割為數值小于T 與數值大于T 兩部分，并計算出對應的灰度平均值T1與T2，接著，對數值區域 ［T1－T2］依據Otsu法的相關原理與步驟，獲得最佳閾值大小。可以看出，該方法走了捷徑，具備降低運算量的優勢，但程度不夠明顯，還不盡如人意。為進一步提升Otsu算法的運算速度，本文依據相關原理，對現有方法進行了改進和完善，基本思路是對最佳閾值進行求解，采取的是二分查找法，從而減少運算量，縮短運算時間。

2 Otsu算法的改進設計

利用分治策略的二分查找法來進行處理，該方法又名為折半查找法理論，它是充分利用元素間的次序關系來進行求解。該方法的操作步驟為：在查找表核心區域選定關鍵字數值大小，并確定給定值數值大小，在此基礎上，將兩個數值做以大小對比。判別標準如下：若兩個數值大小一樣，說明此值即是。否則，對于給定值與搜索值，如果前者較大，判定搜索元素在查找表后半區域；如果后者較大，判定搜索元素在查找表前半區域。緊接著對判定區域重復上述操作，逐漸縮小區域，以獲得目標值而告終。

通過對比可知，該方法只需對比一下，即可把搜尋范圍減去半部分。所以，該方法具備效率高、運算量少的優勢。隨意擇取自然數n值，如果n＞100的情況下，在等概率背景下，該方法操作完成時的平均長度數值近似如下

該方法的處理速度很快，具備的缺點是所處理的查找表要有一定的要求，那就是具備有序性。

研究結果表明，第一區域和第二區域間的方差數值大小決定著圖像中灰度散布的均勻程度，對應數值越大意味著兩區域的差別越明顯。如果兩區域的小范圍目標出現了彼此誤分的情況，對應的方差數值也會減小，所以，該方法讓方差數值盡可能變大，從而誤分情況的出現機率比較低。如果設定的閾值與最佳閾值相距甚遠，則說明誤分機率較高，方差數值是很低的。當所選閥值逼近于最佳值的情景下，說明誤分機率逐漸降低，所對應的方差數值不斷變大。當所選閥值取最優解時，對應方差數值在圖像上顯示為最高點。綜上所述，對應的每一個灰度級方差數值具備次序性，所以說可以把二分查找法應用到此類問題當中，如圖1所示。在計算相關問題中的最大類間方差時，能夠視為在有序表中定位的操作程序，本文把Otsu理論引入到最佳閾值的求解問題當中，發揮其在計算過程中的優勢和具備的強大功能，從而減少在整個求解過程中的運算量，盡可能縮短運算時間，滿足求解問題的需要。

圖1 Lena灰度圖及其各灰度級為閾值的類間方差曲線

（1）獲得灰度均值大小為T，以此為界把全部像素分為兩部分，數值低于T 的與數值高于T 的均值分別為T1與Tr，［T1－Tr］就是確定的搜尋域。

（2）取 ［T1－Tr］的中心點Tmid，大小為兩端點平均值，以及該點兩側臨近的兩灰度值 （分別為Tmid－1 與Tmid＋1）當成閾值，根據上述公式求出對應的類間方差的數值大小Var。

（3）大小判斷

根據獲得的相關數值，進行如下判斷：

如果滿足：Var（Tmid＋1）＜Var（Tmid－1）＆＆Var（Tmid）＜Var（Tmid），則說明最優閾值應該為Tmid，直接獲得了結果，不需進行進一步的計算。

如果滿足：Var（Tmid）＜Var（Tmid＋1）的情況，則說明最優閾值所處范圍是 ［Tmid，Tr］，重新定義T1與Tr進一步縮小范圍進行搜索。

（4）重復 （2），（3），最終得到Tmid為最佳閾值。

3 實驗與分析

通過Matlab編程仿真對本文改進算法進行了驗證，運用該法與先前的折半法進行了多次實驗，并對實驗效果加以綜合評價分析。受論文版面所限，本文只以兩幅圖像為例進行展示說明，如圖2所示，與傳統Otsu算法比較，本文算法和傳統Otsu法對圖像的閾值處理都能達到圖像目標與背景分離的效果。從本文算法的原理來看，由于最佳閾值的判定仍然是使得目標與背景兩類的類間方差最大，因此，本文算法搜索得到的最佳閾值，與傳統的Otsu算法搜索得到的最佳閾值是相同的，即最大類間方差所對應的閾值，因此本文算法對圖像進行閾值分割的結果與傳統Otsu法的處理結果是相同的。但是，本文算法采用了二分法進行搜索與傳統Otsu算法在整個灰度級所搜相比，計算量小了很多。

結果顯示，處理的圖像為8位的灰度圖像，灰度級為0～255。對圖2（a）進行閾值分割處理，傳統Otsu法計算方差的次數為255，文獻 ［3］算法縮小了搜索的范圍，計算方差次數為94，本文算法采用二分查找法，搜索的效率高出很多，計算方差次數為15。對圖2（e）進行閾值進行分割處理的結果，傳統的Otsu閾值法計算方差次數為255，文獻 ［3］算法為124，本文算法為21。

通過使用改進算法、Otsu 閾值分割算法和文獻 ［3］中的方法處理同一問題，通過對3種方法的處理效果進行對比權衡，可以發現改進算法在正確找到目標值的基礎上，極大減少了最佳閾值的搜索次數，計算方差的次數減小10倍以上，提高了Otsu 法的效率。對于8 位的灰度圖像來說，傳統Otsu法需要對整個灰度級進行搜索，對整個灰度級的每一個灰度值進行方差計算，計算的次數為255，根據式 （9）一二分法的搜索長度計算，本文算法對最佳閾值的搜索次數最多不超過9次，搜索效率有了大幅度提高。本文算法每次需要計算搜索點及左右兩個相鄰點—3個灰度值點為閾值時的類間方差的大小，所以總的方差計算次數不超過27次，計算量比傳統的Otsu法小很多。對大量圖像處理的結果驗證了本文算法的可靠性，達到了閾值分割分離的目標和背景、壓縮信息的效果，同時減小了計算量，提高了閾值分割的速度。

圖2 圖像閾值效果對比

4 結束語

對數字圖像制品進行進一步技術處理，獲得質量更高的影像制品已成為重要的領域之一。尤其是以二值化為代表的經典圖像分割理論，從簡單的固定門限閾值法發展到廣泛使用的自適應閾值分割算法，以及多種二值化算法的結合使用，可以說已經趨近成熟。但是，由于人們對圖像質量要求的不斷提高，所以發展該領域的技術和理論十分迫切。Otsu閾值分割算法是目前應用最為廣泛的自適應閾值分割算法之一，其適應性強，處理效果良好，但傳統的Ostu法要對整個灰度級進行搜索才能找到最佳閾值，計算量很大，限制了它在一些實時性高的場合的使用。針對傳統Otsu法的缺陷，文獻 ［3］中，通過邊界閾值的選取縮小了搜索范圍來提高效率，但是計算量的降低程度有限。在文獻 ［3］的基礎上，本文將二分法的查找原理應用于Otsu算法中，大大提高了搜索效率，減少了計算方差的次數，與傳統Otsu法相比，計算量降低10 倍以上，計算速度加快。因此，改進的最大類間方差法能夠更好的應用于實時性高、數據處理量大的場合，使得Otsu閾值分割法在通用閾值分割算法的基礎上，變得更加高效，更具有實用價值。

［1］ZHU Junjie，DU Xiaoping，FAN Xiangtao，et al.Three kinds of the contrast of image segmentation algorithm and the improved image segmentation method ［J］.Computer Applications and Software，2014，31 （1）：194－200 （in Chinese）.［朱俊杰，杜小平，范湘濤，等.三種圖像分割算法的對比及圖像分割方法的改進 ［J］.計算機應用與軟件，2014，31（1）：194－200.］

［2］SUN Yanyue，HE Xiaohai.One for video super－resolution reconstruction of block matching image registration method ［J］.Journal of Automation，2011，37 （1）：37－43 （in Chinese）.［孫琰玥，何小海.一種用于視頻超分辨率重建的塊匹配圖像配準方法 ［J］.自動化學報，2011，37 （1）：37－43.］

［3］Qiao Wanbo，Cao Yinjie.An improved binarization method for gray images ［J］.Electronic Science and Technology，2013，21 （11）：63－64.

［4］Chu Y，Mi H，Ji Z，et al.BFA based neural network for image compression ［J］.Journal of Electronics，2014，25（3）：405－408.

［5］CAI Xun，MENG Xiangxu，HAO Xingwei，et al.Based on the physical reflection mode to open type color invariance threshold segmentation algorithm ［J］.Journal of Computers，2012，32 （2）：282－287 （in Chinese）. ［蔡珣，孟祥旭，郝興偉，等.一種基于物理反射模開型顏色不變性的閾值分割算法［J］.計算機學報，2012，32 （2）：282－287.］

［6］Sathya PD，Kayalvizhi R.PSO－based Tsallis thresholding selection procedure for image segmentation ［J］.International Journal of Computer Applications，2013，5 （4）：39－46.

［7］Karaboga D，Ozturk C.A novel clustering approach：Artificial bee colony（ABC）algorithm ［J］.Applied Soft Computing，2013，11 （1）：652－657.

［8］FAN Jiulun，REN Jing.Threshold method based on square distance symmetrical co－occurrence matrix ［J］.Journal of Electronics，2011，39 （10）：2277－2281 （in Chinese）. ［范九倫，任靜.基于平方距離的對稱共生矩陣閾值法 ［J］.電子學報，2011，39 （10）：2277－2281.］

［9］Verma OP，Hanmandlu M，Kumar P，et al.A novel bacterial foraging technique for edge detection ［J］.Pattern Recognition Letters，2014，23 （8）：1187－1196.

［10］WU Yiquan，ZHANG Jinkuang.Improved two－dimensional Otsu method and threshold segmentation of chaotic particle swarm recursive ［J］.Chinese Journal of Image and Form，2012，14 （9）：1843－1849 （in Chinese）.［吳一全，張金礦.改進的二維Otsu法及混沌粒子群遞推的閾值分割 ［J］.中國圖象形學報，2012，14 （9）：1843－1849.］

［11］CHEN Liang，DING Guohui，GUO Lei.Image threshold value segmentation based on histogram to confirm each ［J］.Journal of Computer Applications，2012，30 （1）：170－174（in Chinese）.［陳亮，丁國輝，郭雷.基于直方圖互確認的圖像 閾 值 化 分 割 ［J］.計 算 機 應 用，2012，30 （1）：170－174.］