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

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

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 and 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 "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,, , ().
[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

2020 Impact Factor: 1.639

Tools

Metrics

Other articles
by authors

on AIMS
Ke Chen Yiqiu Dong Michael Hintermüller
on Google Scholar
Ke Chen Yiqiu Dong Michael Hintermüller

[Back to Top]