# American Institute of Mathematical Sciences

• Previous Article
Solving differential Riccati equations: A nonlinear space-time method using tensor trains
• NACO Home
• This Issue
• Next Article
Fault-tolerant control against actuator failures for uncertain singular fractional order systems
doi: 10.3934/naco.2020013

## On the GSOR iteration method for image restoration

 1 Department of Mathematics, Faculty of Mathematical Sciences, University of Mohaghegh Ardabili, Ardabil, Iran 2 Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

* Corresponding author: Davod Khojasteh Salkuyeh

Received  June 2019 Revised  August 2019 Published  February 2020

In this study, we present a generalization of the successive overrelaxation (GSOR) iteration method to find the solution of the image restoration problem. Moreover, an improved version of the GSOR (IGSOR) method is also given to solve the proposed problem. Convergence of the GSOR and IGSOR methods are investigated. Three numerical examples are given to illustrate the effectiveness and accuracy of the methods.

Citation: Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, doi: 10.3934/naco.2020013
##### References:
 [1] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1996.  doi: 10.1017/CBO9780511624100.  Google Scholar [2] L. R. Berriel, J. Bescos and A. Santistebao, Image restoration for a defocused optical system, Appl. Opt., 22 (1983), 2772-2780.   Google Scholar [3] A. Bouhamidi and K. Jbilou, Sylvester Tikhonov-regularization methods in image restoration, J. Comput. Appl. Math., 206 (2007), 86-98.  doi: 10.1016/j.cam.2006.05.028.  Google Scholar [4] S. Serra-Capizzano, A note on antireflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25 (2003), 1307-1325.  doi: 10.1137/S1064827502410244.  Google Scholar [5] T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22 (2000), 503-516.  doi: 10.1137/S1064827598344169.  Google Scholar [6] L.-J. Deng, T.-Z. Huang and X.-L. Zhao, Wavelet-based two-level methods for image restoration, Commun. Nonlinear Sci. Numer. Simulat., 17 (2012), 5079-5087.  doi: 10.1016/j.cnsns.2012.04.001.  Google Scholar [7] B. Fisher, Digital restoration of snow white: 120,000 famous frames are back, , Advanced Imaging, (1993), 32–36. Google Scholar [8] G. H. Golub, M. Heath and G. Wahba, Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21 (1979), 215-223.  doi: 10.2307/1268518.  Google Scholar [9] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2$^nd$ edition, Prentice Hall, New Jersey, 2002. Google Scholar [10] Y.-S. Han, D. M. Herrington and W. E. Snyder, Quantitative angiography using mean field annealing, Proc. of Computers in Cardiology, (1992), 119–122. Google Scholar [11] P. C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34 (1992), 561-580.  doi: 10.1137/1034115.  Google Scholar [12] P. C. Hansen, J. G. Nagy and D. P. O'leary, Deblurring Images: Matrices Spectra and Filtering, SIAM, Philadelphia, 2006. doi: 10.1137/1.9780898718874.  Google Scholar [13] A. K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ, 1989. Google Scholar [14] G. Landi, A fast truncated Lagrange method for large-scale image restoration problems, Appl. Math. Comput., 186 (2007), 1075-1082.  doi: 10.1016/j.amc.2006.08.039.  Google Scholar [15] X.-G. Lv, T.-Z. Huang, Z.-B. Xu and X.-L. Zhao, A special Hermitian and skew-Hermitian splitting method for image restoration, Appl. Math. Model., 37 (2013), 1069-1082.  doi: 10.1016/j.apm.2012.03.019.  Google Scholar [16] V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7 (1966), 414-417.   Google Scholar [17] J. G. Nagy, M. K. Ng and L. Perrone, Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25 (2003), 829-841.  doi: 10.1137/S0895479802419580.  Google Scholar [18] M. K. Ng, R. H. Chan and W.-C. Tang, A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21 (1999), 851-866.  doi: 10.1137/S1064827598341384.  Google Scholar [19] L. Perrone, Kronecker product approximations for image restoration with anti-reflective boundary conditions, Numer. Linear Algebra Appl., 13 (2006), 1-22.  doi: 10.1002/nla.458.  Google Scholar [20] Y. Saad, Iterative Methods for Sparse Linear Systems, 2$^{nd}$ edition, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898718003.  Google Scholar [21] D. K. Salkuyeh, D. Hezari and V. Edalatpour, Generalized SOR iterative method for a class of complex symmetric linear system of equations, Int. J. Comput. Math., 92 (2015), 802-815.  doi: 10.1080/00207160.2014.912753.  Google Scholar [22] J. L. Starck and F. Murtagh, Astronomical Image and Data Analysis, 2$^nd$ edition, Springer, Berlin, 2006. Google Scholar [23] C. R. Vogel, Computational Methods for Inverse Problems, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898717570.  Google Scholar

