申鉉京 劉 翔 陳海鵬

?

基于多閾值Otsu準(zhǔn)則的閾值分割快速計(jì)算

申鉉京 劉 翔 陳海鵬*

(吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 長(zhǎng)春 130012);(吉林大學(xué)符號(hào)計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室 長(zhǎng)春 130012)

針對(duì)傳統(tǒng)多閾值Otsu方法在尋找最佳閾值過程中窮舉計(jì)算效率低的問題，該文分析了多閾值Otsu的閾值性質(zhì)，證明了使用Otsu方法找到的一組最佳閾值與分割出的各類均值之間的數(shù)學(xué)對(duì)應(yīng)關(guān)系。根據(jù)多閾值Otsu的閾值性質(zhì)，該文提出一個(gè)新算法用來快速計(jì)算所需最佳閾值，建立了一種新的閾值搜索模型。該算法搜尋滿足Otsu多閾值與以此閾值分割出的各類均值之間關(guān)系的一組最優(yōu)閾值，從而確定符合Otsu準(zhǔn)則的最佳閾值。該算法有效減少了閾值搜索范圍，并且在均值、方差等計(jì)算上引入了查找表，優(yōu)化了底層運(yùn)算。實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)多閾值Otsu方法相比，該算法的分割速度大幅度提高，相比于其他多閾值Otsu快速算法，不僅在計(jì)算速度上有所提升，而且得到的最佳閾值克服了隨機(jī)性和偶然性的缺點(diǎn)，是嚴(yán)格符合Otsu原則的。

圖像分割；多閾值Otsu準(zhǔn)則；閾值選?。豢焖儆?jì)算

1 引言

圖像分割算法中，閾值法以計(jì)算簡(jiǎn)單，分割速度快等特點(diǎn)被廣泛應(yīng)用[1,2]。傳統(tǒng)的Otsu法是由Otsu于1979年提出的一種經(jīng)典閾值分割算法，該方法具有較高的分割精度與很強(qiáng)的自適應(yīng)性[3]。為了適應(yīng)更加復(fù)雜的圖像，Otsu方法從單閾值被推廣到了多閾值，但究其本質(zhì)仍然是一種窮舉算法，時(shí)間復(fù)雜度非常高，幾乎很難達(dá)到單閾值的高實(shí)時(shí)性能。到目前為止，多閾值分割技術(shù)仍為研究中的一個(gè)難題。目前閾值分割優(yōu)化算法主要分兩類[9,10]：一類是減少閾值搜索范圍，如松弛余量法[11]，另一類是尋優(yōu)過程優(yōu)化算法，即各種群智能算法。文獻(xiàn)[4]引進(jìn)了單純形法來優(yōu)化多閾值的搜索效率。文獻(xiàn)[5]劃分直方圖區(qū)間，采用快速二分法求取區(qū)間中的閾值，以實(shí)現(xiàn)Otsu多閾值的擴(kuò)展。文獻(xiàn)[11]運(yùn)用了松弛余量的辦法使得多閾值搜索范圍減小，提高了搜索效率，但其搜索結(jié)果卻帶有隨機(jī)性，并不能準(zhǔn)確地找到Otsu閾值。文獻(xiàn)[12]采用遞推的方法優(yōu)化了在Otsu閾值計(jì)算過程中各類均值與方差的計(jì)算方式，大大提高了運(yùn)算效率。近年來，在多閾值分割技術(shù)研究當(dāng)中，主要采用群智能算法進(jìn)行優(yōu)化，如螢火蟲算法[13]、遺傳算法(GA)[6,14]、粒子群算法(PSO)、蟻群算法(ACO)、蜂群算法(BCA)[7,15,16]以及細(xì)菌覓食算法等，但其所得閾值都不能保證與Otsu準(zhǔn)則一致，并不是傳統(tǒng)意義上的多閾值快速分割算法，文獻(xiàn)[17]根據(jù)Otsu單閾值性質(zhì)提出了一種快速算法，計(jì)算所得閾值符合Otsu原則，但并沒有向多閾值情況進(jìn)行推廣，有著一定局限性。

分析多閾值Otsu方法的閾值性質(zhì)可以為改進(jìn)算法提供理論依據(jù)。本文分析并證明了多閾值Otsu方法找出的最佳閾值與分割所得類均值之間的數(shù)學(xué)對(duì)應(yīng)關(guān)系，即：。基于此結(jié)論，建立了一種新的閾值搜索模式，提出了一個(gè)可以快速計(jì)算符合多閾值Otsu準(zhǔn)則的算法，并且在理論上分析了算法優(yōu)化的迭代效率，證明了算法的可行性與有效性。

2 Multi-Otsu閾值性質(zhì)分析

