Skip to main content
SpringerLink
Log in

Duality-based algorithms for total-variation-regularized image restoration

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Image restoration models based on total variation (TV) have become popular since their introduction by Rudin, Osher, and Fatemi (ROF) in 1992. The dual formulation of this model has a quadratic objective with separable constraints, making projections onto the feasible set easy to compute. This paper proposes application of gradient projection (GP) algorithms to the dual formulation. We test variants of GP with different step length selection and line search strategies, including techniques based on the Barzilai-Borwein method. Global convergence can in some cases be proved by appealing to existing theory. We also propose a sequential quadratic programming (SQP) approach that takes account of the curvature of the boundary of the dual feasible set. Computational experiments show that the proposed approaches perform well in a wide range of applications and that some are significantly faster than previously proposed methods, particularly when only modest accuracy in the solution is required.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  2. Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Nashua (1999)

    MATH  Google Scholar 

  3. Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10(4), 1196–1211 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  4. Carter, J.L.: Dual method for total variation-based image restoration. Report 02-13, UCLA CAM (2002)

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

    Article  MathSciNet  Google Scholar 

  6. Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76, 167–188 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Chan, T.F., Zhu, M.: Fast algorithms for total variation-based image processing. In: Proceedings of the 4th ICCM. Hangzhuo, China (2007)

  8. 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  MATH  MathSciNet  Google Scholar 

  9. Chan, T.F., Esedoglu, S., Park, F., Yip, A.: Total variation image restoration: Overview and recent developments. In: Paragios, N., Chen, Y., Faugeras, O. (eds.) Handbook of Mathematical Models in Computer Vision. Springer, Berlin (2005)

    Google Scholar 

  10. Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  11. Dai, Y.H., Hager, W.W., Schittkowski, K., Zhang, H.: The cyclic Barzilai-Borwein method for unconstrained optimization. IMA J. Numer. Anal. 26, 604–627 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  12. Ekeland, I., Témam, R.: Convex Analysis and Variational Problems. SIAM Classics in Applied Mathematics. SIAM, Philadelphia (1999)

    MATH  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  14. Hintermüller, M., Stadler, G.: An infeasible primal-dual algorithm for TV-based inf-convolution-type image restoration. SIAM J. Sci. Comput. 28, 1–23 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  15. Hiriart-Urruty, J., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vol. I. Springer, Berlin (1993)

    Google Scholar 

  16. Osher, S., Marquina, A.: Explicit algorithms for a new time dependent model based on level set motion for nonlinear deblurring and noise removal. SIAM J. Sci. Comput. 22, 387–405 (2000)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  18. Serafini, T., Zanghirati, G., Zanni, L.: Gradient projection methods for large quadratic programs and applications in training support vector machines. Optim. Methods Softw. 20(2–3), 353–378 (2004)

    MathSciNet  Google Scholar 

  19. Vogel, C.R., Oman, M.E.: Iterative methods for total variation denoising. SIAM J. Sci. Comput. 17, 227–238 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  20. Wang, Y., Ma, S.: Projected Barzilai-Borwein methods for large-scale nonnegative image restoration. Inverse Probl. Sci. Eng. 15(6), 559–583 (2007)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Department, UCLA, Box 951555, Los Angeles, CA, 90095-1555, USA

    Mingqiang Zhu & Tony F. Chan

  2. Department of Computer Sciences, University of Wisconsin, 1210 W. Dayton Street, Madison, WI, 53705, USA

    Stephen J. Wright

Authors
  1. Mingqiang Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Stephen J. Wright
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tony F. Chan
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Stephen J. Wright.

Additional information

Computational and Applied Mathematics Report 08-33, UCLA, October, 2008 (Revised). This work was supported by National Science Foundation grants DMS-0610079, DMS-0427689, CCF-0430504, CTS-0456694, and CNS-0540147, and Office of Naval Research grant N00014-06-1-0345. The work was performed while T. Chan was on leave at the National Science Foundation as Assistant Director of Mathematics and Physical Sciences.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zhu, M., Wright, S.J. & Chan, T.F. Duality-based algorithms for total-variation-regularized image restoration. Comput Optim Appl 47, 377–400 (2010). https://doi.org/10.1007/s10589-008-9225-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-008-9225-2

Keywords

Search

Navigation