ALGORITHM: Scalable Algorithms for Regularized Tomography via Decoupling

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

X-ray computerized tomography (CT) and related imaging modalities (e.g., PET) are notorious for their excessive computational demands. While early CT algorithms such as filtered backprojection are now trivial in two-dimensions and scalable in three-dimensions, the more noise-resistant probabilistic methods such as regularized tomography are still prohibitive. The basic idea of regularization is to compute a smooth image whose simulated projections (line integrals) approximate the observed (but noisy) X-ray projections. The computational expense in previous methods stems from explicitly applying a large sparse projection matrix (to compute line integrals of the image) and its transpose to enforce these smoothness and data approximation constraints during each of many iterations of the algorithm. We propose to study a new formulation of regularized tomography in which the smoothness constraint is analytically transformed from the image to the projection domain, before any computations begin. As a result, iterations take place entirely in the projection domain, avoiding the repeated sparse matrix-vector products. A more surprising benefit is the decoupling of a large system of regularization equations into many small systems of simpler equations. The computation thus becomes ``embarassingly parallel'', so that latency tolerant and ideally scalable parallel computations are possible, as our preliminary results show in 2-d. We propose to apply this technique to modalities other than CT, to implement it in three-dimensions, and to embellish the probability models. Further, the network-friendly nature of this method will allow us to study the feasibility of harnessing the increasingly wasted desktop compute power in a typical hospital. We see decoupled regularization as an exciting development in tomography, benefiting society by providing images to doctors, patients, and scientists with fewer artifacts, at higher resolutions, and with greater interactivity.