(45-1) 09 * << * >> * Russian * English * Content * All Issues

A generalization of Otsu method for linear separation of two unbalanced classes in document image binarization
E.I. Ershov 1, S.A. Korchagin 1, V.V. Kokhan 1,3, P.V. Bezmaternykh 2,3

1 Institute for Information Transmission Problems, RAS, 127051, Moscow, Bolshoy Karetny per., 19, str. 1,
2 Federal Research Center "Computer Science and Control" of Russian Academy of Sciences,
Moscow, Russia, 117312, pr. 60-lettya Oktyabrya, 9,
3 Smart Engines Service LLC, Moscow, Russia, 117312, pr. 60-lettya Oktyabrya, 9

 PDF, 3279 kB

DOI: 10.18287/2412-6179-CO-752

Pages: 66-76.

Full text of article: English language.

Abstract:
The classical Otsu method is a common tool in document image binarization. Often, two classes, text and background, are imbalanced, which means that the assumption of the classical Otsu method is not met. In this work, we considered the imbalanced pixel classes of background and text: weights of two classes are different, but variances are the same. We experimentally demonstrated that the employment of a criterion that takes into account the imbalance of the classes' weights, allows attaining higher binarization accuracy. We described the generalization of the criteria for a two-parametric model, for which an algorithm for the optimal linear separation search via fast linear clustering was proposed. We also demonstrated that the two-parametric model with the proposed separation allows increasing the image binarization accuracy for the documents with a complex background or spots.

Keywords:
threshold binarization, Otsu method, optimal linear classification, historical document image binarization.

Citation:
Ershov EI, Korchagin SA, Kokhan VV, Bezmaternykh PV. A generalization of Otsu method for linear separation of two unbalanced classes in document image binarization. Computer Optics 2021; 45(1): 66-76. DOI: 10.18287/2412-6179-CO-752.

Acknowledgements:
We are grateful for the insightful comments offered by D.P. Nikolaev. This research was partially supported by the Russian Foundation for Basic Research No. 19-29-09066 and 18-07-01387.

