《電子技術應用》
您所在的位置：首頁 > 通信與網(wǎng)絡 > 設計應用 > 一種改進的二維Otsu閾值分割算法
一種改進的二維Otsu閾值分割算法
2016年電子技術應用第12期
徐 超1，2，3，黃風華1，4，毛政元1，2，3
1.福州大學 福建省空間信息工程研究中心，福建 福州350002； 2.福州大學 空間數(shù)據(jù)挖掘與信息共享教育部重點實驗室，福建 福州350002； 3.福州大學 地理空間信息技術國家地方聯(lián)合工程研究中心，福建 福州350002；4.福州大學 陽光學院，福建 福州350015
摘要： Otsu算法，也被稱之為最大類間方差算法，是實現(xiàn)閾值分割的經(jīng)典算法之一。二維Otsu算法是一維Otsu算法的推廣，它充分考慮了圖像的灰度信息和空間鄰域信息，可以有效濾除噪聲影響，但是同樣存在著運算量大、時效性差的問題。對此提出了一種改進的二維Otsu快速閾值分割算法，先將二維Otsu算法分解為兩個一維Otsu算法，并集成類間和類內方差信息構造了一種新的閾值判別函數(shù)，同時通過降維，進一步降低計算量。實驗結果表明，該算法在時間效率與分割效果兩方面明顯優(yōu)于傳統(tǒng)的二維Otsu算法與快速二維Otsu算法。
中圖分類號： TN911.73
文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.2016.12.028
中文引用格式： 徐超，黃風華，毛政元. 一種改進的二維Otsu閾值分割算法[J].電子技術應用，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.
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
Abstract： 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.
Key words : threshold segmentation；2D Otsu；inter-class variance；intra-class variance

0 引言

    圖像分割是將圖像劃分為一組子區(qū)，使得每個子區(qū)的內部都具有某種同質性、而任意兩個相鄰的子區(qū)間則不具備此種同質性的過程。它是涉及計算機視覺、圖像分析和模式識別等領域的重要研究內容[1]，歷經(jīng)數(shù)十年的發(fā)展，各類文獻中提出的圖像分割方法已經(jīng)形成了復雜的譜系[2-3]，閾值分割法是其中的一個分支，因其實現(xiàn)簡單、執(zhí)行效率高而被廣泛運用。日本學者OTSU N于1978年提出的Otsu算法被稱之為最大類間方差法[4]，是目前閾值分割法的主流算法之一，分割效果良好[5]。但傳統(tǒng)的一維Otsu法僅僅考慮了圖像的灰度信息，而未充分考慮圖像的空間信息，因此當圖像直方圖沒有出現(xiàn)明顯的雙峰時，利用該方法進行分割會出現(xiàn)信息丟失現(xiàn)象。

    為此，劉健莊等人提出了二維Otsu法，利用圖像灰度值和鄰域平均灰度值作為兩個維度進行閾值分割，使其抗噪性得到了提升，但是同樣提高了計算的復雜度[6]；在此基礎上，Gong Jian等人提出了二維Otsu的快速分割算法，將原算法時間復雜度從O(L4)降低到O(L2)[7]；范九倫等人提出二維Otsu曲線算法，將閾值范圍限制在主對角線與次對角線之間，有效地降低了算法的時間復雜度[8]；汪海洋等人提出了改進的二維Otsu閾值分割算法，通過遞歸的方式創(chuàng)建查找表，減少大量冗余的計算過程，降低計算量[9]；Wu Chengmao等人通過求取多元函數(shù)極值的方法構建迭代算法，降低了時間開銷和存儲空間開銷[10]；江禹生等人利用遺傳算法來快速獲取二維Otsu閾值算法的近似最優(yōu)閾值，唐英干等人則利用粒子群算法來優(yōu)化二維Otsu法的分割閾值，但是這種優(yōu)化算法容易過早地收斂而陷入到局部最優(yōu)的結果中，并且算法的代碼量過大[11-12]。

    為了進一步降低二維Otsu閾值分割算法的計算量同時提高其分割效果，本文利用分解的思想，將二維Otsu最佳閾值(s，t)分解為兩個一維Otsu最佳閾值s和t。同時，在獲取一維Otsu最佳閾值過程中，引入了類內方差概念，并提出一種改進的最佳閾值判別函數(shù)，從而得到最佳閾值s和t。

