zbMATH — the first resource for mathematics

Scaled projected-directions methods with application to transmission tomography. (English) Zbl 1457.90157
Summary: Statistical image reconstruction in X-ray computed tomography yields large-scale regularized linear least-squares problems with nonnegativity bounds, where the memory footprint of the operator is a concern. Discretizing images in cylindrical coordinates results in significant memory savings, and allows parallel operator-vector products without on-the-fly computation of the operator, without necessarily decreasing image quality. However, it deteriorates the conditioning of the operator. We improve the Hessian conditioning by way of a block-circulant scaling operator and we propose a strategy to handle nondiagonal scaling in the context of projected-directions methods for bound-constrained problems. We describe our implementation of the scaling strategy using two algorithms: TRON, a trust-region method with exact second derivatives, and L-BFGS-B, a linesearch method with a limited-memory quasi-Newton Hessian approximation. We compare our approach with one where a change of variable is made in the problem. On two reconstruction problems, our approach converges faster than the change of variable approach, and achieves much tighter accuracy in terms of optimality residual than a first-order method.
90C30 Nonlinear programming
90C90 Applications of mathematical programming
Full Text: DOI
[1] Ahn, S.; Fessler, JA; Blatt, D.; Hero, AO III, Convergent incremental optimization transfer algorithms: application to tomography, IEEE Trans Med Imaging, 25, 3, 283-296 (2006)
[2] Barzilai, J.; Borwein, JM, Two-point step size gradient methods, IMA J Numer Anal, 8, 1, 141-148 (1988) · Zbl 0638.65055
[3] Bertsekas, DP, Projected Newton methods for optimization problems with simple constraints, SIAM J Control Optim, 20, 2, 221-246 (1982) · Zbl 0507.49018
[4] Birgin, EG; Martínez, JM, Large-scale active-set box-constrained optimization method with spectral projected gradients, Comput Optim Appl, 23, 101-125 (2002) · Zbl 1031.90012
[5] Birgin, EG; Martínez, JM; Raydan, M., Spectral projected gradient methods: review and perspectives, J Stat Softw (2014)
[6] Bonettini, S.; Zanella, R.; Zanni, L., A scaled gradient projection method for constrained image deblurring, Inverse Probl, 25, 1, 015002 (2008) · Zbl 1155.94011
[7] Bonettini, S.; Landi, G.; Piccolomini, EL; Zanni, L., Scaling techniques for gradient projection-type methods in astronomical image deblurring, Int J Comput Math, 90, 1, 9-29 (2013) · Zbl 1278.68326
[8] Byrd, RH; Nocedal, J.; Schnabel, RB, Representations of quasi-Newton matrices and their use in limited memory methods, Math Program, 63, 1-3, 129-156 (1994) · Zbl 0809.90116
[9] Byrd, RH; Lu, P.; Nocedal, J.; Zhu, C., A limited memory algorithm for bound constrained optimization, SIAM J Sci Comput, 16, 5, 1190-1208 (1995) · Zbl 0836.65080
[10] Choi, K.; Wang, J.; Zhu, L.; Suh, T.; Boyd, S.; Xing, L., Compressed sensing based cone-beam computed tomography reconstruction with a first-order method, Math Program, 37, 9, 5113-5125 (2010)
[11] Conn, AR; Gould, NIM; Toint, PL, Testing a class of methods for solving minimization problems with simple bounds on the variables, Math Comput, 50, 182, 399-430 (1988) · Zbl 0645.65033
[12] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math Program A, 91, 201-213 (2002) · Zbl 1049.90004
[13] Erdoǧan, H.; Fessler, JA, Monotonic algorithms for transmission tomography, IEEE Trans Med Imaging, 18, 9, 801-814 (1999)
[14] Erdoǧan, H.; Fessler, JA, Ordered subsets algorithms for transmission tomography, Phys Med Biol, 44, 11, 2835-2851 (1999)
[15] Feldkamp, LA; Davis, LC; Kress, JW, Practical cone-beam algorithm, J Opt Soc Am (A), 1, 6, 612-619 (1984)
[16] Fessler, JA; Fritzpatrick, JM; Sonka, M., Statistical image reconstruction methods for transmission tomography, Handbook of medical imaging, chapter 1, 1-70 (2000), Bellingham: SPIE Press, Bellingham
[17] Golkar M (2013) Fast iterative reconstruction in X-ray tomography using polar coordinates. PhD thesis, École Polytechnique de Montréal
[18] Gould, NI; Orban, D.; Toint, PL, CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput Optim Appl, 60, 3, 545-557 (2015) · Zbl 1325.90004
[19] Goussard Y, Golkar M, Wagner A, Voorons M (2013) Cylindrical coordinate representation for statistical 3D CT reconstruction. In: Proceedings of international meeting on fully 3D image reconstruction in radiology and nuclear medicine, Lake Tahoe, CA, Jun, pp 138-141
[20] Hamelin B (2009) Accélération d’une Approche Régularisée de Reconstruction en Tomographie à Rayons X avec Réduction des Artéfacts Métalliques. PhD thesis, École Polytechnique de Montréal
[21] Hamelin, B.; Goussard, Y.; Dussault, J-P; Cloutier, G.; Beaudoin, G.; Soulez, G., Design of iterative ROI transmission tomography reconstruction procedures and image quality analysis, Med Phys, 37, 9, 4577-4589 (2010)
[22] Herman, GT, Fundamentals of computerized tomography: image reconstruction from projections (2009), Berlin: Springer, Berlin · Zbl 1280.92002
[23] Hestenes, MR; Stiefel, E., Methods of conjugate gradients for solving linear systems, J Res Natl Bur Stand (1952) · Zbl 0048.09901
[24] Hudson, HM; Larkin, RS, Accelerated image reconstruction using ordered subsets of projection data, IEEE Trans Med Imaging, 13, 4, 601-609 (1994)
[25] Jensen, TL; Jørgensen, JH; Hansen, PC; Jensen, SH, Implementation of an optimal first-order method for strongly convex total variation regularization, BIT Numer Math, 52, 2, 329-356 (2012) · Zbl 1256.65063
[26] Kim, D.; Ramani, S.; Fessler, JA, Combining ordered subsets and momentum for accelerated X-ray CT image reconstruction, IEEE Trans Med Imaging, 34, 1, 167-178 (2014)
[27] Kolehmainen, V.; Vanne, A.; Siltanen, S.; Jarvenpaa, S.; Kaipio, JP; Lassas, M.; Kalke, M., Parallelized Bayesian inversion for three-dimensional dental X-ray imaging, IEEE Trans Med Imaging, 25, 2, 218-228 (2006)
[28] Kolehmainen, V.; Vanne, A.; Siltanen, S.; Järvenpää, S.; Kaipio, JP; Lassas, M.; Kalke, M., Bayesian inversion method for 3d dental X-ray imaging, e & i Elektrotechnik und Informationstechnik, 124, 7-8, 248-253 (2007)
[29] Landi, G., A projected Newton-CG method for nonnegative astronomical image deblurring, Numer Algorithms, 48, 4, 279-300 (2008) · Zbl 1151.65053
[30] Lange, K.; Fessler, JA, Globally convergent algorithms for maximum a posteriori transmission tomography, IEEE Trans Image Process, 4, 10, 1430-1438 (1995)
[31] Lin, C-J; Moré, JJ, Newton’s method for large bound-constrained optimization problems, SIAM J Optim, 9, 4, 1100-1127 (1999) · Zbl 0957.65064
[32] McLaughlin M (2017) Méthodes sans factorisation pour la tomographie à rayons X en coordonnées cylindriques. Master’s thesis, École Polytechnique de Montréal, URL https://publications.polymtl.ca/2742
[33] Morales, JL; Nocedal, J., Remark on “Algorithm 778: L-BFGS-B: fortran subroutines for large-scale bound constrained optimization”, ACM Trans Math Softw (TOMS), 38, 1, 7 (2011) · Zbl 1365.65164
[34] Moré, JJ; Thuente, DJ, Line search algorithms with guaranteed sufficient decrease, ACM Trans Math Softw, 20, 3, 286-307 (1994) · Zbl 0888.65072
[35] Nesterov, YE, A method for solving the convex programming problem with convergence rate \(o(1/k^2)\), Dokl Akad Nauk SSSR, 269, 543-547 (1983)
[36] Nien, H.; Fessler, JA, Fast X-ray CT image reconstruction using a linearized augmented Lagrangian method with ordered subsets, IEEE Trans Med Imaging, 34, 2, 388-399 (2015)
[37] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math Comput, 35, 151, 773-782 (1980) · Zbl 0464.65037
[38] Noo F, Hahn K, Schöndube H, Stierstorfer K (2016) Iterative CT reconstruction using coordinate descent with ordered subsets of data. In: Medical imaging 2016: physics of medical imaging, vol 9783. International Society for Optics and Photonics, p 97834A. 10.1117/12.2217558
[39] Piccolomini, EL; Coli, V.; Morotti, E.; Zanni, L., Reconstruction of 3D X-ray CT images from reduced sampling by a scaled gradient projection algorithm, Comput Optim Appl, 71, 1, 171-191 (2018) · Zbl 1406.90118
[40] Pock T, Chambolle A (2011) Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In: International conference on computer vision. IEEE, pp 1762-1769. 10.1109/ICCV.2011.6126441 · Zbl 1255.68217
[41] Sauer, KD; Bouman, CA, A local update strategy for iterative reconstruction from projections, IEEE Trans Signal Process, SP-41, 2, 534-548 (1993) · Zbl 0825.92085
[42] Segars, WP; Mahesh, M.; Beck, TJ; Frey, EC; Tsui, BMW, Realistic CT simulation using the 4D XCAT phantom, Med Phys, 35, 8, 3800-3808 (2008)
[43] Sidky, EY; Jørgensen, JS; Pan, X., First-order convex feasibility algorithms for X-ray CT, Med Phys (2013)
[44] Thibaudeau, C.; Leroux, J-D; Fontaine, R.; Lecomte, R., Fully 3D iterative CT reconstruction using polar coordinates, Med Phys, 40, 11, 111904 (2013)
[45] Xu, Q.; Yang, D.; Tan, J.; Sawatzky, A.; Anastasio, MA, Accelerated fast iterative shrinkage thresholding algorithms for sparsity-regularized cone-beam CT image reconstruction, Med Phys, 43, 4, 1849-1872 (2016)
[46] Zheng, X.; Ravishankar, S.; Long, Y.; Fessler, JA, PWLS-ULTRA: an efficient clustering and learning-based approach for low-dose 3D CT image reconstruction, IEEE Trans Med Imaging, 37, 6, 1498-1510 (2018)
[47] Zhu, C.; Byrd, RH; Lu, P.; Nocedal, J., Algorithm 778. L-BFGS-B: fortran subroutines for large-scale bound constrained optimization, ACM Trans Math Softw, 23, 4, 550-560 (1997) · Zbl 0912.65057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.