×

Total variation superiorized conjugate gradient method for image reconstruction. (English) Zbl 1430.94040

Inverse Probl. 34, No. 3, Article ID 034001, 26 p. (2018); erratum ibid. 36, No. 8, Article ID 089601, 2 p. (2020).
Summary: The conjugate gradient (CG) method is commonly used for the relatively-rapid solution of least squares problems. In image reconstruction, the problem can be ill-posed and also contaminated by noise; due to this, approaches such as regularization should be utilized. Total variation (TV) is a useful regularization penalty, frequently utilized in image reconstruction for generating images with sharp edges. When a non-quadratic norm is selected for regularization, as is the case for TV, then it is no longer possible to use CG. Nonlinear CG is an alternative, but it does not share the efficiency that CG shows with least squares and methods such as fast iterative shrinkage-thresholding algorithms (FISTA) are preferred for problems with TV norm. A different approach to including prior information is superiorization.
In this paper it is shown that the conjugate gradient method can be superiorized. Five different CG variants are proposed, including preconditioned CG. The CG methods superiorized by the total variation norm are presented and their performance in image reconstruction is demonstrated. It is illustrated that some of the proposed variants of the superiorized CG method can produce reconstructions of superior quality to those produced by FISTA and in less computational time, due to the speed of the original CG for least squares problems.
In the Appendix we examine the behavior of one of the superiorized CG methods (we call it S-CG); one of its input parameters is a positive number \(\varepsilon\). It is proved that, for any given \(\varepsilon\) that is greater than the half-squared-residual for the least squares solution, S-CG terminates in a finite number of steps with an output for which the half-squared-residual is less than or equal to \(\varepsilon\). Importantly, it is also the case that the output will have a lower value of TV than what would be provided by unsuperiorized CG for the same value \(\varepsilon\) of the half-squared residual.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65J20 Numerical solutions of ill-posed problems in abstract spaces; regularization
68U10 Computing methodologies for image processing
90C20 Quadratic programming
90C52 Methods of reduced gradient type
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Björck, A., Numerical Methods for Least Squares Problems, (1996), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 0847.65023
[2] Barrett, H. H.; Myers, K. J., Foundations of Image Science, (2004), Hoboken, NJ: Wiley, Hoboken, NJ
[3] Kim, K.; Shevlyakov, G., Why Gaussianity?, IEEE Signal Process. Mag., 25, 102-113, (2008) · doi:10.1109/MSP.2007.913700
[4] Vogel, C. R., Computational Methods for Inverse Problems, (2002), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1008.65103
[5] Bovik, A. C., Handbook of Image and Video Processing, (2000), San Diego, CA: Academic, San Diego, CA · Zbl 0967.68155
[6] Romberg, J. K., Imaging via compressive sampling, IEEE Signal Process. Mag., 25, 14-20, (2008) · doi:10.1109/MSP.2007.914729
[7] Dai, Y.; Han, J.; Liu, G.; Sun, D.; Yin, H.; Yuan, Y., Convergence properties of nonlinear conjugate gradient methods, SIAM J. Optim., 10, 345-358, (2000) · Zbl 0957.65062 · doi:10.1137/S1052623494268443
[8] Hager, W.; Zhang, H., A survey of nonlinear conjugate gradient methods, Pac. J. Optim., 2, 35-58, (2006) · Zbl 1117.90048
[9] Rockafellar, R. T.; Wets, R. J B., Variational Analysis, (1998), Berlin: Springer, Berlin · Zbl 0888.49001
[10] Zhao, F.; Noll, D. C.; Nielsen, J-F; Fessler, J. A., Separate magnitude and phase regularization via compressed sensing, IEEE Trans. Med. Imaging, 31, 1713-1723, (2012) · doi:10.1109/TMI.2012.2196707
[11] Zibetti, M. V W.; Pipa, D. R.; De Pierro, A. R., Fast and exact unidimensional L2-L1 optimization as an accelerator for iterative reconstruction algorithms, Digit. Signal Process., 48, 178-187, (2016) · doi:10.1016/j.dsp.2015.09.009
[12] Combettes, P. L.; Pesquet, J. C.; Burachik, H. H., Proximal splitting methods in signal processing, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, 185-212, (2011), New York: Springer, New York · Zbl 1242.90160
[13] Zibulevsky, M.; Elad, M., L1-L2 optimization in signal and image processing, IEEE Signal Process. Mag., 27, 76-88, (2010) · doi:10.1109/MSP.2010.936023
[14] Bioucas-Dias, J.; Figueiredo, M., A new TwIST: two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Process., 16, 2992-3004, (2007) · doi:10.1109/TIP.2007.909319
[15] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 183-202, (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[16] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Optim., 1, 127-239, (2014) · doi:10.1561/2400000003
[17] Chambolle, A., An algorithm for total variation minimization and applications, J. Math. Imaging Vis., 20, 89-97, (2004) · Zbl 1366.94048 · doi:10.1023/B:JMIV.0000011320.81911.38
[18] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40, 120-145, (2011) · Zbl 1255.68217 · doi:10.1007/s10851-010-0251-1
[19] Beck, A.; Teboulle, M., Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems, IEEE Trans. Image Process., 18, 2419-2434, (2009) · Zbl 1371.94049 · doi:10.1109/TIP.2009.2028250
[20] Censor, Y.; Davidi, R.; Herman, G. T., Perturbation resilience and superiorization of iterative algorithms, Inverse Problems, 26, (2010) · Zbl 1193.65019 · doi:10.1088/0266-5611/26/6/065008
[21] Herman, G. T.; Garduño, E.; Davidi, R.; Censor, Y., Superiorization: an optimization heuristic for medical physics, Med. Phys., 39, 5532-5546, (2012) · doi:10.1118/1.4745566
[22] Hansen, P. C., Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, (1998), Philadelphia, PA: SIAM, Philadelphia, PA
[23] Censor, Y.; Davidi, R.; Herman, G. T.; Schulte, R. W.; Tetruashvili, L., Projected subgradient minimization versus superiorization, J. Optim. Theory Appl., 160, 730-747, (2014) · Zbl 1298.90104 · doi:10.1007/s10957-013-0408-3
[24] Garduño, E.; Herman, G. T., Superiorization of the ML-EM algorithm, IEEE Trans. Nucl. Sci., 61, 162-172, (2014) · doi:10.1109/TNS.2013.2283529
[25] Schrapp, M. J.; Herman, G. T., Data fusion in x-ray computed tomography using a superiorization approach, Rev. Sci. Instrum., 85, (2014) · doi:10.1063/1.4872378
[26] Helou, E. S.; Zibetti, M. V W.; Miqueles, E. X., Superiorization of incremental optimization algorithms for statistical tomographic image reconstruction, Inverse Problems, 33, (2017) · Zbl 1367.65029 · doi:10.1088/1361-6420/33/4/044010
[27] Björck, A.; Elfving, T.; Strakos, Z., Stability of conjugate gradient and Lanczos methods for linear least squares problems, SIAM J. Matrix Anal. Appl., 19, 720-736, (1998) · Zbl 0924.65035 · doi:10.1137/S089547989631202X
[28] Herman, G. T., Fundamentals of Computerized Tomography: Image Reconstruction from Projections, (2009), London: Springer, London · Zbl 1280.92002
[29] Dai, Y-H; Kou, C-X, A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search, SIAM J. Optim., 23, 296-320, (2013) · Zbl 1266.49065 · doi:10.1137/100813026
[30] Luenberger, D. G.; Ye, Y., Linear and Nonlinear Programming, (2008), New York: Springer, New York · Zbl 1207.90003
[31] Frayssé, V.; Giraud, L., A set of conjugate gradient routines for real and complex arithmetics, Technical Report TR/PA/00/47, (2000)
[32] Bolz, J.; Farmer, I.; Grinspun, E.; Schröder, P., Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Trans. Graph., 22, 917-924, (2003) · doi:10.1145/882262.882364
[33] Shewchuk, J. R., An introduction to the conjugate gradient method without the agonizing pain, Technical Report, (1994)
[34] Humphries, T.; Winn, J.; Faridani, A., Superiorized algorithm for reconstruction of CT images from sparse-view and limitedangle polyenergetic data, Phys. Med. Biol., 62, 6762-6783, (2017) · doi:10.1088/1361-6560/aa7c2d
[35] Dong, Q.; Gibali, A.; Jiang, D.; Tang, Y., Bounded perturbation resilience of extragradient-type methods and their applications, J. Inequalities Appl., 280, (2017) · Zbl 1378.49026 · doi:10.1186/s13660-017-1555-0
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.