izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2020-24-1-144-158izvestswsu-728Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentАлгоритм сегментации изображений на основе персистентной гомологии для решения задач поиска дефектовAn Algorithm of Image Segmentation Based on Persistent Homology for Solving Defects Searching ProblemsЕремеевС. В.EremeevS. V.

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

ул. Орловская 23, г. Муром 602264

Sergey V. Eremeev, Cand. of Sci. (Engineering), Associate Professor, Department of Information Systems

23 Orlovskaya str., Murom 602264

sv-eremeev@yandex.ruРомановС. А.RomanovS. A.

Романов Семен Алексеевич, магистр информационных систем, старший разработчик

пр. Нариманова 1, г. Ульяновск 432001

Semyon А. Romanov, Master of Information Systems, Senior Developer

1 Narimanova av., Ulyanovsk 432001

cwwc@bk.ruМуромский институт ФГБОУ ВО Владимирского государственного университета им. А. Г. и Н. Г. СтолетовыхMurom Institute (branch) of Vladimir State University named after A.G. and N.G. StoletovsООО «СимбирСофт»SimbirSoft LLC202023062020241144158Copyright © Еремеев С.В., Романов С.А., 20202020Еремеев С.В., Романов С.А.Eremeev S.V., Romanov S.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/728

Целью исследования является разработка алгоритма сегментации изображений на основе персистентной гомологии для решения задач поиска и классификации дефектов. Алгоритм направлен на повышение качества производимой продукции на предприятиях с непрерывным производством (металлургия, деревообрабатывающая промышленность и другие).

Методы

Методы. Для сегментации изображения предлагается установить связи между пикселями изображения. В дальнейшем, в процессе итерационного разрыва связей по мере увеличения их весов пиксели будут объединяться в группы, называемые дырами. Пиксели, объединенные в единую группу, имеют как свои первоначальные характеристики, так и общие характеристики для всей группы, а также изменяют веса своих связей с представителями других групп. Таким образом, образуется история формирования отдельных групп пикселей, которые можно обозначить в виде сегментов с временной характеристикой изменения.

Результаты

Результаты. Итогом проведенного исследования является разработка алгоритма, предназначенного для поиска и классификации дефектов различных материалов. Разработан оптимальный алгоритм применения принципа персистентной гомологии к изображениям, проанализированы и выбраны факторы, определяющие переходные границы объектов изображения. Алгоритм сегментации опробован на изображениях металла, полученных с листопрокатного оборудования. Показаны результаты сравнения работы предложенного алгоритма с алгоритмами сегментации k-means и Mean-Shift при различных параметрах.

Заключение

Заключение. Применение персистентной гомологии в задачах сегментации изображений может позволить создать инструмент, применимый к материалам с различной структурой без необходимости существенных изменений. Программная реализация процесса сегментации на основе применения принципов компьютерной топологии показала высокую гибкость благодаря сохранению истории изменения сегментов.

Purpose of research is to develop an image segmentation algorithm based on the persistent homology for solving problems of searching and classifying defects. The algorithm is aimed at improving the quality of products at enterprises with continuous production (metallurgy, woodworking, and others).

Methods

Methods. To segment an image, it is proposed to specify links between pixels in the image. In the future, during the iterative breaking of links, as their weights increase, pixels will be combined into groups called holes. Pixels that are in a single group have both their original characteristics and characteristics common for the entire group, and they also change the weights of their links with representatives of other groups. This creates a history of the formation of separate groups of pixels which can be specified as segments with a time-based characteristic of the change.

Results

Results. The result of the research is the development of an algorithm designed to search for and classify defects in various materials. The optimal algorithm for applying the principle of persistent homology to images has been developed, and factors determining the transition boundaries of image objects have been analyzed and selected. The segmentation algorithm was tested on metal images obtained from sheet rolling equipment. The results of comparing the proposed algorithm with the K-means and Mean-Shift segmentation algorithms for different parameters are provided in the article.

Conclusion

Conclusion. Using persistent homology in image segmentation tasks can enable creating a tool that can be applied to materials with different structures without any need for significant changes. The software implementation of the segmentation process based on the principles of computer topology has shown high flexibility due to the storing of the history of segment changes.