2.1 Multi-Otsu簡(jiǎn)介

Otsu指出最大類間原則與最小類內(nèi)原則本質(zhì)上是等價(jià)的。

2.2 Multi-Otsu閾值性質(zhì)分析

得到

3 基于多閾值Otsu準(zhǔn)則的快速計(jì)算

3.1 快速計(jì)算原理

3.2 建立查找表

圖1 算法流程圖

4 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)的硬件條件為Core2 E7200 2.53 GHz CPU, 2 G內(nèi)存的戴爾臺(tái)式電腦，編程環(huán)境采用OPENCV2.31。分別采用其他優(yōu)化算法與本文算法對(duì)圖2-圖5進(jìn)行了分割計(jì)算，得出了閾值個(gè)數(shù)為2, 3, 4的情況下的算法運(yùn)行時(shí)間以及分割所得閾值，實(shí)驗(yàn)結(jié)果如圖6-圖17和表1-表3所示。

表1雙閾值算法效率對(duì)比(ms)

分割圖像傳統(tǒng)多閾值Otsu[3]遞推多閾值Otsu[12]遺傳算法多閾值Otsu[14]本文算法 圖276.54(43,113)3.60(43,113)21.00(42,112)0.75(43,113) 圖377.08(70,144)3.21(70,144)19.95(80,148)0.95(70,144) 圖477.66(69,143)3.43(69,143)23.00(67,154)0.99(69,143) 圖576.95(53,146)3.25(53,146)20.00(65,150)0.85(53,146)

表2 3閾值算法效率對(duì)比(ms)

分割圖像傳統(tǒng)多閾值Otsu[3]遞推多閾值Otsu[12]遺傳算法多閾值Otsu[14]本文算法 圖26985.98(23,69,123)170.53(23,69,123)68.95(33,191,192)25.15(23,69,123) 圖36936.87(61,127,188)119.23(61,127,188)69.35(61,106,110)51.00(61,127,188) 圖46933.66(57,116,154)119.01(44,111,182)67.56(125,130,165)52.40(44,111,182) 圖56939.29(40,109,173)118.69(40,109,173)63.00(47,121,173)38.26(40,109,173)

表3 4閾值算法效率對(duì)比(ms)

分割圖像傳統(tǒng)多閾值Otsu[3]遞推多閾值Otsu[12]遺傳算法多閾值Otsu[14]本文算法 圖2458238.00(19,59,97,135)20710.20(19,59,97,135)4354.51(25,40,120,137)1936.12(19,59,97,135) 圖3454857.00(45,90,140,190)14721.60(45,90,140,190)4412.39(35,60,124,173)4099.21(45,90,140,190) 圖4486471.00(38,90,136,166)13801.90(38,90,136,166)4928.60(46,80,124,151)3796.25(38,90,136,166) 圖5531277.00(31,87,136,188)19132.00(31,87,136,188)5469.37(27,57,116,154)3126.62(31,87,136,188)

實(shí)驗(yàn)結(jié)果表明本文分析的多閾值Otsu最佳閾值的性質(zhì)是符合Otsu準(zhǔn)則的，并且基于此性質(zhì)提出的多閾值Otsu快速算法給出的閾值完全符合Otsu準(zhǔn)則，所計(jì)算出的閾值和傳統(tǒng)多閾值Otsu方法一致，并且相對(duì)于遞推多閾值Otsu算法，在底層計(jì)算優(yōu)化的基礎(chǔ)上進(jìn)一步減小了閾值搜索范圍，從而使得算法運(yùn)行效率大大提高，而且相對(duì)其他帶有隨機(jī)性的優(yōu)化算法，不僅運(yùn)算效率得到了提升，而且在分割結(jié)果上也克服了這類算法的隨機(jī)性與偶然性，即分割結(jié)果并不在嚴(yán)格意義上符合Otsu準(zhǔn)則，本文算法所計(jì)算的閾值完全符合Otsu準(zhǔn)則，是嚴(yán)格意義上Otsu多閾值快速算法。

圖2 腦部切片圖像 圖3 復(fù)雜風(fēng)景圖像 圖4 高對(duì)比度人物圖像 圖5 行星圖像

圖6 圖2的雙閾值分割效果 圖7 圖3的雙閾值分割效果 圖8 圖4的雙閾值分割效果 圖9 圖5的雙閾值分割效果

圖10 圖2的3閾值分割效果 圖11 圖3的3閾值分割效果 圖12 圖4的3閾值分割效果 圖13 圖5的3閾值分割效果

圖14 圖2的4閾值分割效果 圖15 圖3的4閾值分割效果 圖16 圖4的4閾值分割效果 圖17 圖5的4閾值分割效果

