Skip to main content
SpringerLink
Log in

Proximity algorithms for the L1/TV image denoising model

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

This paper introduces a proximity operator framework for studying the L1/TV image denoising model which minimizes the sum of a data fidelity term measured in the ℓ1-norm and the total-variation regularization term. Both terms in the model are non-differentiable. This causes algorithmic difficulties for its numerical treatment. To overcome the difficulties, we formulate the total-variation as a composition of a convex function (the ℓ1-norm or the ℓ2-norm) and the first order difference operator, and then express the solution of the model in terms of the proximity operator of the composition. By developing a “chain rule” for the proximity operator of the composition, we identify the solution as fixed point of a nonlinear mapping expressed in terms of the proximity operator of the ℓ1-norm or the ℓ2-norm, each of which is explicitly given. This formulation naturally leads to fixed-point algorithms for the numerical treatment of the model. We propose an alternative model by replacing the non-differentiable convex function in the formulation of the total variation with its differentiable Moreau envelope and develop corresponding fixed-point algorithms for solving the new model. When partial information of the underlying image is available, we modify the model by adding an indicator function to the minimization functional and derive its corresponding fixed-point algorithms. Numerical experiments are conducted to test the approximation accuracy and computational efficiency of the proposed algorithms. Also, we provide a comparison of our approach to two state-of-the-art algorithms available in the literature. Numerical results confirm that our algorithms perform favorably, in terms of PSNR-values and CPU-time, in comparison to the two algorithms.

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. Alliney, S.: A property of the minimum vectors of a regularizing functional defined by means of the absolute norm. IEEE Trans. Signal Process. 45, 913–917 (1997)

    Article  Google Scholar 

  2. Aujol, J.E., Gilboa, G., Chan, T., Osher, S.: Structure-texture image decomposition-modeling, algorithms, and parameter selection. Int. J. Comput. Vis. 67, 111–136 (2006)

    Article  Google Scholar 

  3. Bauschke, H., Borwein, J.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  4. Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont, MA (2003)

    Google Scholar 

  5. Bloomfield, P., Steiger, W.: Least Absolute Deviations. Birkhauser, Boston-Basel (1983)

    MATH  Google Scholar 

  6. Bovik, A.: Handbook of Image and Video Processing. Academic, San Diego (2000)

    MATH  Google Scholar 

  7. Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20, 103–120 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cai, J.F., Chan, R., Shen, L., Shen, Z.: Simultaneously inpainting in image and transformed domains. Numer. Math. 112, 509–533 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  9. Candes, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  10. Candes, E., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52, 5406–5425 (2006)

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  12. Chan, R., Riemenschneider, S.D., Shen, L., Shen, Z.: Tight frame: the efficient way for high-resolution image reconstruction. Appl. Comput. Harmon. Anal. 17, 91–115 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  13. Chan, T., Esedoglu, S.: Aspects of total variation regularized l 1 function approximation. SIAM J. Appl. Math. 65, 1817–1837 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  14. Chan, T., Marquina, A., Mulet, P.: High-order total variation-based image restoration. SIAM J. Sci. Comput. 22, 503–516 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  15. Chen, T., Yin, W., Zhou, X.S., Comaniciu, D., Huang, T.: Total variation models for variable lighting face recognition. IEEE Trans. Pattern Anal. Mach. Intell. 28, 1519–1524 (2006)

    Article  Google Scholar 

  16. Clason, C., Jin, B., Kunisch, K.: A duality-based splitting method for L1-TV image restoration with automatic regularization parameter choice. SIAM J. Sci. Comput. 32, 1484–1505 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Combettes, P., Wajs, V.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul.: SIAM Interdiscip. J. 4, 1168–1200 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  18. Daubechies, I., Defrise, M., Mol, C.D.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1541 (2004)

    Article  MATH  Google Scholar 

  19. Dong, Y., Hintermuller, M., Neri, M.: A primal-dual method for l 1-TV image denoising. SIAM J. Math. Anal. 2, 1168–1189 (2009)

    MathSciNet  MATH  Google Scholar 

  20. Fornasier, M., Rauhut, R.: Recovery algorithms for vector-valued data with joint sparsity constraints. SIAM J. Numer. Anal. 46, 577–613 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  21. Fu, H., Ng, M.K., Nikolova, M., Barlow, J.L.: Efficient minimization of mixed ℓ2 − ℓ1 and ℓ1 − ℓ1 nomrs for image restoration. SIAM J. Sci. Comput. 27, 1881–1902 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  23. Gonzalez, R., Woods, R.: Digital Image Processing. Addison-Wesley, Boston, MA (1993)

    Google Scholar 

  24. Guo, X., Li, F., Ng, M.: A fast ℓ1-TV algorithm for image restoration. SIAM J. Sci. Comput. 31, 2322–2341 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  25. Hiriart-Urruty, J.B., Lemarechal, C.: Convex analysis and minimization algorithms II. In: Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 306. Springer, Berlin (1993)

    Google Scholar 

  26. Lustig, M., Donoho, D., Pauly, J.M.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58, 1182–1195 (2007)

    Article  Google Scholar 

  27. Lysaker, M., Tai, X.: Iterative image restoration combining total variation minimization and a second-order functional. Int. J. Comput. Vis. 66, 5–18 (2006)

    Article  Google Scholar 

  28. Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denosing. Inverse Probl. 27, 045009, 30 pp. (2011)

    Google Scholar 

  29. Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93, 273–299 (1965)

    MathSciNet  MATH  Google Scholar 

  30. Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20, 99–120 (2004)

    Article  MathSciNet  Google Scholar 

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

    Article  MATH  Google Scholar 

  32. Scherzer, O.: Denoising with higher-order derivatives of bounded variation and an application to parameter estimation. Computing 60, 5–27 (1998)

    Article  MathSciNet  Google Scholar 

  33. Stefan, W., Renaut, R.A., Gelb, A.: Improved total variation-type regularization using higher order edge detectors. SIAM J. Imaging Sci. 3, 232–251 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  34. Tropp, J.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50, 2231–2242 (2004)

    Article  MathSciNet  Google Scholar 

  35. Wu, C., Zhang, J., Tai, X.-C.: Augmented lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Probl. Imaging 5, 237–261 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  36. Yang, J., Zhang, Y., Yin, W.: An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM J. Sci. Comput. 31, 2842–2865 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  37. Yin, W., Chen, T., Zhou, X.S., Chakraborty, A.: Background correction for cDNA microarray image using the TV+L1 model. Bioinformatics 10, 2410–2416 (2005)

    Article  Google Scholar 

  38. Yin, W., Goldfard, D., Osher, S.: The total variation regularized l 1 model for multiscale decomposition. Multiscale Model. Simul.: SIAM Interdiscip. J. 6, 190–211 (2007)

    Article  MATH  Google Scholar 

  39. You, Y., Kaveh, M.: Fourth-order partial differential equations for noise removal. IEEE Trans. Image Process. 9, 1723–1730 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  40. Zach, C., Pock, T., Bischof, H.: A duality based approach for realtime TV-l 1 optical flow. In: Lecture Notes in Computer Sciences, vol. 4713, pp. 214–223. Springer, Berlin Heidelberg (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Statistics, SUNY, Albany, NY, USA

    Charles A. Micchelli

  2. Department of Mathematics, City University of Hong Kong, Kowloon, Hong Kong

    Charles A. Micchelli

  3. Department of Mathematics, Syracuse University, Syracuse, NY, 13244, USA

    Lixin Shen & Yuesheng Xu

  4. Guangdong Province Key Lab of Computational Science, Sun Yat-sen University, Guangzhou, 510275, People’s Republic of China

    Yuesheng Xu & Xueying Zeng

Authors
  1. Charles A. Micchelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lixin Shen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yuesheng Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xueying Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuesheng Xu.

Additional information

Communicated by Zhongying Chen.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Micchelli, C.A., Shen, L., Xu, Y. et al. Proximity algorithms for the L1/TV image denoising model. Adv Comput Math 38, 401–426 (2013). https://doi.org/10.1007/s10444-011-9243-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-011-9243-y

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation