Abstract
This paper deals with first-order numerical schemes for image restoration. These schemes rely on a duality-based algorithm proposed in 1979 by Bermùdez and Moreno. This is an old and forgotten algorithm that is revealed wider than recent schemes (such as the Chambolle projection algorithm) and able to improve contemporary schemes. Total variation regularization and smoothed total variation regularization are investigated. Algorithms are presented for such regularizations in image restoration. We prove the convergence of all the proposed schemes. We illustrate our study with numerous numerical examples. We make some comparisons with a class of efficient algorithms (proved to be optimal among first-order numerical schemes) recently introduced by Y. Nesterov.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Acar, R., Vogel, C.: Analysis of total variation penalty methods for ill-posed problems. Inverse Probl. 10, 1217–1229 (1994)
Almansa, A., Ballester, C., Caselles, V., Haro, G.: A TV based restoration model with local constraints. J. Sci. Comput. 34(3), 209–236 (2008)
Ambrosio, L., Fusco, N., Pallara, D.: Functions of Bounded Variations and Free Discontinuity Problems, Oxford mathematical monographs. Oxford University Press, London (2000)
Andreu-Vaillo, F., Caselles, V., Mazon, J.M.: Parabolic Quasilinear Equations Minimizing Linear Growth Functionals. Progress in Mathematics, vol. 223. Birkhäuser, Basel (2002)
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing. Applied Mathematical Sciences, vol. 147. Springer, New York (2002)
Aujol, J.-F.: Some algorithms for total variation based image restoration. CMLA Report 08-21 (2008). http://hal.archives-ouvertes.fr/hal-00260494/fr/
Aujol, J.-F., Gilboa, G.: Constrained and SNR-based solutions for TV-Hilbert space image denoising. J. Math. Imaging Vis. 26(1–2), 217–237 (2006)
Aujol, J.-F., Aubert, G., Blanc-Féraud, L., Chambolle, A.: Image decomposition into a bounded variation component and an oscillating component. J. Math. Imag. Vis., 22(1), 71–88 (2005)
Bect, J., Blanc-Féraud, L., Aubert, G., Chambolle, A.: A l1-unified variational framework for image restoration. In: ECCV 04. Lecture Notes in Computer Sciences, vol. 3024, pp. 1–13. Springer, Berlin (2004)
Bermùdez, A., Moreno, C.: Duality methods for solving variational inequalities. Comput. Math. Appl. 7, 43–58 (1981)
Bioucas-Dias, J., Figueiredo, M.: Thresholding algorithms for image restoration. IEEE Trans. Image Process. 16(12), 2980–2991 (2007)
Bonesky, T., Bredies, K., Lorenz, D., Mass, P.: A generalized conditional gradient method for nonlinear operator equations with sparsity constraints. Inverse Probl. 23, 2041–2048 (2009)
Bresson, X., Chan, T.: Fast minimization of the vectorial total variation norm and applications to color image processing. UCLA CAM report, 07-25 (2007)
Brezis, H.: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert. North Holland, Amsterdam (1973)
Brezis, H.: Analyse Fonctionnelle. Théorie et Applications. Mathématiques Appliquées pour la Maitrise. Masson, Paris (1983)
Chambolle, A.: An algorithm for total variation minimization and applications. J. Math. Imaging Vis. 20, 89–97 (2004)
Chambolle, A.: Total variation minimization and a class of binary MRF models. In: EMMCVPR 05. Lecture Notes in Computer Sciences, vol. 3757, pp. 136–152. Springer, Berlin (2005)
Chambolle, A., Lions, P.L.: Image recovery via total variation minimization and related problems. Numer. Math. 76(3), 167–188 (1997)
Chan, T., Mulet, P.: On the convergence of the lagged diffusity fixed point method in total variation image restoration. SIAM J. Numer. Anal. 36(2), 354–367 (1999)
Chan, T., Shen, J.: Image Processing and Analysis—Variational, PDE, Wavelet, and Stochastic Methods. SIAM, Philadelphia (2005)
Chan, T., Golub, G., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20(6), 1964–1977 (1999)
Charbonnier, P., Blanc-Feraud, L., Aubert, G., Barlaud, M.: Deterministic edge-preserving regularization in computed imaging. IEEE Trans. Image Process. 6(2) (2007)
Ciarlet, P.G.: Introduction à l’Analyse Numérique Matricielle et à l’Optimisation. Masson, Paris (1982)
Combettes, P.L., Pesquet, J.: Image restoration subject to a total variation constraint. IEEE Trans. Image Process. 13(9), 1213–1222 (2004)
Combettes, P.L., Wajs, V.: Signal recovery by proximal forward-backward splitting. SIAM J. Multiscale Model. Simul. 4(4), 1168–1200 (2005)
Darbon, J., Sigelle, M.: Image restoration with discrete constrained total variation part I: Fast and exact optimization. J. Math. Imaging Vis. 26(3), 277–291 (2006)
Daubechies, I., Defrise, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)
Dobson, D., Vogel, C.: Convergence of an iterative method for total variation denoising. SIAM J. Numer. Anal. 34, 1779–1791 (1997)
Durand, S., Fadili, J., Nikolova, M.: Multiplicative noise removal using L 1 fidelity on frame coefficients. CMLA Report, 08-40 (2008)
Duval, V., Aujol, J.-F., Vese, L.: Projected gradient based color image decomposition. In: SSVM 09 (2009)
Ekeland, I., Temam, R.: Analyse Convexe et Problèmes Variationnels, 2nd edn. Grundlehren der mathematischen Wissenschaften, vol. 224. Dunod, Paris (1983)
Facciolo, G., Almansa, A., Aujol, J.-F., Caselles V.: Irregular to regular sampling, denoising and deconvolution. SIAM J. Multiscale Model. Simul. (2009, in press)
Fadili, J., Starck, J.-L.: Monotone operator splitting for fast sparse solutions of inverse problems (2009, submitted)
Fu, H., Ng, M., Nikolova, M., Barlow, J.: Efficient minimization methods of mixed l1-l1 and l2-l1 norms for image restoration. SIAM J. Sci. Comput. 27(6), 1881–1902 (2006)
Goldfarb, D., Yin, W.: Second-order cone programming methods for total variation based image restoration. SIAM J. Sci. Comput. 27(2), 622–645 (2005)
Goldstein, T., Osher, S.: The split Bregman algorithm for L1 regularized problems. UCLA CAM Report, April 2008
Meyer Y.: Oscillating patterns in image processing and in some nonlinear evolution equations, March 2001. The Fifteenth Dean Jacquelines B. Lewis Memorial Lectures
Nesterov, Y.: Introductory Lectures on Convex Optimization: a Basic Course. Kluwer Academic, Dordrecht (2004)
Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. (A) 103(1), 127–152 (2005)
Nesterov, Y.: Gradient methods for minimizing composite objective function. Core discussion paper (2007)
Ng, M.K., Qi, L., Yang, Y.F., Huang, Y.: On semismooth Newton methods for total variation minimization. J. Math. Imaging Vis. 27, 265–276 (2007)
Nikolova, M., Chan, R.: The equivalence of half-quadratic minimization and the gradient linearization iteration. IEEE Trans. Image Process. 16(6), 1623–1627 (2007)
Pazy, A.: On the asymptotic behavior of iterates of nonexpansive mappings in Hilbert space. Isr. J. Math. 26, 197–204 (1977)
Pazy, A.: Semigroups of Linear Operators and Applications to Partial Differential Equations. Applied Mathematical Sciences, vol. 44. Springer, New York (1983)
Polyak, B.: Introduction to Optimization. Translation Series in Mathematics and Engineering. Optimization Software, New York (2004)
Ramlau, R., Teschke, G.: A Tikhonov-based projection iteration for nonlinear ill-posed problems with sparsity constraints. Numer. Math. 104, 177–203 (2006)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Setzer, S.: Split Bregman Algorithm, Douglas-Rachford Splitting and frame shrinkage. Preprint, University of Mannheim (2008)
Weisfeld, E.: Sur le point pour lequel la somme des distances de points donnés est minimum. Tôhoku Math. J. 43, 355–386 (1937)
Weiss, P.: Algorithmes rapides d’optimisation convexe. Applications à la restauration d’images et à la détection de changement. Ph.D. thesis, Université de Nice Sophia-Antipolis, December 2008
Weiss, P., Aubert, G., Blanc-Feraud, L.: Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. (2009, in press)
Yuan, J., Schnörr, C., Steidl, G.: Convex Hodge decomposition and regularization of image flows. J. Math. Imaging Vis. 33(2), 169–177 (2009)
Zhu, M., Chan, T.F.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration, May 2008. UCLA CAM Report 08-34
Zhu, M., Wright, S.J., Chan, T.F.: Duality-based algorithms for total variation image restoration, May 2008. UCLA CAM Report 08-33
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Aujol, JF. Some First-Order Algorithms for Total Variation Based Image Restoration. J Math Imaging Vis 34, 307–327 (2009). https://doi.org/10.1007/s10851-009-0149-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-009-0149-y