# 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] Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 [2] Maika Goto, Kazunori Kuwana, Yasuhide Uegata, Shigetoshi Yazaki. A method how to determine parameters arising in a smoldering evolution equation by image segmentation for experiment's movies. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 881-891. doi: 10.3934/dcdss.2020233 [3] Jan Březina, Eduard Feireisl, Antonín Novotný. On convergence to equilibria of flows of compressible viscous fluids under in/out–flux boundary conditions. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021009 [4] Pavel Eichler, Radek Fučík, Robert Straka. Computational study of immersed boundary - lattice Boltzmann method for fluid-structure interaction. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 819-833. doi: 10.3934/dcdss.2020349 [5] 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 [6] Xiaoxiao Li, Yingjing Shi, Rui Li, Shida Cao. Energy management method for an unpowered landing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020180 [7] Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095 [8] 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 [9] Qing-Hu Hou, Yarong Wei. Telescoping method, summation formulas, and inversion pairs. Electronic Research Archive, , () : -. doi: 10.3934/era.2021007 [10] Roland Schnaubelt, Martin Spitz. Local wellposedness of quasilinear Maxwell equations with absorbing boundary conditions. Evolution Equations & Control Theory, 2021, 10 (1) : 155-198. doi: 10.3934/eect.2020061 [11] Kuntal Bhandari, Franck Boyer. Boundary null-controllability of coupled parabolic systems with Robin conditions. Evolution Equations & Control Theory, 2021, 10 (1) : 61-102. doi: 10.3934/eect.2020052 [12] Qianqian Hou, Tai-Chia Lin, Zhi-An Wang. On a singularly perturbed semi-linear problem with Robin boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 401-414. doi: 10.3934/dcdsb.2020083 [13] Wenrui Hao, King-Yeung Lam, Yuan Lou. Ecological and evolutionary dynamics in advective environments: Critical domain size and boundary conditions. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 367-400. doi: 10.3934/dcdsb.2020283 [14] Franck Davhys Reval Langa, Morgan Pierre. A doubly splitting scheme for the Caginalp system with singular potentials and dynamic boundary conditions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 653-676. doi: 10.3934/dcdss.2020353 [15] 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 [16] 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 [17] 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 [18] 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 [19] 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 [20] Xiu Ye, Shangyou Zhang, Peng Zhu. A weak Galerkin finite element method for nonlinear conservation laws. Electronic Research Archive, 2021, 29 (1) : 1897-1923. doi: 10.3934/era.2020097

Impact Factor: