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

Previous Article
On an inverse problem in electromagnetism with local data: stability and uniqueness
IPI Home
This Issue
Next Article
3D coded aperture imaging, ill-posedness and link with incomplete data radon transform

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

Ke Chen ^1, , Yiqiu Dong ^2, and Michael Hintermüller ^3,

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

Abstract
Related Papers

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].

Keywords: multigrid method., Image restoration, total variation regularization, duality.

Mathematics Subject Classification: Primary: 65M55, 94A08; Secondary: 49M2.

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

American Institute of Mathematical Sciences