On the Convergence of Primal–Dual Hybrid Gradient Algorithms for Total Variation Image Restoration | Journal of Mathematical Imaging and Vision Skip to main content
Springer Nature Link
Log in

On the Convergence of Primal–Dual Hybrid Gradient Algorithms for Total Variation Image Restoration

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

In this paper we establish the convergence of a general primal–dual method for nonsmooth convex optimization problems whose structure is typical in the imaging framework, as, for example, in the Total Variation image restoration problems. When the steplength parameters are a priori selected sequences, the convergence of the scheme is proved by showing that it can be considered as an ε-subgradient method on the primal formulation of the variational problem. Our scheme includes as special case the method recently proposed by Zhu and Chan for Total Variation image restoration from data degraded by Gaussian noise. Furthermore, the convergence hypotheses enable us to apply the same scheme also to other restoration problems, as the denoising and deblurring of images corrupted by Poisson noise, where the data fidelity function is defined as the generalized Kullback–Leibler divergence or the edge preserving removal of impulse noise. The numerical experience shows that the proposed scheme with a suitable choice of the steplength sequences performs well with respect to state-of-the-art methods, especially for Poisson denoising problems, and it exhibits fast initial and asymptotic convergence.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  1. Arrow, K.J., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-Linear Programming, vol. II. Stanford University Press, Stanford (1958)

    MATH  Google Scholar 

  2. Aujol, J.F.: Some first-order algorithms for total variation based image restoration. J. Math. Imaging Vis. 34(3), 307–327 (2009)

    Article  MathSciNet  Google Scholar 

  3. Bardsley, J.M., Luttman, A.: Total variation-penalized Poisson likelihood estimation for ill-posed problems. Adv. Comput. Math. 31(1–3), 35–59 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  4. Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. 18, 2419–2434 (2009)

    Article  MathSciNet  Google Scholar 

  5. Bertsekas, D.: Convex Optimization Theory. Scientific, Athena (2009)

    MATH  Google Scholar 

  6. Bonettini, S., Ruggiero, V.: An alternating extragradient method for total variation based image restoration from Poisson data. Inverse Probl. 27, 095001 (2011)

    Article  MathSciNet  Google Scholar 

  7. Brune, C., Sawatzky, A., Wübbeling, F., Kösters, T., Burger, M.: Forward–Backward EM-TV methods for inverse problems with Poisson noise. http://wwwmath.uni-muenster.de/num/publications/2009/BBSKW09/ (2009)

  8. Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004)

    Article  MathSciNet  Google Scholar 

  9. Chambolle, A.: Total variation minimization and a class of binary MRF models. In: EMMCVPR 05. Lecture Notes in Computer Sciences, vol. 3757, pp. 136–152 (2005)

    Google Scholar 

  10. Chambolle, A., Pock, T.: A first-order primal–dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120–145 (2011)

    Article  MathSciNet  Google Scholar 

  11. Chan, T.F., Golub, G.H., Mulet, P.: A nonlinear primal–dual method for total variation based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Charbonnier, P., Blanc-Féraud, L., Aubert, G., Barlaud, A.: Deterministic edge-preserving regularization in computed imaging. IEEE Trans. Image Process. 6, 298–311 (1997)

    Article  Google Scholar 

  13. Correa, R., Lemaréchal, C.: Convergence of some algorithms for convex minimization. Math. Program. 62, 261–275 (1993)

    Article  MATH  Google Scholar 

  14. Dahl, J., Hansen, P.C., Jensen, S.H., Jensen, T.L.: Algorithms and software for total variation image reconstruction via first-order methods. Numer. Algorithms 53, 67–92 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Ekeland, I., Témam, R.: Convex Analysis and Variational Problems. SIAM, Philadelphia (1999)

    Book  MATH  Google Scholar 

  16. Esser, E., Zhang, X., Chan, T.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015–1046 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Geman, S., Geman, D.: Stochastic relaxation, Gibbs distribution and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984)

    Article  MATH  Google Scholar 

  18. Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation based image restoration. SIAM J. Sci. Comput. 27(2), 622–645 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  19. Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  20. Larsson, T., Patriksson, M., Strömberg, A.B.: On the convergence of conditional ε-subgradient methods for convex programs and convex–concave saddle-point problems. Eur. J. Oper. Res. 151, 461–473 (2003)

    Article  MATH  Google Scholar 

  21. Le, T., Chartrand, R., Asaki, T.J.: A variational approach to reconstructing images corrupted by Poisson noise. J. Math. Imaging Vis. 27, 257–263 (2007)

    Article  MathSciNet  Google Scholar 

  22. Osher, S., Burger, M., Goldfarb, D., Xu, J., Yin, W.: An iterative regularization method for total variation-based image restoration. SIAM J. Multiscale Model. Simul. 4(2), 460–489 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  23. Robinson, S.M.: Linear convergence of epsilon-subgradient descent methods for a class of convex functions. Math. Program., Ser. A 86, 41–50 (1999)

    Article  MATH  Google Scholar 

  24. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    MATH  Google Scholar 

  25. Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)

    Article  MATH  Google Scholar 

  26. Setzer, S., Steidl, G., Teuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21, 193–199 (2010)

    Article  Google Scholar 

  27. Shepp, L.A., Vardi, Y.: Maximum likelihood reconstruction for emission tomography. IEEE Trans. Med. Imaging 1, 113–122 (1982)

    Article  Google Scholar 

  28. Willett, R.M., Nowak, R.D.: Platelets: a multiscale approach for recovering edges and surfaces in photon limited medical imaging. IEEE Trans. Med. Imaging 22, 332–350 (2003)

    Article  Google Scholar 

  29. Yu, G., Qi, L., Dai, Y.: On nonmonotone Chambolle gradient projection algorithms for total variation image restoration. J. Math. Imaging Vis. 35, 143–154 (2009)

    Article  MathSciNet  Google Scholar 

  30. Zanella, R., Boccacci, P., Zanni, L., Bertero, M.: Efficient gradient projection methods for edge-preserving removal of Poisson noise. Inverse Probl. 25, 045010 (2009)

    Article  MathSciNet  Google Scholar 

  31. Zhu, M., Chan, T.F.: An efficient primal–dual hybrid gradient algorithm for Total Variation image restoration. CAM Report 08-34, UCLA (2008)

  32. Zhu, M., Wright, S.J., Chan, T.F.: Duality-based algorithms for total-variation-regularized image restoration. Comput. Optim. Appl. 47, 377–400 (2008)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We are grateful to the anonymous referees for their comments, which stimulated us to greatly improve the paper.

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Ferrara, Ferrara, Italy

    Silvia Bonettini & Valeria Ruggiero

  2. LTTA Lab, University of Ferrara, Ferrara, Italy

    Valeria Ruggiero

Authors
  1. Silvia Bonettini
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valeria Ruggiero
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Silvia Bonettini.

Additional information

This work is supported by the PRIN2008 Project of the Italian Ministry of University and Research, grant 2008T5KA4L, Optimization Methods and Software for Inverse Problems, http://www.unife.it/prisma.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bonettini, S., Ruggiero, V. On the Convergence of Primal–Dual Hybrid Gradient Algorithms for Total Variation Image Restoration. J Math Imaging Vis 44, 236–253 (2012). https://doi.org/10.1007/s10851-011-0324-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-011-0324-9

Keywords

Search

Navigation