A fast fan-beam backprojection algorithm based on efficient sampling

We introduce a fast algorithm to backproject fan-beam tomographic projections. For typical configurations of computed tomography scanners, the algorithm reduces the number of computations and actual runtimes by an order of magnitude. Similar to fast algorithms for the parallel-beam geometry, this algorithm is a divide-and-conquer method that aggregates the projections in a hierarchical manner. The computational speedup results from the use of sparse sampling grids to represent images that are comprised of a small number of projections that are close together in view-angle. In the parallel beam case these sparse (Cartesian) sampling grids were constructed by exploiting the projection slice theorem. Extending the parallel beam algorithms to fan-beam is a significant step because there is no equivalent to the projection-slice theorem for the fan-beam geometry. This was achieved using a novel analysis of fan-beam backprojection that characterizes the spatially-varying frequency content. This analysis, which we present here, allows for the construction and use of the sparse (non-Cartesian) sampling grids.