American Institute of Mathematical Sciences

Advanced
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

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,, , ().   Google Scholar

[2]

A. Bovik, "Handbook of Image and Video Processing," Academic Press, 2000. Google Scholar

[3]

A. Brandt, Guide to multigrid development, In "Multigrid Methods" (Cologne, 1981), volume 960 of Lecture Notes in Math., pages 220-312. Springer, 1982.  Google Scholar

[4]

A. Chambolle, An algorithm for total variation minimization and application, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[8]

Q. Chang and I-L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Applied Mathematics, 25 (2003), 982-994. Google Scholar

[9]

K. Chen, "Matrix Preconditioning Techniques and Applications," Cambridge University Press, 2005. doi: 10.1017/CBO9780511543258.  Google Scholar

[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.  Google Scholar

[11]

I. Ekeland and R. Témam, "Convex Analysis and Variational Problems," Classics Appl. Math. 28, SIAM, Philadelphia, 1999. Google Scholar

[12]

C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput. Vis. Sci., 7 (2004), 199-206.  Google Scholar

[13]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Birkhäuser, Boston, 1984. Google Scholar

[14]

W. Hackbusch, "Multigrid Methods and Applications," volume 4 of Springer Series in Computational Mathematics, Springer-Verlag, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., 101 (2004), 151-184.  Google Scholar

[19]

P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo, Annals of Statistics, 1 (1973), 799-821. doi: 10.1214/aos/1176342503.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

D. Strong and T. Chan, "Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing," Technical report, UCLA, 1996. Google Scholar

[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.  Google Scholar

[25]

X.-C. Tai, "Rate of Convergence for Some Constraint Decomposition Methods for Nonlinear Variational Inequalities," Numerische Mathematik, 2003. Google Scholar

[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). Google Scholar

[27]

U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid," Academic Press, 2001. Google Scholar

[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).  Google Scholar

[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.  Google Scholar

[30]

C. R. Vogel and M. E. Oman, "Iterative Methods for Total Variation Denoising," SIAM Journal on Scientific Computing, 1996. Google Scholar

[31]

C. R. Vogel, "Computational Methods for Inverse Problems," Frontiers Appl. Math. 23, SIAM Philadelphia, 2002. Google Scholar

[32]

P. Wesseling, "An Introduction to Multigrid Methods," John Wiley and Sons, 1992. Google Scholar

show all references

References:
[1]

USC-SIPI image database, In A. Weber, editor,, , ().   Google Scholar

[2]

A. Bovik, "Handbook of Image and Video Processing," Academic Press, 2000. Google Scholar

[3]

A. Brandt, Guide to multigrid development, In "Multigrid Methods" (Cologne, 1981), volume 960 of Lecture Notes in Math., pages 220-312. Springer, 1982.  Google Scholar

[4]

A. Chambolle, An algorithm for total variation minimization and application, Journal of Mathematical Imaging and Vision, 20 (2004), 89-97. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[8]

Q. Chang and I-L. Chern, Acceleration methods for total variation-based image denoising, SIAM J. Applied Mathematics, 25 (2003), 982-994. Google Scholar

[9]

K. Chen, "Matrix Preconditioning Techniques and Applications," Cambridge University Press, 2005. doi: 10.1017/CBO9780511543258.  Google Scholar

[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.  Google Scholar

[11]

I. Ekeland and R. Témam, "Convex Analysis and Variational Problems," Classics Appl. Math. 28, SIAM, Philadelphia, 1999. Google Scholar

[12]

C. Frohn-Schauf, S. Henn and K. Witsch, Nonlinear multigrid methods for total variation image denoising, Comput. Vis. Sci., 7 (2004), 199-206.  Google Scholar

[13]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation," Birkhäuser, Boston, 1984. Google Scholar

[14]

W. Hackbusch, "Multigrid Methods and Applications," volume 4 of Springer Series in Computational Mathematics, Springer-Verlag, 1985.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

M. Hintermüller and M. Ulbrich, A mesh-independence result for semismooth Newton methods, Math. Program., 101 (2004), 151-184.  Google Scholar

[19]

P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo, Annals of Statistics, 1 (1973), 799-821. doi: 10.1214/aos/1176342503.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[23]

D. Strong and T. Chan, "Spatially and Scale Adaptive Total Variation Based Regularization and Anisotropic Diffusion in Image Processing," Technical report, UCLA, 1996. Google Scholar

[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.  Google Scholar

[25]

X.-C. Tai, "Rate of Convergence for Some Constraint Decomposition Methods for Nonlinear Variational Inequalities," Numerische Mathematik, 2003. Google Scholar

[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). Google Scholar

[27]

U. Trottenberg, C. W. Oosterlee and A. Schüller, "Multigrid," Academic Press, 2001. Google Scholar

[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).  Google Scholar

[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.  Google Scholar

[30]

C. R. Vogel and M. E. Oman, "Iterative Methods for Total Variation Denoising," SIAM Journal on Scientific Computing, 1996. Google Scholar

[31]

C. R. Vogel, "Computational Methods for Inverse Problems," Frontiers Appl. Math. 23, SIAM Philadelphia, 2002. Google Scholar

[32]

P. Wesseling, "An Introduction to Multigrid Methods," John Wiley and Sons, 1992. Google Scholar

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

Ruiqiang He, Xiangchu Feng, Xiaolong Zhu, Hua Huang, Bingzhe Wei. RWRM: Residual Wasserstein regularization model for image restoration. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020069
[3]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.639

Tools

Metrics

  • PDF downloads (61)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences