# 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 & Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323
##### References:
 [1] USC-SIPI image database, In A. Weber, editor,, , (). [2] A. Bovik, "Handbook of Image and Video Processing,", Academic Press, (2000). [3] A. Brandt, Guide to multigrid development,, In, 960 (1981), 220. [4] A. Chambolle, An algorithm for total variation minimization and application,, Journal of Mathematical Imaging and Vision, 20 (2004), 89. [5] A. Chambolle and P-L. Lions, Image recovery via total variation minimization and related problems,, Numerische Mathematik, 76 (1997), 167. 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. [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. 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. [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. doi: 10.1137/S003614299528701X. [11] I. Ekeland and R. Témam, "Convex Analysis and Variational Problems,", Classics Appl. Math. 28, (1999). [12] C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising,, Comput. Vis. Sci., 7 (2004), 199. [13] E. Giusti, "Minimal Surfaces and Functions of Bounded Variation,", Birkhäuser, (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. 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. 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. doi: 10.1137/040613263. [18] M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods,, Math. Program., 101 (2004), 151. [19] P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo,, Annals of Statistics, 1 (1973), 799. 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. doi: 10.1137/040605412. [21] L. Rudin, "MTV-Multiscale Total Variation Principle for a PDE-Based Solution to Nonsmooth Ill-Posed Problem,", Technical report, (1995). [22] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. 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, (1996). [24] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization,, Inverse Problems, 19 (2003), 165. 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, (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. [29] C. R. Vogel, A multigrid method for total variation-based image denoising,, In, 20 (1994), 323. [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, (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,, , (). [2] A. Bovik, "Handbook of Image and Video Processing,", Academic Press, (2000). [3] A. Brandt, Guide to multigrid development,, In, 960 (1981), 220. [4] A. Chambolle, An algorithm for total variation minimization and application,, Journal of Mathematical Imaging and Vision, 20 (2004), 89. [5] A. Chambolle and P-L. Lions, Image recovery via total variation minimization and related problems,, Numerische Mathematik, 76 (1997), 167. 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. [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. 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. [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. doi: 10.1137/S003614299528701X. [11] I. Ekeland and R. Témam, "Convex Analysis and Variational Problems,", Classics Appl. Math. 28, (1999). [12] C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising,, Comput. Vis. Sci., 7 (2004), 199. [13] E. Giusti, "Minimal Surfaces and Functions of Bounded Variation,", Birkhäuser, (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. 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. 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. doi: 10.1137/040613263. [18] M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods,, Math. Program., 101 (2004), 151. [19] P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo,, Annals of Statistics, 1 (1973), 799. 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. doi: 10.1137/040605412. [21] L. Rudin, "MTV-Multiscale Total Variation Principle for a PDE-Based Solution to Nonsmooth Ill-Posed Problem,", Technical report, (1995). [22] L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms,, Physica D, 60 (1992), 259. 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, (1996). [24] D. Strong and T. Chan, Edge-preserving and scale-dependent properties of total variation regularization,, Inverse Problems, 19 (2003), 165. 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, (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. [29] C. R. Vogel, A multigrid method for total variation-based image denoising,, In, 20 (1994), 323. [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, (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 & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237 [2] Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171 [3] Bartomeu Coll, Joan Duran, Catalina Sbert. Half-linear regularization for nonconvex image restoration models. Inverse Problems & Imaging, 2015, 9 (2) : 337-370. doi: 10.3934/ipi.2015.9.337 [4] Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565 [5] Juan Carlos De los Reyes, Estefanía Loayza-Romero. Total generalized variation regularization in data assimilation for Burgers' equation. Inverse Problems & Imaging, 2019, 13 (4) : 755-786. doi: 10.3934/ipi.2019035 [6] Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547 [7] Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems & Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008 [8] Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031 [9] You-Wei Wen, Raymond Honfu Chan. Using generalized cross validation to select regularization parameter for total variation regularization problems. Inverse Problems & Imaging, 2018, 12 (5) : 1103-1120. doi: 10.3934/ipi.2018046 [10] 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 [11] Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507 [12] Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167 [13] 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 & Imaging, 2015, 9 (1) : 55-77. doi: 10.3934/ipi.2015.9.55 [14] Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022 [15] Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455 [16] 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 [17] 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 [18] Xin-Guo Liu, Kun Wang. A multigrid method for the maximal correlation problem. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 785-796. doi: 10.3934/naco.2012.2.785 [19] Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 [20] Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191

2017 Impact Factor: 1.465