Medical Imaging Seminar: Fast Hierarchical Algorithms for Tomography

Computer Tomography is the primary non invasive means for examining the internal structure of the human body. The revolutionary nature of this imaging technology was recognized by the 1979 Nobel Prize in Medicine. Tomographic reconstruction underlies nearly all diagnostic imaging modalities, including x-ray computed tomography (CT), positron emission tomography, single photon emission tomography, and certain acquisition methods for magnetic resonance imaging. It is also widely used for nondestructive evaluation in manufacturing, and more recently for airport baggage security. The reconstruction problem in tomography is recovery (inversion) from samples of either the x-ray transform (set of the line-integral projections) or the Radon transform (set of integrals on hyperplanes) 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(N^3) for an NxN pixel
image in two dimensions, and at least O(N^4) for an NxNxN voxel image in three dimensions. We present a family of fast hierarchical tomographic backprojection algorithms, which reduce the complexities to O(N^2 log N) and O(N^3 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.