izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2023-27-1-126-139izvestswsu-1094Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentРекурсивный алгоритм закрашивания областей распознанных объектовThe Recursive Algorithm for Filling Areas of Recognized Objectshttps://orcid.org/0000-0002-5400-6817БобырьМ. В.BobyrM. V.

Бобырь Максим Владимирович, доктор технических наук, профессор кафедры вычислительной техники

Researcher ID: G-2604-2013 

ул. 50 лет Октября, д. 94, г. Курск 305040, Российская Федерация 

Maxim V. Bobyr, Dr. of Sci. (Engineering), Associate Professor of the Computer Engineering Department

Researcher ID: G-2604-2013 

 50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation 

maxbobyr@gmail.comhttps://orcid.org/0000-0001-7947-1427ХраповаН. И.KhrapovaN. I.

Храпова Наталия Игоревна, аспирант

ул. 50 лет Октября, д. 94, г. Курск 305040, Российская Федерация 

 Natalia I. Khrapova, Post-Graduate Student 

 50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation 

KhrapovaNI@yandex.ruhttps://orcid.org/0000-0002-8371-6543СупруноваО. Г.SuprunovaO. G.

Супрунова Ольга Геннадьевна, аспирант

 ул. 50 лет Октября, д. 94, г. Курск 305040, Российская Федерация 

Olga G. Suprunova, Post-Graduate Student 

 50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation 

Dlya.dela2010@yandex.ruhttps://orcid.org/0000-0003-0292-3127ДородныхА. А.DorodnykhA. A.

Дородных Александр Алексеевич, аспирант

 ул. 50 лет Октября, д. 94, г. Курск 305040, Российская Федерация 

Alexander A. Dorodnykh, Post-Graduate Student 

 50 Let Oktyabrya str. 94, Kursk 305040, Russian Federation 

alex.dorodnych@mail.ruЮго-Западный государственный университетSouthwest State University202304042023271126139Copyright © Бобырь М.В., Храпова Н.И., Супрунова О.Г., Дородных А.А., 20232023Бобырь М.В., Храпова Н.И., Супрунова О.Г., Дородных А.А.Bobyr M.V., Khrapova N.I., Suprunova O.G., Dorodnykh A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvestswsu.elpub.ru/jour/article/view/1094

Цель исследования. Разработка рекурсивного алгоритма закрашивания распознанных областей на бинаризованном изображении и выделение контуров цветовой метки с целью нахождения минимального времени подсчета количества закрашенных пикселей в распознанной метке.Методы. Алгоритм закрашивания областей основывается на рекурсивном методе. Алгоритм начинает работу с центральной точки изображения и анализирует наличие незакрашенных пикселей в смежных ячейках. Рассматривается восемь направлений обхода пикселей относительно начальной точки с целью определения наименьшего времени закрашивания распознанной области. Обход осуществляется в следующих направлениях: восток-юг-запад-север; восток-север-запад-юг; юг-восток-север-запад; юг-запад-север-восток; запад-юг-восток-север; запад-север-восток-юг; север-восток-юг-запад; север-запад-юг-восток. Алгоритм содержит несколько этапов: проверка выхода из рекурсии при условии закрашивания всех областей, закрашивание исходной ячейки, закрашивание элементов по четырем направлениям от начальной точки, подсчет количества закрашенных элементов.Результаты. Разработан рекурсивный алгоритм закрашивания распознанных областей на бинаризованном изображении, с возможностью выделения контуров распознанной метки. Определено направление оптимального обхода, который имеет наименьшее время по отношению к другим рассматриваемым направлениям. Тестирование осуществлялось для циклов с 10, 50 и 100 итерациями. По представленному алгоритму создана специализированная программная модель. Номер свидетельства о государственной регистрации программы для ЭВМ «Программа для заливки распознанной метки» – 2023612631.Заключение. Результаты экспериментальных исследований показали, что для значения цикла в 10 итераций наилучшее время закрашивания области равно 12762 мс, для значения цикла в 50 итераций наилучшее время равно 76008 мс, для значения цикла в 100 итераций наилучшее время равно160568 мс. Минимальное среднее время выполнения операции по закрашиванию составило 84357 мс, следовательно, наилучшей из восьми комбинаций прохода оказалось направление – север-восток-юг-запад.

