• 1990 (Vol.4)
  • 1989 (Vol.3)
  • 1988 (Vol.2)
  • 1987 (Vol.1)

Fast filtering and back projection for CT image reconstruction

© 2020 A. V. Dolmatova1,2, D. P. Nikolaev1

Institute for Information Transmission Problem RAS 127051 Moscow, B. Karetny per., 19, Russia
Smart Engines Ltd, 117312 Moscow, pr. 60-letiya Oktybrya, 9, Russia

Received 13 Sep 2019

Filtered back projection is a common method for the tomographic images reconstruction. The classical implementation of the algorithm requires operations, where N is the characteristic linear size of the image. In this paper, we propose methods for reducing the computational complexity of the algorithm to additions and multiplications; whereas the previously proposed methods require multiplications. We show that the convolution operation with a symmetric filter can be approximated by successive application of two coupled IIR filters. A discrete method for fast calculating the inverse Radon transform is demonstrated. It allows to accelerate the back projection operation

Key words: computed tomography, fast filtering, fast convolution-, inverse Radon transform, IIR filterd

DOI: 10.31857/S0235009220010072

Cite: Dolmatova A. V., Nikolaev D. P. Uskorenie svertki i obratnogo proetsirovaniya pri rekonstruktsii tomograficheskikh izobrazhenii [Fast filtering and back projection for ct image reconstruction]. Sensornye sistemy [Sensory systems]. 2020. V. 34(1). P. 64–71 (in Russian). doi: 10.31857/S0235009220010072


  • Ershov E.I., Terekhin A.P., Nikolaev D.P. Obobchenie bustrogo preobrazovaniy Hafa dly trehmernuch izobrazenii [Fast Hough transform generalization for three-dimensional images] Informatsionnue processu [Information processes]. 2017. V. 17. № 4. P. 294–308 (in Russian)
  • Prun V.E., Buzmakov A.V., Nikolaev D.P., Chukalina M.V., Asadchikov V.E. Vuchislitelyno effektivnui variant algebraicheskogo metoda komputernoy tomografee [A computationally efficient version of the algebraic method for computer tomography]. Avtomateka I Telemehanika [Automation and Remote Control]. 2013. V. 74. № 10. P. 1670–1678. DOI: 10.1134/S000511791310007X.
  • 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.
  • Basu S., Bresler Y. 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
  • 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
  • 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
  • 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
  • Deriche R. Recursively implementating the Gaussian and its derivatives. [Research Report] RR-1893. INRIA. 1993.
  • 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
  • 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
  • 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
  • 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
  • Kak A.C., Slaney M. Principles of computerized tomographic imaging. 1988 New York . IEEE press, 1988.
  • 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
  • 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
  • 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.
  • 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
  • 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
  • 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
  • Xiao S., Bresler Y., Munson D.C. native fanbeam tomographic reconstruction. Proceedings IEEE International Symposium on Biomedical Imaging. IEEE press, 2002. P. 824–827.
  • 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