show all references

##### References:
 [1] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1996.  doi: 10.1017/CBO9780511624100.  Google Scholar [2] L. R. Berriel, J. Bescos and A. Santistebao, Image restoration for a defocused optical system, Appl. Opt., 22 (1983), 2772-2780.   Google Scholar [3] A. Bouhamidi and K. Jbilou, Sylvester Tikhonov-regularization methods in image restoration, J. Comput. Appl. Math., 206 (2007), 86-98.  doi: 10.1016/j.cam.2006.05.028.  Google Scholar [4] S. Serra-Capizzano, A note on antireflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25 (2003), 1307-1325.  doi: 10.1137/S1064827502410244.  Google Scholar [5] T. Chan, A. Marquina and P. Mulet, High-order total variation-based image restoration, SIAM J. Sci. Comput., 22 (2000), 503-516.  doi: 10.1137/S1064827598344169.  Google Scholar [6] L.-J. Deng, T.-Z. Huang and X.-L. Zhao, Wavelet-based two-level methods for image restoration, Commun. Nonlinear Sci. Numer. Simulat., 17 (2012), 5079-5087.  doi: 10.1016/j.cnsns.2012.04.001.  Google Scholar [7] B. Fisher, Digital restoration of snow white: 120,000 famous frames are back, , Advanced Imaging, (1993), 32–36. Google Scholar [8] G. H. Golub, M. Heath and G. Wahba, Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21 (1979), 215-223.  doi: 10.2307/1268518.  Google Scholar [9] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2$^nd$ edition, Prentice Hall, New Jersey, 2002. Google Scholar [10] Y.-S. Han, D. M. Herrington and W. E. Snyder, Quantitative angiography using mean field annealing, Proc. of Computers in Cardiology, (1992), 119–122. Google Scholar [11] P. C. Hansen, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34 (1992), 561-580.  doi: 10.1137/1034115.  Google Scholar [12] P. C. Hansen, J. G. Nagy and D. P. O'leary, Deblurring Images: Matrices Spectra and Filtering, SIAM, Philadelphia, 2006. doi: 10.1137/1.9780898718874.  Google Scholar [13] A. K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ, 1989. Google Scholar [14] G. Landi, A fast truncated Lagrange method for large-scale image restoration problems, Appl. Math. Comput., 186 (2007), 1075-1082.  doi: 10.1016/j.amc.2006.08.039.  Google Scholar [15] X.-G. Lv, T.-Z. Huang, Z.-B. Xu and X.-L. Zhao, A special Hermitian and skew-Hermitian splitting method for image restoration, Appl. Math. Model., 37 (2013), 1069-1082.  doi: 10.1016/j.apm.2012.03.019.  Google Scholar [16] V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7 (1966), 414-417.   Google Scholar [17] J. G. Nagy, M. K. Ng and L. Perrone, Kronecker product approximations for image restoration with reflexive boundary conditions, SIAM J. Matrix Anal. Appl., 25 (2003), 829-841.  doi: 10.1137/S0895479802419580.  Google Scholar [18] M. K. Ng, R. H. Chan and W.-C. Tang, A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21 (1999), 851-866.  doi: 10.1137/S1064827598341384.  Google Scholar [19] L. Perrone, Kronecker product approximations for image restoration with anti-reflective boundary conditions, Numer. Linear Algebra Appl., 13 (2006), 1-22.  doi: 10.1002/nla.458.  Google Scholar [20] Y. Saad, Iterative Methods for Sparse Linear Systems, 2$^{nd}$ edition, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898718003.  Google Scholar [21] D. K. Salkuyeh, D. Hezari and V. Edalatpour, Generalized SOR iterative method for a class of complex symmetric linear system of equations, Int. J. Comput. Math., 92 (2015), 802-815.  doi: 10.1080/00207160.2014.912753.  Google Scholar [22] J. L. Starck and F. Murtagh, Astronomical Image and Data Analysis, 2$^nd$ edition, Springer, Berlin, 2006. Google Scholar [23] C. R. Vogel, Computational Methods for Inverse Problems, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898717570.  Google Scholar