5 結(jié)論

本文通過對(duì)多閾值Otsu最佳閾值性質(zhì)的研究，從理論上證明了多閾值Otsu方法找出的最佳閾值與分割所得類的均值之間的數(shù)學(xué)對(duì)應(yīng)關(guān)系，即：,，從而針對(duì)傳統(tǒng)多閾值Otsu窮舉搜索量大的缺點(diǎn)，提出了一種新的搜索模式，建立數(shù)據(jù)計(jì)算查找表優(yōu)化直方圖底層數(shù)據(jù)計(jì)算，從理論上分析了新算法的時(shí)間復(fù)雜度的提升效果并分別利用其它優(yōu)化算法以及本文算法對(duì)4幅圖像進(jìn)行了算法效率對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，本文提出的算法能夠有效地減小閾值搜索范圍，將大部分冗余閾值剔除，相比于傳統(tǒng)的窮舉計(jì)算，大大地提高了算法效率，并且算法優(yōu)化的時(shí)間復(fù)雜度比較穩(wěn)定，更適合Otsu多閾值方法在實(shí)時(shí)計(jì)算上的一些應(yīng)用，并且分析證明了多閾值Otsu最佳閾值的性質(zhì)嚴(yán)格符合Otsu準(zhǔn)則，因此算法計(jì)算得出的閾值與嚴(yán)格的多閾值Otsu算法一致，即嚴(yán)格符合Otsu準(zhǔn)則，解決了其他一些優(yōu)化算法所帶來的閾值隨機(jī)性與偶然性問題。

[1] 申鉉京, 龍建武, 陳海鵬, 等. 三維直方圖重建和降維的Otsu閾值分割算法[J]. 電子學(xué)報(bào), 2011, 39(5) : 1108-1114.

SHEN Xuanjing, LONG Jianwu, CHEN Haipeng,. Otsu thresholding algorithm based on rebuilding and dimension reduction of the 3-dimensional histogram[J]., 2011, 39(5): 1108-1114.

[2] 汪海洋, 潘德爐, 夏德深. 二維Otsu自適應(yīng)閾值選取算法的快速實(shí)現(xiàn)[J]. 自動(dòng)化學(xué)報(bào), 2007, 33(9): 968-971. doi: 10.16383/j.aas.2007.09.004.

WANG Haiyang, PAN Delu, and XIA Deshen. A fast algorithm for two-dimensional Otsu adaptive threshold algorithm[J]., 2007, 33(9): 968-971. doi: 10.16383/j.aas.2007.09.004.

[3] OTSU N. A threshold selection method from gray-level histograms[J].,,, 1979, 9(1): 62-66.

[4] 劉立, 焦斌亮, 劉欽龍. Otsu 多閾值算法推廣實(shí)現(xiàn)[J]. 測(cè)繪科學(xué), 2009, 34(6): 240-241.

LIU Li, JIAO Binliang, and LIU Qinlong. Otsu multi- threshold promotion and realization of Otsu multi-threshold segmentation method[J]., 2009, 34(6): 240-241.

[5] 劉艷, 趙英良. Otsu多閾值快速求解算法[J]. 計(jì)算機(jī)應(yīng)用, 2011, 31(12): 3363-3365. doi: 10.3724/SP.J.1087.2011.03363.

LIU Yan and ZHAO Yingliang. Quick approach of multi-threshold Otsu method for image segmentation[J]., 2011, 31(12): 3363-3365. doi: 10.3724/SP.J.1087.2011.03363.

[6] HAMMOUCHE K, DIAF M, and SIARRY P. A comparative study of various meta-heuristic techniques applied to the multilevel thresholding problem[J]., 2010, 23(5): 676-688.doi: 10.1016 /j.engappai.2009.09.011.

[7] HORNG Minghuwi. A multi-level image thresholding using the honey bee mating optimization[J]., 2010, 215(9): 3302-3310.doi: 10.1016/ j.amc.2009.10.018.

[8] 張懷柱, 向長(zhǎng)波, 宋建中, 等. 改進(jìn)的遺傳算法在實(shí)時(shí)圖像分割中的應(yīng)用[J]. 光學(xué)精密工程, 2008, 16(2): 333-338.

ZHANG Huaizhu, XIANG Changbo, SONG Jianzhong,. Application of improved adaptive genetic algorithm to image segmentation in real-time[J]., 2008, 16(2): 333-338.

[9] BHANDARI A K, KUMAR A, and SINGH G K.Modified artificial bee colony based computationally efficient multilevel thresholding for satellite image segmentation using Kapur’s, Otsu and Tsallis functions[J]., 2015, 42(3): 1573-1601. doi: 10.1016/j.eswa. 2014.09.049.

