# American Institute of Mathematical Sciences

May  2011, 5(2): 323-339. doi: 10.3934/ipi.2011.5.323

## A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration

 1 Department of Mathematical Sciences, University of Liverpool, Peach Street, Liverpool L69 7ZL, United Kingdom 2 Institute of Biomathematics and Biometry, Helmholtz Zentrum München, Ingolstädter Landstrasse 1, 85764 Neuherberg, Germany 3 Department of Mathematics, Humboldt-University of Berlin, Unter den Linden 6, 10099 Berlin, Germany

Received  September 2010 Revised  February 2011 Published  May 2011

Based on the Fenchel pre-dual of the total variation model, a nonlinear multigrid algorithm for image denoising is proposed. Due to the structure of the differential operator involved in the Euler-Lagrange equations of the dual models, line Gauss-Seidel-semismooth-Newton step is utilized as the smoother, which provides rather good smoothing rates. The paper ends with a report on numerical results and a comparison with a very recent nonlinear multigrid solver based on Chambolle's iteration [6].
Citation: Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems and Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323
##### References:
 [1] USC-SIPI image database, In A. Weber, editor, http://sipi.usc.edu/services/database/Database.html, University of Southern California. [2] A. Bovik, "Handbook of Image and Video Processing," Academic Press, 2000. [3] A. Brandt, Guide to multigrid development, In "Multigrid Methods" (Cologne, 1981), volume 960 of Lecture Notes in Math., pages 220-312. Springer, 1982. [4] A. Chambolle, An algorithm for total variation minimization and application, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. [5] A. Chambolle and P-L. Lions, Image recovery via total variation minimization and related problems, Numerische Mathematik, 76 (1997), 167-188. doi: 10.1007/s002110050258. [6] T. Chan, K. Chen and J. L. Carter, Iterative methods for solving the dual formulation arising from image restoration, Electronic Transactions on Numerical Analysis, 26 (2007), 299-311. [7] T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), 1964-1977. doi: 10.1137/S1064827596299767. [8] Q. Chang and I-L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Applied Mathematics, 25 (2003), 982-994. [9] K. Chen, "Matrix Preconditioning Techniques and Applications," Cambridge University Press, 2005. doi: 10.1017/CBO9780511543258. [10] D. C. Dobson and C. R. Vogel, Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal., 34 (1997), 1779-1791. doi: 10.1137/S003614299528701X. [11] I. Ekeland and R. Témam, "Convex Analysis and Variational Problems," Classics Appl. Math. 28, SIAM, Philadelphia, 1999. [12] C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput. Vis. Sci., 7 (2004), 199-206. [13] E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Birkhäuser, Boston, 1984. [14] W. Hackbusch, "Multigrid Methods and Applications," volume 4 of Springer Series in Computational Mathematics, Springer-Verlag, 1985. [15] M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth newton method, SIAM J. Optim., 13 (2002), 865-888. doi: 10.1137/S1052623401383558. [16] M. Hintermüller and K. Kunisch, Total bounded variation regularization as bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), 1311-1333. doi: 10.1137/S0036139903422784. [17] M. Hintermüller and G. Stadler, An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration, SIAM Journal on Scientific Computing, 28 (2006), 1-23. doi: 10.1137/040613263. [18] M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., 101 (2004), 151-184. [19] P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo, Annals of Statistics, 1 (1973), 799-821. doi: 10.1214/aos/1176342503. [20] S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. and Simu., 4 (2005), 460-489. doi: 10.1137/040605412. [21] L. Rudin, "MTV-Multiscale Total Variation Principle for a PDE-Based Solution to Nonsmooth Ill-Posed Problem," Technical report, Cognitech, Inc. Talk presented at the Workshop on Mathematical Methods in Computer Vision, University of Minnesota, 1995. [22] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [23] D. Strong and T. Chan, "Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing," Technical report, UCLA, 1996. [24] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), 165-187. doi: 10.1088/0266-5611/19/6/059. [25] X.-C. Tai, "Rate of Convergence for Some Constraint Decomposition Methods for Nonlinear Variational Inequalities," Numerische Mathematik, 2003. [26] X.-C. Tai, B. Heimsund and J. Xu, Rate of convergence for parallel subspace correction methods for nonlinear variational inequalities, In "Thirteenth International Domain Decomposition Conference" (Barcelona, Spain, 2002). [27] U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid," Academic Press, 2001. [28] P. S. Vassilevski and J. G. Wade, A comparison of multilevel methods for total variation regularization, Electron. Trans. Numer. Anal., 6 (1997), 255-270. Special issue on multilevel methods (Copper Mountain, CO, 1997). [29] C. R. Vogel, A multigrid method for total variation-based image denoising, In "Computation and Control, IV" (Bozeman, MT, 1994), volume 20 of Progr. Systems Control Theory, pages 323-331. Birkhauser Boston, 1995. [30] C. R. Vogel and M. E. Oman, "Iterative Methods for Total Variation Denoising," SIAM Journal on Scientific Computing, 1996. [31] C. R. Vogel, "Computational Methods for Inverse Problems," Frontiers Appl. Math. 23, SIAM Philadelphia, 2002. [32] P. Wesseling, "An Introduction to Multigrid Methods," John Wiley and Sons, 1992.