1 二維Otsu閾值分割算法

    傳統(tǒng)的二維Otsu算法主要是利用圖像鄰域中心灰度值與其鄰域均值構成的二維直方圖來進行分割，因此具有良好的抗噪性，其原理如下：

    設一幅圖像f(x，y)的大小為M×M，其灰度級為L(0，1，2，…，L-1)，它的鄰域均值圖像g(x，y)(以3×3鄰域均值作為該像素灰度值)灰度級也為L(0，1，2，…，L-1)，由此形成一個二元組：像素的灰度值i和其鄰域灰度均值j。設灰度值為i且鄰域灰度均值為j的像素數(shù)為fij，圖像像素總數(shù)為N，則對應的聯(lián)合概率密度pij可定義為：

jsj1-gs1.gif

    假設給定一個門限向量(s，t)，s為灰度閾值，t為鄰域灰度均值閾值，可以將圖1所示的正方形分割為I、II、III、IV 4個區(qū)域。由于圖像目標或者背景內部像素點之間的相關性很強，像素點的灰度值和其鄰域灰度均值十分接近；而在目標和背景邊緣處或者噪聲部分，它的灰度值與其鄰域灰度均值差異明顯。因此，圖1中I代表的是背景部分，III代表的是目標部分，II和IV分別代表邊緣和噪聲部分。假設圖像目標和背景分別用C0和C1表示，則它們出現(xiàn)的概率分別為：

    jsj1-gs2-4.gif

jsj1-t1.gif

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

    定義圖像類間離散度矩陣為：

     jsj1-gs5-7.gif

    最佳閾值為tr(Sb)取得最大時的(s，t)。

2 改進的快速二維Otsu算法

    為了降低二維Otsu算法復雜度以及提高分割效果，本文提出一種改進的快速二維Otsu算法。該算法將傳統(tǒng)的二維Otsu算法分解為兩個一維Otsu算法，即原圖像f(x，y)獲取一個閾值s，它的鄰域均值圖像g(x，y)獲取一個閾值t。從計算機的角度上看，分別求解兩個閾值以代替原來二維Otsu算法的閾值，這種方法不但降低了算法時間復雜度，而且降低了計算機的存儲空間。另外，傳統(tǒng)的二維Otsu算法以及一些改進的二維Otsu算法的閾值判別函數(shù)只考慮目標與背景之間的方差大小，即類間方差越大，分割效果越好。然而，這些算法并未考慮目標或背景內的內聚性，即目標類和背景類內部像素具有較強的相關性。因此，本文綜合考慮類間方差和類內方差的概念，提出一個新的閾值判別函數(shù)。

    定義1 設閾值s將一組離散的數(shù)據(jù)分成了兩類，定義其類間方差為：

     jsj1-gs8-9.gif