[10] CHEN Zezhi , PEARS N, FREEMAN M,. Background subtraction in video using recursive mixture models, spatio- temporal filtering and shadow removal[C]. International Symposium on Visual Computing, Berlin, Germany, 2009: 1141-1150. doi: 10.1007/978-3-642-10520-3_109.

[11] ARORA S, ACHARYA J, VERMA A,. Multi-level thresholding for image segmentation through a fast statistical recursive algorithm[J]., 2008, 29(2): 119-125. doi: 10.1016/j.patrec.2007.09.005.

[12] 范九倫, 趙鳳, 張雪峰. 三維Otsu閾值分割方法的遞推算法[J]. 電子學(xué)報(bào), 2007, 35(7): 1398-1402.

FAN Jiulun, ZHAO Feng, and ZHANG Xuefeng. Recursive algorithm for three-dimensional Otsu,s thresholding segmentation method[J]., 2007, 35(7): 1398-1402.

[13] WU Peng. Image segmentation method based on firefly algorithm and maximum entropy method[J]., 2014, 50(12): 115-119.

[14] 曲仕茹, 楊紅紅. 基于遺傳算法參數(shù)優(yōu)化的PCNN紅外圖像分割[J]. 強(qiáng)激光與粒子束, 2015, 27(5): 38-43. doi: 10.11884/ HPLPB201527.051007.

QU Shiru and YANG Honghong. Infrared image segmentation based on PCNN with genetic algorithm parameter optimization[J]., 2015, 27(5): 38-43. doi: 10.11884/HPLPB201527. 051007.

[15] YUAN Xiaocui, WU Lushen, and PENG Qingjin. An improved Otsu method using the weighted object variance for defect detection[J]., 2015, 349(15): 472-484. doi: 10.1016/j.apsusc.2015.05.033.

[16] FAYCAL Hamdaoui, ANIS Sakly, and ABDELLATIF Mtibaa. Computational Intelligence Applications in Modeling and Control[M]. Germany: Springer, 2015: 343-367.

[17] 何志勇, 孫立寧, 陳立國(guó). Otsu準(zhǔn)則下分割閾值的快速計(jì)算[J]. 電子學(xué)報(bào), 2013, 41(2): 267-272. doi: 10.3969/j.issn.0372- 2112.2013.02.010.

HE Zhiyong, SUN Lining, and CHEN Liguo. Fast computation of threshold based on Otsu criterion[J]., 2013, 41(2): 267-272. doi: 10.3969/j. issn.0372-2112. 2013.02.010.

申鉉京： 男，1958年生，教授，博士生導(dǎo)師，研究方向?yàn)閳D像處理與模式識(shí)別、多媒體信息安全、智能控制技術(shù).

劉 翔： 男，1990年生，碩士生，研究方向?yàn)閳D像分割.

陳海鵬： 男，1978年生，副教授，研究方向?yàn)閳D像處理與模式識(shí)別、多媒體信息安全.

Fast Computation of Threshold Based on Multi-threshold Otsu Criterion

SHEN Xuanjing LIU Xiang CHEN Haipeng

(,,130012,);(,,130012,)

To resolve the problem of low efficiency which traditional multi-threshold Otsu existing in searching of optimal thresholds on the brute-force method, the thresholds properties of multi-threshold Otsu are analyzed, and the mathematical correspondence is proved between a set of optimal thresholds and the means of various categories. A new algorithm is proposed to calculate the optimal thresholds and a new model of searching thresholds is also built according to the properties of thresholds of multi-threshold Otsu.The algorithm searches for a set of optimal thresholds that satisfy the correspondence between the thresholds and the means of various categories segmented by them, so the optimal thresholds of Otsu can be determined.The algorithm reduces the search range effectively and optimizes the calculation of means and variances using lookup table. Experimental results show that the segmentation speed of the algorithm is greatly improved compared with the traditional multi-threshold Otsu method, and the algorithm can not only improve the computation speed, but also overcome the shortcomings of randomness and contingency of thresholds compared with other fast multi-threshold Otsu algorithm, and the results are strictly in line with the principle of multi-threshold Otsu.

Image segmentation; Multi-threshold Otsu criterion; Threshold selection; Fast computation

TP391

A

1009-5896(2017)01-0144-06

10.11999/JEIT160248

2016-03-17；改回日期：2016-07-22；

2016-09-30

陳海鵬 chenhp@jlu.edu.cn

國(guó)家青年科學(xué)基金(61305046)，吉林省自然科學(xué)基金(20140101193JC, 20150101055JC)

The Young Scientists Fund of the National Natural Science Foundation of China (61305046), The Natural Science Foundation of Jilin Province (20140101193JC, 20150101055JC)