采用二維Otsu直方圖斜分快速算法實現方式的改進

錢衛(wèi)星， 黃麗亞

(1. 杭州職業(yè)技術學院 信息工程學院， 浙江 杭州 310018；

2. 南京郵電大學 電子科學與工程學院， 江蘇 南京 210003)

?

采用二維Otsu直方圖斜分快速算法實現方式的改進

錢衛(wèi)星1,2， 黃麗亞2

(1. 杭州職業(yè)技術學院 信息工程學院， 浙江 杭州 310018；

2. 南京郵電大學 電子科學與工程學院， 江蘇 南京 210003)

摘要：在二維Otsu自適應閾值快速算法的斜方窄帶判決域特性基礎上，依據斜分線穿越窄帶區(qū)的同一特性，設立算法輔助軸，對原快速算法實現方式進行改進.簡化算法實現過程，在原算法降維基礎上，進一步降低算法復雜度.結果表明：改進后的二維Otsu自適應閾值快速算法更加適應圖像分割的實際工況，在實驗驗證中取得良好的圖像分割效果.

關鍵詞：圖像分割； 二維Otsu； 斜方窄帶； 自適應閾值

閾值分割[1]是圖像處理算法的典型方法.日本學者大津于1979年提出了經典Otsu算法[2]，并發(fā)展了二維Otsu自適應閾值分割方法，充分應用了圖像的關聯信息量[3，4]，使分割效果得到改善.文獻[5-7]對算法進行改進，改判決域直分為斜分，提出不同閾值分割準則，降低算法運算量，提高算法處理速度，在實時處理中得到較好的應用.文獻[8]提出多段折線斜分閾值分割法.文獻[9-11]提出二維Otsu快速斜分算法的最小誤差方式改進方法，但在斜分算法實現時，對斜方窄帶域的劃分較復雜，同一特性域內也因邊界域值的變化要進行再細分才能實現，需要進行20多次細分，大大增加了算法實現時的程序復雜度.文獻[12-14]等從不同的側面提出了快速算法方案.本文依據斜分窄帶域區(qū)域同一特性原則，加入算法輔助軸，改進簡化了算法實現過程.

1算法原理

在經典Otsu算法一維直方圖的基礎上，關聯圖像中像素點與其鄰域像素點的信息，形成圖像像素信息聯合直方圖.建立Otsu算法二維直方圖，并引入自適應閾值判別方法.原始圖像，如圖1所示.圖像f(x,y)的灰度等級為0,1,2,…,L-1，共L級，其鄰域平滑圖像g(x,y)(以k×k的鄰域圖像像素均值作為該灰度值)的灰度級為L級，其聯立的二維直方圖，如圖2所示.

圖1　原始圖像　　　　　圖2　二維直方圖　Fig.1　Original image　　Fig.2　2D Otsu histogram

由圖2可知：圖像像素的灰度等級主要排布在二維直方圖斜對角線附近，圖像前景、背景各自像素灰度值和其鄰域灰度均值較接近，但在兩者分界領接處，像素自身和鄰域灰度均值差距較大.在圖2上設定一閾值數據(s,t)，水平垂直分割直方圖為A～D等4個區(qū)域，如圖3所示.由圖3可知：區(qū)域A，D大部分遠離對角線，像素灰度與領域均值灰度差距較大，為圖像邊緣或圖像噪聲等；區(qū)域B，C分別對應于圖像前景和背景.

在二維直方圖的閾值直分法中，由于區(qū)域A和區(qū)域D在靠近對角線附近實際為圖像主體的像素數據被忽略了，使圖像分割達不到理想效果，且在計算最佳閾值點數據s，t時，直分法圖像每幀均需要作雙重循環(huán)s×t+(L-s)×(L-t)次累加運算，對圖像實時連續(xù)處理有一定影響.二維直方圖的閾值斜分快速算法分割方式，如圖4所示.建立截距為N的與對角線平行的斜方窄帶域，截距斜線表達式為

設定閾值點(s,t)，斜分直線f通過閾值點，與對角線相垂直，將斜分窄帶域分割成上下兩部分.位于斜分線下側的窄帶區(qū)域對應于圖像前景，上側部分對應于圖像背景，該斜分線表達式為

圖3　二維直方圖直分法 　圖4　二維直方圖斜分法　　Fig.3　2D Otsu histogram vertical segmentation method　Fig.4　2D Otsu histogram oblique segmentation method

