Authors O. Yu. Voronkov, D. G. Kovtun, S. A. Sinyutin
Month, Year 03, 2018 @en
Index UDC 004.421
Abstract The paper describes a method for simulating the X-ray path through the voxel space based on the Xiaolin Wu algorithm for vector lines rasterizing with smoothing. The proposed method is designed to obtain three-dimensional ray sums and a system matrix in the design of a medical device for tomosynthesis having limited viewing angles of the projected object. General design of the X-ray device having several modes of operation including the mode of tomosynthesis is described, its technical characteristics are given. The advantage of the method before the built-in capabilities of the MatLab software package and before the previously created algorithm without anti-aliasing for the same device is explained. The general principles of the proposed algorithm for constructing the rays path in the space of voxels are outlined, and a block diagram is shown. The results of the computational experiment in the MatLab environment for constructing the ray path through a mathematical phantom, two-dimensional and three-dimensional ray sums are shown. The concept of the system matrix necessary for the functioning of a certain class of tomographic reconstruction algorithms is explained. The urgency of the work consists in the development of tomosynthesis as a cheaper, quicker and safer method in comparison with the full tomography, while there are no ready-made software products for the intrinsic problems solution, so it becomes necessary to develop special algorithms and programs oriented to the posed problem. The scientific novelty of the work lies in the application of the two-dimensional Xiaolin’s line algorithm from the field of computer graphics to the field of radiography by expanding this algorithm to a three-dimensional version taking into account all the features of the medical device design.

Download PDF

