Везде

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

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

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

Вы можете
Код статьи
10.31857/S0555292324040053-1
DOI
10.31857/S0555292324040053
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Полевой Д. В
  • Аффилиация:
    Институт проблем передачи информации им. А.А. Харкевича РАН
    Федеральный исследовательский центр “Информатика и управление” РАН
    ООО “Смарт Энджинс Сервис”
Казимиров Д. Д
  • Аффилиация:
    Институт проблем передачи информации им. А.А. Харкевича РАН
    ООО “Смарт Энджинс Сервис”
Чукалина М. В
  • Аффилиация:
    Федеральный исследовательский центр “Информатика и управление” РАН
    ООО “Смарт Энджинс Сервис”
Николаев Д. П
  • Аффилиация:
    Федеральный исследовательский центр “Информатика и управление” РАН
    ООО “Смарт Энджинс Сервис”
Том/ Выпуск
Том 60 / Номер выпуска 4
Страницы
72-90
Аннотация
Представлен новый метод транспонирования суммирующих алгоритмов с использованием их графового представления, обеспечивающий большую гибкость по сравнению с предыдущими подходами, основанными на явном матричном представлении соответствующего суммирующего оператора. Применение нашего метода продемонстрировано на примере транспонирования нескольких алгоритмов быстрого преобразования Хафа. Важно отметить, что наш подход сохраняет асимптотическую вычислительную сложность исходного алгоритма. Последнее свойство очень важно для приложений в компьютерной томографии.
Ключевые слова
суммирующие алгоритмы транспонированный оператор быстрое преобразование Хафа паттерны компьютерная томография оператор прямого проецирования оператор обратного проецирования
Дата публикации
18.09.2025
Год выхода
2025
Всего подписок
0
Всего просмотров
12

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

  1. 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. 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. 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. 4. Chaloeivoot T., Phiphobmongkol S. Building Detection from Terrestrial Images // J. Image Graph. 2016. V. 4. № 1. P. 46–50.
  5. 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. 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. 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. 8. Алиев М.А., Николаев Д.П., Сараев А.А. Построение быстрых вычислительных схем настройки алгоритма бинаризации Ниблэка // Тр. ИСА РАН. 2014. Т. 64. № 3. С. 25–34.
  9. 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. 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. 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. 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. 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. 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. 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. 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. 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. 18. Котов А.А., Коноваленко И.А., Николаев Д.П. Прослеживание объектов в видеопотоке, оптимизированное с помощью быстрого преобразования Хафа // ИтиВС. 2015. № 1. С. 56–68.
  19. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 34. Ершов Е.И., Терехин А.П., Николаев Д.П. Обобщение быстрого преобразования Хафа для трехмерных изображений // Информационные процессы. 2017. Т. 17. № 4. С. 294–308.
  35. 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. 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. 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. 38. Карпенко С.М., Ершов Е.И. Исследование свойств диадического паттерна быстрого преобразования Хафа // Пробл. передачи информ. 2021. Т. 57. № 3. С. 102–111. https://doi.org/10.31857/S0555292321030074
  39. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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
QR
Перевести

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

Scopus

Scopus

Scopus

Crossref

Scopus

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

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

Scopus

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