Two-step skeletization of binary images based on the Zhang-Suen model and the producing mask
https://doi.org/10.21122/2309-4923-2021-1-62-69
Abstract
The aim of the work is to limit excessive thinning and increase the resistance to contour noise of skeletons resulted from arbitrary binary image shape while maintaining a high skeletonization rate. The skeleton is a set of thin lines, the relative position, the size and shape, which conveys information of size, shape and orientation in space of the corresponding homogeneous region of the image. To ensure resistance to contour noise, skeletonization algorithms are built on the basis of several steps. Zhang-Suen algorithm is widely known by high-quality skeletons and average performance, which disadvantages are the blurring of diagonal lines with a thickness of 2 pixels and the totally disappear patterns of 2x2 pixels. To overcome them, a mathematical model that compensates the Zhang-Suen algorithm has proposed in this paper, along with a producing mask and two logical conditions for evaluating its elements.
About the Authors
J., Ma
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
Ma Jun PG student of department of infocommunication technologies
Minsk
V. Yu. Tsviatkou
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
Doctor of Engineering, associate professor, head of department of infocommunications technologie
Minsk
V. K. Kanapelka
Belarusian State University of Informatics and Radioelectronics
Belarus
Belarus
Doctor of Engineering, professor, professor of department of infocommunications
Minsk
References
1. Saha, P. K. A survey on skeletonization algorithms and their applications / P. K. Saha, G. Borgefors, G. Baja // Pattern Recognition Letters. – 2016. – Vol. 76. – P. 3–12.
2. Zhang, T. Y. A fast parallel algorithm for thinning digital patterns / T. Y. Zhang, C. Y. Suen // Comm. ACM. – 1984. – Vol. 27(3). – P. 236–239.
3. Harous, S. Handwritten Character-Based Parallel Thinning Algorithms: A Comparative Study / S. Harous, A. Elnagar // University of Sharjah Journal of Pure & Applied Sciences. – 2009. – Vol. 6(1). – P. 81–101.
4. Lu, H. E. A Comment on “A Fast Parallel Algorithm for Thinning Digital Patterns” / H. E. Lu, P.S.P. Wang // Communications of the ACM. – 1986. – Vol. 29(3). – P. 239–242.
5. Kocharyan, D. A Modified fingerprint image thinning algorithm / D. Kocharyan // American Journal of Software Engineering and Applications. – 2013. – Vol. 2(1). – P. 1–6.
6. Boudaoud, L. B. A new thinning algorithm for binary images / L. B. Boudaoud, A. Sider, A. Tari // 3rd International Conference on Control, Engineering & Information Technology. – 2015. – P. 1–6.
7. Boudaoud L. B. A modified ZS thinning algorithm by a hybrid approach / L. B. Boudaoud, B. Solaiman, A. Tari // The Visual Computer. – 2017. –P. 689–706.
8. Guo, Z. Parallel thinning with two-subiteration algorithms / Z. Guo, R. W. Hall // Communications of the ACM. – 1989. – Vol. 32(3). – P. 359–373.
9. Guo, Z. Fast fully parallel thinning algorithms / Z. Guo, R. W. Hall // CVGIP: Image Understanding. – 1992. – Vol. 55(3). – P. 317–328.
10. Zhang, Y. Y. A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons / Y. Y. Zhang, P. P. Wang // International Conference on Pattern Recognition, Vienna, Austria. – 1996. – Vol. 4. – P. 457–461.
11. Abdulla, W. H. A preprocessing algorithm for handwritten character recognition / W. H. Abdulla, A.O.M. Saleh, A. H. Morad // Pattern Recognition Letters. – 1988. – Vol. 7(1). – P. 13–18.
12. Sossa, J. H. An improved parallel algorithm for thinning digital patterns / J. H. Sossa // Pattern Recognition Letters. – 1989. – Vol. 10. – P. 77–80.
13. Tarabek, P. A Robust Parallel Thinning Algorithm for Pattern Recognition / P. Tarabek // 7th IEEE International Symposium on Applied Computational Intelligence and Informatics. – 2012. – P. 75–79.
14. Kwon, J.-S. An enhanced thinning algorithm using parallel processing / J.-S. Kwon, J. – W. Gi, E.-K. Kang // IEEE. – 2001. – P. 752–755.
15. Dong, J. An improved parallel thinning algorithm / J. Dong, W. Lin, C. Huang // Proceedings of the 2016 International Conference on Wavelet Analysis and Pattern Recognition, Jeju, South Korea. – 2016. – P. 162–167.
16. Chin, R. T. A one-pass thinning algorithm and its parallel implementation // R. T. Chin, H. K. Wan, D. L. Stover, R. D. Iverson // Computer Vision, Graphics, and Image Processing. – 1987. – Vol. 40. – P. 30–40.
17. Ма, Ц. Скелетизация изображений на основе комбинации однои двухподытерационных моделей // Ц. Ма, В. Ю. Цветков, В. К. Конопелько // Информатика. – 2020. – Т. 17, № 2. – С. 25–35.
18. Jang, B. K. One-pass parallel: analysis, properties, and quantitative evaluation / B. K. Jang, R. T. Chin // IEEE Transactions on Pattern Analysis and Machine Intelligence. – 1992. – Vol. 14. – P. 1129–1140.
19. Sebastian, T. B. Recognition of shapes by editing their shock graphs / T. B. Sebastian, P. N. Klein, B. B. Kimia // IEEE transactions on pattern analysis and machine intelligence. – 2004. – Vol. 26(5). – P. 550–571.
Review
For citations:
Ma J., Tsviatkou V.Yu., Kanapelka V.K. Two-step skeletization of binary images based on the Zhang-Suen model and the producing mask. «System analysis and applied information science». 2021;(1):62-69. (In Russ.) https://doi.org/10.21122/2309-4923-2021-1-62-69
Views:
2138
Email this article 