Keywords Tomography; tomosynthesis; ray sums; system matrix; computer modeling; limited angles of removal; Xiaolin’s line algorithm.
References 1. Voronkov O.Yu., Sinyutin S.A. Metod polucheniya luchevykh summ pri modelirovanii ustanovok dlya tomosinteza na osnove algoritma Brezenhema [A method of obtaining radiation amounts in modeling systems for tomosynthesis-based algorithm Bresenham], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 6 (191), pp. 189-200.
2. Voronkov O.Yu., Sinyutin S.A. Ispol'zovanie algoritma Brezenhema dlya polucheniya luchevykh summ pri modelirovanii tomograficheskikh ustanovok [The use of the algorithm of Brezenchem to obtain beam sums in the simulation of tomographic installations], Materialy Vserossijskoy nauchno-tekhnicheskoy konferencii s mezhdunarodnym uchastiem «Komp'yuternye i informacionnye tekhnologii v nauke, inzhenerii i upravlenii (KomTekh-2017)» [Materials of the all-Russian scientific and technical conference with international participation "Computer and information technologies in science, engineering and management (Comtech-2017)"]. Taganrog: Izd-vo YuFU, 2017, pp. 38-43.
3. Hofer M. Komp'yuternaya tomografiya. Bazovoe rukovodstvo [Computer tomography. A basic guide]. 2nd ed. Moscow: Med. lit., 2008, 224 p.
4. Ternovoy S.K., Abduraimov A.B., Fedotenkov I.S. Komp'yuternaya tomografiya: ucheb. posobie [Computed tomography: a textbook]. Moscow: GEHOTAR-Media, 2008, 176 p.
5. Gubareni N.M. Vychislitel'nye metody i algoritmy malorakursnoy komp'yuternoy tomografii [Computational methods and algorithms of low-competition computed tomography]. Kiev: Naukova dumka, 1997, 328 p.
6. Natterer F. Matematicheskie aspekty komp'yuternoy tomografii [Mathematical aspects of computed tomography]: transl. from engl. Moscow: Mir, 1990, 288 p.
7. Avinash C. Kak, Malcolm Slaney. Principles of Computerized Tomographic Imaging. New York: The Institute of Electrical and Electronics Engineers, Inc., 337 p.
8. Lihachev A.V. Algoritmy tomograficheskoн rekonstrukcii: ucheb. posobie [The tomographic reconstruction algorithms: a tutorial]. Novosibirsk: NIU-NGU, 2013, 117 p.
9. Izuchenie metodov komp'yuternoн tomografii. Metod. ukazaniya k lab. rab. po kursu «Fizicheskie osnovy polucheniya informacii» [Study of methods of computed tomography. Guidelines for laboratory work on the course "Physical basis of information"]. Available at:
10. Edwin L. Dove. Notes on Computerized Tomography. Available at: edu/courses/TBMT02/ct/CTNotes.pdf.
11. Moskvitin E.V. Tomograficheskaya rekonstrukciya tryohmernogo ob"ekta na baze metodov tomosinteza [Tomographic reconstruction of a three-dimensional object based on tomosynthesis methods], Izvestiya Tomskogo politekhnicheskogo universiteta [Bulletin of the Tomsk Polytechnic University], 2002, Vol. 305, Issue 5, pp. 31-35.
12. Noda Takesi. Ustroystvo dlya obrabotki izobrazheniya, sposob obrabotki izobrazheniya i sreda dolgovremennogo hraneniya informacii [A device for processing image, method of image processing and the environment long-term storage of information]. Patent RF No. 2510080, 21.11.2011.
13. Tsutomu Gomi, Hiroshi Hirano, Masahiro Nakajima, Tokuo Umeda. X-ray digital linear tomosynthesis imaging. Available at: PaperInformation.aspx? PaperID=5640.
14. Yulia Levakhina. Three-Dimensional Digital Tomosynthesis: Iterative Reconstruction, Artifact Reduction and Alternative Acquisition Geometry. Springer Vieweg, 2014, 192 p.
15. Ingrid Reiser, Stephen Glick. Tomosynthesis Imaging. CRC Press, Taylor & Francis Group, 2014, 257 p.
16. Hiroshi Hirano. Utility of Tomosynthesis with a Flat-panel Detector – Comparison with MSCT, Medical Now, 2005, Vol. 57, pp. 16-23.
17. Grant D.G. Tomosynthesis: a three-dimensional radiographic imaging technique, IEEE Trans Biomed Eng., 1972, No. 19, pp. 20-27.
18. D'yakonov V.P. MatLab. Polnyy samouchitel' [MatLab. Complete tutorial]. Moscow: DMK Press, 2012, 768 p.
19. Porshnev S.V. Komp'yuternoe modelirovanie fizicheskikh processov v pakete MatLab [Computer simulation of physical processes in MatLab package]. Moscow: Goryachaya liniya-Telekom, 2003, 592 p.
20. Sizikov V.S. Obratnye prikladnye zadachi i MatLab: ucheb. posobie [The reverse applied problems and MatLab: a tutorial]. Saint Petersburg: Izd-vo «Lan'», 2011, 256 p.
21. Artyom M. Grigoryan, Merughan M. Grigoryan. Image Processing: Tensor Transform and Discrete Tomography with MATLAB. CRC Press, Taylor & Francis Group, 2013, 466 p.
22. Zhuravel' I.M. Kratkiy kurs teorii obrabotki izobrazheniy [A short course in image processing theory]. Available at:
23. Daniil Basmanov. Brezenkhem i U na strazhe diagonaley [Bresenham, and the guardian of the diagonals]. Available at:
24. Algoritm Brezenkhema [Algorithm Bresenham]. Available at: wiki/Algoritm_Brezenhehma.
25. Algoritm Vu [Wu's Algorithm]. Available at:
26. Andersen A.H., Kak A.C. Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm, Ultrasonic imaging, 1984, Vol. 6, No. 1, pp. 81-94.
27. Yu X. et al. cuART: Fine-Grained Algebraic Reconstruction Technique for Computed Tomography Images on GPUs, Cluster, Cloud and Grid Computing (CCGrid), 2016 16th IEEE/ACM International Symposium on. IEEE, 2016, pp. 165-168.

Comments are closed.