Scalable Regularized Tomography

X-ray computerized tomography (CT) and other related imaging modalities, such as positron emission tomography (PET), are notorious for their excessive computational demands. While the earliest algorithms in tomography, such as filtered backprojection (FBP), are now trivial in two-dimensions and scalable in three-dimensions due to their ``embarassingly parallel'' nature, the more noise-resistant probabilistic tomography methods are still prohibitive, especially in three-dimensions and at high resolutions. In this project we are studying a new class of algorithms in which probabilistic tomography becomes ``embarassingly parallel'' as well.

To understand how, recall that tomographs are produced by converting observed projections into an image. For example, in X-ray CT, X-ray beams directed at a patient are attenuated to varying degrees by the different materials within the body. On the opposite side of the patient, the attenuated beams are detected as with an array of measurements called a projection. Such projections are produced at many different angles around the patient.

In reality these measurements are noisy, and the relative noise level even depends on the amount of attenuation. In particular, projections through dense materials such as bone and especially metal have lower signal-to-noise ratio than projections through only flesh or water. Coping with the large and spatially-varying fluctuations in the number of detected photons often requires a probabilistic smoothing technique (also known as regularization) to improve the image. The basic idea of regularization is to infer a smooth image whose simulated projections approximate the observed (but noisy) projections. The difficulty is that the standard regularization specifies the two basic constraints in different domains: (1) smoothness is an image property specified in the image domain, while (2) closeness to the data is determined in the projection domain. Enforcing these constraints computationally requires a large sparse matrix-vector multiplication (projection or backprojection) to convert between the two domains during processing. This multiplication places heavy demands on system memory and memory bandwidth, and requires significant network usage when parallelized (a global summation).

The novelty in our formulation of regularized tomography is in the analytical conversion of the smoothness constraint itself from the image to the projection domain, before any computations begin. Thus the most difficult part of the computation takes place entirely in the projection domain. The standard (and expensive) practice of numerically iterating between the image and projection domains is avoided. Another benefit of the conversion of the smoothness constraint to the projection domain is the decoupling of a large system of regularization equations into many small systems of simpler regularization equations. The difficult computation of regularized tomography becomes ``embarassingly parallel'', so that latency tolerant and ideally scalable parallel computations are possible, as our results show in 2-d.


Before applying scalable decoupled regularization (click on image to zoom):

This is a CT scan of a human hip with a metal hip implant shown on the left. Observe the streak artifacts emanating from the implant.

After applying scalable decoupled regularization (click on image to zoom):

This is the result of our algorithm. Note that the streaking has been reduced without a significant increase in blur.


This material is based upon work supported by the National Science Foundation under Grant No. 0305719. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.