sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2021-1-62-69sapi-504Research ArticleОбработка информации и принятие решенийData processing and decision–makingДвухшаговая скелетизация бинарных изображений на основе модели Занга-Суена и порождающей маскиTwo-step skeletization of binary images based on the Zhang-Suen model and the producing maskМаЦ.MaJ.,

Ма Цзюнь – аспирант кафедры инфокоммуникационных технологий

Ma Jun PG student of department of infocommunication technologies

Minsk

majun1313@hotmail.comЦветковВ. Ю.TsviatkouV. Yu.

Доктор технических наук, доцент, заведующий кафедрой инфокоммуникационных технологий

Doctor of Engineering, associate professor, head of department of infocommunications technologie

Minsk

vtsvet@bsuir.byКонопелькоВ. К.KanapelkaV. K.

Доктор технических наук, профессор, профессор кафедры инфокоммуникационных технологий

Doctor of Engineering, professor, professor of department of infocommunications

Minsk

kafikt@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиБеларусьBelarusian State University of Informatics and RadioelectronicsBelarus202126042021016269Copyright © Ма Ц., Цветков В.Ю., Конопелько В.К., 20212021Ма Ц., Цветков В.Ю., Конопелько В.К.Ma J., Tsviatkou V.Y., Kanapelka V.K.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/504

Целью работы является предельное утоньшение и повышение устойчивости к контурному шуму скелетов бинарных объектов произвольной формы при сохранении высокой скорости скелетизации. Скелет представляет собой множество тонких линий, взаимное расположение, размеры и форма которых передает информацию о размере, форме и ориентации в пространстве соответствующей однородной области изображения. Для обеспечения устойчивости к контурному шуму каждая итерация алгоритмов скелетизации разделяется на несколько шагов. Благодаря относительно качественным скелетам и средней производительности широкую известность получил двухшаговый алгоритм Занга-Суена. Его недостатками являются размытие диагональных линий толщиной 2 пикселя и удаление областей размером 2х2 пикселей. Для их устранения в статье предложена математическая модель, дополняющая модель Занга-Суена порождающей маской и двумя логическими условиями оценки ее элементов.

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.

скелетизация изображенийалгоритм Занга-Суенадвухшаговая скелетизацияпараллельная скелетизацияimage skeletonizationZhang-Suen algorithmtwo-step skeletonizationparallel skeletonizationРабота выполнена в рамках ГБЦ 16–2033 «Исследование методов обработки и передачи видеоданных в инфокоммуникациях» (№ госрегистрации 20163903)ReferencesSaha, 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.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.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.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.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.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.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.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.Kocharyan, D. A Modified fingerprint image thinning algorithm / D. Kocharyan // American Journal of Software Engineering and Applications. – 2013. – Vol. 2(1). – P. 1–6.Kocharyan, D. A Modified fingerprint image thinning algorithm / D. Kocharyan // American Journal of Software Engineering and Applications. – 2013. – Vol. 2(1). – P. 1–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.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.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.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.Guo, Z. Parallel thinning with two-subiteration algorithms / Z. Guo, R. W. Hall // Communications of the ACM. – 1989. – Vol. 32(3). – P. 359–373.Guo, Z. Parallel thinning with two-subiteration algorithms / Z. Guo, R. W. Hall // Communications of the ACM. – 1989. – Vol. 32(3). – P. 359–373.Guo, Z. Fast fully parallel thinning algorithms / Z. Guo, R. W. Hall // CVGIP: Image Understanding. – 1992. – Vol. 55(3). – P. 317–328.Guo, Z. Fast fully parallel thinning algorithms / Z. Guo, R. W. Hall // CVGIP: Image Understanding. – 1992. – Vol. 55(3). – P. 317–328.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.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.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.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.Sossa, J. H. An improved parallel algorithm for thinning digital patterns / J. H. Sossa // Pattern Recognition Letters. – 1989. – Vol. 10. – P. 77–80.Sossa, J. H. An improved parallel algorithm for thinning digital patterns / J. H. Sossa // Pattern Recognition Letters. – 1989. – Vol. 10. – P. 77–80.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.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.Kwon, J.-S. An enhanced thinning algorithm using parallel processing / J.-S. Kwon, J. – W. Gi, E.-K. Kang // IEEE. – 2001. – P. 752–755.Kwon, J.-S. An enhanced thinning algorithm using parallel processing / J.-S. Kwon, J. – W. Gi, E.-K. Kang // IEEE. – 2001. – P. 752–755.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.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.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.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.Ма, Ц. Скелетизация изображений на основе комбинации однои двухподытерационных моделей // Ц. Ма, В. Ю. Цветков, В. К. Конопелько // Информатика. – 2020. – Т. 17, № 2. – С. 25–35.Ма, Ц. Скелетизация изображений на основе комбинации однои двухподытерационных моделей // Ц. Ма, В. Ю. Цветков, В. К. Конопелько // Информатика. – 2020. – Т. 17, № 2. – С. 25–35.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.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.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.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.

The authors declare that there are no conflicts of interest present.