Abstract
We present a MATLAB software package with efficient, robust, and flexible implementations of algebraic iterative reconstruction (AIR) methods for computing regularized solutions to discretizations of inverse problems. These methods are of particular interest in computed tomography and similar problems where they easily adapt to the particular geometry of the problem. All our methods are equipped with stopping rules as well as heuristics for computing a good relaxation parameter, and we also provide several test problems from tomography. The package is intended for users who want to experiment with algebraic iterative methods and their convergence properties. The present software is a much expanded and improved version of the package AIR Tools from 2012, based on a new modular design. In addition to improved performance and memory use, we provide more flexible iterative methods, a column-action method, new test problems, new demo functions, and—perhaps most important—the ability to use function handles instead of (sparse) matrices, allowing larger problems to be handled.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andersen, A. H., Kak, A. C.: Simultaneous algebraic reconstruction technique (SART): a superior implementation of the ART algorithm. Ultrason. Imaging 6, 81–94 (1984)
Andersen, M. S., Hansen, P. C.: Generalized row-action methods for tomographic imaging. Numer. Algorithms 67, 121–144 (2014). https://doi.org/10.1007/s11075-013-9778-8
Bertsekas, D. P.: Incremental proximal methods for large scale convex optimization. Math. Prog. 129, 163–195 (2011)
Björck, Å., Elfving, T.: Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations. BIT 19, 145–163 (1979)
Buzug, T. M.: Computed Tomography. Springer, Berlin (2008)
Censor, Y., Elfving, T.: Block-iterative algorithms with diagonally scaled oblique projections for the linear feasibility problem. SIAM J. Matrix Anal. Appl. 24, 40–58 (2002)
Censor, Y., Elfving, T., Herman, G. T., Nikazad, T.: On diagonally relaxed orthogonal projection methods. SIAM J. Sci. Comp. 30, 473–504 (2007)
Censor, Y, Gordon, D., Gordon, R.: Component averaging: an efficient iterative parallel algorithm for large sparse unstructured problems. Parallel Comput. 27, 777–808 (2001)
Cimmino, G.: Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari. La Ricerca Scientifica, XVI, Series II, Anno IX 1, 326–333 (1938)
Coban, S. B.: Sophiabeads datasets project codes, May 2017. Available online from: https://sophilyplum.github.io/sophiabeads-datasets
Coban, S. B., McDonald, S. A.: Sophiabeads dataset project, March 2015. Available online from: https://doi.org/10.5281/zenodo.16474
Dos Santos, I. T.: A parallel subgradient projections method for the convex feasibility problem. J. Comput. Appl. Math. 18, 307–320 (1987)
Elfving, T., Hansen, P. C., Nikazad, T.: Convergence analysis for column-action methods in image reconstruction. Numerical Algorithms (2016). https://doi.org/10.1007/s11075-016-0176-x. Erratum (Fig. 3 was incorrect), https://doi.org/10.1007/s11075-016-0232-6
Elfving, T., Hansen, P. C., Nikazad, T.: Semi-convergence properties of Kaczmarz’s method. Inverse Prob. 30 (2014). https://doi.org/10.1088/0266-5611/30/5/055007
Elfving, T., Hansen, P. C., Nikazad, T.: Semi-convergence and relaxation parameters for projected SIRT algorithms. SIAM J. Sci. Comput. 34, A2000–A2017 (2012). https://doi.org/10.1137/110834640
Elfving, T., Nikazad, T.: Properties of a class of block-iterative methods. Inverse Prob. 25, 115011 (2009). https://doi.org/10.1088/0266-5611/25/11/115011
Elfving, T., Nikazad, T.: Stopping rules for Landweber-type iteration. Inverse Prob. 23, 1417–1432 (2007). https://doi.org/10.1088/0266-5611/23/4/004
Elfving, T., Nikazad, T., Hansen, P. C.: Semi-convergence and relaxation parameters for a class of SIRT algorithms. Electron. Trans. Numer. Anal. 37, 321–336 (2010)
Gilbert, P.: Iterative methods for the three-dimensional reconstruction of an object from projections. J. Theor. Biol. 36, 105–117 (1972)
Gordon, R, Bender, R, Herman, G. T.: Algebraic reconstruction techniques (ART) for three-dimensional electron microscopy and X-ray photography. J. Theor. Biol. 29, 471–481 (1970). https://doi.org/10.1016/0022-5193(70)90109-8
Hansen, P. C.: Discrete Inverse Problems: Insight and Algorithms. SIAM, Philadelphia (2010)
Hansen, P. C., Kilmer, M. E., Kjeldsen, R. H.: Exploiting residual information in the parameter choice for discrete ill-posed problems. BIT Numer. Math. 46, 41–59 (2006)
Hansen, P. C., Nagy, J. G., Tigkos, K.: Rotational image deblurring with sparse matrices. BIT Numer. Math. 54, 649–671 (2014). https://doi.org/10.1007/s10543-013-0464-y
Hansen, P. C., Saxild-Hansen, M.: AIR Tools—a MATLAB package of algebraic iterative reconstruction methods. J. Comp. Appl. Math. 236, 2167–2178 (2012). https://doi.org/10.1016/j.cam.2011.09.039
Herman, G. T., Lent, A.: Iterative reconstruction algorithms. Comput. Biol. Med. 6, 273–294 (1976)
Hämarik, U., Tautenhahn, U.: On the monotone error rule for parameter choice in iterative and continuous regularization methods. BIT 41, 1029–1038 (2001)
Jensen, J. M., Jacobsen, B. H., Christensen-Dalsgaard, J.: Sensitivity kernels for time-distance inversion. Sol. Phys. 192, 231–239 (2000)
Jørgensen, J. S., Sidky, E. Y., Hansen, P. C., Pan, X.: Empirical average-case relation between undersampling and sparsity in X-ray CT. Inverse Problems and Imaging 9, 431–446 (2015). https://doi.org/10.3934/ipi.2015.9.431
Kaczmarz, S.: Angenäherte auflösung von Systemen linearer Gleichungen. Bulletin de l’Académie Polonaise des Sciences et Lettres A35, 355–357 (1937)
Klukowska, J., Davidi, R., Herman, G. T.: SNARK09—a software package for reconstruction of 2D images from 1D projections. Comput. Methods Programs Biomed. 110, 424–440 (2013). https://doi.org/10.1016/j.cmpb.2013.01.003. The software is available from https://www.dig.cs.gc.cuny.edu/software/snark09/index.php
Kuchment, P., Kunyansky, L.: Mathematics of thermoacoustic tomography. Euro. J. Applied Math. 19, 191–224 (2008)
Landweber, L.: An iteration formula for Fredholm integral of the first kind. Am. J. Math. 73, 615–624 (1951)
Natterer, F.: The Mathematics of Computerized Tomography. Reprinted by SIAM, Philadelphia (2001)
Palenstijn, W. J., Batenburg, K. J., Sijbers, J.: Performance improvements for iterative electron tomography reconstruction using graphics processing units (GPUs). J. Structural Biology 176, 250–253 (2011)
Perry, K., Reeves, S.: A practical stopping rule for iterative signal restoration. IEEE Trans. Signal Proces. 42, 1829–1833 (1994)
Rust, B. W., O’Leary, D. P.: Residual periodograms for choosing regularization parameters for ill-posed problems. Inverse Prob. 24 (2008). https://doi.org/10.1088/0266-5611/24/3/034005
Siddon, R. L.: Fast calculation of the exact radiological path for a three-dimensional CT array. Med. Phys. 12, 252–255 (1985)
Strohmer, T., Vershynin, R.: A randomized Kaczmarz algorithm for linear systems with exponential convergence. J. Fourier Anal. Appl. 15, 262–278 (2009)
Sørensen, H. H. B., Hansen, P. C.: Multicore performance of block algebraic iterative reconstruction methods. SIAM J. Sci. Comp. 36, C524–C546 (2014)
TIGRE: Tomographic iterative GPU-based reconstruction toolbox, available from https://github.com/CERN/TIGRE
van Aarle, W., Palenstijn, W. J., Cant, J., Janssens, E., Bleichrodt, F., Dabravolski, A., De Beenhouwer, J., Batenburg, K. J., Sijbers, J.: Fast and flexible X-ray tomography using the ASTRA toolbox. Opt. Express 24, 25129–25147 (2016). https://doi.org/10.1364/OE.24.025129. The software is available from https://www.astra-toolbox.com
van der Sluis, A., van der Vorst, H. A.: SIRT- And CG-type methods for the iterative solution of sparse linear least-squares problems. Linear Algebra Appl. 130, 257–303 (1990)
Vogel, C. R.: Computational Methods for Inverse Problems. SIAM, Philadelphia (2002)
Watt, D. W.: Column-relaxed algebraic reconstruction algorithm for tomography with noisy data. Appl. Opt. 33, 4420–4427 (1994)
Wright, S. J.: Coordinate descent algorithms. Math. Program., Ser. B 151, 3–34 (2015)
Acknowledgements
We thank Tommy Elfving for his continued help and support during this project.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work is a part of the project HD-Tomo funded by Advanced Grant No. 291405 from the European Research Council. Networking support was provided by the EXTREMA COST Action MP1207.
The work was carried out while the author Jakob Sauer Jørgensen was with the Department of Applied Mathematics and Computer Science, Technical University of Denmark.
Rights and permissions
About this article
Cite this article
Hansen, P.C., Jørgensen, J.S. AIR Tools II: algebraic iterative reconstruction methods, improved implementation. Numer Algor 79, 107–137 (2018). https://doi.org/10.1007/s11075-017-0430-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-017-0430-x
Keywords
- Algebraic iterative reconstruction
- ART methods
- SIRT methods
- Column-action methods
- Semi-convergence
- Stopping rules
- Tomographic imaging