Журнал «Труды Института системного анализа Российской академии наук» - М.С. Мехова, П.В. Безматерных "Формализм структурных преобразований изображений и методы их оптимизации"

Низкоуровневые методы обработки и преобразований изображений имеют фундаментальное значение для множества прикладных задач в совершенно различных областях. Частные вопросы их оптимизации рассмотрены в многочисленных технических и научных публикациях, однако общий подход к ним в литературе представлен явно неполно. В статье представлен новый формализм – структурное преобразование изображений, который нацелен на устранение данного пробела. Он позволяет формализовать ряд методов из области обработки изображений, оценить сложность их вычисления в количестве операций и выявить общие подходы к их ускорению. Приведено три таких метода оптимизации, с помощью которых структурные преобразования изображений конвертируются в быстрые структурные преобразования, обладающие меньшей сложностью по сравнению с наивным независимым вычислением отдельно взятых элементов исходных преобразований. Рассмотрены применения указанных методов для задач автоматической обработки изображений документов, чтения штриховых кодов и вычислительной томографии.

Полная версия статьи в формате pdf.

EDN: YUDLHH

Стр. 74-87.

Литература

1. Яне Б. Цифровая обработка изображений. М.: Техносфера. 2007. С. 584.

2. Gonzalez R.C., Woods R.E., Masters B.R. Digital image processing, third edition. 14. 029901.

3. Limonova E., Terekhin A., Nikolaev D., Arlazarov V. Fast implementation of morphological filtering using ARM NEON extension. // IJAER. 2016;11(24):11675–11680.

4. Zekri A.S. Enhancing the matrix transpose operation using intel AVX instruction set extension. // International Journal of Computer Science & Information Technology (IJCSIT). 2014;6(3):67–78. DOI: 10.5121/ijcsit.2014.6305.

5. Хуанг Т.С. (ред.). Быстрые алгоритмы в цифровой обработке изображений. М.: Радио и связь. 1984. С. 224.

6. Weiss B. Fast isotropic median filtering. // SIGGRAPH Conference Papers ‘25: Proceedings of the Special Interest Group on Computer Graphics and Interactive Techniques Conference Conference Papers. 2025;(137):1–10. DOI: 10.1145/3721238.3730763.

7. Bezmaternykh P.V., Nikolaev D.P., Arlazarov V.L. High-performance digital image processing. // Pattern Recognit. Image Anal. 2023;33(4):743–755. DOI: 10.1134/S1054661823040090.

8. Винберг Э.Б. Курс алгебры. М.: МЦНМО. 2014. С. 290.

9. Klette R., Rosenfeld A. Digital straightness – a review. // Discrete Applied Mathematics. 2004;139(1-3):197–230. DOI: 10.1016/j.dam.2002.12.001.

10. Koplowitz J., Lindenbaum M., Bruckstein A. The number of digital straight lines on an NxN grid. // IEEE Transactions on Information Theory. 1990;36(1):192–197. DOI: 10.1109/18.50392.

11. Viola P., Jones M. Robust real-time object detection. // International Journal of Computer Vision – IJCV. 2001;57(2).

12. Crow F.C. Summed-area tables for texture mapping. // In Proceedings of the 11th annual conference on Computer graphics and interactive techniques – SIGGRAPH 84. ACM Press. 1984. Р. 207-212. DOI: 10.1145/800031.808600.

13. Van Herk M. A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels. // Pattern Recognition Letters. 1992;13(7):517–521. DOI: 10.1016/0167-8655(92)90069-C.

14. Gil J., Werman M. Computing 2-d min, median, and max filters. // IEEE Transactions on Pattern Analysis and Machine Intelligence. 1993;15(5):504–507.

15. Слугин Д.Г., Арлазаров В.В. Поиск текстовых полей документа с помощью методов обработки изображений // Труды ИСА РАН. 2017. Т. 67. № 4. С. 65–73.

16. Bradley D., Roth G. Adaptive thresholding using the integral image. // Journal of Graphics Tools. 2007;12(2):13–21. DOI: 10.1080/2151237x.2007.10129236.

17. Shafait F., Keysers D., Breuel T. Efficient implementation of local adaptive thresholding techniques using integral images // In Document Recognition and Retrieval XV. 2008;6815:317–322. International Society for Optics and Photonics, SPIE. DOI: 10.1117/12.767755.

18. Samorodova O.A., Samorodov A.V. Fast implementation of the Niblack binarization algorithm for microscope image segmentation. // Pattern Recognition and Image Analysis. 2016;26(3):548–551. DOI: 10.1134/s1054661816030020.