True image, PSF and degraded image in Example 1
Restored images with GSOR method for various BCs in Example 1
Restored images with IGSOR method for various BCs in Example 1
True image and degraded image in Example 2
Restored images with GSOR method for various BCs in Example 2
Restored images with IGSOR method for various BCs in Example 2
True image, PSF and degraded image in Example 3
Restored images with GSOR method for various BCs in Example 3
Restored images with IGSOR method for various BCs in Example 3
Values of $(\alpha,\omega)$ in Example 1
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3283,-)$ $(0.3333,-)$ $(0.3290,-)$ $(0.4650,-)$ GSOR $(-,0.22)$ $(-,0.20)$ $(-,0.14)$ $(-,0.19)$ IGSOR $(0.27,0.36)$ $(0.31,0.22)$ $(0.02,0.34)$ $(0.01,0.28)$
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3283,-)$ $(0.3333,-)$ $(0.3290,-)$ $(0.4650,-)$ GSOR $(-,0.22)$ $(-,0.20)$ $(-,0.14)$ $(-,0.19)$ IGSOR $(0.27,0.36)$ $(0.31,0.22)$ $(0.02,0.34)$ $(0.01,0.28)$
PSNR values of various methods in Example 1
 Method Zero Periodic Reflexive Antireflective SHSS $21.08$ $22.09$ $23.98$ $24.17$ GSOR $21.12$ $22.18$ $24.13$ $24.40$ IGSOR $21.23$ $22.25$ $24.23$ $24.46$
 Method Zero Periodic Reflexive Antireflective SHSS $21.08$ $22.09$ $23.98$ $24.17$ GSOR $21.12$ $22.18$ $24.13$ $24.40$ IGSOR $21.23$ $22.25$ $24.23$ $24.46$
Relative error of various methods in Example 1
 Method Zero Periodic Reflexive Antireflective SHSS $0.1796$ $0.1592$ $0.1287$ $0.1259$ GSOR $0.1790$ $0.1582$ $0.1265$ $0.1224$ IGSOR $0.1767$ $0.1571$ $0.1252$ $0.1218$
 Method Zero Periodic Reflexive Antireflective SHSS $0.1796$ $0.1592$ $0.1287$ $0.1259$ GSOR $0.1790$ $0.1582$ $0.1265$ $0.1224$ IGSOR $0.1767$ $0.1571$ $0.1252$ $0.1218$
CPU times of various methods in Example 1
 Method Zero Periodic Reflexive Antireflective SHSS $5.26$ $5.05$ $5.74$ $5.31$ GSOR $0.49$ $0.52$ $0.49$ $0.51$ IGSOR $0.48$ $0.52$ $0.49$ $0.51$
 Method Zero Periodic Reflexive Antireflective SHSS $5.26$ $5.05$ $5.74$ $5.31$ GSOR $0.49$ $0.52$ $0.49$ $0.51$ IGSOR $0.48$ $0.52$ $0.49$ $0.51$
