Parallel ART for image reconstruction in CT using processor arrays

Abstract

Algebraic Reconstruction Technique (ART) is a widely-used iterative method for solving sparse systems of linear equations. This method (originally due to Kaczmarz) is inherently sequential according to its mathematical definition since, at each step, the current iterate is projected toward one of the hyperplanes defined by the equations. The main advantages of ART are its robustness, its cyclic convergence on inconsistent systems, and its relatively good initial convergence. ART is widely used as an iterative solution to the problem of image reconstruction from projections in computerized tomography (CT), where its implementation with a small relaxation parameter produces excellent results. It is shown that for this particular problem, ART can be implemented in parallel on a linear processor array. Reconstructing an image of n pixels from Θ(n) equations can be done on a linear array of processors with optimal efficiency (linear speedup) and O(n/p) memory for each processor. The parallel technique can be applied to various geometric models of image reconstruction, as well as to 3D reconstruction with spherically symmetric volume elements, using a 2D rectangular mesh-connected array of processors.

Keywords:

• ART
• Computerized tomography
• Kaczmarz
• Image reconstruction
• Linear equations
• Sparse systems

Acknowledgements

The author is indebted to the anonymous reviewers whose comments led to a much-improved presentation.