采用斜分分割，在計算最佳閾值點時，運算僅包括窄帶內數據，可以忽略窄帶外部分，縮小運算范圍.將s+t看成一個整體，從而將閾值判斷從二維(s,t)轉換成一維s+t閾值判斷.在編程計算時，從雙重循環(huán)降為單重循環(huán)，大幅降低了數據運算量.由圖4可知：當截距N足夠大時，窄帶域內可以包括所有概率不為零的像素點信息，獲得理想的閾值點數據，但運算量增大.

2算法實現及改進

2.1　原二維Otsu斜分快速算法實現方式

根據(s,t)的位置，將其分為左側區(qū)域(f=N-g，s+t

以區(qū)間的算法實現為例.分割斜線左側部分為前景區(qū)，根據斜分直線與上截距直線交點坐標與N的關系，原算法實現分為2種情況,如圖6所示.

1) (s+t+N)/2<2N，即s+t<3N.此時，圖像前景C0包括3個區(qū)間：當g<(s+t-N)/2時，0≤f≤g+N；當(s+t-N)/2≤g

圖5　斜分法區(qū)域劃分 圖6　N≤s+t<2L-2-N時的區(qū)域劃分Fig.5　Region division for oblique segmentation method　　 Fig.6　N≤s+t<2L-2-N region division

2) (s+t+N)/2≥2N，即s+t≥3N.此時，前景C0包括3個區(qū)間. 當g

后景區(qū)C1算法實現與此相似.其他2個區(qū)間段的算法實現以此類推.

2.2　二維Otsu斜分快速算法實現改進方式

原二維Otsu斜分快速算法雖然實現了降維運算，但在具體算法實現時分段復雜，在程序實現時不易累計ω0(s,t),ω1(s,t),μ0，i(s,t),μ0，j(s,t).在原算法斜方窄帶劃分的基礎上，增加輔助軸s+t，并以斜分線與窄帶區(qū)的交點坐標變化特點為依據，在算法實現時，對前景圖像和后景圖像再劃分，如圖7所示.

圖7　斜分新法閾值區(qū)域Fig.7　Region division for new oblique segmentationmethod

圖7中：斜分線f=s0+t0-g，在輔助軸s+t上的軸截距為s0+t0.由圖7可知：斜分線與斜方窄帶區(qū)的交點坐標變換存在3個不同區(qū)段.

1) 當s+t

2) 當N≤s+t<2L-2-N時，邊界交點的坐標分別為((s+t-N)/2,(s+t+N)/2))，((s+t+N)/2,(s+t-N)/2));

3) 當2L-2-N≤s+t<2L-2時，邊界交點的坐標分別為(s+t-L+1,L-1)和(t-L,s+t-L+1)劃分圖.

無論在哪一區(qū)段，上交點坐標沿斜分線向下交點坐標過渡時，f，g的步進增量分別為+1，-1.因此，在算法實現時，以輔助軸s+t數值從0到2L-2遞進變化為主循環(huán)量，以交點坐標變化為副循環(huán)量，統(tǒng)一處理ω0(s,t),ω1(s,t),μ0，i(s,t),μ0，j(s,t)數據增減量.改進后算法的實現程序框架如下

for (nThreshold_st=0;nThreshold_st<2L-2;nThreshold_st++)

if ((nThreshold_st>2L-2-N)& (nThreshold_st≤2L-2))

{if (nThreshold_st≤N){g1=L-1;g2=nThreshold_st-L+1;

g1=nThreshold_st;g2=0;f1=nThreshold_st-L+1;

f1=0;i=f1i=f1;

for (j=g1;j>g2;j--)?

{ω0+=dHistogram_pij[i][j];}

μ0，i+=i*dHistogram_pij[i][j];sb=((ω0·μz，i·μ0，i)2+(ω0·μz，j·μ0，j)2)/(ω0*(1-ω0));

μ0，j+=j*dHistogram_pij[i][j];if (sb>temp_Data)

i++{temp_Data=sb;

}nThreshold_Data=nThreshold_st;

}}

if ((nThreshold_st>N) & (nThreshold_st≤2L-2-N))

{g1=(nThreshold_st+N)/2;g2=(nThreshold_st-N)/2

f1=(nThreshold_st-N)/2;i=f1;

?

}

最佳閾值獲取耗時對比，如表1所示.表1中：t1，t2分別為算法改進前和改進后的耗時;tave為平均耗時.由表1可知：改進后比改進前的速度快了約3.6倍;圖像越大,處理數據越多時，改進后的實現方式優(yōu)勢越明顯.算法實現方式改進后的圖像分割效果，如圖8所示.由圖8可知：算法實現方式改進后，圖像分割效果依舊很理想.

