Dual Norm Based Iterative Methods for Image Restoration | Journal of Mathematical Imaging and Vision Skip to main content
Springer Nature Link
Log in

Dual Norm Based Iterative Methods for Image Restoration

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

Abstract

A convergent iterative regularization procedure based on the square of a dual norm is introduced for image restoration models with general (quadratic or non-quadratic) convex fidelity terms. Iterative regularization methods have been previously employed for image deblurring or denoising in the presence of Gaussian noise, which use L 2 (Tadmor et al. in Multiscale Model. Simul. 2:554–579, 2004; Osher et al. in Multiscale Model. Simul. 4:460–489, 2005; Tadmor et al. in Commun. Math. Sci. 6(2):281–307, 2008), and L 1 (He et al. in J. Math. Imaging Vis. 26:167–184, 2005) data fidelity terms, with rigorous convergence results. Recently, Iusem and Resmerita (Set-Valued Var. Anal. 18(1):109–120, 2010) proposed a proximal point method using inexact Bregman distance for minimizing a convex function defined on a non-reflexive Banach space (e.g. BV(Ω)), which is the dual of a separable Banach space. Based on this method, we investigate several approaches for image restoration such as image deblurring in the presence of noise or image deblurring via (cartoon+texture) decomposition. We show that the resulting proximal point algorithms approximate stably a true image. For image denoising-deblurring we consider Gaussian, Laplace, and Poisson noise models with the corresponding convex fidelity terms as in the Bayesian approach. We test the behavior of proposed algorithms on synthetic and real images in several numerical experiments and compare the results with other state-of-the-art iterative procedures based on the total variation penalization as well as the corresponding existing one-step gradient descent implementations. The numerical experiments indicate that the iterative procedure yields high quality reconstructions and superior results to those obtained by one-step standard gradient descent, with faster computational time.

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. Attouch, H., Buttazzo, G., Michaille, G.: Variational Analysis in Sobolev and BV Spaces. MPS-SIAM Series on Optimization (2006)

    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. Barbu, V., Precupanu, T.: Convexity and Optimization in Banach Spaces. Reidel, Dordrecht (1985)

    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(11), 2419–2434 (2009)

    Article  MathSciNet  Google Scholar 

  5. Benning, M., Burger, M.: Error estimates for variational models with non-Gaussian noise. UCLA CAM Report 09-40 (2009)

  6. Bregman, L.M.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. U.S.S.R. Comput. Math. Math. Phys. 7, 200–217 (1967)

    Article  Google Scholar 

  7. Brune, C., Sawatzky, A., Kösters, T., Wübbeling, F., Burger, M.: An Analytical View on EM-TV Based Methods for Inverse Problems with Poisson Noise (2009)

    Google Scholar 

  8. Burger, M., Resmerita, E., He, L.: Error estimation for Bregman iterations and inverse scale space methods in image restoration. Computing 81(2–3), 109–135 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Burger, M., Kaltenbacher, B., Neubauer, A.: Iterative solution methods. In: Scherzer, O. (ed.) Handbook of Mathematical Methods in Imaging. Springer, Berlin (2010)

    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(1), 120–145 (2011)

    Article  MathSciNet  Google Scholar 

  11. Chan, T.F., Esedoglu, S.: Aspects of total variation regularized L1 function approximation. SIAM J. Appl. Math. 65(5), 1817–1837 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  13. Ekeland, I., Temam, R.: Convex Analysis and Variational Problems, SIAM, Philadelphia (1999)

    Book  MATH  Google Scholar 

  14. Frick, K., Scherzer, O.: Regularization of ill-posed linear equations by the non-stationary augmented Lagrangian method. J. Integral Equ. Appl. 22, 217–258 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Frick, K., Lorenz, D., Resmerita, E.: Morozov’s principle for the augmented Lagrangian method applied to linear inverse problems. arXiv:1010.5181

  16. Gossez, J.P.: Opérateurs monotones nonlineaires dans les espaces de Banach nonreflexifs. J. Math. Anal. Appl. 34, 371–395 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  17. Bonnans, J.F., Gilbert, J.Ch., Lemaréchal, C., Sagastizábal, C.: Numerical Optimization: Theoretical and Practical Aspects, 2nd edn. Springer, Berlin (2006)

    MATH  Google Scholar 

  18. Solodov, M.V.: On approximations with finite precision in bundle methods for nonsmooth optimization. J. Optim. Theory Appl. 119, 151–165 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kiwiel, K.C.: A proximal bundle method with approximate subgradient linearizations. SIAM J. Optim. 16, 1007–1023 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  20. He, L., Osher, S., Burger, M.: Iterative total variation regularization with non-quadratic fidelity. J. Math. Imaging Vis. 26, 167–184 (2005)

    Article  MathSciNet  Google Scholar 

  21. Iusem, A.N., Resmerita, E.: A proximal point method in nonreflexive Banach spaces. Set-Valued Var. Anal. 18(1), 109–120 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  22. Jung, M., Resmerita, E., Vese, L.A.: An iterative method with general convex fidelity term for image restoration. In: Proceedings of the 11th European Conference on Computer Vision (ECCV 2010), September 2010

    Google Scholar 

  23. Kim, Y., Vese, L.A.: Image recovery using functions of bounded variation and Sobolev spaces of negative differentiability. Inverse Probl. Imaging 3, 43–68 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  24. Marques, A.M., Svaiter, B.: On the surjectivity properties of perturbations of maximal monotone operators in non-reflexive Banach spaces. J. Convex Anal. 18, 209–226 (2011)

    MathSciNet  MATH  Google Scholar 

  25. Meyer, Y.: Oscillatory Patterns in Image Processing and Nonlinear Evolution Equations. University Lecture Series, vol. 22. American Mathematical Society, Providence (2001)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  27. Pöschl, C.: Regularization with a similarity measure. PhD Thesis, University of Innsbruck (2008)

  28. Resmerita, E., Anderssen, R.S.: Joint additive Kullback–Leibler residual minimization and regularization for linear inverse problems. Math. Methods Appl. Sci. 30(13), 1527–1544 (2007)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  30. Rudin, L.I., Osher, S.: Total variation based image restoration with free local constraints. In: ICIP (1), pp. 31–35 (1994)

    Google Scholar 

  31. Sawatzky, A., Brune, C., Mueller, J., Burger, M.: Total Variation Processing of Images with Poisson Statistics. LNCS, vol. 5702, pp. 533–540 (2009)

    Google Scholar 

  32. Scherzer, O., Groetsch, C.: Inverse scale space theory for inverse problems. In: Kerckhove, M. (ed.) Scale-Space and Morphology in Computer Vision. LNCS, vol. 2106, pp. 317–325. Springer, New York (2001)

    Chapter  Google Scholar 

  33. Scherzer, O., Grasmair, M., Grossauer, H., Haltmeier, M., Lenzen, F.: Variational Methods in Imaging. Applied Mathematical Sciences, vol. 167. Springer, Berlin (2009)

    MATH  Google Scholar 

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

  35. Tadmor, E., Nezzar, S., Vese, L.: A multiscale image representation using hierarchical (BV,L 2) decompositions. Multiscale Model. Simul. 2, 554–579 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  36. Tadmor, E., Nezzar, S., Vese, L.: Multiscale hierarchical decomposition of images with applications to deblurring, denoising and segmentation. Commun. Math. Sci. 6(2), 281–307 (2008)

    MathSciNet  MATH  Google Scholar 

  37. Treves, F.: Topological Vector Spaces Distributions, and Kernels. Pure and Applied Mathematics, vol. 25. Academic Press, New York (1967)

    MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  39. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithm for l 1 minimization with applications to compressed sensing. SIAM J. Imaging Sci. 1(1), 143–168 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  40. Zalinescu, C.: Personal communication (2010)

  41. Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. UCLA CAM Report, pp. 08–34 (2008)

Download references

Author information

Authors and Affiliations

  1. Ceremade, University of Paris-Dauphine, 75775, Paris Cedex 16, France

    Miyoun Jung

  2. Institute of Mathematics, Alpen-Adria University, Universitaetsstrasse 65-67, 9020, Klagenfurt, Austria

    Elena Resmerita

  3. Department of Mathematics, University of California at Los Angeles (UCLA), Los Angeles, CA, 90095, USA

    Luminita A. Vese

Authors
  1. Miyoun Jung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Elena Resmerita
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luminita A. Vese
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Luminita A. Vese.

Additional information

Research supported by a UC Dissertation Year Fellowship, by Austrian Science Fund Elise Richter Scholarship V82-N18 FWF, by NSF-DMS Award 0714945, and by NSF Expeditions in Computing Award CCF-0926127.

The work of the first author was mainly done while at the University of California, Los Angeles. The work of the second author was mainly done while at the Johannes Kepler University, Linz, Austria.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Jung, M., Resmerita, E. & Vese, L.A. Dual Norm Based Iterative Methods for Image Restoration. J Math Imaging Vis 44, 128–149 (2012). https://doi.org/10.1007/s10851-011-0318-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-011-0318-7

Keywords