Towards In-Place Fast Hough Transform Algorithm for Images of Arbitrary Size

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

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.

Keywords

References

  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. 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. 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. 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. 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. Алиев М.А., Николаев Д.П., Сараев А.А. Построение быстрых вычислительных схем настройки алгоритма бинаризации Ниблэка // Тр. ИСА РАН. 2014. Т. 64. № 3. С. 25–34.
  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. 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. Кунина И.А., Гладилин С.А., Николаев Д.П. Слепая компенсация радиальной дисторсии на одиночном изображении с использованием быстрого преобразования Хафа // Компьютерная оптика. 2016. Т. 40. № 3. С. 395–403. https://doi.org/10.18287/2412-6179-2016-40-3-395-403
  10. Асватов Е.Н., Ершов Е.И., Николаев Д.П. Робастная ортогональная линейная регрессия для маломерных гистограмм // Сенсорные системы. 2017. Т. 31. № 4. С. 331–342.
  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. Карпенко С.М., Ершов Е.И. Исследование свойств диадического паттерна быстрого преобразования Хафа // Пробл. передачи информ. 2021. Т. 57. № 3. С. 102–111. https://doi.org/10.31857/S0555292321030074
  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. Thongpan N., Rattanasiriwongwut M., Ketcham M. Lane Detection Using Embedded System // Int. J. Comput. Internet Manag. 2020. V. 28. № 2. P. 46–51.
  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. Котов А.А., Коноваленко И.А., Николаев Д.П. Прослеживание объектов в видеопотоке, оптимизированное с помощью быстрого преобразования Хафа // ИтиВС. 2015. № 1. С. 56–68.
  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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. Bramas B., Bramas Q. On the Improvement of the In-place Merge Algorithm Parallelization, https://arxiv.org/abs/2005.12648 [cs.DC], 2020.
  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. 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. Khanipov T. Computational Complexity Lower Bounds of Certain Discrete Radon Transform Approximations, https://arxiv.org/abs/1801.01054 [cs.CC], 2018.
  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. IITP Vision Lab. adrt: Approximate Discrete Radon Transform. GitHub repository, accessed 21.10.2024. https://github.com/iitpvisionlab/adrt

Supplementary files

Supplementary Files
Action
1. JATS XML
Download

Copyright (c) 2024 Russian Academy of Sciences

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».