基于多阈值Otsu准则的阈值分割快速计算

申铉京 刘 翔 陈海鹏



基于多阈值Otsu准则的阈值分割快速计算

申铉京 刘 翔 陈海鹏*

(吉林大学计算机科学与技术学院 长春 130012);(吉林大学符号计算与知识工程教育部重点实验室 长春 130012)

针对传统多阈值Otsu方法在寻找最佳阈值过程中穷举计算效率低的问题，该文分析了多阈值Otsu的阈值性质，证明了使用Otsu方法找到的一组最佳阈值与分割出的各类均值之间的数学对应关系。根据多阈值Otsu的阈值性质，该文提出一个新算法用来快速计算所需最佳阈值，建立了一种新的阈值搜索模型。该算法搜寻满足Otsu多阈值与以此阈值分割出的各类均值之间关系的一组最优阈值，从而确定符合Otsu准则的最佳阈值。该算法有效减少了阈值搜索范围，并且在均值、方差等计算上引入了查找表，优化了底层运算。实验结果表明，与传统多阈值Otsu方法相比，该算法的分割速度大幅度提高，相比于其他多阈值Otsu快速算法，不仅在计算速度上有所提升，而且得到的最佳阈值克服了随机性和偶然性的缺点，是严格符合Otsu原则的。

图像分割；多阈值Otsu准则；阈值选取；快速计算

1 引言

图像分割算法中，阈值法以计算简单，分割速度快等特点被广泛应用[1,2]。传统的Otsu法是由Otsu于1979年提出的一种经典阈值分割算法，该方法具有较高的分割精度与很强的自适应性[3]。为了适应更加复杂的图像，Otsu方法从单阈值被推广到了多阈值，但究其本质仍然是一种穷举算法，时间复杂度非常高，几乎很难达到单阈值的高实时性能。到目前为止，多阈值分割技术仍为研究中的一个难题。目前阈值分割优化算法主要分两类[9,10]：一类是减少阈值搜索范围，如松弛余量法[11]，另一类是寻优过程优化算法，即各种群智能算法。文献[4]引进了单纯形法来优化多阈值的搜索效率。文献[5]划分直方图区间，采用快速二分法求取区间中的阈值，以实现Otsu多阈值的扩展。文献[11]运用了松弛余量的办法使得多阈值搜索范围减小，提高了搜索效率，但其搜索结果却带有随机性，并不能准确地找到Otsu阈值。文献[12]采用递推的方法优化了在Otsu阈值计算过程中各类均值与方差的计算方式，大大提高了运算效率。近年来，在多阈值分割技术研究当中，主要采用群智能算法进行优化，如萤火虫算法[13]、遗传算法(GA)[6,14]、粒子群算法(PSO)、蚁群算法(ACO)、蜂群算法(BCA)[7,15,16]以及细菌觅食算法等，但其所得阈值都不能保证与Otsu准则一致，并不是传统意义上的多阈值快速分割算法，文献[17]根据Otsu单阈值性质提出了一种快速算法，计算所得阈值符合Otsu原则，但并没有向多阈值情况进行推广，有着一定局限性。

分析多阈值Otsu方法的阈值性质可以为改进算法提供理论依据。本文分析并证明了多阈值Otsu方法找出的最佳阈值与分割所得类均值之间的数学对应关系，即：。基于此结论，建立了一种新的阈值搜索模式，提出了一个可以快速计算符合多阈值Otsu准则的算法，并且在理论上分析了算法优化的迭代效率，证明了算法的可行性与有效性。

2 Multi-Otsu阈值性质分析

2.1 Multi-Otsu简介

Otsu指出最大类间原则与最小类内原则本质上是等价的。

2.2 Multi-Otsu阈值性质分析

得到

3 基于多阈值Otsu准则的快速计算

3.1 快速计算原理

3.2 建立查找表

图1 算法流程图

4 实验结果

实验的硬件条件为Core2 E7200 2.53 GHz CPU, 2 G内存的戴尔台式电脑，编程环境采用OPENCV2.31。分别采用其他优化算法与本文算法对图2-图5进行了分割计算，得出了阈值个数为2, 3, 4的情况下的算法运行时间以及分割所得阈值，实验结果如图6-图17和表1-表3所示。

表1双阈值算法效率对比(ms)

分割图像传统多阈值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)

分割图像传统多阈值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)

分割图像传统多阈值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)

实验结果表明本文分析的多阈值Otsu最佳阈值的性质是符合Otsu准则的，并且基于此性质提出的多阈值Otsu快速算法给出的阈值完全符合Otsu准则，所计算出的阈值和传统多阈值Otsu方法一致，并且相对于递推多阈值Otsu算法，在底层计算优化的基础上进一步减小了阈值搜索范围，从而使得算法运行效率大大提高，而且相对其他带有随机性的优化算法，不仅运算效率得到了提升，而且在分割结果上也克服了这类算法的随机性与偶然性，即分割结果并不在严格意义上符合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 结论

本文通过对多阈值Otsu最佳阈值性质的研究，从理论上证明了多阈值Otsu方法找出的最佳阈值与分割所得类的均值之间的数学对应关系，即：,，从而针对传统多阈值Otsu穷举搜索量大的缺点，提出了一种新的搜索模式，建立数据计算查找表优化直方图底层数据计算，从理论上分析了新算法的时间复杂度的提升效果并分别利用其它优化算法以及本文算法对4幅图像进行了算法效率对比实验，实验结果表明，本文提出的算法能够有效地减小阈值搜索范围，将大部分冗余阈值剔除，相比于传统的穷举计算，大大地提高了算法效率，并且算法优化的时间复杂度比较稳定，更适合Otsu多阈值方法在实时计算上的一些应用，并且分析证明了多阈值Otsu最佳阈值的性质严格符合Otsu准则，因此算法计算得出的阈值与严格的多阈值Otsu算法一致，即严格符合Otsu准则，解决了其他一些优化算法所带来的阈值随机性与偶然性问题。

[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自适应阈值选取算法的快速实现[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 多阈值算法推广实现[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] 曲仕茹, 杨红红. 基于遗传算法参数优化的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年生，教授，博士生导师，研究方向为图像处理与模式识别、多媒体信息安全、智能控制技术.

刘 翔： 男，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)