# American Institute of Mathematical Sciences

March  2021, 11(1): 27-43. 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, 2021, 11 (1) : 27-43. 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] Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 [2] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [3] Mengni Li. Global regularity for a class of Monge-Ampère type equations with nonzero boundary conditions. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020267 [4] Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076 [5] Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078 [6] Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462 [7] Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250 [8] Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120 [9] Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319 [10] Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056 [11] Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351 [12] Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465 [13] Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321 [14] Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 [15] Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045 [16] João Marcos do Ó, Bruno Ribeiro, Bernhard Ruf. Hamiltonian elliptic systems in dimension two with arbitrary and double exponential growth conditions. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 277-296. doi: 10.3934/dcds.2020138 [17] Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013 [18] Marco Ghimenti, Anna Maria Micheletti. Compactness results for linearly perturbed Yamabe problem on manifolds with boundary. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020453 [19] H. M. Srivastava, H. I. Abdel-Gawad, Khaled Mohammed Saad. Oscillatory states and patterns formation in a two-cell cubic autocatalytic reaction-diffusion model subjected to the Dirichlet conditions. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020433 [20] Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020383

Impact Factor:

## Tools

Article outline

Figures and Tables