Values of $(\alpha,\omega)$ in Example 2
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3277,-)$ $(0.3333,-)$ $(0.3339,-)$ $(0.6039,-)$ GSOR $(-,0.32)$ $(-,0.30)$ $(-,0.17)$ $(-,0.18)$ IGSOR $(0.01,0.09)$ $(0.001,0.15)$ $(0.005,0.22)$ $(0.01,0.25)$
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3277,-)$ $(0.3333,-)$ $(0.3339,-)$ $(0.6039,-)$ GSOR $(-,0.32)$ $(-,0.30)$ $(-,0.17)$ $(-,0.18)$ IGSOR $(0.01,0.09)$ $(0.001,0.15)$ $(0.005,0.22)$ $(0.01,0.25)$
PSNR values of various methods in Example 2
 Method Zero Periodic Reflexive Antireflective SHSS $27.50$ $27.71$ $28.81$ $28.39$ GSOR $27.53$ $27.76$ $29.41$ $29.14$ IGSOR $27.61$ $27.83$ $29.43$ $29.16$
 Method Zero Periodic Reflexive Antireflective SHSS $27.50$ $27.71$ $28.81$ $28.39$ GSOR $27.53$ $27.76$ $29.41$ $29.14$ IGSOR $27.61$ $27.83$ $29.43$ $29.16$
Relative error of various methods in Example 2
 Method Zero Periodic Reflexive Antireflective SHSS $0.2771$ $0.2704$ $0.2384$ $0.2502$ GSOR $0.2764$ $0.2690$ $0.2224$ $0.2296$ IGSOR $0.2740$ $0.2671$ $0.2222$ $0.2292$
 Method Zero Periodic Reflexive Antireflective SHSS $0.2771$ $0.2704$ $0.2384$ $0.2502$ GSOR $0.2764$ $0.2690$ $0.2224$ $0.2296$ IGSOR $0.2740$ $0.2671$ $0.2222$ $0.2292$
CPU times of various methods in Example 2
 Method Zero Periodic Reflexive Antireflective SHSS $4.98$ $5.08$ $5.21$ $5.40$ GSOR $0.49$ $0.52$ $0.51$ $0.52$ IGSOR $0.49$ $0.51$ $0.53$ $0.50$
 Method Zero Periodic Reflexive Antireflective SHSS $4.98$ $5.08$ $5.21$ $5.40$ GSOR $0.49$ $0.52$ $0.51$ $0.52$ IGSOR $0.49$ $0.51$ $0.53$ $0.50$
Values of $(\alpha,\omega)$ in Example 3
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3330,-)$ $(0.3333,-)$ $(0.3333,-)$ $(0.5894,-)$ GSOR $(-,0.26)$ $(-,0.25)$ $(-,0.25)$ $(-,0.29)$ IGSOR $(0.003,0.19)$ $(0.008,0.13)$ $(0.006,0.13)$ $(0.05,0.09)$
 Method Zero Periodic Reflexive Antireflective SHSS $(0.3330,-)$ $(0.3333,-)$ $(0.3333,-)$ $(0.5894,-)$ GSOR $(-,0.26)$ $(-,0.25)$ $(-,0.25)$ $(-,0.29)$ IGSOR $(0.003,0.19)$ $(0.008,0.13)$ $(0.006,0.13)$ $(0.05,0.09)$
PSNR values of various methods in Example 3
 Method Zero Periodic Reflexive Antireflective SHSS $22.68$ $27.65$ $26.22$ $26.69$ GSOR $22.72$ $27.90$ $26.54$ $26.80$ IGSOR $22.75$ $28.43$ $26.87$ $27.93$
 Method Zero Periodic Reflexive Antireflective SHSS $22.68$ $27.65$ $26.22$ $26.69$ GSOR $22.72$ $27.90$ $26.54$ $26.80$ IGSOR $22.75$ $28.43$ $26.87$ $27.93$
