Fast implementations of algebraic methods for three-dimensional reconstruction from cone-beam data

The prime motivation of this work is to devise techniques that make the algebraic reconstruction technique (ART) and related methods more efficient for routine clinical use, while not compromising their accuracy. Since most of the computational effort of ART is spent for projection/backprojection operations, we first seek to optimize the projection algorithm. Existing projection algorithms are surveyed and it is found that these algorithms either lack accuracy or speed, or are not suitable for cone-beam reconstruction. We hence devise a new and more accurate extension to the splatting algorithm, a well-known voxel-driven projection method. We also describe a new three-dimensional (3-D) ray-driven projector that is considerably faster than the voxel-driven projector and, at the same time, more accurate and perfectly suited for the demands of cone beam. We then devise caching schemes for both ART and simultaneous ART (SART), which minimize the number of redundant computations for projection and backprojection and, at the same time, are very memory conscious. We find that with caching, the cost for an ART projection/backprojection operation can be reduced to the equivalent cost of 1.12 projections. We also find that SART, due to its image-based volume correction scheme, is considerably harder to accelerate with caching. Implementations of the algorithms yield runtime ratios T_SART/T_ART between 1.5 and 1.15, depending on the amount of caching used.