×

A class of upper and lower triangular splitting iteration methods for image restoration. (English) Zbl 1480.65071

Summary: Based on the augmented linear system, a class of upper and lower triangular (ULT) splitting iteration methods are established for solving the linear systems arising from image restoration problem. The convergence analysis of the ULT methods is presented for image restoration problem. Moreover, the optimal iteration parameters which minimize the spectral radius of the iteration matrix of these ULT methods and corresponding convergence factors for some special cases are given. In addition, numerical examples from image restoration are employed to validate the theoretical analysis and examine the effectiveness and competitiveness of the proposed methods. Experimental results show that these ULT methods considerably outperform the newly developed methods such as SHSS and RGHSS methods in terms of the numerical performance and image recovering quality. Finally, the SOR acceleration scheme for the ULT iteration method is discussed.

MSC:

65F10 Iterative numerical methods for linear systems
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory

Software:

RestoreTools
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Gonzalez, F. A.; Romero, E., Biomedical image analysis and machine learning technologies: Applications and techniques (2009), Information Science Reference-Imprint of IGI Publishing: Information Science Reference-Imprint of IGI Publishing Hershey, PA
[2] Han, Y.-S.; Herrington, D. M.; Snyder, W. E., Quantitative angiography using mean field annealing, Proceedings of the Computers in Cardiology, 119-122 (1992), IEEE
[3] Fisher, B., Digital restoration of snow white: 120,000 famous frames are back, Adv. Imaging, 137, 32-36 (1993)
[4] Starck, J. L.; Murtagh, F., Astronomical Image and Data Analysis (2006), Springer
[5] Berriel, L. R.; Bescos, J.; Santisteban, A., Image restoration for a defocused optical system, Appl. Opt., 22, 2772-2780 (1983)
[6] Chan, T. F.; Shen, J., Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods (2005), SIAM: SIAM Philadelphia · Zbl 1095.68127
[7] Hansen, P. C.; Nagy, J. G.; O’leary, D. P., Deblurring Images: Matrices, Spectra, and Filtering (2006), SIAM · Zbl 1112.68127
[8] Gonzalez, R. C.; Woods, R. E., Digital Image Processing (2002), Prentice Hall: Prentice Hall New Jersey
[9] Serra-Capizzano, S., A note on antireflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25, 1307-1325 (2003) · Zbl 1062.65152
[10] Lv, X.-G.; Huang, T.-Z.; Xu, Z.-B.; Zhao, X.-L., Kronecker product approximations for image restoration with whole-sample symmetric boundary conditions, Inf. Sci., 186, 150-163 (2012) · Zbl 1239.94011
[11] Nagy, J. G.; Ng, M. K.; Perrone, L., Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25, 829-841 (2004) · Zbl 1068.65055
[12] Perrone, L., Kronecker product approximations for image restoration with anti-reflective boundary conditions, Numer. Linear Algebra Appl., 13, 1-22 (2006) · Zbl 1174.94309
[13] Zhao, X.-L.; Huang, T.-Z.; Lv, X.-G.; Xu, Z.-B.; Huang, J., Kronecker product approximations for image restoration with new mean boundary conditions, Appl. Math. Model., 36, 225-237 (2012) · Zbl 1236.65063
[14] Nagy, J. G.; Palmer, K. M., Steepest descent, CG, and iterative regularization of ill-posed problems, BIT Numer. Math., 43, 1003-1017 (2003) · Zbl 1045.65034
[15] Kaltenbacher, B.; Neubauer, A.; Scherzer, O., Iterative Regularization Methods for Nonlinear Ill-Posed Problems (2008), Walter de Gruyter: Walter de Gruyter Berlin · Zbl 1145.65037
[16] Ng, M. K.; Chan, R. H.; Tang, W. C., A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21, 851-866 (1999) · Zbl 0951.65038
[17] Zheng, N.; Hayami, K.; Yin, J.-F., Modulus-type inner outer iteration methods for nonnegative constrained least squares problems, SIAM J. Matrix Anal. Appl., 37, 1250-1278 (2016) · Zbl 1348.65069
[18] Liu, J.; Huang, T.-Z.; Selesnick, I. W.; Lv, X.-G.; Chen, P.-Y., Image restoration using total variation with overlapping group sparsity, Inf. Sci., 295, 232-246 (2015) · Zbl 1360.94042
[19] Cai, Y.-T.; Donatelli, M.; Bianchi, D.; Huang, T.-Z., Regularization preconditioners for frame-based image deblurring with reduced boundary artifacts, SIAM J. Sci. Comput., 38, 189 (2016) · Zbl 1382.94010
[20] Liu, G.; Huang, T.-Z.; Liu, J., High-order TVL1-based images restoration and spatially adapted regularization parameter selection, Comput. Math. Appl., 67, 2015-2026 (2014) · Zbl 1366.94058
[21] Bai, Z.-Z.; Parlett, B. N.; Wang, Z.-Q., On generalized successive overrelaxation methods for augmented linear systems, Numer. Math., 102, 1-38 (2005) · Zbl 1083.65034
[22] Bai, Z.-Z.; Wang, Z.-Q., On parameterized inexact Uzawa methods for generalized saddle point problems, Linear Algebra Appl., 428, 2900-2932 (2008) · Zbl 1144.65020
[23] Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T., Analysis of the inexact Uzawa algorithm for saddle point problems, SIAM J. Numer. Anal., 34, 1072-1092 (1997) · Zbl 0873.65031
[24] Bramble, J. H.; Pasciak, J. E.; Vassilev, A. T., Uzawa type algorithms for nonsymmetric saddle point problems, Math. Comp., 69, 667-689 (2000) · Zbl 0951.65122
[25] Elman, H. C.; Golub, G. H., Inexact and preconditioned Uzawa algorithms for saddle point problems, SIAM J. Numer. Anal., 31, 1645-1661 (1994) · Zbl 0815.65041
[26] Arrow, K. J.; Hurwicz, L.; Uzawa, H., Studies in Linear and Non-Linear Programming (1958), Stanford University Press · Zbl 0091.16002
[27] Lu, J.-F.; Zhang, Z.-Y., A modified nonlinear inexact Uzawa algorithm with a variable relaxation parameter for the stabilized saddle point problem, SIAM J. Matrix Anal. Appl., 31, 1934-1957 (2010) · Zbl 1201.65047
[28] Hu, Q.-Y.; Zou, J., Two new variants of nonlinear inexact Uzawa algorithms for saddle-point problems, Numer. Math., 93, 333-359 (2002) · Zbl 1019.65024
[29] Wu, S.-L.; Huang, T.-Z.; Zhao, X.-L., A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math., 228, 424-433 (2009) · Zbl 1167.65016
[30] Li, L.; Huang, T.-Z.; Liu, X.-P., Modified Hermitian and skew-Hermitian splitting methods for non-Hermitian positive-definite linear systems, Numer. Linear Algebra Appl., 14, 217-235 (2007) · Zbl 1199.65109
[31] Bai, Z.-Z., Optimal parameters in the HSS-like methods for saddle-point problems, Numer. Linear Algebra Appl., 16, 447-479 (2009) · Zbl 1224.65081
[32] Bai, Z.-Z.; Golub, G. H.; Pan, J.-Y., Preconditioned Hermitian and skew-Hermitian splitting methods for non-Hermitian positive semidefinite linear systems, Numer. Math., 98, 1-32 (2004) · Zbl 1056.65025
[33] Bai, Z.-Z.; Golub, G. H., Accelerated Hermitian and skew-Hermitian splitting iteration methods for saddle-point problems, IMA J. Numer. Anal., 27, 1-23 (2007) · Zbl 1134.65022
[34] Bai, Z.-Z.; Golub, G. H.; Lu, L.-Z.; Yin, J.-F., Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Comput., 26, 844-863 (2005) · Zbl 1079.65028
[35] Peng, X.-F.; Li, W., The alternating-direction iterative method for saddle point problems, Appl. Math. Comput., 216, 1845-1858 (2010) · Zbl 1195.65040
[36] Fan, H.-T.; Zhu, X.-Y., A modified relaxed splitting preconditioner for generalized saddle point problems from the incompressible Navier-Stokes equations, Appl. Math. Lett., 55, 18-26 (2016) · Zbl 1398.65037
[37] D.M. Young, Iterative Solution of Large Linear Systems, Dover Publications, 2003.; D.M. Young, Iterative Solution of Large Linear Systems, Dover Publications, 2003. · Zbl 1049.65022
[38] Golub, G. H.; Wu, X.; Yuan, J.-Y., SOR-like methods for augmented systems, BIT Numer. Math., 41, 71-85 (2001) · Zbl 0991.65036
[39] Bai, Z.-Z.; Li, G.-Q., Restrictively preconditioned conjugate gradient methods for systems of linear equations, IMA J. Numer. Anal., 23, 561-580 (2003) · Zbl 1046.65018
[40] Bai, Z.-Z.; Wang, Z.-Q., Restrictive preconditioners for conjugate gradient methods for symmetric positive definite linear systems, J. Comput. Appl. Math., 187, 202-226 (2006) · Zbl 1083.65045
[41] Sturler, E.; Liesen, J., Block-diagonal and constraint preconditioners for nonsymmetric indefinite linear systems. part i: theory, SIAM J. Sci. Comput., 26, 1598-1619 (2005) · Zbl 1078.65027
[42] Pan, J.-Y.; Ng, M. K.; Bai, Z.-Z., New preconditioners for saddle point problems, Appl. Math. Comput., 172, 762-771 (2006) · Zbl 1088.65040
[43] Elman, H. C., Preconditioning for the steady-state Navier-Stokes equations with low viscosity, SIAM J. Sci. Comput., 20, 1299-1316 (1999) · Zbl 0935.76057
[44] Keller, C.; Gould, N. I.M.; Wathen, A. J., Constraint preconditioning for indefinite linear systems, SIAM J. Matrix Anal. Appl., 21, 1300-1317 (2000) · Zbl 0960.65052
[45] Gould, N. I.M.; Hribar, M. E.; Nocedal, J., On the solution of equality constrained quadratic programming problems arising in optimization, SIAM J. Sci. Comput., 23, 1376-1395 (2001) · Zbl 0999.65050
[46] Sarin, V.; Sameh, A., An efficient iterative method for the generalized stokes problem, SIAM J. Sci. Comput., 19, 206-226 (1998) · Zbl 0911.76039
[47] Zheng, Q.-Q.; Ma, C.-F., A class of triangular splitting methods for saddle point problems, J. Comput. Appl. Math., 298, 13-23 (2016) · Zbl 1332.65048
[48] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl., 24, 603-626 (2003) · Zbl 1036.65032
[49] Lv, X.-G.; Huang, T.-Z.; Xu, Z.-B.; Zhao, X.-L., A special Hermitian and skew-Hermitian splitting method for image restoration, Appl. Math. Model., 37, 1069-1082 (2013) · Zbl 1351.94006
[50] Aghazadeh, N.; Bastani, M.; Salkuyeh, D. K., Generalized Hermitian and skew-Hermitian splitting iterative method for image restoration, Appl. Math. Model., 39, 6126-6138 (2015) · Zbl 1443.94003
[51] Krukier, L. A.; Krukier, B. L.; Ren, Z.-R., Generalized skew-Hermitian triangular splitting iteration methods for saddle-point linear systems, Numer. Linear Algebra Appl., 21, 152-170 (2014) · Zbl 1324.65053
[52] Bai, Z.-Z.; Benzi, M., Regularized HSS iteration methods for saddle-point linear systems, BIT Numer. Math. (2016)
[53] Bai, Z.-Z.; Golub, G. H.; Ng, M. K., On successive-overrelaxation acceleration of the Hermitian and skew-Hermitian splitting iterations, Numer. Linear Algebra Appl., 14, 319-335 (2007) · Zbl 1199.65097
[54] Y. Saad, Iterative Methods for Sparse Linear Systems, second ed., SIAM, Philadelphia, 2002.; Y. Saad, Iterative Methods for Sparse Linear Systems, second ed., SIAM, Philadelphia, 2002.
[55] Hansen, P. C., Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34, 561-580 (1992) · Zbl 0770.65026
[56] Morozov, V., On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7, 414-417 (1966) · Zbl 0187.12203
[57] Golub, G. H.; Heath, M.; Wahba, G., Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 215-223 (1979) · Zbl 0461.62059
[58] R.S. Varga, Matrix Iterative Analysis, second ed., Springer, New York and London, 2000.; R.S. Varga, Matrix Iterative Analysis, second ed., Springer, New York and London, 2000. · Zbl 0998.65505
[59] Nagy, J. G.; Palmer, K.; Perrone, L., Iterative methods for image deblurring: a matlab object-oriented approach, Numer. Algor., 36, 73-93 (2004) · Zbl 1048.65039
[60] Paige, C. C.; Saunders, M. A., Solution of sparse indefinite systems of linear equations, SIAM J. Numer. Anal., 12, 617-629 (1975) · Zbl 0319.65025
[61] Fischer, B.; Ramage, A.; Silvester, D. J.; Wathen, A. J., Minimum residual methods for augmented systems, BIT Numer. Math., 38, 527-543 (1998) · Zbl 0914.65026
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.