Complexity-Preserving Transposition of Summing Algorithms Using Their Computational Graph Representations

Cover Page

Cite item

Full Text

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

Abstract

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

References

  1. Polevoy D., Gilmanov M., Kazimirov D., Chukalina M., Ingacheva A., Kulagin P., Nikolaev D. Tomographic Reconstruction: General Approach to Fast Back-Projection Algorithms // Mathematics. 2023. V. 11. № 23. Paper No. 4759 (37 pp.). https://doi.org/10.3390/math11234759
  2. 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.
  3. 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
  4. Chaloeivoot T., Phiphobmongkol S. Building Detection from Terrestrial Images // J. Image Graph. 2016. V. 4. № 1. P. 46–50.
  5. 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
  6. Aggarwal N., Karl W. Line Detection in Images through Regularized Hough Transform // IEEE Trans. Image Process. 2006. V. 15. № 3. P. 582–591. https://doi.org/10.1109/TIP.2005.863021
  7. 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
  8. Алиев М.А., Николаев Д.П., Сараев А.А. Построение быстрых вычислительных схем настройки алгоритма бинаризации Ниблэка // Тр. ИСА РАН. 2014. Т. 64. № 3. С. 25–34.
  9. Ozturk H., Saricam I.T. Core Segmentation and Fracture Path Detection Using Shadows // J. Image Graph. 2018. V. 6. № 1. P. 69–73.
  10. 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.
  11. Yazdi M., Mohammadi M. Metal Artifact Reduction in Dental Computed Tomography Images Based on Sinogram Segmentation Using Curvelet Transform Followed by Hough Transform // J. Med. Signals Sens. 2017. V. 7. № 3. P. 145–152.
  12. 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
  13. 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.
  14. 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).
  15. 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.
  16. Thongpan N., Rattanasiriwongwut M., Ketcham M. Lane Detection Using Embedded System // Int. J. Comput. Internet Manag. 2020. V. 28. № 2. P. 46–51.
  17. 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
  18. Котов А.А., Коноваленко И.А., Николаев Д.П. Прослеживание объектов в видеопотоке, оптимизированное с помощью быстрого преобразования Хафа // ИтиВС. 2015. № 1. С. 56–68.
  19. van den Braak G.-J., Nugteren C., Mesman B., Corporaal H. Fast Hough Transform on GPUs: Exploration of Algorithm Trade-Offs // Advanced Concepts For Intelligent Vision Systems: Proc. 13th Int. Conf. ACIVS 2011. Ghent, Belgium. Aug. 22–25, 2011. Lect. Notes Comput. Sci. V. 6915. Berlin: Springer, 2011. P. 611–622. https://doi.org/10.1007/978-3-642-23687-7_55
  20. Brady M.L. A Fast Discrete Approximation Algorithm for the Radon Transform // SIAM J. Comput. 1998. V. 27. № 1. P. 107–119. https://doi.org/10.1137/S0097539793256673
  21. Prun V.E., Nikolaev D.P., Buzmakov A.V., Chukalina M.V., Asadchikov V.E. Effective Regularized Algebraic Reconstruction Technique for Computed Tomography // Crystallogr. Rep. 2013. V. 58. № 7. P. 1063–1066. https://doi.org/10.1134/S1063774513070158
  22. Buzug T.M. Computed Tomography: From Photon Statistics to Modern Cone-Beam CT. Berlin: Springer, 2008. https://doi.org/10.1007/978-3-540-39408-2
  23. Withers P.J., Bouman C., Carmignato S., Cnudde V., Grimaldi D., Hagen C.K., Maire E., Manley M., Du Plessis A., Stock S.R. X-Ray Computed Tomography // Nat. Rev. Methods Primers. 2021. V. 1. № 1. Article No. 18. https://doi.org/10.1038/s43586-021-00015-4
  24. Arlazarov V.L., Nikolaev D.P., Arlazarov V.V., Chukalina M.V. X-Ray Tomography: The Way from Layer-by-Layer Radiography to Computed Tomography // Компьютерная оптика. 2021. Т. 45. № 6. С. 897–906. https://doi.org/10.18287/2412-6179-CO-898
  25. Lewitt R.M. Reconstruction Algorithms: Transform Methods // Proc. IEEE. 1983. V. 71. № 3. P. 390–408. https://doi.org/10.1109/PROC.1983.12597
  26. Dolmatova A., Chukalina M., Nikolaev D. Accelerated FBP for Computed Tomography Image Reconstruction // Proc. 2020 IEEE Int. Conf. on Image Processing (ICIP 2020). Abu Dhabi, United Arab Emirates. Virtual Conf. Oct. 25–28, 2020. P. 3030–3034. https: //doi.org/10.1109/ICIP40778.2020.9191044
  27. Mileto A., Guimaraes L.S., McCollough C.H., Fletcher J.G., Yu. L. State of the Art in Abdominal CT: The Limits of Iterative Reconstruction Algorithms // Radiology. 2019. V. 293. № 3. P. 491–503. https://doi.org/10.1148/radiol.2019191422
  28. Kasai R., Yamaguchi Y., Kojima T., Abou Al-Ola O.M., Yoshinaga T. Noise-Robust Image Reconstruction Based on Minimizing Extended Class of Power-Divergence Measures // Entropy. V. 23. № 8. 2021. Paper No. 1005 (16 pp.). https://doi.org/10.3390/e23081005
  29. Kerr J.P., Bartlett E.B. Neural Network Reconstruction of Single-Photon Emission Computed Tomography Images // J. Digit. Imaging. 1995. V. 8. № 3. P. 116–126. https://doi.org/10.1007/BF03168085
  30. Adler J., Oktem O. ¨ Learned Primal-Dual Reconstruction // IEEE Trans. Med. Imaging. 2018. V. 37. № 6. P. 1322–1332. https://doi.org/10.1109/TMI.2018.2799231
  31. Yamaev A.V., Chukalina M.V., Nikolaev D.P., Kochiev L.G., Chulichkov A.I. Neural Network Regularization in the Problem of Few View Computed Tomography // Компьютерная оптика. 2022. Т. 46. № 3. С. 422–428. https://doi.org/10.18287/2412-6179-CO-1035
  32. G¨ otz W.A., Druckm¨ uller H.J. A Fast Digital Radon Transform—An Efficient Means for Evaluating the Hough Transform // Pattern Recognit. 1995. V. 28. № 12. P. 1985–1992. https://doi.org/10.1016/0031-3203(95)00057-7
  33. Wu T.-K., Brady M.L. A Fast Approximation Algorithm for 3D Image Reconstruction // Proc. 1998 Int. Computer Symp. Workshop on Image Processing and Character Recognition. Tainan, Taiwan. Dec. 17–19, 1998. P. 213–220.
  34. Ершов Е.И., Терехин А.П., Николаев Д.П. Обобщение быстрого преобразования Хафа для трехмерных изображений // Информационные процессы. 2017. Т. 17. № 4. С. 294–308.
  35. Aliev M., Ershov E.I., Nikolaev D.P. On the Use of FHT, Its Modification for Practical Applications and the Structure of Hough Image // 11th Int. Conf. on Machine Vision (ICMV 2018). Munich, Germany. Nov. 1–3, 2018. Proc. SPIE. V. 11041. P. 1–9. https://doi.org/10.1117/12.2522803
  36. Bulatov K.B., Chukalina M.V., Nikolaev D.P. Fast X-Ray Sum Calculation Algorithm for Computed tomography problem // Вестник ЮурГУ ММП. 2020. Т. 13. № 1. С. 95–106. https://doi.org/10.14529/mmp200107
  37. Nikolaev D., Ershov E., Kroshnin A., Limonova E., Mukovozov A., Faradzhev I. On a Fast Hough/Radon Transform as a Compact Summation Scheme over Digital Straight Line Segments // Mathematics. 2023. V. 15. № 15. Papre No. 3336 (22 pp.). https://doi.org/10.3390/math11153336
  38. Карпенко С.М., Ершов Е.И. Исследование свойств диадического паттерна быстрого преобразования Хафа // Пробл. передачи информ. 2021. Т. 57. № 3. С. 102–111. https://doi.org/10.31857/S0555292321030074
  39. Ershov E., Terekhin A., Nikolaev D., Postnikov V., Karpenko S. Fast Hough Transform Analysis: Pattern Deviation from Line Segment // 8th Int. Conf. on Machine Vision (ICMV 2015). Barcelona, Spain. Nov. 19–21, 2015. Proc. SPIE. V. 9875. P. 42–46. https://doi.org/10.1117/12.2228852
  40. Stanier J., Watson D. Intermediate Representations in Imperative Compilers: A Survey // ACM Comput. Surv. (CSUR). 2013. V. 45. № 3. Article No. 26. P. 1–27. https://doi.org/10.1145/2480741.2480743
  41. Gandarillas V., Joshy A.J., Sperry M.Z., Ivanov A.K., Hwang J.T., A Graph-based Methodology for Constructing Computational Models that Automates Adjoint-based Sensitivity Analysis // Struct. Multidiscip. Optim. 2024. V. 67. № 5. P. 76. https://doi.org/10.1007/s00158-024-03792-0
  42. Shingde N., Blattner T., Bardakoff A., Keyrouz W., Berzins M. An Illustration of Extending Hedgehog to Multi-Node GPU Architectures Using GEMM // SN Comput. Sci. 2024. V. 5. № 5. Article No. 654. https://doi.org/10.1007/s42979-024-02917-y
  43. Bardakoff A. Analysis and Execution of a Data-Flow Graph Explicit Model Using Static Metaprogramming. Ph.D. Thesis. Universit´e Clermont Auvergne, Clermont-Ferrand, France, 2021. Available at https://theses.hal.science/tel-03813645v1.
  44. Sheshkus A., Ingacheva A., Arlazarov V., Nikolaev D. HoughNet: Neural Network Architecture for Vanishing Points Detection // Proc. 15th IAPP Int. Conf. on Document Analysis and Recognition (ICDAR 2019). Sept. 20–25, 2019. Sydney, NSW, Australia. P. 844–849. https://doi.org/10.1109/ICDAR.2019.00140
  45. Sheshkus A., Nikolaev D.P., Arlazarov V.L. Houghencoder: Neural Network Architecture for Document Image Semantic Segmentation // Proc. 2020 IEEE Int. Conf. on Image Processing (ICIP 2020). Abu Dhabi, United Arab Emirates. Virtual Conf. Oct. 25–28, 2020. P. 1946–1950. https://doi.org/10.1109/ICIP40778.2020.9191182
  46. Yamaev A., Chukalina M., Nikolaev D., Sheshkus A. Chulichkov A. Lightweight Denoising Filtering Neural Network for FBP Algorithm // 13th Int. Conf. on Machine Vision (ICMV 2020). Rome, Italy. Nov. 2–6, 2020. Proc. SPIE. V. 11605. P. 158–167. https://doi.org/10.1117/12.2587185
  47. Ge R., He Y., Xia C., Sun H., Zhang Y., Hu D., Chen S., Chen Y., Li S., Zhang D. DDPNet: A Novel Dual-Domain Parallel Network for Low-Dose CT Reconstruction // Medical Image Computing and Computer Assisted Intervention – MICCAI 2022: Proc. 25th Int. Conf. Singapore. Sept. 18–22, 2022. Part VI. Lect. Notes Comput. Sci. V. 6915. Cham: Springer, 2022. P. 748–757. https://doi.org/10.1007/978-3-031-16446-0_71
  48. Niu C., Li M., Guo X., Wang G. Self-supervised Dual-Domain Network for Low-Dose CT Denoising // Developments in X-Ray Tomography XIV. San Diego, California, United States. Aug. 22–24, 2022. Proc. SPIE. V. 12242. P. 85–91. https://doi.org/10.1117/12.2633197
  49. Smolin A., Yamaev A., Ingacheva A., Shevtsova T., Polevoy D., Chukalina M., Nikolaev D., Arlazarov V. Reprojection-based Numerical Measure of Robustness for CT Reconstruction Neural Networks Algorithms // Mathematics. 2022. V. 10. № 22. Paper No. 4210 (17 pp.). https://doi.org/10.3390/math10224210
  50. Kojima T., Yoshinaga T. Iterative Image Reconstruction Algorithm with Parameter Estimation by Neural Network for Computed Tomography // Algorithms. 2023. V. 16. № 1. Paper No. 60 (18 pp.). https://doi.org/10.3390/a16010060

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») на элемент с текстом «Принять и продолжить».