informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2020-17-2-25-35inform-1051Research ArticleОБРАБОТКА СИГНАЛОВ, ИЗОБРАЖЕНИЙ, РЕЧИ, ТЕКСТА И РАСПОЗНАВАНИЕ ОБРАЗОВSIGNAL, IMAGE, SPEECH, TEXT PROCESSING AND PATTERN RECOGNITIONСкелетизация изображений на основе комбинации одно- и двухподытерационных моделейImage skeletonization based on combination of one- and two-sub-iterations modelsМаЦ.MaJ.

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

Минск

Jun Ma, Postgraduate Student of Department of Infocommunication Technologies

Minsk

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

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

Минск

Viktar Yu. Tsviatkou, Dr. Sci (Eng.), Associate Professor, Head of Department of Infocommunication Technologies

Minsk

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

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

Минск

Valery K. Kanapelka, Dr. Sci (Eng.), Professor, Professor of Department of Infocommunication Technologies

Minsk

kafikt@bsuir.byБелорусский государственный университет информатики и радиоэлектроникиBelarusian State University of Informatics and Radioelectronics2020220420201722535Copyright © Ма Ц., Цветков В.Ю., Конопелько В.К., 20202020Ма Ц., Цветков В.Ю., Конопелько В.К.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://inf.grid.by/jour/article/view/1051

Рассматривается задача скелетизации бинарных изображений. Скелетизация дает возможность представить бинарное изображение в виде множества тонких линий, взаимное расположение, размеры и форма которых адекватно описывают размеры, форму и ориентацию в пространстве соответствующих областей изображения. Высокое качество скелетов обеспечивают итерационные параллельные алгоритмы. Они могут реализовываться с использованием одной или нескольких подытераций. На каждой из них происходит удаление избыточных элементов, окрестности которых удовлетворяют определенным условиям. Для многих одноподытерационных алгоритмов характерно нарушение связности и формирование избыточных фрагментов скелета. Наиболее качественные скелеты формирует известный одноподытерационный алгоритм OPTA (One-Pass Thinning Algorithm), основанный на 18 бинарных масках, который, однако, чувствителен к контурному шуму и имеет высокую вычислительную сложность. Благодаря относительной простоте широкую известность получил двухподытерационный алгоритм Zhang – Suen (ZS), основанный на шести логических условиях, но он размывает диагональные линии толщиной 2 пиксела и удаляет области размером 2×2 пиксела. Оба алгоритма не обеспечивают достижение минимальной толщины линий скелета (многие неузловые элементы имеют более двух соседей). Для построения предельно тонких связанных скелетов бинарных изображений с низкой вычислительной сложностью предлагаются математическая модель и алгоритм OPCA (One-Pass Combination Algorithm) одноподытерационной скелетизации на основе комбинации и упрощения моделей одно- и двухподытерационной скелетизации. Данные модель и алгоритм позволяют повысить скорость скелетизации, восстановить исходное изображение по скелету, снизить избыточность связей элементов скелета.

This paper is focused on the field of the skeletonization of the binary image. Skeletonization makes it possible to represent a binary image in the form of many thin lines, the relative position, sizes and shape of which adequately describe the size, shape and orientation in space of the corresponding image areas. Skeletonization has many variety methods. Iterative parallel algorithms provide high quality skeletons. They can be implemented using one or more sub-iterations. In each iteration, redundant pixels, the neighborhoods of which meet certain conditions, are removed layer by layer along the contour and finally they leave only the skeleton. Many one-sub-iterations algorithms are characterized by a breakdown in connectivity and the formation of excess skeleton fragments. The highest-quality skeletons are formed by the well-known single-iteration OPTA algorithm, which based on 18 binary masks, but it is sensitive to contour noise and has a high computational complexity. The Zhang and Suen two-iteration algorithm (ZS), which is based on 6 logical conditions, is widely used due to its relative simplicity. But it suffers from the problem of the blurs of the diagonal lines with a thickness of 2 pixels and the lost of the square which size is 2×2 pixels. Besides, both algorithms mentioned above do not achieve the unit pixel thickness of the skeleton lines (many non-node pixels have more than two neighbors). Mathematical model and OPCA (One-Pass Combination Algorithm) algorithm which is based on a combination and simplification of single-iterative OPTA and two-iterative ZS are proposed for constructing extremely thin bound skeletons of binary images with low computational complexity. These model and algorithm also made it possible to accelerate the speed of skeletonization, to enhance recoverability of the original image on the skeleton and to reduce the redundancy of the bonds of the skeleton elements.