show all references

##### References:
 [1] USC-SIPI image database, In A. Weber, editor, http://sipi.usc.edu/services/database/Database.html, University of Southern California. [2] A. Bovik, "Handbook of Image and Video Processing," Academic Press, 2000. [3] A. Brandt, Guide to multigrid development, In "Multigrid Methods" (Cologne, 1981), volume 960 of Lecture Notes in Math., pages 220-312. Springer, 1982. [4] A. Chambolle, An algorithm for total variation minimization and application, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. [5] A. Chambolle and P-L. Lions, Image recovery via total variation minimization and related problems, Numerische Mathematik, 76 (1997), 167-188. doi: 10.1007/s002110050258. [6] T. Chan, K. Chen and J. L. Carter, Iterative methods for solving the dual formulation arising from image restoration, Electronic Transactions on Numerical Analysis, 26 (2007), 299-311. [7] T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), 1964-1977. doi: 10.1137/S1064827596299767. [8] Q. Chang and I-L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Applied Mathematics, 25 (2003), 982-994. [9] K. Chen, "Matrix Preconditioning Techniques and Applications," Cambridge University Press, 2005. doi: 10.1017/CBO9780511543258. [10] D. C. Dobson and C. R. Vogel, Convergence of an iterative method for total variation denoising, SIAM J. Numer. Anal., 34 (1997), 1779-1791. doi: 10.1137/S003614299528701X. [11] I. Ekeland and R. Témam, "Convex Analysis and Variational Problems," Classics Appl. Math. 28, SIAM, Philadelphia, 1999. [12] C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput. Vis. Sci., 7 (2004), 199-206. [13] E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Birkhäuser, Boston, 1984. [14] W. Hackbusch, "Multigrid Methods and Applications," volume 4 of Springer Series in Computational Mathematics, Springer-Verlag, 1985. [15] M. Hintermüller, K. Ito and K. Kunisch, The primal-dual active set strategy as a semismooth newton method, SIAM J. Optim., 13 (2002), 865-888. doi: 10.1137/S1052623401383558. [16] M. Hintermüller and K. Kunisch, Total bounded variation regularization as bilaterally constrained optimization problem, SIAM J. Appl. Math., 64 (2004), 1311-1333. doi: 10.1137/S0036139903422784. [17] M. Hintermüller and G. Stadler, An infeasible primal-dual algorithm for total bounded variation-based inf-convolution-type image restoration, SIAM Journal on Scientific Computing, 28 (2006), 1-23. doi: 10.1137/040613263. [18] M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., 101 (2004), 151-184. [19] P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo, Annals of Statistics, 1 (1973), 799-821. doi: 10.1214/aos/1176342503. [20] S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, SIAM Multiscale Model. and Simu., 4 (2005), 460-489. doi: 10.1137/040605412. [21] L. Rudin, "MTV-Multiscale Total Variation Principle for a PDE-Based Solution to Nonsmooth Ill-Posed Problem," Technical report, Cognitech, Inc. Talk presented at the Workshop on Mathematical Methods in Computer Vision, University of Minnesota, 1995. [22] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F. [23] D. Strong and T. Chan, "Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing," Technical report, UCLA, 1996. [24] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization, Inverse Problems, 19 (2003), 165-187. doi: 10.1088/0266-5611/19/6/059. [25] X.-C. Tai, "Rate of Convergence for Some Constraint Decomposition Methods for Nonlinear Variational Inequalities," Numerische Mathematik, 2003. [26] X.-C. Tai, B. Heimsund and J. Xu, Rate of convergence for parallel subspace correction methods for nonlinear variational inequalities, In "Thirteenth International Domain Decomposition Conference" (Barcelona, Spain, 2002). [27] U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid," Academic Press, 2001. [28] P. S. Vassilevski and J. G. Wade, A comparison of multilevel methods for total variation regularization, Electron. Trans. Numer. Anal., 6 (1997), 255-270. Special issue on multilevel methods (Copper Mountain, CO, 1997). [29] C. R. Vogel, A multigrid method for total variation-based image denoising, In "Computation and Control, IV" (Bozeman, MT, 1994), volume 20 of Progr. Systems Control Theory, pages 323-331. Birkhauser Boston, 1995. [30] C. R. Vogel and M. E. Oman, "Iterative Methods for Total Variation Denoising," SIAM Journal on Scientific Computing, 1996. [31] C. R. Vogel, "Computational Methods for Inverse Problems," Frontiers Appl. Math. 23, SIAM Philadelphia, 2002. [32] P. Wesseling, "An Introduction to Multigrid Methods," John Wiley and Sons, 1992.
 [1] Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems and Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [2] Ruiqiang He, Xiangchu Feng, Xiaolong Zhu, Hua Huang, Bingzhe Wei. RWRM: Residual Wasserstein regularization model for image restoration. Inverse Problems and Imaging, 2021, 15 (6) : 1307-1332. doi: 10.3934/ipi.2020069 [3] Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013 [4] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems and Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [5] Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems and Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337 [6] J. Mead. $\chi^2$ test for total variation regularization parameter selection. Inverse Problems and Imaging, 2020, 14 (3) : 401-421. doi: 10.3934/ipi.2020019 [7] Juan Carlos De los Reyes, Estefanía Loayza-Romero. Total generalized variation regularization in data assimilation for Burgers' equation. Inverse Problems and Imaging, 2019, 13 (4) : 755-786. doi: 10.3934/ipi.2019035 [8] Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems and Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565 [9] Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems and Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064 [10] Haijuan Hu, Jacques Froment, Baoyan Wang, Xiequan Fan. Spatial-Frequency domain nonlocal total variation for image denoising. Inverse Problems and Imaging, 2020, 14 (6) : 1157-1184. doi: 10.3934/ipi.2020059 [11] Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems and Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547 [12] Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems and Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008 [13] Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems and Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031 [14] Sudeb Majee, Subit K. Jain, Rajendra K. Ray, Ananta K. Majee. A fuzzy edge detector driven telegraph total variation model for image despeckling. Inverse Problems and Imaging, 2022, 16 (2) : 367-396. doi: 10.3934/ipi.2021054 [15] You-Wei Wen, Raymond Honfu Chan. Using generalized cross validation to select regularization parameter for total variation regularization problems. Inverse Problems and Imaging, 2018, 12 (5) : 1103-1120. doi: 10.3934/ipi.2018046 [16] Jing Xu, Xue-Cheng Tai, Li-Lian Wang. A two-level domain decomposition method for image restoration. Inverse Problems and Imaging, 2010, 4 (3) : 523-545. doi: 10.3934/ipi.2010.4.523 [17] Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems and Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507 [18] Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems and Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167 [19] Raymond H. Chan, Haixia Liang, Suhua Wei, Mila Nikolova, Xue-Cheng Tai. High-order total variation regularization approach for axially symmetric object tomography from a single radiograph. Inverse Problems and Imaging, 2015, 9 (1) : 55-77. doi: 10.3934/ipi.2015.9.55 [20] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems and Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022

2021 Impact Factor: 1.483