式中，u0、u1分別代表目標類和背景類的均值，w0、w1分別代表目標類和背景類的概率。因此，sp值越大，即類間方差越大，目標類和背景類區(qū)分就越明顯，分割效果越好。

    定義2 設閾值s將一組離散的數(shù)據(jù)分成了兩類，pi表示i出現(xiàn)的概率，u0、u1分別表示兩類的均值，w0、w1分別表示兩類的概率，則這組數(shù)據(jù)兩類的類內方差分別表示：

     jsj1-gs10-12.gif

    顯然，sw表示這組數(shù)據(jù)兩類類內的內聚性，其值越小，分割效果越好。

    為了進一步考慮類間方差和類內方差這兩個因素，即類間方差越大，類內方差越小，所得到的分割效果越好。因此，本文提出一個新的判別函數(shù)，即類間類內方差比值法：

    S=sp/sw                                (13)

    則最優(yōu)閾值滿足S*=argmax{S}，其對應的灰度值則為最佳閾值。類似可求得鄰域均值圖像g(x，y)的最佳閾值t，該方法避免了在L×L維進行窮舉遍歷，只需要在兩個長度為L的空間內尋找最佳閾值即可，從而降低了計算量，減少計算機所需存儲空間。算法步驟如下：

    (1)初始閾值范圍計算

    由于圖像目標灰度必然高于大量背景的均值，因此將初始閾值的下限設定為圖像灰度均值m，實驗也證實了該結論。另外由于圖像目標灰度必然不高于圖像最大灰度值，因此將初始閾值的上限設定為圖像最大灰度值n。

    (2)最佳閾值求取

    為了進一步降低運算時間，本文將二維圖像灰度矩陣轉換為一維矩陣(1，L)，并根據(jù)式(9)、式(12)分別求取圖像類間方差sp、類內方差sw，進而根據(jù)式(13)得到最佳閾值s，同樣可以求得鄰域均值圖像g(x，y)的最佳閾值t。

    (3)分割圖像

    利用上一步得到的閾值(s，t)分割圖像，并將其二值化。

3 實驗結果

    為了驗證本文算法的可行性和有效性，將它與傳統(tǒng)二維Otsu算法、快速二維Otsu算法進行比較。實驗環(huán)境為：Win8.1專業(yè)版，IntelCore(TM) i5-3570 CPU @ 3.40 GHz，RAM 4.00 GB，MATLAB R2012b。

    在實際應用環(huán)境中，獲取到的圖像背景一般較為復雜并且信噪比較低。為了驗證本文算法的分割效果，以rice圖像、lena圖像、學生合照作為樣本數(shù)據(jù)，選擇目前閾值法中效果較好的傳統(tǒng)二維Otsu算法、快速二維Otsu算法與本文算法進行實驗對比，結果如圖2～圖4所示。表1為本文算法與傳統(tǒng)二維Otsu法、快速二維Otsu法針對各樣本數(shù)據(jù)的運算時間。

jsj1-t2.gif

jsj1-t3.gif

jsj1-t4.gif

jsj1-b1.gif

    上述實驗所用的lena圖像大小為512×512，rice圖像大小為256×256,學生合照大小為768×1 024。從表1可知，在上述實驗環(huán)境下，本文算法時間復雜度遠低于文獻[6]和文獻[9]的算法，處理時間大為降低。就分割效果而言，本文綜合考慮類間方差和類內方差(即類間的離散測度信息和類內的內聚性)得到的分割結果抗噪性和目標內聚性均優(yōu)于傳統(tǒng)二維Otsu算法與快速二維Otsu算法。圖2(d)的上半部分沒有出現(xiàn)圖2(b)與圖2(c)中的細微噪聲顆粒，而下半部分米粒的完整性也更好；圖3(d)中分割出來的頭發(fā)和柱子內部更具飽和性；圖4(d)中漢字和學生眼睛、鼻子、嘴巴等目標更能清晰地識別出來。

4 結論

    為了進一步降低二維Otsu算法復雜度、提高分割質量，本文提出了改進的二維Otsu算法。根據(jù)本文算法與其他同類算法處理相同樣本圖像的實驗結果表明，本文提出的算法在分割效果和算法復雜度兩個方面都具有明顯提高。另外，將本文的算法思想擴展到三維甚至高維Otsu算法時，算法復雜度不會明顯提高。如何集成Otsu與其他同類算法得到更佳的分割效果，是后續(xù)研究要解決的問題。

參考文獻

[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自動閾值分割法[J].自動化學報，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].電子學報，2007，35(4)：751-755.

[9] 汪海洋，潘德爐，夏德深.二維Otsu自適應閾值選取算法的快速實現(xiàn)[J].自動化學報，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].計算機應用研究，2010，27(3)：1189-1191.

[12] 唐英干，劉冬，關新平.基于粒子群和二維Otsu方法的快速圖像分割[J].控制與決策，2007，22(2)：202-205.

此內容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權禁止轉載。