Algorithms and software for total variation image reconstruction via first-order methods | Numerical Algorithms Skip to main content
Springer Nature Link
Log in

Algorithms and software for total variation image reconstruction via first-order methods

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

This paper describes new algorithms and related software for total variation (TV) image reconstruction, more specifically: denoising, inpainting, and deblurring. The algorithms are based on one of Nesterov’s first-order methods, tailored to the image processing applications in such a way that, except for the mandatory regularization parameter, the user needs not specify any parameters in the algorithms. The software is written in C with interface to Matlab (version 7.5 or later), and we demonstrate its performance and use with examples.

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

Similar content being viewed by others

References

  1. Alter, F., Durand, S., Froment, J.: Adapted total variation for artifact free decompression of JPEG images. J. Math. Imaging Vis. 23, 199–211 (2005)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  3. Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)

    MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Chan, T.F., Shen, J.: Image processing and analysis: variational, PDE, wavelet, and stochastic methods. SIAM, Philadelphia (2005)

    MATH  Google Scholar 

  6. 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 

  7. Combettes, P.L., Pennanen, T.: Generalized mann iterates for constructing fixed points in Hilbert spaces. J. Math. Anal. Appl. 275, 521–536 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-region methods. SIAM, Philadelphia (2000)

    MATH  Google Scholar 

  9. Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation. Part I: fast and exact optimization. J. Math. Imaging Vis. 26, 261–276 (2006)

    Article  MathSciNet  Google Scholar 

  10. FFTW: Freely available C subroutine library for computing the discrete Fourier transform (DFT) in one or more dimensions. http://www.fftw.org (2009)

  11. Fornasier, M., Schönlieb, C.-B.: Subspace correction methods for total variation and ℓ1-minimization. SIAM J. Numer. Anal. (2009, in press)

  12. Frigo, M., Johnson, S.G.: The design and implementation of FFTW3. Proc. IEEE 93, 216–231 (2005)

    Article  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. Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  15. Hansen, P.C., Nagy, J.G., O’Leary, D.P.: Deblurring Images: Matrices, Spectra, and Filtering. SIAM, Philadelphia (2006)

    MATH  Google Scholar 

  16. Krishnan, D., Ping, L., Yip, A.M.: A primal-dual active-set methods for non-negativity constrained total variation deblurring problems. IEEE Trans. Image Process. 16, 2766–2777 (2007)

    Article  MathSciNet  Google Scholar 

  17. Nesterov, Yu.: Introductory lectures on convex optimization. Kluwer, Dordrecht (2004)

    MATH  Google Scholar 

  18. Nesterov, Yu.: Smooth minimization of nonsmooth functions. Math. Program. Ser. A 103, 127–152 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  19. Nesterov, Yu.: Excessive gap technique in non-smooth convex optimization. SIAM J. Optim. 16, 235–249 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  20. Nesterov, Yu.: Gradient methods for minimizing composite objective functions. CORE Discussion Papers series, Université Catholique de Louvain, Center for Operations Research and Econometrics. http://www.uclouvain.be/en-44660.html (2007)

  21. Vogel, C.R.: Computational methods for inverse problems. SIAM, Philadelphia (2002)

    MATH  Google Scholar 

  22. Weiss, P., Blanc-Féraud, L., Aubert, G.: Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. 31, 2047–2080 (2009)

    Article  MathSciNet  Google Scholar 

  23. Yang, J., Zhang, Y., Yin, W., Wang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1, 248–272 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Zhu, M., Wright, S., Chan, T.F.: Duality-based algorithms for total-variation-regularized image restoration. Comput. Optim. Appl. (2008). doi:10.1007/s10589-008-9225-2

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. AnyBody Technology A/S, Niels Jernes Vej 10, 9220, Aalborg Ø, Denmark

    Joachim Dahl

  2. Department of Informatics and Mathematical Modelling, Technical University of Denmark, Building 321, 2800, Lyngby, Denmark

    Per Christian Hansen

  3. Department of Electronic Systems, Aalborg University, Niels Jernesvej 12, 9220, Aalborg Ø, Denmark

    Søren Holdt Jensen & Tobias Lindstrøm Jensen

Authors
  1. Joachim Dahl
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Per Christian Hansen
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Søren Holdt Jensen
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Tobias Lindstrøm Jensen
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Per Christian Hansen.

Additional information

This work is part of the project CSI: Computational Science in Imaging, supported by grant no. 274-07-0065 from the Danish Research Council for Technology and Production Sciences. J. Dahl’s work was carried out at Aalborg University.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dahl, J., Hansen, P.C., Jensen, S.H. et al. Algorithms and software for total variation image reconstruction via first-order methods. Numer Algor 53, 67–92 (2010). https://doi.org/10.1007/s11075-009-9310-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-009-9310-3

Keywords

Mathematics Subject Classifications (2000)