A Fast Shear-Like Divergent-Beam Backprojection Algorithm

We introduce a fast algorithm for backprojecting images from 2D fan-beam tomographic projections. It aggregates the projections in a hierarchical structure and reduces the computational cost from O(N³) to O(N² log N), when backprojecting an NtimesN pixel image from O(N) projections. Unlike our previous O(N² log N) rotation-based algorithm, this new algorithm is based on a separable image transformation called a warped shear that is implementable by fractional shifts. The key innovation of this algorithm is its implementation in a hybrid space-frequency domain. The warped shearing interpretation of fan-beam backprojection allows for intermediate images throughout all levels of the algorithm to be maintained in one space index and one frequency index. This allows for several optimizations including the implementation of high-quality shears at no extra computational cost, the O(N) parallelization of the algorithm, and efficient memory access. The algorithm can be extended to 3D geometries including helical cone-beam.