скелетизация изображенийалгоритм OPTAалгоритм Zhang – Suenодноподытерационная скелетизациядвухподытерационная скелетизацияimage skeletonizationalgorithm OPTAalgorithm Zhang – Suensingle-iteration skeletonizationdouble-iteration skeletonizationReferencesDinneen G. P. Programming pattern recognition. Western Joint Computer Conference, New York, 1–3 March 1955. New York, 1955, vol. 1, pp. 94–100.Dinneen G. P. Programming pattern recognition. Western Joint Computer Conference, New York, 1–3 March 1955. New York, 1955, vol. 1, pp. 94–100.Kirsch R. A, Cahn L., Ray C., Urban G. H. Experiments in processing pictorial information with a digital computer. Eastern Computer Conference, Washington, 9–13 December 1957. Washington, 1957, vol. 12, pp. 221–229.Kirsch R. A, Cahn L., Ray C., Urban G. H. Experiments in processing pictorial information with a digital computer. Eastern Computer Conference, Washington, 9–13 December 1957. Washington, 1957, vol. 12, pp. 221–229.Lam L., Lee S.-W., Suen C. Y. Thinning methodologies – a comprehensive survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, no. 9, pp. 869–885.Lam L., Lee S.-W., Suen C. Y. Thinning methodologies – a comprehensive survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, no. 9, pp. 869–885.Holt C., Stewart A., Clint C., Perrott R. An improved parallel thinning algorithm. Communication ACM, 1987, vol. 30, pp. 156–160.Holt C., Stewart A., Clint C., Perrott R. An improved parallel thinning algorithm. Communication ACM, 1987, vol. 30, pp. 156–160.Manzanera A., Bernard T., Preteux F., Longuet B. Ultra-fast skeleton based on an isotropic fully parallel algorithm. Discrete Geometry for Computer Imagery, 1999, vol. 1568, pp. 313–324.Manzanera A., Bernard T., Preteux F., Longuet B. Ultra-fast skeleton based on an isotropic fully parallel algorithm. Discrete Geometry for Computer Imagery, 1999, vol. 1568, pp. 313–324.Bernard T. M., Manzanera A. Improved low complexity fully parallel thinning algorithm. Proceedings 10th International Conference on Image Analysis and Processing, Venice, Italy, 27–29 September 1999. Venice, 1999, pp. 215–220.Bernard T. M., Manzanera A. Improved low complexity fully parallel thinning algorithm. Proceedings 10th International Conference on Image Analysis and Processing, Venice, Italy, 27–29 September 1999. Venice, 1999, pp. 215–220.Chen C.-S., Tsai W.-H. A new fast one-pass thinning algorithm and its parallel hardware implementation. Pattern Recognition Letters, 1990, vol. 11, pp. 471–477.Chen C.-S., Tsai W.-H. A new fast one-pass thinning algorithm and its parallel hardware implementation. Pattern Recognition Letters, 1990, vol. 11, pp. 471–477.Wu R.-Y., Tsai W.-H. A new one-pass parallel algorithm for binary images. Pattern Recognition Letters, 1992, vol. 13, pp. 715–723.Wu R.-Y., Tsai W.-H. A new one-pass parallel algorithm for binary images. Pattern Recognition Letters, 1992, vol. 13, pp. 715–723.Deng W., Lyengar S. S, Brener N. E. A fast parallel thinning algorithm for the binary image skeletonization. International Journal of High Performance Computing Applications, 2000, vol. 14, pp. 65–81.Deng W., Lyengar S. S, Brener N. E. A fast parallel thinning algorithm for the binary image skeletonization. International Journal of High Performance Computing Applications, 2000, vol. 14, pp. 65–81.Stefanelli R., Rosenfeld A. Some parallel thinning algorithms for digital pictures. Journal of the ACM, 1971, vol. 18, pp. 255–264.Stefanelli R., Rosenfeld A. Some parallel thinning algorithms for digital pictures. Journal of the ACM, 1971, vol. 18, pp. 255–264.Chin R. T., Wan H. K., Stover D. L., Iverson R. D. A one-pass thinning algorithm and its parallel implementation. Computer Vision, Graphics, and Image Processing, 1987, vol. 40, pp. 30–40.Chin R. T., Wan H. K., Stover D. L., Iverson R. D. A one-pass thinning algorithm and its parallel implementation. Computer Vision, Graphics, and Image Processing, 1987, vol. 40, pp. 30–40.Harous, S., Elnagar A. Handwritten character-based parallel thinning algorithms: a comparative study. University of Sharjah Journal of Pure & Applied Sciences, 2009, vol. 6, no. 1, pp. 81–101.Harous, S., Elnagar A. Handwritten character-based parallel thinning algorithms: a comparative study. University of Sharjah Journal of Pure & Applied Sciences, 2009, vol. 6, no. 1, pp. 81–101.Zhang T. Y., Suen C. Y. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 1984, vol. 27, no. 3, pp. 236–239.Zhang T. Y., Suen C. Y. A fast parallel algorithm for thinning digital patterns. Communications of the ACM, 1984, vol. 27, no. 3, pp. 236–239.Lu H. E., Wang P. S. P. A comment on "a fast parallel algorithm for thinning digital patterns". Communications of the ACM, 1986, vol. 29, no. 3, pp. 239–242.Lu H. E., Wang P. S. P. A comment on "a fast parallel algorithm for thinning digital patterns". Communications of the ACM, 1986, vol. 29, no. 3, pp. 239–242.Abdulla W. H., Saleh A. O. M., Morad A. H. A preprocessing algorithm for handwritten character recognition. Pattern Recognition Letters, 1988, vol. 7, no. 1, pp. 13–18.Abdulla W. H., Saleh A. O. M., Morad A. H. A preprocessing algorithm for handwritten character recognition. Pattern Recognition Letters, 1988, vol. 7, no. 1, pp. 13–18.Sossa J. H. An improved parallel algorithm for thinning digital patterns. Pattern Recognition Letters, 1989, vol. 10, pp. 77–80.Sossa J. H. An improved parallel algorithm for thinning digital patterns. Pattern Recognition Letters, 1989, vol. 10, pp. 77–80.Guo Z., Hall R. W. Parallel thinning with two-subiteration algorithms. Communications of the ACM, 1989, vol. 32, no. 3, pp. 359–373.Guo Z., Hall R. W. Parallel thinning with two-subiteration algorithms. Communications of the ACM, 1989, vol. 32, no. 3, pp. 359–373.Guo Z., Hall R. W. Fast fully parallel thinning algorithms. CVGIP: Image Understanding, 1992, vol. 55, no. 3, pp. 317–328.Guo Z., Hall R. W. Fast fully parallel thinning algorithms. CVGIP: Image Understanding, 1992, vol. 55, no. 3, pp. 317–328.Zhang Y. Y., Wang P. P. A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons. International Conference on Pattern Recognition, Vienna, Austria, 25–29 August 1996. Vienna, 1996, vol. 4, pp. 457–461.Zhang Y. Y., Wang P. P. A parallel thinning algorithm with two-subiteration that generates one-pixel-wide skeletons. International Conference on Pattern Recognition, Vienna, Austria, 25–29 August 1996. Vienna, 1996, vol. 4, pp. 457–461.Kundu M. K., Chaudhuri B. B., Majumder D. D. A parallel graytone thinning algorithm (PGTA). Pattern Recognition Letters, 1991, vol. 12, no. 8, pp. 491–494.Kundu M. K., Chaudhuri B. B., Majumder D. D. A parallel graytone thinning algorithm (PGTA). Pattern Recognition Letters, 1991, vol. 12, no. 8, pp. 491–494.Kwon J.-S., Gi J.-W., Kang E.-K. An enhanced thinning algorithm using parallel processing. Proceeding of the International Conference on Image Processing, Thessaloniki, Greece, 7–10 October 2001. Thessaloniki, 2001, pp. 752–755.Kwon J.-S., Gi J.-W., Kang E.-K. An enhanced thinning algorithm using parallel processing. Proceeding of the International Conference on Image Processing, Thessaloniki, Greece, 7–10 October 2001. Thessaloniki, 2001, pp. 752–755.Jang B. K., Chin R. T. One-pass parallel: analysis, properties, and quantitative evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, pp. 1129–1140.Jang B. K., Chin R. T. One-pass parallel: analysis, properties, and quantitative evaluation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1992, vol. 14, pp. 1129–1140.Boudaoud L. B., Sider A., Tari A. A new thinning algorithm for binary images. 3rd International Conference on Control, Engineering & Information Technology, Tlemcen, Algeria, 25–27 May 2015. Tlemcen, 2015, pp. 1–6.Boudaoud L. B., Sider A., Tari A. A new thinning algorithm for binary images. 3rd International Conference on Control, Engineering & Information Technology, Tlemcen, Algeria, 25–27 May 2015. Tlemcen, 2015, pp. 1–6.Sebastian T. B., Klein P. N., Kimia B. B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, vol. 26, no. 5, pp. 550–571.Sebastian T. B., Klein P. N., Kimia B. B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, vol. 26, no. 5, pp. 550–571.

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