A full multigrid technique to accelerate an ART scheme for tomographic image reconstruction

Prümmer M, Köstler H, Hornegger J, Rüde U (2005)

Publication Language: English

Publication Type: Conference contribution, Conference Contribution

Publication year: 2005

Original Authors: Prümmer Marcus, Köstler Harald, Hornegger Joachim, Rüde Ulrich

Publisher: SCS Publishing House e.V.

City/Town: Erlangen

Pages Range: 632-637

Conference Proceedings Title: Frontiers in Simulation

Event location: Erlangen DE

URI: http://www5.informatik.uni-erlangen.de/Forschung/Publikationen/2005/Pruemmer05-AFM.pdf

Open Access Link: https://www10.cs.fau.de/publications/papers/2005/Pruemmer_Koestler_ASIM05.pdf


Tomographic reconstruction is the process of reconstructing a 3-D object or its cross section from several of its 2-D projection images. The object is illuminated by a cone-beam of Xrays, where the signal is attenuated by the object. Due to its speed filtered back projection (FBP) still is state-of-the-art in 3-D reconstruction for clinical use where time matters. But considering the accuracy and number of projections required for FBP, as shown in [1], an algebraic reconstruction technique (ART) is superior. Our current focus lies on 3-D angiography using C-arm systems. But this new approach should also be applicable on many real world reconstruction problems. Within ART, the object is represented as a linear combination of basis functions, typically voxels, with some unknown coefficients. The observations can also be expressed as a linear combination of these coefficients. This results in a linear system of equations with a sparse system matrix, because each X-ray intensity observation is influenced only by the pixels on the corresponding beam path. If enough measures are available, one has an over-determined system, which is solved in the leastsquares sense. On the other hand, if there are not enough measures in a region to determine the coefficient values, one is faced with an under-determined problem. In this case, one solves the regularized version of the problem which supplies the additional constraints. Due to the large number of unknowns in real applications, an iterative instead of a direct linear solver has to be used. Techniques such as Kaczmarz’s algorithm or CAV (component averaging) are currently used as iterative solvers, but for large problems, their computational costs are high. In addition, these solvers tend to improve the solution very much only in the first few iterations. An efficient ART is therefore essential to compete with FBP successfully. In this paper we think of these iterative methods as smoothers within a multigrid solver. It should be noted that because of the structure of the system matrix, the standard multigrid theory is not applicable here. The additional ingredients of the multigrid method are coarser versions of the problem on different levels, interpolation and restriction operators. For the coarser problems, we uniformly reduce the number of rays and the number of voxels while keeping the overall volume constant. Furthermore, we use trilinear interpolation and full weighting as restriction. Full multigrid is then accomplished by starting on each level the V-cycle with an initial guess for the solution that is interpolated from the next coarser level. Our experiments show that we are able to reduce the relative error to a certain size by less Kaczmarz smoothing steps on the finest level when using the multigrid method instead of the common Kaczmarz algorithm. We present results for real medical datasets and compare our multigrid method with Kaczmarz and CAV on a phantom. One of the next steps will be to detail the theory for our multigrid method in order to get estimates for the asymptotic convergence rates.

Authors with CRIS profile

Related research project(s)

How to cite


Prümmer, M., Köstler, H., Hornegger, J., & Rüde, U. (2005). A full multigrid technique to accelerate an ART scheme for tomographic image reconstruction. In Hülsemann Frank, Kowarschik Markus, Rüde Ulrich (Eds.), Frontiers in Simulation (pp. 632-637). Erlangen, DE: Erlangen: SCS Publishing House e.V..


Prümmer, Marcus, et al. "A full multigrid technique to accelerate an ART scheme for tomographic image reconstruction." Proceedings of the Simulationstechnique 18th Symposium in Erlangen 2005, Erlangen Ed. Hülsemann Frank, Kowarschik Markus, Rüde Ulrich, Erlangen: SCS Publishing House e.V., 2005. 632-637.

BibTeX: Download