дефектоскопияперсистентные гомологиисегментациякомпьютерная топологияdefect detectionpersistent homologysegmentationcomputer topologyReferencesИлющенко А. В. Анализ методов обработки изображений пиломатериалов, имеющих пороки и дефекты // Известия Санкт-Петербургской лесотехнической академии. 2017. № 218. С. 153–163.Ilyushchenko A. V. Analiz metodov obrabotki izobrazhenij pilomaterialov, imeyushchih poroki i defekty [Analysis of methods for processing images of lumber with flaws and defects]. Izvestiya Sankt-Peterburgskoj lesotekhnicheskoj akademii = Izvestia of the St. Petersburg Academy of Forestry Engineering, 2017, no. 218, pp. 153–163 (in Russ.).Цапаев А. П., Кретинин О. В. Методы сегментации изображений в задачах обнаружения дефектов поверхности // Компьютерная оптика. 2012. № 36(3). С. 448–452.Capaev A. P., Kretinin O. V. Metody segmentacii izobrazhenij v zadachah obnaruzheniya defektov poverhnosti [Image segmentation methods in problems of surface defect detection]. Komp'yuternaya optika = Computer Optics, 2012, vol. 36, no. 3, pp. 448–452 (in Russ.).Badrinarayanan V., Kendall A., Cipolla R. A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2017. Vol. 39. P. 2481–2495.Badrinarayanan V., Kendall A., Cipolla R. A Deep Convolutional Encoder-Decoder Architecture for Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017, vol. 39, pp. 2481–2495.Learning Video Object Segmentation from Static Images / F. Perazzi, A. Khoreva, R. Benenson, B. Schiele, A. Sorkine-Hornung // IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2017. P. 2663–2672.Perazzi F., Khoreva A., Benenson R, Schiele B., Sorkine-Hornung A. Learning Video Object Segmentation from Static Images. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017, pp. 2663–2672.Panoptic Segmentation / A. Kirillov, K. He, R. Girshick, C. Rother, P. Dollar // The IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2019. P. 94049413.Kirillov A., He K., Girshick R., Rother C., Dollar P. Panoptic Segmentation. The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019, pp. 9404–9413.A multi-scale 3D Otsu thresholding algorithm for medical image segmentation / Y. Feng, H. Zhao, X. Li, X. Zhang, H. Li // Digital Signal Processing. 2017. Vol. 60. P. 186–199.Feng Y., Zhao H., Li X., Zhang X, Li H. A multi-scale 3D Otsu thresholding algorithm for medical image segmentation. Digital Signal Processing, 2017, vol. 60, pp. 186–199.Head and neck target delineation using a novel PET automatic segmentation algorithm / B. Berthon, M. Evans, C. Marshall, N. Palaniappan, N. Cole, V. Jayaprakasam, T. Rackley, E. Spezi // Radiotherapy and Oncology. 2017. Vol. 122. P. 242–247.Berthon B., Evans M., Marshall C., Palaniappan N., Cole N., Jayaprakasam V., Rackley T., Spezi E. Head and neck target delineation using a novel PET automatic segmentation algorithm. Radiotherapy and Oncology, 2017, vol. 122, pp. 242–247.Real-Time Superpixel Segmentation by DBSCAN Clustering Algorithm / J. Shen, X. Hao, Z. Liang, Y. Liu, W. Wang, L. Shao // IEEE Transactions on Image Processing. 2016. Vol. 25. P. 5933–5942.Shen J., Hao X., Liang Z., Liu Y., Wang W., Shao L. Real-Time Superpixel Segmentation by DBSCAN Clustering Algorithm. IEEE Transactions on Image Processing, 2016, vol. 25, pp. 5933–5942.Еремеев С.В., Андрианов Д.Е., Титов В.С. Алгоритм совмещения пространственных объектов разномасштабных карт на основе топологического анализа данных // Компьютерная оптика. 2019. № 43(6). С. 1021–1029.Eremeev S.V., Andrianov D.E., Titov V.S. Algoritm sovmeshcheniya prostranstvennyh ob"ektov raznomasshtabnyh kart na osnove topologicheskogo analiza dannyh [An algorithm for matching spatial objects of different-scale maps based on topological data analysis]. Komp'yuternaya optika = Computer Optics, 2019, vol. 43, no. 6, pp. 1021–1029 (in Russ.).Андрианов Д. Е., Еремеев С. В., Купцов К. В. Алгоритм семантической классификации пространственных объектов и сцен с использованием топологических признаков и классификатора random forest на многомасштабных картах // Прикаспийский журнал: управление и высокие технологии. 2018. № 4. С. 8–18.Andrianov D. E., Eremeev S. V., Kuptsov K. V. Algoritm semanticheskoj klassifikacii prostranstvennyh ob"ektov i scen s ispol'zovaniem topologicheskih priznakov i klassifikatora random forest na mnogomasshtabnyh kartah [Algorithm of semantic classification of spatial objects and scenes using topological features and random forest classifier on multiscale maps]. Prikaspijskij zhurnal: upravlenie i vysokie tekhnologii = Caspian Sea Journal: Management and High Technology, 2018, no. 4, pp. 8–18 (in Russ.).Eremeev S., Seltsova E. Algorithms for Topological Analysis of Spatial Data // Advances in Intelligent Systems and Computing. 2020. Vol. 902. P. 81 – 92.Eremeev S., Seltsova E. Algorithms for Topological Analysis of Spatial Data. Advances in Intelligent Systems and Computing, 2020, vol. 902, pp. 81–92.Еремеев С.В., Сельцова Е.А. Алгоритм топологического анализа пространственных структур в геоинформационных системах // Алгоритмы, методы и системы обработки данных. 2017. № 1. С. 16–27.Eremeev S.V., Seltsova E.A. Algoritm topologicheskogo analiza prostranstvennyh struktur v geoinformacionnyh sistemah [Algorithm of topological analysis of spatial structures in geographic information systems]. Algoritmy, metody i sistemy obrabotki dannyh = Algorithms, methods, and data processing systems , 2017, no. 1, pp. 16–27 (in Russ.).Edelsbrunner H., Harer J. Computational topology. An introduction. AMS, Providence. 2010.Edelsbrunner H., Harer J. Computational topology. An introduction. AMS, Providence, 2010.Kurlin V. A fast persistence-based segmentation of noisy 2d clouds with provable guarantees // Pattern Recognition Letters. 2016. Vol. 83. P. 3–12.Kurlin V. A fast persistence-based segmentation of noisy 2d clouds with provable guarantees. Pattern Recognition Letters, 2016, vol. 83, pp. 3–12.Распознавание текстур на цифровых изображениях методами вычислительной топологии / Н.Г. Макаренко, Ф.А. Уртьев, И.С. Князева, Д.Б. Малкова, И.Т. Пак, Л.М. Каримова // Современные проблемы дистанционного зондирования Земли из космоса. 2015. № 12(1). С. 131-144.Makarenko N.G., Urtev F.A., Knyazeva I.S., Malkova D.B., Pak I.T., Karimova L.M. Raspoznavanie tekstur na cifrovyh izobrazheniyah metodami vychislitel'noj topologii [Recognition of textures in digital images using computational topology methods]. Sovremennye problemy distancionnogo zondirovaniya Zemli iz kosmosa = Current problems of remote sensing of the Earth from space, 2015, vol. 12, no. 1, pp. 131–144 (in Russ.).Eremeev S., Kuptsov K., Romanov S. An approach to establishing the correspondence of spatial objects on heterogeneous maps based on methods of computational topology // Lecture Notes in Computer Science. 2018. Vol. 10716. P. 172–182.Eremeev S., Kuptsov K., Romanov S. An approach to establishing the correspondence of spatial objects on heterogeneous maps based on methods of computational topology. Lecture Notes in Computer Science, 2018, vol. 10716, pp. 172–182.Алгоритм идентификации пространственных объектов растровой карты на основе топологического анализа данных / С.В. Еремеев, Д.Е. Андрианов, К.В. Купцов, Ю.А. Ковалев // Телекоммуникации. 2017. № 7. С. 39–44.Eremeev S.V., Andrianov D.E., Kuptsov K.V., Kovalev Y.A. Algoritm identifikacii prostranstvennyh ob"ektov rastrovoj karty na osnove topologicheskogo analiza dannyh [Algorithm for identification of spatial objects in a raster map based on topological data analysis]. Telekommunikacii = Telecommunications, 2017, no. 7, pp. 39–44 (in Russ.).Room segmentation: Survey, implementation, and analysis / R. Bormann, F. Jordan, W. Li, J. Hampp, M Hägele // IEEE International Conference on Robotics and Automation (ICRA). 2016. P. 1018–1026.Bormann R., Jordan F., Li W., Hampp J., Hägele M. Room segmentation: Survey, implementation, and analysis. IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 1018–1026.El-Khatib S., Skobtsov Y., Rodzin S. Theoretical and Experimental Evaluation of Hybrid ACO-k-means Image Segmentation Algorithm for MRI Images Using Drift-analysis // Procedia Computer Science. 2019. Vol. 150. P. 324–332.El-Khatib S., Skobtsov Y., Rodzin S. Theoretical and Experimental Evaluation of Hybrid ACO-k-means Image Segmentation Algorithm for MRI Images Using Drift-analysis. Procedia Computer Science, 2019, vol. 150, pp. 324–332.Kavzoglu T., Tonbul H. A comparative study of segmentation quality for multiresolution segmentation and watershed transform // 8th International Conference on Recent Advances in Space Technologies (RAST). 2017. P. 113–117.Kavzoglu T., Tonbul H. A comparative study of segmentation quality for multiresolution segmentation and watershed transform. 8th International Conference on Recent Advances in Space Technologies (RAST), 2017, pp. 113–117.

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