References:
  1. Chaki N, Shaikh SH, Saeed K. A comprehensive survey on image binarization techniques. Stud Comput Intell 2014; 560: 5-15. DOI: 10.1007/978-81-322-1907-1_2.
  2. Challa R, Rao KS. Efficient compression of binarized tainted documents. Int J Adv Comput Sci Appl 2018; 9(2): 663-667. DOI: 10.26483/ijarcs.v9i2.5520.
  3. Arlazarov VL, Emel'janov NE, ed. Razvitie bezbumazhnoj tehnologii v organizacionnyh sistemah [In Russian]. Moscow: "URSS" Publisher; 1999. ISBN: 5-8360-0097-2.
  4. Fan H, Xie F, Li Y, Jiang Z, Liu J. Automatic segmentation of dermoscopy images using saliency combined with Otsu threshold. Comput Biol Med 2017; 85: 75-85. DOI: 10.1016/j.compbiomed.2017.03.025.
  5. Vizilter YV, Gorbatcevich VS, Vishnyakov BV, Sidyakin SV. Object detection in images using morphlet descriptions [In Russian]. Computer Optics 2017; 41(3): 406-411. DOI: 10.18287/2412-6179-2017-41-3-406-411.
  6. Iskhakov AR, Malikov RF. Calculation of aircraft area on satellite images by genetic algorithm [In Russian]. Vestnik JuUrGU. Ser. Matematicheskoe Modelirovanie i Programmirovanie 2016; 9(4): 148-154.
  7. Mustafa WA, Haniza Y. Illumination and contrast correction strategy using bilateral filtering and binarization comparison. J Telecommun Electron Comput Eng 2016; 8(1): 67-73.
  8. Kokhan V, Grigoriev M, Buzmakov A, Uvarove V, Ingacheva A, Shvets E, Chukalina M. Segmentation criteria in the problem of porosity determination based on CT scans. Proc SPIE 2020; 11433: 114331E. DOI: 10.1117/12.2558081.
  9. Fedorenko VA, Sidak EV. Method of the binarization of images of traces on the shot bullets for the automatic assessment of their suitability to identification of the fierarms [In Russian]. Informacionnye Tehnologii i Vychislitel'nye Sistemy 2016; 3: 82-88.
  10. Otsu N. A threshold selection method from gray-level histograms. IEEE Trans Syst Man Cybern Syst 1979; 9(1): 62-66. DOI: 10.1109/tsmc.1979.4310076.
  11. Niblack W. An introduction to digital image processing. Englewood Cliffs: Prentice Hall; 1986.
  12. Aliev MA, Nikolaev DP, Saraev AA. Postroenie bystryh vychislitel'nyh shem nastrojki algoritma binarizacii Nibljeka [In Russian]. Trudy ISA RAN 2014; 64(3): 25-34.
  13. Pratikakis I, Zagoris K, Barlas G, Gatos B. ICDAR2017 Competition on document image binarization (DIBCO 2017). 14th IAPR International Conference on Document Analysis and Recognition (ICDAR) 2017: 1395-1403. DOI: 10.1109/icdar.2017.228.
  14. Calvo-Zaragoza J, Gallego A-J. A selectional auto-encoder approach for document image binarization. Patt Recogn 2018; 86: 37-47. DOI: 10.1016/j.patcog.2018.08.011.
  15. Chen Y, Leedham G. Decompose algorithm for thresholding degraded historical document images. IEE Proceedings – Vision, Image and Signal Processing 2005; 152(6): 702-714. DOI: 10.1049/ip-vis:20045054.
  16. Gatos B, Ntirogiannis K, Pratikakis I. ICDAR 2009 Document image binarization contest (DIBCO 2009). 10th International Conference on Document Analysis and Recognition 2009: 1375-1382. DOI: 10.1109/icdar.2009.246.
  17. Document image binarization. Source: <https://dib.cin.ufpe.br>.
  18. Bezmaternykh PV, Ilin DA, Nikolaev DP. U-Net-bin: hacking the document image binarization contest. Computer Optics 2019; 43(5): 825-832. DOI: 10.18287/2412-6179-2019-43-5-825-832.
  19. Tropin DV, Shemyakina YA, Konovalenko IA, Faradzhev IA. Localization of planar objects on the images with complex structure of projective distortion [In Russian]. Informacionnye Processy 2019; 19(2): 208-229.
  20. Kurita T, Otsu N, Abdelmalek N. Maximum likelihood thresholding based on population mixture models. Patt Recogn 1992; 25(10): 1231-1240. DOI: 10.1016/0031-3203(92)90024-d.
  21. Ershov EI. Fast binary linear clustering algorithm for small dimensional histograms [In Russian]. Sensory systems 2017; 31(3): 261-269.
  22. Sezgin M, Sankur B. Survey over image thresholding techniques and quantitative performance evaluation. J Electron Imaging 2004; 13(1): 146-165. DOI: 10.1117/1.1631315.
  23. Pratikakis I, Zagoris K, Barlas G, Gatos B. ICFHR2016 handwritten document image binarization contest (H-DIBCO 2016). 15th International Conference on Frontiers in Handwriting Recognition (ICFHR) 2016: 619-623. DOI: 10.1109/ICFHR.2016.0118.
  24. Ntirogiannis K, Gatos B, Pratikakis I. ICFHR2014 competition on handwritten document image binarization (H-DIBCO 2014). 14th International conference on frontiers in handwriting recognition 2014: 809-813. DOI: 10.1109/ICFHR.2014.141.
  25. Kittler J, Illingworth J. Minimum error thresholding. Patt Recogn 1986; 19(1): 41-47. doi: 10.1016/0031-3203(86)90030-0.
  26. Sungzoon C, Haralick R, Yi S. Improvement of Kittler and Illingworth's minimum error thresholding. Patt Recogn 1989; 22(5): 609-617. DOI: 10.1016/0031-3203(89)90029-0.
  27. AlSaeed DH, Bouridane A, ElZaart A, Sammouda R. Two modified Otsu image segmentation methods based on Lognormal and Gamma distribution models. International Conference on Information Technology and e-Services 2012: 1-5. DOI: 10.1109/ICITeS.2012.6216680.
  28. AlSaeed DH, Bouridane A, ElZaart A. A novel fast Otsu digital image segmentation method. Int Arab J Inf Technol (IAJIT) 2016; 13(4): 427-433.
  29. Cheriet M, Said JN, Suen CY. A recursive thresholding technique for image segmentation. IEEE Trans Image Process 1998; 7(6): 918-921. DOI: 10.1109/83.679444.
  30. Liu J, Li W, Tian Y. Automatic thresholding of gray-level pictures using two-dimensional Otsu method. International Conference on Circuits and Systems 1991: 325-327. DOI: 10.1109/ciccas.1991.184351.
  31. Gong J, Li L, Chen W. Fast recursive algorithms for two-dimensional thresholding. Patt Recogn 1998; 31(3): 295-300. DOI: 10.1016/S0031-3203(97)00043-5.
  32. Lu C, Zhu P, Cao Y. The segmentation algorithm improvement of a two-dimensional Otsu and application research. Software Technology and Engineering (ICSTE) 2010; 1: V1-76-V1-79. 3-5. DOI: 10.1109/ICSTE.2010.5608908.
  33. Chen Q, Zhao L, Lu J, Kuang G, Wang N, Jiang Y. Modified two-dimensional Otsu image segmentation algorithm and fast realization. Image Process 2012; 6(4): 426-433. DOI: 10.1049/iet-ipr.2010.0078.
  34. Sha C, Hou J, Cui H. A robust 2D Otsu’s thresholding method in image segmentation. J Vis Commun Image Represent 2016; 41: 339-351. doi: 10.1016/j.jvcir.2016.10.013.
  35. Zhang X, Zhao H, Li X, Feng Y, Li H. A multi-scale 3D Otsu thresholding algorithm for medical image segmentation. Digit Signal Process 2017; 60: 186-199. DOI: 10.1016/j.dsp.2016.08.003.
  36. Zhang J, Hu J. Image segmentation based on 2D Otsu method with histogram analysis. 2008 International Conference on Computer Science and Software Engineering 2008: 6: 105-108. DOI: 10.1109/CSSE.2008.206.
  37. Zhang Y, Zeng L, Zhang Y, Meng J. 2D Otsu segmentation algorithm improvement based on FOCPSO. 2018 IEEE Intl Conf on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications (ISPA/IUCC/BDCloud/SocialCom/SustainCom) 2018; 809-815. DOI: 10.1109/BDCloud.2018.00121.
  38. Zhu X, Xiao Y, Tan G, Zhou Sh, Leung C-S, Zheng Y. GPU-accelerated 2D OTSU and 2D entropy-based thresholding. J Real Time Image Process 2020; 17: 993-1005. DOI: 10.1007/s11554-018-00848-5.
  39. Nafchi HZ, Moghaddam RF, Cheriet M. Phase-based binarization of ancient document images: Model and applications. IEEE Trans Image Process 2014; 23(7): 2916-2930. DOI: 10.1109/TIP.2014.2322451.
  40. Bolotova YA, Spitsyn VG, Osina PM. A review of algorithms for text detection in images and videos. Computer Optics 2017; 41(3): 441-452. DOI: 10.18287/2412-6179-2017-41-3-441-452.
  41. Boudraa O, Hidouci WK, Michelucci D. A robust multi stage technique for image binarization of degraded historical documents. 5th International Conference on Electrical Engineering – Boumerdes (ICEE-B) 2017. DOI: 10.1109/ICEE-B.2017.8192044.
  42. Farrahi MR, Cheriet M. AdOtsu: An adaptive and parameterless generalization of Otsu's method for document image binarization.Patt Recogn 2012; 45(6): 2419-2431. DOI: 10.1016/j.patcog.2011.12.013.
  43. Bolotova YU, Spitsyn VG, Rudometkina MN. License plate recognition algorithm on the basis of a connected components method and a hierarchical temporal memory model. Computer Optics 2015; 39(2): 275-280. DOI: 10.18287/0134-2452-2015-39-2-275-280.
  44. Lech P, Okarma K. Binarization of document images using the modified local-global Otsu and Kapur algorithms. Przeglad Elektrotechniczny 2015; 1(2): 73-76. DOI: 10.15199/48.2015.02.18.
  45. Ayatollahi SM, Nafchi HZ. Persian heritage image binarization competition (PHIBC 2012). First Iranian Conference on Pattern Recognition and Image Analysis (PRIA) 2013. DOI: 10.1109/PRIA.2013.6528442.
  46. Lins RD. Nabuco – Two decades of document processing in Latin America. J Univers Comput Sci 2011; 17(1): 151-161. DOI: 10.3217/jucs-017-01-0151.
  47. Lins RD, Silva G, Torreão G. Content recognition and indexing in the LiveMemory platform. In Book: Ogier J-M, Liu W, Lladós J, eds. Graphics recognition. Achievements, challenges, and evolution. Berlin, Heidelberg, New York: Springer; 2009: 220-230. DOI: 10.1007/978-3-642-13728-0_20.
  48. Ershov E, Korchagin S. Description of the collected dataset. 2019. Source: <ftp://vis.iitp.ru/dataset_description.txt>.
  49. Ntirogiannis K, Gatos B, Pratikakis I. Performance evaluation methodology for historical document image binarization. IEEE Trans Image Process 2012; 22(2): 595-609. DOI: 10.1109/TIP.2012.2219550.
  50. Bocharov DA. A linear regression method robust to extreme stationary clutter [In Russian]. Sensory Systems 2020; 34(1): 44-56. DOI: 10.31857/S0235009220010059.

© 2009, IPSI RAS
151, Molodogvardeiskaya str., Samara, 443001, Russia; E-mail:journal@computeroptics.ru ; Tel: +7 (846) 242-41-24 (Executive secretary), +7 (846) 332-56-22 (Issuing editor), Fax: +7 (846) 332-56-20