Purpose of research. The recursive algorithm for painting recognized areas on a binarized image and extracting the contours of a color mark, in order to find the minimum time for counting the number of filled pixels in a recognized mark, was developed in the article.Methods. The region filling algorithm in the image is based on the recursive method. The algorithm begins the work from the central point of the image and analyzes the presence of unshaded pixels in adjacent cells. In the article is considered the definition of the shortest time for filling the recognized area in eight directions: east-south-west-north, east-north-west-south, southeast-northwest, southwest-northeast, west-south-east-north, west-north-east-south, north-east-south-west, north west south east. The algorithm contains several stages: checking the exit from the recursion provided that all areas are filled, filling the initial cell, filling the elements in four directions from the starting point, counting the number of filled elements.Results. A recursive algorithm for filling recognized areas on a binarized image with the possibility of highlighting the contours of a recognized mark has been developed. The direction of the optimal bypass, which has the shortest time in relation to other considered directions, is determined. The testing was carried out for cycles with 10, 50 and 100 iterations. According to the presented algorithm, a specialized software model was created. The number of the certificate of state registration of the computer program "Program for filling a recognized mark" is 2023612631.Conclusion. The results of experimental studies showed that for a cycle value of 10 iterations, the best time to fill the area is 12762 msec, for a cycle value of 50 iterations, the best time is 76008 msec, for a cycle value of 100 iterations, the best time is 160568 msec. The minimum average time to complete the filling operation was 84357 msec, therefore, the best of the eight pass combinations turned out to be the direction - north-east-south-west.

рекурсивный алгоритмзакрашивание областейраспознавание меткинаправления обходабыстродействиеrecursive algorithmregion fillingmark recognitionbypass directionsperformanceРабота выполнена при поддержке гранта РНФ 23-21-00071 – «Разработка модели компьютерного зрения для интеллектуальной навигации робототехнических систем, основанной на построении трехмерных сцен по картам глубин».The work was supported by the grant of the Russian Science Foundation 23-21-00071 – "Development of a computer vision model for intelligent navigation of robotic systems based on the construction of three-dimensional scenes based on depth maps".ReferencesБобырь М. В., Архипов А. Е., Якушев А. С. Распознавание оттенка цветовой метки на основе нечёткой кластеризации // Информатика и автоматизация. 2021. № 20(2). С. 407-434.Bobyr M. V., Arkhipov A. E., Yakushev A. S. Raspoznavanie ottenka tsvetovoi metki na osnove nechetkoi klasterizatsii [Recognition of the shade of a color label based on fuzzy clustering]. Informatika i avtomatizatsiya = Computer Science and Automation, 2021, no. 20(2), pp. 407-434.Аврашков П. П., Коськин Н. А., Константинов И. С. Оценка эффективности различных моделей конвертации изображений в стереоформат с помощью карт глубины // Научно-технический вестник Поволжья. 2020. № 12. С. 165-168.Avrashkov P. P., Koskin N. A., Konstantinov I. S. Otsenka effektivnosti razlichnykh modelei konvertatsii izobrazhenii v stereoformat s pomoshch'yu kart glubiny [Evaluation of the effectiveness of various models for converting images to stereo format using depth maps]. Nauchno-tekhnicheskii vestnik Povolzh'ya = Scientific and Technical Volga Region Bulletin, 2020, no. 12, pp. 165-168.Гайворонский В. А. Подход к созданию объемного панорамного изображения на основе пассивных методов определения карт глубины // Информационные системы и технологии. 2022. № 1(129). С. 24-29.Gaivoronsky V. A. Podkhod k sozdaniyu ob"emnogo panoramnogo izobrazheniya na osnove passivnykh metodov opredeleniya kart glubiny [An approach to creating a three-dimensional panoramic image based on passive methods for determining depth maps]. Informatsionnye sistemy i tekhnologii = Information Systems and Technologies, 2022, no. 1 (129), pp. 24-29.Бобырь М. В., Храпова Н. И., Ламонов М. А. Система управления интеллектуальным светофором на основе нечеткой логики // Известия Юго-Западного государственного университета. 2021; 25(4): 162-176. https://doi.org/10.21869/2223-1560-2021-25-4-162-176Bobyr M.V., Khrapova N. I., Lamonov M. A. Smart Traffic Light Control System Based on Fuzzy Logic. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2021; 25(4): 162-176 (In Russ.). https://doi.org/10.21869/2223-1560-2021-25-4-162-176.Bobyr M. V., Emelyanov S. G. A nonlinear method of learning neuro-fuzzy models for dynamic control systems. 2020. Vol. 88. P. 106030. DOI 10.1016/j.asoc.2019.106030.Bobyr M. V., Emelyanov S. G. A nonlinear method of learning neuro-fuzzy models for dynamic control systems, 2020, vol. 88, 106030 p.Bobyr M. V., Yakushev A. S., Dorodnykh A. A. Fuzzy devices for cooling the cutting tool of the CNC machine implemented on FPGA // Measurement. 2020. Vol. 152. P. 107378. DOI 10.1016/j.measurement.2019.107378.Bobyr M. V., Yakushev A. S., Dorodnykh A. A. Fuzzy devices for cooling the cutting tool of the CNC machine implemented on FPGA. Measurement, 2020, vol. 152, 107378 p.Обнаружение опухоли мозга на основе МРТ с применением метода нечеткой кластеризации с-средних / А. Г. Зотин, Ю. А. Хамад, С. В. Кириллова [и др.] // Медицина и высокие технологии. 2018. № 1. С. 20-28.Zotin, A. G., Khamad Yu. A., Kirillova S. V. [et al.] Obnaruzhenie opukholi mozga na osnove MRT s primeneniem metoda nechetkoi klasterizatsii s-srednikh [Detection of a brain tumor based on MRI using the method of fuzzy c-means clustering]. Meditsina i vysokie tekhnologii = Medicine and High Technologies, 2018, no. 1, pp. 20-28.Смольникова У. А., Ушков А. Д. Опыт оценки цифровых рентгенограмм с применением системы автоматического распознавания изменений в легких // Лучевая диагностика и терапия. 2020. № S1. С. 84.Smolnikova U.A., Ushkov A.D., Ushkov A.D. Opyt otsenki tsifrovykh rentgenogramm s primeneniem sistemy avtomaticheskogo raspoznavaniya izmenenii v legkikh [Experience in evaluating digital radiographs using a system for automatic recognition of changes in the lungs]. Luchevaya diagnostika i terapiya = Radiation Diagnostics and Therapy, 2020, no. S1, pp. 84.Улучшение сегментации патологий легких и плеврального выпота на КТ-снимках пациентов с Covid-19 / Д. С. Лащенова, А. М. Громов, А. С. Конушин, А. М. Мещерякова // Программирование. 2021. № 4. С. 56-62.Laschenova D. S., Gromov A. M., Konushin A. S., Meshcheryakova A. M. Uluchshenie segmentatsii patologii legkikh i plevral'nogo vypota na KT-snimkakh patsientov s Covid-19 [Improvement of segmentation of lung pathologies and pleural effusion on CT images of patients with Covid-19]. Programmirovanie = Programming, 2021, no. 4, pp. 56-62.Алгоритмы предобработки и постобработки данных для биометрических систем распознавания лиц / В. С. Горбацевич, Ю. В. Визильтер, С. Ю. Желтов, С. А. Хаин // Вестник компьютерных и информационных технологий. 2014. № 6(120). С. 9-14.Gorbatsevich V. S., Vizilter V. V., Zheltov S. Yu., Khain S. A. Algoritmy predobrabotki i postobrabotki dannykh dlya biometricheskikh sistem raspoznavaniya lits [Algorithms for pre-processing and post-processing of data for biometric face recognition systems]. Vestnik komp'yuternykh i informatsionnykh tekhnologii = Bulletin of Computer and Information Technologies, 2014, no. 6 (120), pp. 9-14.Мельников Б. Ф., Чурикова Н. П. Алгоритмы сравнительного исследования двух инвариантов графа // Современные информационные технологии и ИТ-образование. 2019. Т.15, №1. С. 45-51.Melnikov B. F., Churikova N. P. Algoritmy sravnitel'nogo issledovaniya dvukh invariantov grafa [Algorithms for a comparative study of two graph invariants]. Sovremennye informatsionnye tekhnologii i IT-obrazovanie = Modern information technologies and IT education, 2019, vol.15, no. 1, pp. 45-51.Хачумов М. В., Талалаев А. А., Хачумов В. М. Об одном эвристическом критерии в задаче определения изоморфизма графов на основе инвариантов // Современные наукоемкие технологии. 2022. № 2. С. 159-163.Khachumov M. V., Talalaev A. A., Khachumov V. M. Ob odnom evristicheskom kriterii v zadache opredeleniya izomorfizma grafov na osnove invariantov [On one heuristic criterion in the problem of determining the isomorphism of graphs based on invariants]. Sovremennye naukoemkie tekhnologii = Modern Science-intensive Technologies, 2022, no. 2, pp. 159-163.Галкин В. А., Арьков К. А. Автоматизированная система визуализации алгоритма Дейкстры на графах // Естественные и технические науки. 2019. № 6(132). С. 190-192.Galkin V. A., Arkov K. A. Avtomatizirovannaya sistema vizualizatsii algoritma Deikstry na grafakh [Automated visualization system for Dijkstra's algorithm on graphs]. Estestvennye i tekhnicheskie nauki = Natural and Technical Sciences, 2019, no. 6 (132), pp. 190-192.Ковалев А. В., Бакуменко А. Н. Алгоритм маркировки связанных областей при потоковой обработке изображения // Инженерный вестник Дона. 2022. № 4(88). С. 191-201. EDN NTTPYR.Kovalev A. V., Bakumenko A. N. Algoritm markirovki svyazannykh oblastei pri potokovoi obrabotke izobrazheniya [Algorithm for labeling related areas in streaming image processing]. Inzhenernyi vestnik Dona = Engineering Bulletin of the Don, 2022, no. 4 (88), pp. 191-201.Емельянов С. Г., Бобырь М. В., Крюков А. Г. Исследование свойств алгоритма поиска в ширину для нахождения маршрута передвижения роботов // Известия Юго-Западного государственного университета. 2022; 26(4): 39-56. https://doi.org/10.21869/2223-1560-2022-26-4-39-56.Emelianov S. G., Bobyr M. V., Kryukov A. G. Research of the Properties of the Breadth-First Search Algorithm for Finding the Movement Route of Robots. Izvestiya YugoZapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2022; 26(4): 39-56 (In Russ.). https://doi.org/ 10.21869/2223-1560-2022-26-4-39-56.Метод распределения нагрузки в GPU-реализации алгоритма поиска в ширину на графе / М. А. Черноскутов, Д. Г. Ермаков, М. Л. Гольдштейн, Д. А. Усталов // Научно-технический вестник Поволжья. 2014. № 2. С. 229-232. EDN SAYCFZ.Chernoskutov M. A., Ermakov D. G., Goldshtein M. L., Ustalov D. A. Metod raspredeleniya nagruzki v GPU-realizatsii algoritma poiska v shirinu na grafe [Load distribution method in GPU-implementation of breadth-first search algorithm]. Nauchnotekhnicheskii vestnik Povolzh'ya = Scientific and Technical Volga Region Bulletin, 2014, no. 2, pp. 229-232.Зуенко А. А. Интеграция методов поиска в ширину и логического вывода для удовлетворения табличных ограничений // Онтология проектирования. 2021. Т. 11, № 4(42). С. 521-532. DOI 10.18287/2223-9537-2021-11-4-521-532.Zuenko A. A. Integratsiya metodov poiska v shirinu i logicheskogo vyvoda dlya udovletvoreniya tablichnykh ogranichenii [Integration of Breadth-First Search and Inference Methods to Satisfy Table Constraints]. Ontologiya proektirovaniya = Design Ontology, 2021, vol. 11, no. 4 (42), pp. 521-532.Компьютерная реализация поиска в глубину / Е. А. Пронина, А. А. Лебединская, П. Г. Шурхаленко // Мировая наука. 2018. № 11(20). С. 234-237.Pronina E. A., Lebedinskaya A. A., Shurkhalenko P. G. Komp'yuternaya realizatsiya poiska v glubinu [Computer implementation of depth-first search]. Mirovaya Nauka = World Science, 2018, no. 11(20), pp. 234-237.Будникова И. К., Бабкин Т. А. Интеллектуальный анализ данных на основе инструментария алгоритма C&RT (Общие деревья) // Информационные технологии в строительных, социальных и экономических системах. 2021. № 1(23). С. 112-115.Budnikova I. K., Babkin T. A. Intellektual'nyi analiz dannykh na osnove instrumentariya algoritma C&RT (Obshchie derev'ya) [Data mining based on the tools of the C&RT algorithm (General Trees)]. Informatsionnye tekhnologii v stroitel'nykh, sotsial'nykh i ekonomicheskikh sistemakh = Information Technologies in Construction, Social and Economic systems, 2021, no. 1 (23), pp. 112-115.Мельников Б. Ф., Дудников В. А. О задаче псевдооптимального размещения графа на плоскости и эвристиках для её решения // Информатизация и связь. 2018. № 1. С. 63-70.Melnikov B.F., Dudnikov V.A. O zadache psevdooptimal'nogo razmeshcheniya grafa na ploskosti i evristikakh dlya ee resheniya [On the problem of pseudo-optimal placement of a graph on a plane and heuristics for its solution]. Informatizatsiya i svyaz' = Informatization and Communication, 2018, no. 1, pp. 63-70.Alzakki H. M., Tsvetkov V. Yu. Selection texture regions on the image based on classification assessment density of contour elements // Big Data and Advanced Analytics. 2017. No. 3. P. 113-118.Alzakki H. M., Tsvetkov V. Yu. Selection texture regions on the image based on classification assessment density of contour elements. Big Data and Advanced Analytics, 2017, no. 3, pp. 113-118.Свидетельство о государственной регистрации программы для ЭВМ № 2023612631 Российская Федерация. Программа для заливки распознанной метки: № 2023610839: заявл. 23.01.2023: опубл. 06.02.2023 / М. В. Бобырь, Н. И. Храпова, О. Г. Супрунова; заявитель Федеральное государственное бюджетное образовательное учреждение высшего образования "Юго-Западный государственный университет".Bobyr'M. V., Khrapova N. I., Suprunova O. G. Programma dlya zalivki raspoznannoi metki № 2023610839 [Program for filling recognized label. No. 2023610839]. Certificate of state registration of the computer program RF. 2023.

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