Skip to main content
SpringerLink
Log in

Removing Multiplicative Noise by Douglas-Rachford Splitting Methods

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

Abstract

In this paper, we consider a variational restoration model consisting of the I-divergence as data fitting term and the total variation semi-norm or nonlocal means as regularizer for removing multiplicative Gamma noise. Although the I-divergence is the typical data fitting term when dealing with Poisson noise we substantiate why it is also appropriate for cleaning Gamma noise. We propose to compute the minimizers of our restoration functionals by applying Douglas-Rachford splitting techniques, resp. alternating direction methods of multipliers. For a particular splitting, we present a semi-implicit scheme to solve the involved nonlinear systems of equations and prove its Q-linear convergence. Finally, we demonstrate the performance of our methods by numerical examples.

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. Aja-Fernández, S., Alberola-López, C.: On the estimation of the coefficient of variation for anisotropic diffusion speckle filtering. IEEE Trans. Image Process. 15(9), 2694–2701 (2006)

    Article  Google Scholar 

  2. Aliprantis, C.D., Border, K.C.: Infinite Dimensional Analysis: A Hitchhikers Guide, 3rd edn. Springer, Berlin (2007)

    Google Scholar 

  3. Andreu-Vaillo, F., Caselles, V., Mazón, J.M.: Parabolic Quasilinear Equations Minimizing Linear Growth Functionals. Birkhäuser, Basel (2004)

    MATH  Google Scholar 

  4. Aubert, G., Aujol, J.-F.: A variational approach to removing multiplicative noise. SIAM J. Appl. Math. 68(4), 925–946 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  5. Aubin, J.-P.: Optima and Equilibria: An Introduction to Nonlinear Analysis, 2nd edn. Graduate Texts in Mathematics, vol. 140. Springer, Berlin (1998)

    MATH  Google Scholar 

  6. Beck, A., Teboulle, M.: Fast gradient-based algorithms for constrained total variation image denoising and deblurring problems. IEEE Trans. Image Process. (2009, to appear)

  7. Bioucas-Dias, J.M., Figueiredo, M.A.T.: Total variation restoration of speckled images using a split-Bregman algorithm. In: IEEE International Conference on Image Processing, Cairo, Egypt (2009)

  8. Braides, A.: Gamma-Convergence for Beginners. Oxford Lecture Series in Mathematics and Its Applications, vol. 22. Oxford University Press, Oxford (2002)

    MATH  Google Scholar 

  9. Bratsolis, E., Sigelle, M.: Fast SAR image restoration, segmentation and detection of high-reflectance regions. IEEE Trans. Geosci. Remote Sens. 41(12), 2890–2899 (2003)

    Article  Google Scholar 

  10. Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200–217 (1967)

    Article  Google Scholar 

  11. Brune, C., Sawatzky, A., Wübbeling, F., Kösters, T., Burger, M.: An analytical view of EM-TV based methods for inverse problems with Poisson noise. Preprint, University of Münster (2009)

  12. Buades, A., Coll, B., Morel, J.-M.: A non-local algorithm for image denoising. In: IEEE Computer Society Conference on Computer Vision and Pattern Recognition, vol. 2, pp. 60–65 (2005)

  13. Censor, Y., Lent, A.: An interval row action method for interval convex programming. J. Optim. Theory Appl. 34, 321–353 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  14. Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imag. Vis. 20(1–2), 89–97 (2004)

    MathSciNet  Google Scholar 

  15. Chambolle, A.: Total variation minimization and a class of binary MRF models. In: Rangarajan, A., Vemuri, B., Yuille, A.L. (eds.) Energy Minimization Methods in Computer Vision and Pattern Recognition. LNCS, vol. 3757, pp. 136–152. Springer, Berlin (2005)

    Chapter  Google Scholar 

  16. Combettes, P.L.: Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53(5–6), 475–504 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  17. Combettes, P.L., Pesquet, J.-C.: A Douglas-Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Top. Signal Process. 1(4), 564–574 (2007)

    Article  Google Scholar 

  18. Corless, R.M., Gonnet, G.H., Hare, D.E.G., Jeffrey, D.J., Knuth, D.E.: On the Lambert W function. Adv. Comput. Math. 5, 329–359 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  19. Coupé, P., Hellier, P., Kervrann, C., Barillot, C.: Nonlocal means-based speckle filtering for ultrasound images. IEEE Trans. Image Process. 18(10), 2221–2229 (2009)

    Article  Google Scholar 

  20. Csiszár, I.: Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems. Ann. Stat. 19(4), 2032–2066 (1991)

    Article  MATH  Google Scholar 

  21. Dal Maso, G.: An Introduction to Γ-Convergence. Birkhäuser, Boston (1993)

    Google Scholar 

  22. Deledalle, C.-A., Denis, L., Tupin, F.: Iterative weighted maximum likelihood denoising with probabilistic patch-based weights. IEEE Trans. Image Process. 18(12), 2661–2672 (2009)

    Article  Google Scholar 

  23. Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82(2), 421–439 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  24. Durand, S., Fadili, J., Nikolova, M.: Multiplicative noise cleaning via a variational method involving curvelet coefficients. In: Tai, X.-C., Morken, K., Lysaker, M., Lie, K.-A. (eds.) Scale Space and Variational Methods in Computer Vision. LNCS, vol. 5567, pp. 282–294. Springer, Berlin (2009)

    Chapter  Google Scholar 

  25. Eckstein, J., Bertsekas, D.P.: On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(3), 293–318 (1992)

    Article  MATH  MathSciNet  Google Scholar 

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

    MATH  Google Scholar 

  27. Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. CAM Report 09-31, UCLA (2009)

  28. European Space Agency (ESA). Multilook SAR image

  29. Evans, L.C., Gariepy, R.F.: Measure Theory and Fine Properties of Functions. Studies in Advanced Mathematics. CRC Press, Boca Raton (1992)

    MATH  Google Scholar 

  30. Figueiredo, M.A.T., Bioucas-Dias, J.M.: Deconvolution of Poissonian images using variable splitting and augmented Lagrangian optimization. In: IEEE Workshop on Statistical Signal Processing, Cardiff (2009)

  31. Fonseca, I., Leoni, G.: Modern Methods in the Calculus of Variations: L p Spaces. Springer Monographs in Mathematics. Springer, Berlin (2007)

    MATH  Google Scholar 

  32. Frick, K.: The Augmented Lagrangian Method and Associated Evolution Equations. Dissertation, University of Innsbruck (2008)

  33. Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary–Value Problems. Studies in Mathematics and Its Applications, vol. 15, pp. 299–331. North-Holland, Amsterdam (1983). Chap. 9

    Chapter  Google Scholar 

  34. Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)

    Article  MATH  Google Scholar 

  35. Gilboa, G., Osher, S.: Nonlocal linear image regularization and supervised segmentation. Multiscale Model. Simul. 6(2), 595–630 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  36. Gilboa, G., Osher, S.: Nonlocal operators with applications to image processing. Multiscale Model. Simul. 7(3), 1005–1028 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  37. Gilboa, G., Darbon, J., Osher, S., Chan, T.: Nonlocal convex functionals for image regularization. UCLA CAM Report, 06-57 (2006)

  38. Glowinski, R., Marrocco, A.: Sur l’approximation par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Revue Fr. Autom. Inform. Rech. Opér., Anal. Numér. 9(2), 41–76 (1975)

    MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  40. Goodman, J.W.: Statistical properties of laser speckle patterns. In: Dainty, J.C. (ed.) Laser Speckle and Related Phenomena. Topics in Applied Physics, vol. 9, pp. 9–75. Springer, Berlin (1975)

    Chapter  Google Scholar 

  41. Grasmair, M.: A coarea formula for anisotropic total variation regularisation. Preprint to appear, University of Vienna (2009)

  42. Huang, Y.-M., Ng, M.K., Wen, Y.-W.: A new total variation method for multiplicative noise removal. SIAM J. Imag. Sci. 2(1), 20–40 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  43. Kervrann, C., Boulanger, J., Coupé, P.: Bayesian non-local means filter, image redundancy and adaptive dictionaries for noise removal. In: Sgallari, F., Murli, A., Paragios, N. (eds.) Scale Space and Variational Methods in Computer Vision. LNCS, vol. 4485, pp. 520–532. Springer, Berlin (2007)

    Chapter  Google Scholar 

  44. Krissian, K., Westin, C.-F., Kikinis, R., Vosburgh, K.G.: Oriented speckle reducing anisotropic diffusion. IEEE Trans. Image Process. 16(5), 1412–1424 (2007)

    Article  MathSciNet  Google Scholar 

  45. Kryvanos, A., Hesser, J., Steidl, G.: Nonlinear image restoration methods for marker extraction in 3D fluorescent microscopy. In: Bouman, C.A., Miller, E.L. (eds.) Computational Imaging III, Proc. SPIE, vol. 5674, pp. 432–443 (2005)

  46. Kuan, D.T., Sawchuk, A.A., Strand, T.C., Chavel, P.: Adaptive noise smoothing filter for images with signal-dependent noise. IEEE Trans. Pattern Anal. Mach. Intell. 7(2), 165–177 (1985)

    Article  Google Scholar 

  47. Lee, J.-S.: Digital image enhancement and noise filtering by use of local statistics. IEEE Trans. Pattern Anal. Mach. Intell. 2(2), 165–168 (1980)

    Article  Google Scholar 

  48. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16(6), 964–979 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  49. Natterer, F., Wübbeling, F.: Mathematical Methods in Image Reconstruction. Monographs on Mathematical Modeling and Computation. SIAM, Philadelphia (2001)

    MATH  Google Scholar 

  50. Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103(1), 127–152 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  51. Panin, V.Y., Zeng, G.L., Gullberg, G.T.: Total variation regulated EM algorithm. IEEE Trans. Nucl. Sci. 46(6), 2202–2210 (1999)

    Article  Google Scholar 

  52. Resmerita, E., Engl, H.W., Iusem, A.N.: The expectation-maximization algorithm for ill-posed integral equations: a convergence analysis. Inverse Probl. 23(6), 2575–2588 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  53. Rockafellar, R.T.: Integral functions, normal integrands and measurable selections. In: Gossez, J.P., Lami Dozo, E.J., Mawhin, J., Waelbroeck, L. (eds.) Nonlinear Operators and the Calculus of Variations. Lecture Notes in Mathematics, vol. 543, pp. 157–207. Springer, Berlin (1976)

    Chapter  Google Scholar 

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

    Article  MATH  Google Scholar 

  55. Rudin, L.I., Lions, P.-L., Osher, S.: Multiplicative denoising and deblurring: theory and algorithms. In: Osher, S., Paragios, N. (eds.) Geometric Level Set Methods in Imaging, Vision, and Graphics, pp. 103–119. Springer, Berlin (2003)

    Chapter  Google Scholar 

  56. Sawatzky, A., Brune, C., Wübbeling, F., Kösters, T., Schäfers, K., Burger, M.: Accurate EM-TV algorithm in PET with low SNR. In: IEEE Nuclear Science Symposium Conference Record, pp. 5133–5137 (2008)

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

    Google Scholar 

  58. Setzer, S.: Split Bregman algorithm, Douglas-Rachford splitting and frame shrinkage. In: Tai, X.-C., Morken, K., Lysaker, M., Lie, K.-A. (eds.) Scale Space and Variational Methods in Computer Vision. LNCS, vol. 5567, pp. 464–476. Springer, Berlin (2009)

    Chapter  Google Scholar 

  59. Shi, J., Osher, S.: A nonlinear inverse scale space method for a convex multiplicative noise model. SIAM J. Imag. Sci. 1(3), 294–321 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  60. Steidl, G.: A note on the dual treatment of higher-order regularization functionals. Computing 76(1–2), 135–148 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  61. Steidl, G., Teuber, T.: Anisotropic smoothing using double orientations. In: Tai, X.-C., Morken, K., Lysaker, M., Lie, K.-A. (eds.) Scale Space and Variational Methods in Computer Vision. LNCS, vol. 5567, pp. 477–489. Springer, Berlin (2009)

    Chapter  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

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

  64. Welk, M., Steidl, G., Weickert, J.: Locally analytic schemes: a link between diffusion filtering and wavelet shrinkage. Appl. Comput. Harmon. Anal. 24(2), 195–224 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  65. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for ℓ 1-minimization with applications to compressed sensing. SIAM J. Imag. Sci. 1(1), 143–168 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  66. Yu, Y., Acton, S.T.: Speckle reducing anisotropic diffusion. IEEE Trans. Image Process. 11(11), 1260–1270 (2002)

    Article  MathSciNet  Google Scholar 

  67. Zhou, D., Schölkopf, B.: Regularization on discrete spaces. In: Kropatsch, W., Sablatnig, R., Hanbury, A. (eds.) Pattern Recognition, Proceedings of the 27th DAGM Symposium. LNCS, vol. 3663, pp. 361–368. Springer, Berlin (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Mathematics and Computer Science, University of Mannheim, Mannheim, Germany

    G. Steidl & T. Teuber

Authors
  1. G. Steidl
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. T. Teuber
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to G. Steidl.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Steidl, G., Teuber, T. Removing Multiplicative Noise by Douglas-Rachford Splitting Methods. J Math Imaging Vis 36, 168–184 (2010). https://doi.org/10.1007/s10851-009-0179-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-009-0179-5

Search

Navigation