Fast tomographic reconstruction via rotation-based hierarchical backprojection

We introduce a family of fast algorithms for tomographic backprojection in the parallel-beam geometry. The algorithms reduce the computational cost of backprojecting P projections onto an N × N pixel image from the conventional O(N²P) to O(N² log P). The new algorithms aggregate the projections in a hierarchical structure, with images in the hierarchy formed by the rotation and addition of other images made up of fewer projections. While these algorithms are related to existing fast algorithms, this work places them within the signal processing framework, providing a systematic means to optimize and adjust the trade-off between computational cost and accuracy. Rotations are performed separably in order that higher-order interpolators may be used with low computational cost. The same ideas are applied to create a tomographic projection algorithm, which computes projections of an N × N pixel image onto P view-angles at a cost of O(N² log P).