Relative error of various methods in Example 3
 Method Zero Periodic Reflexive Antireflective SHSS $0.1287$ $0.0726$ $0.0857$ $0.0811$ GSOR $0.1281$ $0.0706$ $0.0825$ $0.0801$ IGSOR $0.1276$ $0.0664$ $0.0795$ $0.0704$
 Method Zero Periodic Reflexive Antireflective SHSS $0.1287$ $0.0726$ $0.0857$ $0.0811$ GSOR $0.1281$ $0.0706$ $0.0825$ $0.0801$ IGSOR $0.1276$ $0.0664$ $0.0795$ $0.0704$
CPU times of various methods in Example 3
 Method Zero Periodic Reflexive Antireflective SHSS $24.62$ $22.81$ $22.95$ $24.65$ GSOR $2.27$ $2.30$ $2.41$ $2.35$ IGSOR $2.26$ $2.28$ $2.29$ $2.33$
 Method Zero Periodic Reflexive Antireflective SHSS $24.62$ $22.81$ $22.95$ $24.65$ GSOR $2.27$ $2.30$ $2.41$ $2.35$ IGSOR $2.26$ $2.28$ $2.29$ $2.33$
 [1] Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems & Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523 [2] Moulay Rchid Sidi Ammi, Ismail Jamiai. Finite difference and Legendre spectral method for a time-fractional diffusion-convection equation for image restoration. Discrete & Continuous Dynamical Systems - S, 2018, 11 (1) : 103-117. doi: 10.3934/dcdss.2018007 [3] Jia Li, Zuowei Shen, Rujie Yin, Xiaoqun Zhang. A reweighted $l^2$ method for image restoration with Poisson and mixed Poisson-Gaussian noise. Inverse Problems & Imaging, 2015, 9 (3) : 875-894. doi: 10.3934/ipi.2015.9.875 [4] Yosra Boukari, Houssem Haddar. The factorization method applied to cracks with impedance boundary conditions. Inverse Problems & Imaging, 2013, 7 (4) : 1123-1138. doi: 10.3934/ipi.2013.7.1123 [5] Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195 [6] Thomas Y. Hou, Pingwen Zhang. Convergence of a boundary integral method for 3-D water waves. Discrete & Continuous Dynamical Systems - B, 2002, 2 (1) : 1-34. doi: 10.3934/dcdsb.2002.2.1 [7] Frederic Rousset. The residual boundary conditions coming from the real vanishing viscosity method. Discrete & Continuous Dynamical Systems - A, 2002, 8 (3) : 605-625. doi: 10.3934/dcds.2002.8.606 [8] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [9] Alexey Penenko. Convergence analysis of the adjoint ensemble method in inverse source problems for advection-diffusion-reaction models with image-type measurements. Inverse Problems & Imaging, 2020, 14 (5) : 757-782. doi: 10.3934/ipi.2020035 [10] Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems & Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010 [11] Ugur G. Abdulla. On the optimal control of the free boundary problems for the second order parabolic equations. II. Convergence of the method of finite differences. Inverse Problems & Imaging, 2016, 10 (4) : 869-898. doi: 10.3934/ipi.2016025 [12] Alexander Zlotnik, Ilya Zlotnik. Finite element method with discrete transparent boundary conditions for the time-dependent 1D Schrödinger equation. Kinetic & Related Models, 2012, 5 (3) : 639-667. doi: 10.3934/krm.2012.5.639 [13] Amir Averbuch, Pekka Neittaanmäki, Valery Zheludev. Periodic spline-based frames for image restoration. Inverse Problems & Imaging, 2015, 9 (3) : 661-707. doi: 10.3934/ipi.2015.9.661 [14] Nicolas Lermé, François Malgouyres, Dominique Hamoir, Emmanuelle Thouin. Bayesian image restoration for mosaic active imaging. Inverse Problems & Imaging, 2014, 8 (3) : 733-760. doi: 10.3934/ipi.2014.8.733 [15] Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial & Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199 [16] Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033 [17] Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial & Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381 [18] Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1 [19] Karl Kunisch, Markus Müller. Uniform convergence of the POD method and applications to optimal control. Discrete & Continuous Dynamical Systems - A, 2015, 35 (9) : 4477-4501. doi: 10.3934/dcds.2015.35.4477 [20] Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995

Impact Factor: