Fast multi-threshold Otsu algorithm with complete linear time complexity

被引：0

作者：

Shen X.-J. ^{[1
]}

Qin J. ^{[1
]}

Lyu Y.-D. ^{[2
]}

Wang R.-Q. ^{[3
]}

Liu X. ^{[1
]}

机构：

[1] College of Computer Science and Technology, Jilin University, Changchun

[2] Public Computer Education and Research Center, Jilin University, Changchun

[3] The Second Hospital of Jilin University, Changchun

来源：

Jilin Daxue Xuebao (Gongxueban)/Journal of Jilin University (Engineering and Technology Edition) | 2019年 / 49卷 / 01期

关键词：

Computer application; Fast Otsu; Image segmentation; Linear algorithm; Multi-threshold segmentation;

D O I：

10.13229/j.cnki.jdxbgxb20171036

中图分类号：

学科分类号：

摘要：

The classical multi-threshold Otsu algorithm always uses exhaustive method to find the optimal threshold value for segmenting the image, which leads to high computational complexity. With the increase in the number of thresholds, the time complexity increases exponentially. In order to solve this problem, a fast multi-threshold Otsu segmentation algorithm is proposed, which reduces the time complexity to a complete linear of O(n). This study theoretically analyze the main factors leading to the high computational complexity and time complexity in multi-threshold Otsu algorithm. Based on the above analysis, it is improved in three major aspects: numerical calculation, multi-threshold partitioning and search for optimal threshold. In the proposed algorithm, first, the numerical calculation in the segmentation process is optimized by the idea of dynamic planning. Then, the problem of multi-threshold is recursively solved, and the multi-threshold problem is decomposed into multiple single threshold problems. Finally, the multi-population PSO algorithm is used to search the optimal threshold. Experimental results show that the proposed algorithm reduces the time complexity of multi-threshold Otsu algorithm, which can be better applied in real-time environment. © 2019, Editorial Board of Jilin University. All right reserved.

引用

页码：268 / 274

页数：6

共 18 条

[1]

Shen X.-J., Long J.-W., Chen H.-P., Et al., Otsu thresholding algorithm based on rebuilding and dimension reduction of the 3-dimensional histogram, Acta Electronica Sinica, 39, 5, pp. 1108-1114, (2011)

[2]

Otsu N., A threshold selection method from gray-level histograms, IEEE Transactions on System Man and Cybemetic, 9, 1, pp. 62-66, (1979)

[3]

Fan J.-L., Zhao F., Zhang X.-F., Recursive algorithm for three-dimensional Otsu's thresholding segmentation method, Acta Electronica Sinica, 35, 7, pp. 1398-1402, (2007)

[4]

Arora S., Acharya J., Prasanta V.A., Et al., Multi-level thresholding for image segmentation through a fast statistical recursive algorith, Pattern Recognition Letters, 29, 2, pp. 119-125, (2008)

[5]

Liu L., Jiao B.-L., Liu Q.-L., Otsu multi-threshold promotion and realization of Otsu multi-threshold segmentation method, Science of Surveying and Mapping, 34, 6, pp. 240-241, (2009)

[6]

Ng H.-F., Automatic thresholding for defect detection, Pattern Recognition Letters, 27, 14, pp. 1644-1649, (2006)

[7]

Muangkote N., Sunat K., Chiewchanwattana S., Rr-cr-IJADE: An efficient differential evolution algorithm for multilevel image thresholding, Expert Systems With Applications, 90, pp. 272-289, (2017)

[8]

Peng W.U., Image segmentation method based on firefly algorithm and maximum entropy method, Computer Engineering & Applications, 50, 12, pp. 115-119, (2014)

[9]

Zhang H.-Z., Xiang C.-B., Song J.-Z., Et al., Application of improved adaptive genetic algorithm to image segmentation in real-time, Optics and Precision Engineering, 16, 2, pp. 333-338, (2008)

[10]

Yuan X.-C., Wu L.-S., Peng Q.-J., An improved Otsu method using the weighted object variance for defect detection, Applied Surface Science, 349, 15, pp. 472-484, (2015)

← 1 2 →