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

[4]

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

[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.  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.   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.  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.   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.  doi: 10.1137/S003614299528701X.  Google Scholar

[11]

I. Ekeland and R. Témam, "Convex Analysis and Variational Problems,", Classics Appl. Math. 28, (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.   Google Scholar

[13]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation,", Birkhäuser, (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.  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.  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.  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.   Google Scholar

[19]

P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo,, Annals of Statistics, 1 (1973), 799.  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.  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, (1995).   Google Scholar

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

[23]

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

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

[29]

C. R. Vogel, A multigrid method for total variation-based image denoising,, In, 20 (1994), 323.   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, (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, 960 (1981), 220.   Google Scholar

[4]

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

[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.  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.   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.  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.   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.  doi: 10.1137/S003614299528701X.  Google Scholar

[11]

I. Ekeland and R. Témam, "Convex Analysis and Variational Problems,", Classics Appl. Math. 28, (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.   Google Scholar

[13]

E. Giusti, "Minimal Surfaces and Functions of Bounded Variation,", Birkhäuser, (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.  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.  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.  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.   Google Scholar

[19]

P. J. Huber, Robust regression: Asymptotics, conjectures, and Monte Carlo,, Annals of Statistics, 1 (1973), 799.  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.  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, (1995).   Google Scholar

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

[23]

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

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

[29]

C. R. Vogel, A multigrid method for total variation-based image denoising,, In, 20 (1994), 323.   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, (2002).   Google Scholar

[32]

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

[1]

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

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013
[3]

Yi-Hsuan Lin, Gen Nakamura, Roland Potthast, Haibing Wang. Duality between range and no-response tests and its application for inverse problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020072
[4]

Kha Van Huynh, Barbara Kaltenbacher. Some application examples of minimization based formulations of inverse problems and their regularization. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020074
[5]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321
[6]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019
[7]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076
[8]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078
[9]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[10]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250
[11]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120
[12]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[13]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319
[14]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[15]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351
[16]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355
[17]

Gervy Marie Angeles, Gilbert Peralta. Energy method for exponential stability of coupled one-dimensional hyperbolic PDE-ODE systems. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020108
[18]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[19]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[20]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.373

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences