基于多閾值Otsu準則的閾值分割快速計算

申鉉京 劉 翔 陳海鵬

?

基于多閾值Otsu準則的閾值分割快速計算

申鉉京 劉 翔 陳海鵬*

(吉林大學計算機科學與技術(shù)學院 長春 130012);(吉林大學符號計算與知識工程教育部重點實驗室 長春 130012)

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

圖像分割；多閾值Otsu準則；閾值選??；快速計算

1 引言

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

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

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

2.1 Multi-Otsu簡介

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

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

得到

3 基于多閾值Otsu準則的快速計算

3.1 快速計算原理

3.2 建立查找表

圖1 算法流程圖

4 實驗結(jié)果

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

表1雙閾值算法效率對比(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閾值算法效率對比(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閾值算法效率對比(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)

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

圖2 腦部切片圖像 圖3 復雜風景圖像 圖4 高對比度人物圖像 圖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é)論

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

[1] 申鉉京, 龍建武, 陳海鵬, 等. 三維直方圖重建和降維的Otsu閾值分割算法[J]. 電子學報, 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自適應閾值選取算法的快速實現(xiàn)[J]. 自動化學報, 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 多閾值算法推廣實現(xiàn)[J]. 測繪科學, 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]. 計算機應用, 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] 張懷柱, 向長波, 宋建中, 等. 改進的遺傳算法在實時圖像分割中的應用[J]. 光學精密工程, 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]. 電子學報, 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]. 強激光與粒子束, 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] 何志勇, 孫立寧, 陳立國. Otsu準則下分割閾值的快速計算[J]. 電子學報, 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年生，教授，博士生導師，研究方向為圖像處理與模式識別、多媒體信息安全、智能控制技術(shù).

劉 翔： 男，1990年生，碩士生，研究方向為圖像分割.

陳海鵬： 男，1978年生，副教授，研究方向為圖像處理與模式識別、多媒體信息安全.

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

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

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