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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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)
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)
Bauschke, H., Borwein, J.: On projection algorithms for solving convex feasibility problems. SIAM Rev. 38, 367–426 (1996)
Bertsekas, D.: Nonlinear Programming. Athena Scientific, Belmont, MA (2003)
Bloomfield, P., Steiger, W.: Least Absolute Deviations. Birkhauser, Boston-Basel (1983)
Bovik, A.: Handbook of Image and Video Processing. Academic, San Diego (2000)
Byrne, C.: A unified treatment of some iterative algorithms in signal processing and image reconstruction. Inverse Probl. 20, 103–120 (2004)
Cai, J.F., Chan, R., Shen, L., Shen, Z.: Simultaneously inpainting in image and transformed domains. Numer. Math. 112, 509–533 (2009)
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)
Candes, E., Tao, T.: Near optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52, 5406–5425 (2006)
Chambolle, A., Lions, P.L.: Image recovery via total variational minimization and related problems. Numer. Math. 76, 167–188 (1997)
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)
Chan, T., Esedoglu, S.: Aspects of total variation regularized l 1 function approximation. SIAM J. Appl. Math. 65, 1817–1837 (2005)
Chan, T., Marquina, A., Mulet, P.: High-order total variation-based image restoration. SIAM J. Sci. Comput. 22, 503–516 (2000)
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)
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)
Combettes, P., Wajs, V.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul.: SIAM Interdiscip. J. 4, 1168–1200 (2005)
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)
Dong, Y., Hintermuller, M., Neri, M.: A primal-dual method for l 1-TV image denoising. SIAM J. Math. Anal. 2, 1168–1189 (2009)
Fornasier, M., Rauhut, R.: Recovery algorithms for vector-valued data with joint sparsity constraints. SIAM J. Numer. Anal. 46, 577–613 (2008)
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)
Goldfard, D., Yin, W.: Second-order cone programming methods for total variation based image restoration. SIAM J. Sci. Comput. 27, 622–645 (2005)
Gonzalez, R., Woods, R.: Digital Image Processing. Addison-Wesley, Boston, MA (1993)
Guo, X., Li, F., Ng, M.: A fast ℓ1-TV algorithm for image restoration. SIAM J. Sci. Comput. 31, 2322–2341 (2009)
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)
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)
Lysaker, M., Tai, X.: Iterative image restoration combining total variation minimization and a second-order functional. Int. J. Comput. Vis. 66, 5–18 (2006)
Micchelli, C.A., Shen, L., Xu, Y.: Proximity algorithms for image models: denosing. Inverse Probl. 27, 045009, 30 pp. (2011)
Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. Fr. 93, 273–299 (1965)
Nikolova, M.: A variational approach to remove outliers and impulse noise. J. Math. Imaging Vis. 20, 99–120 (2004)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Scherzer, O.: Denoising with higher-order derivatives of bounded variation and an application to parameter estimation. Computing 60, 5–27 (1998)
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)
Tropp, J.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50, 2231–2242 (2004)
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)
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)
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)
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)
You, Y., Kaveh, M.: Fourth-order partial differential equations for noise removal. IEEE Trans. Image Process. 9, 1723–1730 (2000)
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)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Zhongying Chen.
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10444-011-9243-y