Везде

ОНИТПроблемы передачи информации Problems of Information Transmission

  • ISSN (Print) 0555-2923
  • ISSN (Online) 3034-5839

БЫСТРЫЙ АЛГОРИТМ ВЫЧИСЛЕНИЯ ПРЕОБРАЗОВАНИЯ ХАФА ДЛЯ ИЗОБРАЖЕНИЙ ПРОИЗВОЛЬНОГО РАЗМЕРА С ПЕРЕИСПОЛЬЗОВАНИЕМ ВЫДЕЛЕННОЙ ПАМЯТИ

Вы можете
Код статьи
10.31857/S0555292324040065-1
DOI
10.31857/S0555292324040065
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Казимиров Д. Д
  • Аффилиация:
    Институт проблем передачи информации им. А.А. Харкевича РАН
    Московский государственный университет им. М.В. Ломоносова
    ООО “Смарт Энджинс Сервис”
Николаев Д. П
  • Аффилиация:
    ООО “Смарт Энджинс Сервис”
    Федеральный исследовательский центр “Информатика и управление” РАН
Рыбакова Е. О
  • Аффилиация:
    Московский государственный университет им. М.В. Ломоносова
    ООО “Смарт Энджинс Сервис”
Терехин А. П
  • Аффилиация: Институт проблем передачи информации им. А.А. Харкевича РАН
Том/ Выпуск
Том 60 / Номер выпуска 4
Страницы
91-115
Аннотация
In-place алгоритмы эффективно используют память, уже выделенную для входных данных, ограничиваясь лишь незначительным дополнительным объемом памяти для промежуточных вычислений. Для изображений ширины, равной степени двойки, известен in-place алгоритм, являющийся вариацией стандартного алгоритма Брейди – Ёна для вычисления преобразования Хафа. Однако этот алгоритм неприменим к изображениям с произвольной шириной, наиболее часто встречающимся на практике. Напротив, out-of-place алгоритм FHT 2DS может обрабатывать изображения различных размеров. В настоящей статье представлен in-place вариант алгоритма FHT 2DS, названный FHT 2IDS. Мы показываем, что алгоритм FHT 2IDS дает такие же результаты, как и алгоритм FHT 2DS, но использует значительно меньше памяти на каждом шаге рекурсии. В частности, на каждом шаге рекурсии алгоритм FHT 2IDS требует массива размера не более w+h (где w и h – ширина и высота изображения), в то время как алгоритм FHT 2DS требует массива размера wh. Экспериментальные результаты показывают, что алгоритм FHT 2IDS, реализованный на C/C++, работает на 26% быстрее своего out-of-place аналога, алгоритма FHT 2DS. Алгоритм FHT 2IDS также доступен на Python через открытый исходный код библиотеки adrt.
Ключевые слова
преобразование Хафа быстрое преобразование Хафа приближенное дискретное преобразование Радона вычислительный граф
Дата публикации
18.09.2025
Год выхода
2025
Всего подписок
0
Всего просмотров
13

Библиография

  1. 1. Hough P.V.C. Machine Analysis of Bubble Chamber Pictures // Proc. 2nd Int. Conf. on High-Energy Accelerators and Instrumentation (HEACC 1959). CERN, Geneva, Switzerland. Sept. 14–19, 1959. P. 554–558.
  2. 2. Rahmdel P.S., Comley R., Shi D., McElduff S. A Review of Hough Transform and Line Segment Detection Approaches // Proc. 10th Int. Conf. on Computer Vision Theory and Applications (VISAPP 2015). Berlin, Germany. Mar. 11–14, 2015. V. 2. P. 411–418. https://doi.org/10.5220/0005268904110418
  3. 3. Mukhopadhyay P., Chaudhuri B.B. A Survey of Hough Transform // Pattern Recognit. 2015. V. 48. № 3. P. 993–1010. https://doi.org/10.1016/j.patcog.2014.08.027
  4. 4. Illingworth J., Kittler J. A Survey of the Hough Transform // Comput. Vision Graph. Image Process. 1988. V. 44. № 1. P. 87–116. https://doi.org/10.1016/S0734-189X (88)80033-1
  5. 5. Xu Z., Shin B., Klette R. Accurate and Robust Line Segment Extraction Using Minimum Entropy with Hough Transform // IEEE Trans. Image Process. 2014. V. 24. № 3. P. 813–822. https://doi.org/10.1109/TIP.2014.2387020
  6. 6. Алиев М.А., Николаев Д.П., Сараев А.А. Построение быстрых вычислительных схем настройки алгоритма бинаризации Ниблэка // Тр. ИСА РАН. 2014. Т. 64. № 3. С. 25–34.
  7. 7. Nikolaev D.P., Nikolayev P.P. Linear Color Segmentation and Its Implementation // Comput. Vis. Image Und. 2004. V. 94. № 1–3. P. 115–139. https://doi.org/10.1016/j.cviu.2003.10.012
  8. 8. Saha S., Basu S., Nasipuri M., Basu D. A Hough Transform Based Technique for Text Segmentation // J. Comput. 2010. V. 2. № 2. P. 134–141.
  9. 9. Кунина И.А., Гладилин С.А., Николаев Д.П. Слепая компенсация радиальной дисторсии на одиночном изображении с использованием быстрого преобразования Хафа // Компьютерная оптика. 2016. Т. 40. № 3. С. 395–403. https://doi.org/10.18287/2412-6179-2016-40-3-395-403
  10. 10. Асватов Е.Н., Ершов Е.И., Николаев Д.П. Робастная ортогональная линейная регрессия для маломерных гистограмм // Сенсорные системы. 2017. Т. 31. № 4. С. 331–342.
  11. 11. Brady M.L., Yong W. Fast Parallel Discrete Approximation Algorithms for the Radon Transform // Proc. 4th Ann. ACM Symp. on Parallel Algorithms and Architectures (SPAA’92). San Diego, California, USA. June 29 – July 1, 1992. P. 91–99. https://doi.org/10.1145/140901.140911
  12. 12. Карпенко С.М., Ершов Е.И. Исследование свойств диадического паттерна быстрого преобразования Хафа // Пробл. передачи информ. 2021. Т. 57. № 3. С. 102–111. https://doi.org/10.31857/S0555292321030074
  13. 13. Jahan R, Suman P., Singh D.K. Lane Detection Using Canny Edge Detection and Hough Transform on Raspberry Pi // Int. J. Adv. Res. Comput. Sci. 2018. V. 9. № 2. P. 85–89.
  14. 14. Thongpan N., Rattanasiriwongwut M., Ketcham M. Lane Detection Using Embedded System // Int. J. Comput. Internet Manag. 2020. V. 28. № 2. P. 46–51.
  15. 15. Panfilova E., Shipitko O.S., Kunina I. Fast Hough Transform-Based Road Markings Detection For Autonomous Vehicle // 13th Int. Conf. on Machine Vision (ICMV 2020). Rome,Italy. Nov. 2–6, 2020. Proc. SPIE. V. 11605. P. 671–680. https://doi.org/10.1117/12.2587615
  16. 16. Котов А.А., Коноваленко И.А., Николаев Д.П. Прослеживание объектов в видеопотоке, оптимизированное с помощью быстрого преобразования Хафа // ИтиВС. 2015. № 1. С. 56–68.
  17. 17. Tropin D.V., Ilyuhin S.A., Nikolaev D.P., Arlazarov V.V. Approach for Document Detection by Contours and Contrasts // Proc. 25th Int. Conf. on Pattern Recognition (ICPR 2020). Milan, Italy. Jan. 10–15, 2021. P. 9689–9695. https://doi.org/10.1109/ICPR48806.2021.9413271
  18. 18. Bezmaternykh P.V., Nikolaev D.P. A Document Skew Detection Method Using Fast Hough Transform // 12th Int. Conf. on Machine Vision (ICMV 2019). Amsterdam, Netherlands. Nov. 16–18, 2020. Proc. SPIE. V. 11433. P. 132–137. https://doi.org/10.1117/12.2559069
  19. 19. Min-Allah N., Qureshi M.B., Alrashed S., Rana O.F. Cost Efficient Resource Allocation for Real-Time Tasks in Embedded Systems // Sustainable Cities And Society. 2019 V. 48. Article No. 101523. https://doi.org/10.1016/j.scs.2019.101523
  20. 20. Gupta R.K., De Micheli G. Specification and Analysis of Timing Constraints for Embedded Systems // IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 1997. V. 16. № 3. P. 240–256. https://doi.org/10.1109/43.594830
  21. 21. Surianarayanan C., Lawrence, J.J., Chelliah P.R., Prakash E., Hewage C. A Survey on Optimization Techniques for Edge Artificial Intelligence (AI) // Sensors. 2023. V. 23. № 3. Papaer No. 1279 (33 pp.). https://doi.org/10.3390/s23031279
  22. 22. Ranjith M.S., Parameshwara S., Pavan Yadav A., Hegde S. Optimizing Neural Network for Computer Vision Task in Edge Device, https://arxiv.org/abs/2110.00791 [cs.CV], 2021.
  23. 23. Sharmila B.S., Santhosh H.S., Parameshwara S., Swamy M.S., Baig W.H., Nanditha S.V. Optimizing Deep Learning Networks for Edge Devices with an Instance of Skin Cancer and Corn Leaf Disease Dataset // SN Comput. Sci. 2023. V. 4. Article No. 793. https://doi.org/10.1007/s42979-023-02239-5
  24. 24. Comeag˘ a A.-M., Marin I. Memory Management Strategies for an Internet of Things System, https://arxiv.org/abs/2311.10458 [cs.SE], 2023.
  25. 25. Almutairi R., Bergami G., Morgan G. Advancements and Challenges in IoT Simulators: A Comprehensive Review // Sensors. 2024. V. 24. № 5. Paper No. 1511 (35 pp.), https: //doi.org/10.3390/s24051511
  26. 26. Anikeev F.A., Raiko G.O., Limonova E.E., Aliev M.A., Nikolaev D.P. Efficient Implementation of Fast Hough Transform Using CPCA Coprocessor // Program. Comput. Soft. 2021. V. 47. № 5. P. 335–343. https://doi.org/10.1134/S0361768821050029
  27. 27. Kazimirov D., Nikolaev D., Rybakova E., Terekhin A. Generalization of Brady–Yong Algorithm for Fast Hough Transform to Arbitrary Image Size, https://arxiv.org/abs/2411.07351 [cs.CV], 2024.
  28. 28. Kazimirov D., Nikolaev D., Rybakova E., Terekhin A. Generalization of Brady–Yong Algorithm for Fast Hough Transform to Arbitrary Image Size // Proc. 5th Symp. on Pattern Recognition and Applications (SPRA 2024). Istanbul, Turkey. Nov. 11–13, 2024 (to appear).
  29. 29. Gava M.A., Rocha H.R.O., Faber M.J., Segatto M.E.V., W¨ ortche H., Silva J.A.L. Optimizing Resources and Increasing the Coverage of Internet-of-Things (IoT) Networks: An Approach Based on LoRaWAN // Sensors. 2023. V. 23. № 3. Paper No. 1239 (17 pp.). https://doi.org/10.3390/s23031239
  30. 30. Almurshed O., Meshoul S., Muftah A., Kaushal A.K., Almoghamis O., Petri I., Auluck N., Rana O. A Framework for Performance Optimization of Internet of Things Applications // Euro-Par 2023: Parallel Processing Workshops (Euro-Par 2023 Int. Workshops. Limassol, Cyprus. Aug. 28 – Sept. 1, 2023. Revised Selected Papers, Part I). Lect. Notes Comput. Sci. V. 14351. Cham: Springer, 2024. P. 165–176. https://doi.org/10.1007/978-3-031-50684-0_13
  31. 31. Chakraborty S., Mukherjee A., Raman V., Satti S.R. A Framework for In-place Graph Algorithms // 26th Annu. Europ. Symp. on Algorithms (ESA 2018). Helsinki, Finland. Aug. 20–22, 2018. Leibniz Int. Proc. Inform. (LIPIcs). V. 112. Schloss Dagstuhl – LeibnizZentrum f¨ ur Informatik, Germany: Dagstuhl Publ., 2018. P. 13:1–13:16. https://doi.org/10.4230/LIPIcs.ESA.2018.13
  32. 32. Axtmann M., Witt S., Ferizovic D., Sanders P. Engineering In-place (Shared-Memory) Sorting Algorithms // ACM Trans. Parallel Comput. 2022. V. 9. № 1. P. 1–62. https://doi.org/10.1145/3505286
  33. 33. Gu Y., Obeya O., Shun J. Parallel In-place Algorithms: Theory and Practice // 2nd Symp. on Algorithmic Principles of Computer Systems (APOCS 2020). Virtual Conf. Jan. 13, 2021.P. 114–128. https://doi.org/10.1137/1.9781611976489.9
  34. 34. Br¨onnimann H., Chan T.M., Chen E.Y. Towards In-place Geometric Algorithms and Data Structures // Proc. 12th Annu. Symp. on Computational Geometry (SCG’04). Brooklyn, New York, USA. June 8–11, 2004. P. 239–246. https://doi.org/10.1145/997817.997854
  35. 35. Kuszmaul W., Westover A. Cache-Efficient Parallel-Partition Algorithms Using ExclusiveRead-and-Write Memory // Proc. 32nd ACM Symp. on Parallelism in Algorithms and Architectures (SPAA’20). Virtual Event, USA. July 15–17, 2020. P. 551–553. https://doi.org/10.1145/3350755.3400234
  36. 36. Bramas B., Bramas Q. On the Improvement of the In-place Merge Algorithm Parallelization, https://arxiv.org/abs/2005.12648 [cs.DC], 2020.
  37. 37. Cooley J.W., Tukey J.W. An Algorithm for the Machine Calculation of Complex Fourier Series // Math. Comp. 1965. V. 19. № 90. P. 297–301. https://doi.org/10.2307/2003354
  38. 38. Brady M.L., Yong W. Fast Parallel Discrete Approximation Algorithms for the Radon Transform // Proc. 4th Ann. ACM Symp. on Parallel Algorithms and Architectures (SPAA’92). San Diego, California, USA. June 29 – July 1, 1992. P. 91–99. https://doi.org/10.1145/140901.140911
  39. 39. Khanipov T. Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations, https://arxiv.org/abs/1801.01054 [cs.CC], 2018.
  40. 40. Johnson H., Burrus C. An In-order, In-place Radix-2 FFT // Proc. ICASSP’84: IEEE Int. Conf. on Acoustics, Speech, and Signal Processing. San Diego, CA, USA. Mar. 19–21, 1984. P. 473–476. https://doi.org/10.1109/ICASSP.1984.1172660
  41. 41. IITP Vision Lab. adrt: Approximate Discrete Radon Transform. GitHub repository, accessed 21.10.2024. https://github.com/iitpvisionlab/adrt
QR
Перевести

Индексирование

Scopus

Scopus

Scopus

Crossref

Scopus

Высшая аттестационная комиссия

При Министерстве образования и науки Российской Федерации

Scopus

Научная электронная библиотека