Сенсорные системы, 2020, T. 34, № 1, стр. 64-71

Ускорение свертки и обратного проецирования при реконструкции томографических изображений

А. В. Долматова 12*, Д. П. Николаев 1

1 Институт проблем передачи информации РАН
127051 Москва, Большой Каретный переулок 19, Россия

2 ООО “Смарт Энджинс Сервис”
117312 Москва, проспект 60-летия Октября 9, Россия

* E-mail: anastasiya.v.dolmatova@gmail.com

Поступила в редакцию 13.09.2019
После доработки 11.10.2019
Принята к публикации 30.10.2019

Аннотация

Метод свертки и обратной проекции (также известный как метод фильтрованных обратных проекций, FBP) широко используется для восстановления томографических изображений. Классическая реализация данного алгоритма требует выполнения $O({{N}^{3}})$ операций, где N – характерный линейный размер изображения. В данной работе предлагаются методы, позволяющие снизить вычислительную сложность алгоритма до $O({{N}^{2}}\log N)$ операций сложения и $O({{N}^{2}})$ операций умножения; тогда как ранее предложенные методы требуют $O({{N}^{2}}\log N)$ операций умножения. Показано, что операция свертки с рамп-фильтром может быть аппроксимирована последовательным применением двух рекурсивных фильтров. Также описан метод быстрого вычисления обратного дискретного преобразования Радона, позволяющий ускорить обратное проецирование.

Ключевые слова: обратное преобразование Радона, метод фильтрованных обратных проекций, метод свертки и обратной проекции, компьютерная томография, ускорение свертки, БИХ-фильтр, рекурсивный фильтр

DOI: 10.31857/S0235009220010072

Список литературы

  1. Ершов Е.И., Терехин А.П., Николаев Д.П. Обобщение быстрого преобразования Хафа для трехмерных изображений. Информационные процессы. 2017. Т. 17. № 4. С. 294–308.

  2. Прун В.Е., Бузмаков А.В., Николаев Д.П., Чукалина М.В., Асадчиков В.Е. Вычислительно эффективный вариант алгебраического метода компьютерной томографии. Автоматика и телемеханика. 2013. Т. 10. С. 86–97. https://doi.org/10.1134/S000511791310007X

  3. Andersson F. Fast inversion of the Radon transform using log-polar coordinates and partial back-projections. SIAM Journal on Applied Mathematics. 2005. V. 65. № 3. P. 818–837.

  4. Basu S., Bresler Y. $O({{N}^{2}}\log N)$ filtered backprojection reconstruction algorithm for tomography. IEEE Transactions on Image Processing. 2000. V. 9. № 10. P. 1760–1773. https://doi.org/10.1109/83.869187

  5. Basu S., Bresler Y. Error analysis and performance optimization of fast hierarchical backprojection algorithms. IEEE Transactions on Image Processing. 2001. V. 10. № 7. P. 1103–1117. https://doi.org/10.1109/83.931104

  6. Brady M.L. A fast discrete approximation algorithm for the Radon transform. SIAM Journal on Computing. 1998. V. 27. № 1. P. 107–119. https://doi.org/10.1137/S0097539793256673

  7. Deriche R. Using Canny’s criteria to derive a recursively implemented optimal edge detector. International journal of computer vision. 1987. V. 1. № 2. P. 167–187. https://doi.org/10.1007/BF00123164

  8. Deriche R. Recursively implementating the Gaussian and its derivatives. [Research Report] RR-1893. INRIA. 1993.

  9. Edholm P.R., Herman G.T. Linograms in image reconstruction from projections. IEEE transactions on medical imaging. 1987. V. 6. № 4. P. 301–307. https://doi.org/10.1109/TMI.1987.4307847

  10. Fourmont K. Non-equispaced fast Fourier transforms with applications to tomography. Journal of Fourier Analysis and Applications. 2003. V. 9. № 5. P. 431–450. https://doi.org/10.1007/s00041-003-0021-1

  11. Gao F., Han L. Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications. 2012. V. 51. № 1. P. 259–277. https://doi.org/10.1007/s10589-010-9329-3

  12. Hamill J., Michel C., Kinahan P. Fast PET EM reconstruction from linograms. IEEE Transactions on Nuclear Science.2003. V. 50. № 5. P. 1630–2635. https://doi.org/10.1109/NSSMIC.2002.1239647

  13. Kak A.C., Slaney M. Principles of computerized tomographic imaging. 1988 New York . IEEE press, 1988.

  14. O’Connor Y.Z., Fessler J.A. Fourier-based forward and back-projectors in iterative fan-beam tomographic image reconstruction. IEEE transactions on medical imaging. 2006. V. 25. № 5. P. 582–589. https://doi.org/10.1109/TMI.2006.872139

  15. Potts D., Steidl G. Fourier reconstruction of functions from their nonstandard sampled Radon transform. Journal of Fourier Analysis and Applications. 2002. V. 8. № 6. P. 513–534. https://doi.org/10.1007/s00041-002-0025-2

  16. Potts D., Steidl G. New Fourier reconstruction algorithms for computerized tomography. Wavelet Applications in Signal and Image Processing VIII. 2000. V. 4119. P. 13–23.

  17. Powell M.J.D. An efficient method for finding the minimum of a function of several variables without calculating derivatives. The Computer Journal. 1964. V. 7. № 2. P. 155–162. https://doi.org/10.1093/comjnl/7.2.155

  18. Ramachandran G.N., Lakshminarayanan A.V. Three-dimensional reconstruction from radiographs and electron micrographs: application of convolutions instead of Fourier transforms. Proceedings of the National Academy of Sciences. 1971. V. 68. № 9. P. 2236–2240. https://doi.org/10.1073/pnas.68.9.2236

  19. Wei Y., Wang G., Hsieh J. An intuitive discussion on the ideal ramp filter in computed tomography (I). Computers and Mathematics with Applications. 2005. V. 49. № 5–6. P. 731–740. https://doi.org/10.1016/j.camwa.2004.10.034

  20. Xiao S., Bresler Y., Munson D.C. $O({{N}^{2}}\log N)$ native fan-beam tomographic reconstruction. Proceedings IEEE International Symposium on Biomedical Imaging. IEEE press, 2002. P. 824–827.

  21. Young I.T., Van Vliet L.J. Recursive implementation of the Gaussian filter. Signal processing. 1995. V. 44. № 2. P. 139–151. DOI: 0165-1684(95)00020-E

Дополнительные материалы отсутствуют.