表1　最佳閾值獲取耗時對比

(a) N=20 (b) N=40圖8　圖像分割效果Fig.8　Image segmentation effect

3結束語

充分利用二維Otsu直方圖的斜方窄帶域各分區(qū)段的同一特性，借助算法輔助軸，統(tǒng)一判斷依據，斜分窄帶判決域的劃分由原先的20多個細分區(qū)域降為3個劃分區(qū)域，使算法實現時得到了極大簡化.在圖像分割效果保持理想的情況下，閾值計算的運算速度提高了近4倍.因此，改進的二維Otsu直方圖斜分快速算法實現方式更加適合需實時處理的圖像分割工況場合.

參考文獻：

[1]章毓晉.圖象分割評價技術分類和比較[J].中國圖象圖形學報，1996,1(2):151-157.

[2]OTSU N.A threshold selection method from gray-level histograms[J].IEEE Transactions on System Man and Cybernetic,1979,9(1):62-66.

[3]劉健莊,栗文青.灰度圖象的二維Otsu自動閾值分割法[J].自動化學報,1993,19(1):101-105.

[4]郝穎明,朱楓.2維Otsu自適應閾值的快速算法[J].中國圖象圖形學報,2005,10(4):484-488.

[5]楊金龍,張光南,厲樹忠，等.基于二維直方圖的圖像分割算法研究[J].激光與紅外,2008,38(4):400-403.

[6]吳一全,潘喆,吳文怡，等.二維直方圖區(qū)域斜分的最大熵閾值分割算法[J].模式識別與人工智能,2009,22(1):162-168.

[7]范九倫，雷博.灰度圖像最小誤差閾值分割法的二維推廣[J].自動化學報，2009，35(4):386-393.

[8]梁義濤，龐蕊，朱遠坤.灰度圖像二維Otsu折線閾值分割法[J].計算機工程與應用，2012，48(33)：178-182.

[9]朱齊丹，荊麗秋，畢榮生，等.最小誤差閾值分割法的改進算法[J].光電工程，2010，37(7):107-113.

[10]陳琪，熊博蒞，陸軍，等.改進的二維 Otsu 圖像分割方法及其快速實現[J]. 電子與信息學報，2010，32(5)：1100-1104.

[11]李淼，楊恢先.改進二維直方圖區(qū)域劃分的閾值分割方法研究[J].光電子·激光，2013，24(7)：1426-1433.

[12]張新明,李振云，孫印杰，等.快速二維直方圖斜分最小誤差的圖像閾值分割[J].電光與控制,2012,19(6):8-12.

[13]何志勇，孫立寧，陳立國.Otsu準則下分割閾值的快速計算[J].電子學報，2013，41(2)：267-272.

[14]錢衛(wèi)星，黃麗亞.基于二維Otsu的自適應閾值快速算法改進[J].華僑大學學報(自然科學版)，2015，36(4)：427-431.

(責任編輯： 錢筠英文審校： 吳逢鐵)

Improved Implementations for 2D Otsu Histogram Fast Algorithm

QIAN Weixing1， HUANG Liya2

(1. Electronic Information College, Hangzhou Vocational and Technical College, Hangzhou 310018, China;

2. School of Electronic Science and Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210003, China)

Abstract：Based on the characteristics of the trapezius narrowband verdict scope of 2D Otsu adaptive thresholdfast algorithm, and the same characteristic of obliqueline traversing anarrow bandregion, we proposed the establishment of algorithm auxiliary shaft which improved and simplified the realization of original fast algorithm. Compared to the original algorithm of dimension reduction, this algorithm simplify the implementation process and algorithm complexity. Results show that the improved fast algorithm of 2D Otsu adaptive threshold was more adapted to the actual condition of image segmentation, which has achieved good effect of image segmentation in experiment.

Keywords：image segmentation; 2D Otsu; trapezius narrowband; adaptive threshold

基金項目：浙江省教育廳科研基金資助項目(Y201327284)

通信作者：錢衛(wèi)星(1974-)，男，講師，博士研究生，主要從事嵌入式技術應用的研究.E-mail:qianweixingxdx@163.com.

收稿日期：2015-11-16

中圖分類號：TP 391.41

文獻標志碼：A

doi:10.11830/ISSN.1000-5013.2016.01.0088

文章編號：1000-5013(2016)01-0088-04