INCREMENTAL ALGORITHM - A NEW FAST BACKPROJECTION SCHEME FOR PARALLEL BEAM GEOMETRIES

In this paper, we propose a new fast backprojection scheme for parallel beam geometries, the Incremental algorithm, which performs backprojection on a ray-by-ray (beam-by-beam) basis in contrast with a pixel-by-pixel backprojection in the conventional algorithm. By restructuring a conventional backprojection algorithm, the interdependency of pixel computations (position and value) is transformed to a set of incremental relations for a beam, where a beam is a set of pixels enclosed by two adjacent rays in 2-D CT and a set of voxels enclosed by four adjacent rays in 3-D CT. This incremental backprojection algorithm should be distinguished from the incremental ray tracing algorithms in computer graphics in that it is not only to locate pixels within each beam, but also to compute pixel values by additions only. To minimize the overhead for searching for the next pixels, a searching flow technique has been developed to implement the first-and second-order incremental relations for 2-D and 3-D CT’s, respectively. The values of all pixels in each beam except the first pixel are computed with additions only, which is the key idea of the proposed backprojection scheme. To be compared to Shepp and Logan’s algorithm, the incremental algorithm has been implemented on two different machines. The implementation results show the superiority of our approach over the conventional algorithm. It is believed that the proposed incremental algorithm will significantly reduce backprojection time (reconstruction time) in real applications, and has a potential for efficient parallelization. © 1990 IEEE