Fast X-Ray Sum Calculation Algorithm for Computed Tomography Problem

In iterative methods of computed tomography, each iteration requires to calculate a multitude of sums over values for the current reconstruction approximation. Each summable set is an approximation of a straight line in the three-dimensional space. In a cone-beam tomography, the number of sums to be calculated on each iteration has a cubic dependence on the linear size of the reconstructed image. Direct calculation of these sums requires the number of summations in a quartic dependence on the linear image size, which limits the performance of the iterative methods. The novel algorithm proposed in this paper approximates the three-dimensional straight lines using dyadic patterns, and, using the adjustment of precalculation and inference complexity similar to the adjustment employed in the Method of Four Russians, provides the calculation of these sums with a sub-quartic dependence on the linear size of the reconstructed image.

Keywords

computed tomography; algebraic reconstruction; fast Radon transform; fast Hough transform; Method of Four Russians.

References

1. Rubin G.D. Computed Tomography: Revolutionizing the Practice of Medicine for 40 Years. Radiology, 2014, vol. 273, no. 2, pp. 45-74. DOI: 10.1148/radiol.14141356
2. Kharchenko V.P., Glagolev N.A. Renthenovskaya kompyuternaya tomografiya v diagnostike zabolevaniy lyogkih i sredosteniya [X-Ray Computed Tomography in the Diagnosis of Diseases of The Lungs and Mediastinum]. Moscow, Medika, 2005. (in Russian)
3. Smelkina N.A., Kolsanov A.V., Chaplygin S.S., Zelter P.M., Khramov A.G. Pulmonary Emphysema Recognition be CT Scan. Computer Optics, 2017, vol. 41, no. 5, pp. 726-731. (in Russian) DOI: 10.18287/2412-6179-2017-41-5-726-731
4. De Chiffre L., Carmignato S., Kruth P., Schmitt R., Weckenmann A. Industrial Applications of Computed Tomography. CIRP Annals. Manufacturing Technology, 2014, vol. 63, no. 2, pp. 655-677. DOI: 10.1016/j.cirp.2014.05.011
5. Nikolaev D., Gladkov A., Chernov T., Bulatov K. Diamond Recognition Algorithm Using Two-Channel X-Ray Radiographic Separator. The International Society for Optical Engineering, 2015, vol. 9445, article ID: 944507, 10 p. DOI: 10.1117/12.2181204
6. Krivoshhokov S.N., Kochnev A.A. Application Experience of Computed Tomography to Study the Properties of Rocks. Journal of Petroleum and Mining Engineering, 2013, vol. 12, no. 6, pp. 32-42. (in Russian) DOI: 10.15593/2224-9923/2013.6.4
7. Cunningham J.A., Rahman I.A., Lautenschlager S., Rayfield E.J., Donoghue P.C.J. A Virtual World of Paleontology. Trends in Ecology and Evolution, 2014, vol. 29, no. 6, pp. 347-357. DOI: 10.1016/j.tree.2014.04.004
8. Kak A.C, Slaney M. Principles of Computerized Tomographic Imaging. N.Y., IEEE Press, 2001. DOI: 10.1137/1.9780898719277
9. Natterer F. The Mathematics of Computerized Tomography. Stuttgart, John Wiley and Sons, 2001. DOI: 10.1137/1.9780898719284
10. Simonov E.N., Avramov M.V., Avramov D.V. Comparison of 3D Reconstruction Algorithm in X-Ray Computed Tomography. Bulletin of the South Ural State University. Series: Computer Technologies, Automatic Control, Radio Electronics, 2017, vol. 17, no. 2, pp. 24-32. (in Russian) DOI: 10.14529/ctcr170202
11. Gordon R. A Tutorial on Art (Algebraic Reconstruction Techniques). IEEE Transactions on Nuclear Science, 1974, vol. 21, no. 31974, pp. 78-93. DOI: 10.1109/TNS.1974.6499238
12. Beister M., Kolditz D., Kalender W. A. Iterative Reconstruction Methods in X-ray CT. Physica Medica, 2012, vol. 28, no. 2, pp. 94-108. DOI: 10.1016/j.ejmp.2012.01.003
13. Vatscuk A.V., Ingacheva A.S., Chukalina M.V. Algebraic Methods for Tomography Problem. Sensory Systems, 2018. vol. 32, no. 1, pp. 83-91. (in Russian) DOI: 10.7868/S0235009218010122
14. Saha S., Tahtali M., Lambert A., Pickering M. Novel Algebraic Reconstruction Technique for Faster and Finer CT Reconstruction. Computer Vision, Image Analysis and Processing, 2013, article ID: 878307, 6 p. DOI: 10.1117/12.2011073
15. Hara A.K., Paden R.G., Silva A.C., Kujak J.L., Lawder H.J., Pavlicek W. Iterative Reconstruction Technique for Reducing Body Radiation Dose at CT: Feasibility Study. American Journal of Roentgenology, 2009, vol. 193, no. 3, pp. 764-771. DOI: 10.2214/AJR.09.2397
16. Buzmakov A., Nikolaev D., Chukalina M., Schaefer G. Efficient and Effective Regularised Art for Computed Tomography. 33rd Annual International Conference of the IEEE EMBS. Boston. Massachusetts USA, 2011, pp. 6200-6203. DOI: 10.1109/IEMBS.2011.6091531
17. Kulchin Yu.N., Notkin B.S., Sedov V.A. Neuro-Iterative Algorithm of Tomographic Reconstruction of the Distributed Physical Fields in the Fibre-Optic Measuring Systems. Computer Optics, 2009, vol. 33, no. 4, pp. 446-455. (in Russian)
18. Pan T., Lee T.-Y., Rietzel E., Chen. G.Y. 4D-CT imaging of a Volume Influenced by Respiratory Motion on Multi-Slice CT. Medical physics, 2004, vol. 31, no. 2, pp. 333-340. DOI: 10.1118/1.1639993
19. Scherl H., Kowarschik. M., Hofmann. H.G., Keck B., Hornegger. J. Evaluation of State-of-the-Art Hardware Architectures for Fast Cone-Beam CT Reconstruction. Parallel Computing, 2012, vol. 38, no. 3, pp. 111-124. DOI: 10.1016/j.parco.2011.10.004
20. Prun V.E., Buzmakov A.V, Nikolaev D.P., Chukalina M.V., Asadchikov V.E. A Computationally Efficient Version of the Algebraic Method for Computer Tomography. Automation and Remote Control, 2013, vol. 74, no. 10, pp. 1670-1678. DOI: 10.1134/S000511791310007X
21. Ershov E.I., Terekhin A.P., Nikolaev D.P. Generalization of the Fast Hough Transform for Three-Dimensional Images. Journal of Communications Technology and Electronics, 2018, vol. 63, no. 6, pp. 626-636. DOI: 10.1134/S1064226918060074
22. Kotov A.A., Konovalenko I.A., Nikolaev D.P. Tracking of Objects Containing Multiple Concentric Arcs in a Video Stream, Optimized with Fast Hough Transform. Information Technologies and Computational Systems, 2015, vol. 1, pp.56-68. (In Russian)
23. Donoho D.L., Levi O. Fast X-Ray and Beamlet Transforms for Three-Dimensional Data. Modern Signal Processing, 2003, vol. 46, pp. 79-116.
24. Arlazarov V.L., Dinits E.A., Kronrod M.A., Farajev I.A. On the Efficient Construction of a Transitive Closure of a Direct Graph. Reports of Academy of Science USSR, 1970, vol. 194, no. 3, pp. 487-488.
25. Brooks R.A., Chiro G. Beam Hardening in X-Ray Reconstructive Tomography. Physics in medicine and biology, 1976, vol. 21, no. 3, pp. 390-398. DOI: 10.1088/0031-9155/21/3/004
26. Shipeng Xie, Wenqin Zhuang, Baosheng Li, Peirui Bai, Wenze Shao, Yubing Tong. Blind Deconvolution Combined with Level Set Method for Correcting Cupping Artifacts in Cone Beam CT. Medical Imaging, 2017, vol. 10133, article ID: 101331Z, 5 p. DOI: 10.1117/12.2254049
27. Ingacheva A, Chukalina M. Mathematical Problems in Engineering, 2019, vol. 2019, article ID: 1405365, 11 p. DOI: 10.1155/2019/1405365
28. Prun V.E., Buzmakov A.V., Chukalina M.V. X-Ray Tomography in Polychromatic Case: Utilizing the Multicomponent Object Structure in the Reconstruction Method. Crystallography Reports, 2019, vol. 64, no. 1, pp. 185-190. DOI: 10.1134/S1063774519010218