A fast and accurate decimation-in-angle hierarchical fan-beam backprojection algorithm

We introduce a fast algorithm for backprojecting images from tomographic fan-beam projections that aggregates the projections in a hierarchical structure and achieves a computational cost of O(N ² log P), when backprojecting an N × N pixel image from P projections. Like in the parallel-beam algorithm in [1], the images in the hierarchy are formed by the rotation and the adding together of other images made up of fewer projections. The low computational cost of the algorithm depends on the efficient sampling of the intermediate images in the hierarchy. Understanding the algorithm within the signal processing framework, a general scheme for sampling an image made up of projections of arbitrary geometries is introduced. While the algorithm is related to one by Nilsson [2], the Fourier domain understanding leads to a more efficient sampling scheme for the intermediate images.