The reconstruction problem in practical tomographic imaging systems is
recovery from samples of either the x-ray transform
(set of the line-integral projections) or the Radon transform
(set of integrals on planes) of an unknown object density
distribution. The method of choice for tomographic reconstruction is
filtered
backprojection (FBP), which uses a backprojection step.
This step is the computational bottleneck in the technique,
with computational requirements of O(N3) for an N x N pixel
image in two dimensions, and at least O(N4) for an N x N x N voxel image in
three
dimensions. We present a family of fast hierarchical tomographic
backprojection algorithms, which reduce the complexities to O(N2 log N)
and O(N3 log N), respectively. These algorithms employ a divide-and-conquer
strategy in the image domain, and rely on properties of the harmonic
decomposition of the Radon transform.
For image sizes typical in medical applications or airport baggage
security, this results in speedups by a factor of 50 or greater.
Such speedups are critical for next-generation real-time imaging systems.
This work was supported in part by NSF grants CCR 99-72980 and CCR 02-09203.
Copyright. All Rights Reserved.