19. Brady M.L., Yong W. Fast parallel discrete approximation algorithms for the radon transform. // In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ‘92. 1992. P. 91–99. ACM. DOI: 10.1145/140901.140911.

20. Gotz W.A., Druckmuller H.J. A fast digital Radon transform – an efficient means for evaluating the hough transform // Pattern Recognition. 1995;28:1985-1992.

21. Карпенко С.М., Николаев Д.П., Николаев П.П., Постников В.В. Быстрое преобразование Хафа с управляемой робастностью // In IEEE AIS’04, CAD-2004. 2004. Т. 2. С. 303–309.

22. He K., Sun J., Tang X. Single image haze removal using dark channel prior. // In 2009 IEEE Conference on Computer Vision and Pattern Recognition. 2009. Р. 1956–1963. DOI: 10.1109/CVPR.2009.5206515.

23. Kunina I.A., Sher A.V., Nikolaev D.P. Screen recapture detection based on color-texture analysis of document boundary regions // Computer Optics. 2022.

24. Пытьев Ю.П., Чуличков А.И. Методы морфологического анализа изображений. М.: ФИЗ-МАТЛИТ. 2010. С. 336.

25. Куроптев А.В., Николаев Д.П., Постников В.В. Точная локализация опорных решеток полей заполнения в анкетах методами динамического программирования и морфологической фильтрации. // Труды ИСА РАН. 2013. Т. 63. №3. С. 111–116.

26. Bulatov K.B., Bezmaternykh P.V., Nikolaev D.P., Arlazarov V.V. Towards a unified framework for identity documents analysis and recognition. // Computer Optics. 2022;46(3):436–454. DOI: 10.18287/2412-6179-CO-1024.

27. Арлазаров В.В., Постников В.В., Шоломов Д.Л. Cognitive forms – система массового вводаструктурированных документов. // Труды ИСА РАН. 2002. Т. 1. С. 35–46.

28. Gatos B.G. Imaging techniques in document analysis processes. // In Handbook of Document Image Processing and Recognition. 2014. Р. 73–131. Springer London. DOI: 10.1007/978-0-85729-859-1_4.

29. Безматерных П.В. Нормализация изображения текста с помощью быстрого преобразования Хафа // ИТиВС. 2024. Т. 4. С. 3-16. DOI: 10.14357/20718632240401.

30. Muniz R. A robust software barcode reader using the Hough transform // Proceedings 1999 International Conference on Information Intelligence and Systems. 1999. Р. 313–319. DOI: 10.1109/ICIIS.1999.810282.

31. Szentandrasi I., Herout A., Dubska M. Fast detection and recognition of QR codes in high-resolution images. // In Proceedings of the 28th Spring Conference on Computer Graphics (SCCG ‘12). 2012. Р. 129–136. DOI: 10.1145/2448531.2448548.

32. Zamberletti A., Gallo I., Albertini S., Noce L. Neural 1D Barcode Detection Using the Hough Transform // IPSJ Transactions on Computer Vision and Applications. 2014;7:1-9. DOI: 10.2197/ipsjtcva.7.1.

33. Mitrofanov D.G., Zlobin P.K., Shemiakina Y.A., Bezmaternykh P.V. Precise localization of PDF417 code based on fast hough transform // Vestnik YuUrGU «Vychislitelnaya matematika i informatika». 2024;13(4):19-34. DOI: 10.14529/cmse240402.

34. Martynov S.I., Bezmaternykh P.V. Aztec core symbol detection method based on connected components extraction and contour signature analysis. // ICMV 2019. Society of Photo-Optical Instrumentation Engineers (SPIE). 2020. P. 11433. DOI: 10.1117/12.2559183.

35. Безматерных П.В., Вылегжанин Д.В., Гладилин С.А., Николаев Д.П. Генеративное распознавание двумерных штрихкодов. // ИИиПР. 2010. Т. 4. С. 63–69.

36. Долматова А.В., Николаев Д.П. Ускорение свертки и обратного проецирования при реконструкции томографических изображений // Сенсорные системы. 2020. Т. 34. № 1. С. 64–71. DOI: 10.31857/S0235009220010072.

37. Bulatov K., Chukalina M., Kutukova K., Kohan V., Ingacheva A., Buzmakov A., Arlazarov V.V., Zschech E. Monitored tomographic reconstruction - An advanced tool to study the 3D morphology of nanomaterials // Nanomaterials. 2021;11(10):1-12. DOI: 10.3390/nano11102524.

38. Sheshkus A., Ingacheva A., Arlazarov V., Nikolaev D. HoughNet: neural network architecture for vanishing points detection // In ICDAR 2019. 2020;(8978201):844–849. The Institute of Electrical and Electronics Engineers (IEEE).