Abstract
In computed tomography, iterative methods perform better than conventional analytical methods when reconstructing from sparse, insufficient or noisy data. Siddon’s forward projection has been widely used in iterative reconstruction. By contrast, Joseph’s forward projection is more accurate. However, the calculation of the system matrix for conventional Joseph’s projection is more complex and time-consuming. In this paper, we first propose a fast algorithm for the computation of two-dimensional (2D) Joseph’s projection, in which pixel indices and weight factors are determined by an interpolation coefficient for a given ray. The interpolation coefficient is repeatedly updated by incrementing a constant value. Then, we extend the fast algorithm to cone-beam geometry by projecting the ray onto horizontal and vertical planes, respectively. Thus, the voxel indices and weight factors can be calculated via the projected rays similarly to the 2D case. Experimental results show that the proposed algorithm achieves the same precision as conventional Joseph’s projection. The calculation of the system matrix using our algorithm is 6.5 times faster than that of Joseph’s projection, and 6 times faster than that of standard Siddon’s projection. Furthermore, the iterative reconstruction results demonstrate that our algorithm could significantly improve both the reconstruction speed and quality compared with Siddon’s projection.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Andersen A, Kak A (1984) Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ARTalgorithm. Ultrason Imaging 6(1):81–94
Biguri A, Lindroos R, Bryll R et al (2020) Arbitrarily large tomography with iterative algorithms on multiple GPUs using the TIGRE toolbox. J Parallel Distr Com 146:52–63
Champley KM, Willey TM, Kim H et al (2022) Livermore tomography tools: accurate, fast, and flexible software for tomographic science. NDT & E Int 126:102595
Cheng K, Yu Y, Zhou H et al (2021) GPU fast restoration of non-uniform illumination images. J Real-Time Image Proc 18:75–83
Gao J, Liu Q, Zhou C et al (2021) An improved patch-based regularization method for PET image reconstruction. Quant Imaging Med Surg 11(2):556–570
Gomes L, Bellon O, Silva L (2014) 3D Reconstruction Methods for digital preservation of cultural heritage: a survey. Pattern Recogn Lett 50:3–14
Gordon R, Bender R, Herman G (1970) Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J Theor Biol 29(3):471–476
Ha S, Mueller K (2018) A look-up table-based ray integration framework for 2-D/3-D forward and back projection in X-ray CT. IEEE T Med Imaging 37(2):361–371
Harms J, Lei Y, Wang T et al (2019) Paired cycle-GAN-based image correction for quantitative cone-beam computed tomography. Med Phys 46(9):3998–4009
Herman G, Meyer L (1993) Algebraic reconstruction can be made computationally efficient. IEEE T Med Imaging 12(3):600–609
Joseph PM (1983) An improved algorithm for reprojecting rays through pixel images. IEEE T Med Imaging 1(3):192–196
Kohler T, Turbell H, Grass M (2000) Efficient forward projection through discrete data sets using tri-linear interpolation. Nuclear Science Symposium Conference Record, IEEE
Kretzler ME (2022) Novel Domains and Image Reconstruction Algorithms for Radially Sampled MRI Data. Dissertation, Case Western Reserve University
Laycock S, Bell G, Corps N et al (2015) Using a combination of micro–computed tomography, CAD and 3D printing techniques to reconstruct incomplete 19th-century cantonese chess pieces. ACM J Comput Cult He 7(4):1–6
Li X, Li Y, Chen P, Li F (2022) Combining convolutional sparse coding with total variation for sparse-view CT reconstruction. Appl Optics 61(6):C116–C124
Liu X, Ounifi H, Gherbi A et al (2019) A hybrid GPU-FPGA based design methodology for enhancing machine learning applications performance. J Ambient Intell Human Comput 11:2309–2323
Long Y, Fessler J, Balter J (2010) 3D forward and back-projection for X-ray CT using separable footprints. IEEE T Med Imaging 29(11):1839–1850
Luo G, Zhao N, Jiang W et al (2020) MRI reconstruction using deep Bayesian estimation. Magnetic resonance in medicine. Magn Reson Med 84(4):2246−2261
Maiza C, Rihani H, Rivas J et al (2019) A survey of timing verification techniques for multi-core real-time systems. ACM Comput Surv 52(3):1–38
Man BD, Basu S (2002) Distance-driven projection and backprojection. IEEE Nuclear Science Symp, Medical Imaging Conf
Man BD, Basu S (2004) Distance-driven projection and backprojection in three dimensions. Phy Med Biol 49(11):2463–2475
Mesquita J, Matela N, Oliveira N et al (2010) Choosing the ART relaxation parameter for Clear-PEM 2D image reconstruction. Comput Meth Prog Bio 98(2):183–190
Mueller K, Yagel R, Wheller J (1999) Fast implementations of algebraic methods for three-dimensional reconstruction from cone-beam data. IEEE T Med Imaging 18(6):538–548
Park J, Hwang D, Kim K et al (2018) Computed tomography super-resolution using deep convolutional neural network. Phys Med Biol 63(14):145011
Prakash J, Agarwal U, Yalavarthy P (2021) Multi GPU parallelization of maximum likelihood expectation maximization method for digital rock tomography data. Sci Rep 11:18536
Ramesh K, Thilagavathy A (2021) Reinforcement learning-based spatial sorting based dynamic task allocation on networked multicore GPU processors. J Ambient Intell Human Comput 12:9731–9738
Sakai M, Parajuli R, Kubota Y et al (2020) Improved iterative reconstruction method for Compton imaging using median filter. PLoS ONE 15(3):e0229366
Schubiger M, Banjac G, Lygeros J (2020) GPU acceleration of ADMM for large-scale quadratic programming. J Parallel Distr Com 144:55–67
Siddon R (1985) Fast calculation of the exact radiological path for a three-dimensional CT array. Med Phys 12(2):252–255
Wan X, Zhang F, Chu Q et al (2011) Three-dimensional reconstruction using an adaptive simultaneous algebraic reconstruction technique in electron tomography. J Struct Biol 175(3):277–287
Wang Z, Pan K, Du Z et al (2022) Improvements in Micro-CT Method for Characterizing X-ray Monocapillary Optics. Opt Commun 504:127474
Yu H, Wang G (2012) Finite detector based projection model for high spatial resolution. J X-Ray Sci Technol 20(2):229–238
Zeng G (2000) Unmatched projector/backprojector pairs in an iterative reconstruction algorithm. IEEE T Med Imaging 19(5):548–555
Zhang Y, Yu H (2018) Convolutional neural network based metal artifact reduction in x-ray computed tomography. IEEE T Med Imaging 37(6):1370–1381
Zhang X, Blaas J, Botha C et al (2012) Process for the 3D virtual reconstruction of a microcultural heritage artifact obtained by synchrotron radiation CT technology using open source and free software. J Cult Herit 13:221–225
Zhang S, Zhang D, Gong H, Ghasemalizadeh O, Wang G, Cao G (2014) Fast and accurate computation of system matrix for area integral model-based algebraic reconstruction technique. Opt Eng 53(3):113101–113109
Zhang S, Geng G, Cao G et al (2018) Fast projection algorithm for LIM-based simultaneous algebraic reconstruction technique and its parallel implementation on GPU. IEEE Access 6:23007–23018
Zhang S, Geng G, Zhao J (2019) Fast parallel image reconstruction for cone-beam FDK algorithm. Concurr Comp-Pract E 31(10):e4697
Zhang S, Zhang X, Tuo M et al (2022) Iterative image reconstruction based on Köhler’s forward projection. J Ambient Intell Human Comput. https://doi.org/10.1007/s12652-022-03716-0
Zhao H, Reader A (2002) Fast projection algorithm for voxel arrays with object dependent boundaries. IEEE Nuclear Science Symposium Conference Record 3:1490–1494
Acknowledgements
This work was supported by the National Natural Science Foundation of China (NSFC) (No. 61772421, No. 61572400, No. 61902317) and the Science and Technology Plan Program in Shaanxi Province of China (No. 2019JQ-166).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix 1
Variables and abbreviations
2D, two-dimensional.
3D, three-dimensional.
A, system matrix.
AIM, area integral model.
ART, algebraic reconstruction technique.
b, intercept of a line.
CSC, convolutional sparse coding.
CT, computed tomography.
d, horizontal interpolation coefficient.
DDM, distance driven model.
f, linear attenuation function.
i, row index of a pixel or voxel.
j, column index of a pixel or voxel.
k, layer index of a voxel.
L, slab intersection length.
LIM, line intersection model.
m, slope of a line.
MLEM, maximum-likelihood expectation–maximization.
MRI, magnetic resonance imaging.
N, total number of pixels.
NMA, normalized mean absolute.
NRMS, normalized root mean square.
OS-EM, Ordered-subset expectation–maximization.
p, projection data.
PET, positron emission tomography.
POCS, projection on convex sets.
proj, projection value.
s, number of elements of weight factor array.
SART, simultaneous ART.
SF, separable footprint.
TV, total variation.
v, vertical interpolation coefficient.
VIM, volume integral model.
λ, relaxation factor.
δ, pixel or voxel size.
Rights and permissions
About this article
Cite this article
Zhang, S., Zhang, Y., Tuo, M. et al. Fast algorithm for Joseph’s forward projection in iterative computed tomography reconstruction. J Ambient Intell Human Comput 14, 12535–12548 (2023). https://doi.org/10.1007/s12652-022-04324-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12652-022-04324-8