Article Contents
Article Contents

# On the GSOR iteration method for image restoration

• * Corresponding author: Davod Khojasteh Salkuyeh
• 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.

Mathematics Subject Classification: Primary: 65F10; Secondary: 65D18.

 Citation:

• Figure 1.  True image, PSF and degraded image in Example 1

Figure 2.  Restored images with GSOR method for various BCs in Example 1

Figure 3.  Restored images with IGSOR method for various BCs in Example 1

Figure 4.  True image and degraded image in Example 2

Figure 5.  Restored images with GSOR method for various BCs in Example 2

Figure 6.  Restored images with IGSOR method for various BCs in Example 2

Figure 7.  True image, PSF and degraded image in Example 3

Figure 8.  Restored images with GSOR method for various BCs in Example 3

Figure 9.  Restored images with IGSOR method for various BCs in Example 3

Table 1.  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)$

Table 2.  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$

Table 3.  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$

Table 4.  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$

Table 5.  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)$

Table 6.  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$

Table 7.  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$

Table 8.  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$

Table 9.  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)$

Table 10.  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$

Table 11.  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$

Table 12.  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$
•  [1] O. Axelsson,  Iterative Solution Methods, Cambridge University Press, Cambridge, 1996.  doi: 10.1017/CBO9780511624100. [2] L. R. Berriel, J. Bescos and A. Santistebao, Image restoration for a defocused optical system, Appl. Opt., 22 (1983), 2772-2780. [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. [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. [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. [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. [7] B. Fisher, Digital restoration of snow white: 120,000 famous frames are back, , Advanced Imaging, (1993), 32–36. [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. [9] R. C. Gonzalez and R. E. Woods, Digital Image Processing, 2$^nd$ edition, Prentice Hall, New Jersey, 2002. [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. [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. [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. [13] A. K. Jain, Fundamentals of Digital Image Processing, Prentice Hall, Englewood Cliffs, NJ, 1989. [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. [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. [16] V. A. Morozov, On the solution of functional equations by the method of regularization, Soviet Math. Dokl., 7 (1966), 414-417. [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. [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. [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. [20] Y. Saad, Iterative Methods for Sparse Linear Systems, 2$^{nd}$ edition, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898718003. [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. [22] J. L. Starck and F. Murtagh, Astronomical Image and Data Analysis, 2$^nd$ edition, Springer, Berlin, 2006. [23] C. R. Vogel, Computational Methods for Inverse Problems, SIAM, Philadelphia, 2002. doi: 10.1137/1.9780898717570.

Figures(9)

Tables(12)