Abstract
The main aim of this paper is to accelerate the Chambolle gradient projection method for total variation image restoration. In the proposed minimization method model, we use the well known Barzilai-Borwein stepsize instead of the constant time stepsize in Chambolle’s method. Further, we adopt the adaptive nonmonotone line search scheme proposed by Dai and Fletcher to guarantee the global convergence of the proposed method. Numerical results illustrate the efficiency of this method and indicate that such a nonmonotone method is more suitable to solve some large-scale inverse problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Aubert, G., Aujol, J.F.: A variational approach to removing multiplicative noise. SIAM J. Appl. Math. 68, 925–946 (2008)
Aubert, G., Kornprobst, P.: Mathematical Problems in Image Processing. Applied Mathematical Sciences, vol. 147. Springer, Berlin (2002)
Aujol, J.F.: Some algorithms for total variation based image restoration. Report CLMA 2008-05 (2008)
Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)
Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Nashua (1999)
Birgin, E.G., Martinez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000)
Bresson, X., Chan, T.: Fast dual minimization of the vectorial total variation norm and applications to color image processing. Technical report, UCLA CAM Report 07-25 (2007)
Carter, J.L.: Dual methods for total variation-based image restoration. Ph.D. thesis, University of California at Los Angeles (2001) (Advisor: T.F. Chan)
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, 167–188 (1997)
Chan, T., Chen, K., Carter, J.L.: Iterative methods for solving the dual formulation arising from image restoration. Electron. Trans. Numer. Anal. 26, 299–311 (2007)
Chan, T., Shen, J.: Image Processing and Analysis—Variational, PDE, Wavelet, and Stochastic Methods. Philadelphia, SIAM (2005)
Chan, T., Golub, G., Mulet, P.: A nonlinear primal-dual method for total variation-based image restoration. SIAM J. Sci. Comput. 20, 1964–1977 (1999)
Dahl, J., Hansen, P., Jensen, S., Jensen, T.: Algorithms and software for total variation image reconstruction via first-order methods. Numer. Algorithms (2009, to appear)
Dai, Y.H., Fletcher, R.: Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming. Numer. Math. 100, 21–47 (2005)
Dai, Y.H., Liao, L.Z.: R-linear convergence of the Barzilai and Borwein gradient method. IMA J. Numer. Anal. 22, 1–10 (2002)
Ekeland, I., Témam, R.: Convex Analysis and Variational Problems. SIAM Classics in Applied Mathematics. SIAM, Philadelphia (1999)
Goldstein, T., Osher, S.: The split Bregman method for L1 regularized problems. UCLA CAM Report 08-29 (2008)
Grippo, L., Sciandrone, M.: Nonmonotone globalization techniques for the Barzilai-Borwein gradient method. Comput. Optim. Appl. 23, 143–169 (2002)
Huang, Y.M., Ng, M.K., Wen, Y.W.: A fast total variation method for multiplicative noise removal. SIAM J. Imaging Sci. 2, 20–40 (2009)
Ng, M.K., Qi, L., Yang, Y.F., Huang, Y.M.: On semismooth Newton methods for total variation minimization. J. Math. Imaging Vis. 27, 265–276 (2007)
Raydan, M.: On the Barzilai and Borwein choice of steplength for the gradient method. IMA J. Numer. Anal. 13, 321–326 (1993)
Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Physica D 60, 259–268 (1992)
Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1, 248–272 (2008)
Weiss, P., Blanc-Féraud, L., Aubert, G.: Efficient schemes for total variation minimization under constraints in image processing. SIAM J. Sci. Comput. 31, 2047–2080 (2009)
Zhu, M.: Fast numerical algorithms for total variation based image restoration. Ph.D. thesis, University of California at Los Angeles, July 2008 (Advisor: T.F. Chan)
Zhu, M., Chan, T.F.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. Technical report, UCLA CAM Report 08-34 (2008)
Zhu, M., Wright, S.J., Chan, T.F.: Duality-based algorithms for total variation image restoration. Technical report, UCLA CAM Report 08-33 (2008)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was partly supported by the Research Grant Council of Hong Kong, a postdoctoral fellowship from the Department of Applied Mathematics at the Hong Kong Polytechnic University (1-ZV0K), a grant from the Ph.D. Programs Foundation of Ministry of Education of China (No.200805581022) and the National Natural Science Foundation of China (No.10571171, 10831006 and 60804008), and the CAS grant kjcx-yw-s7-03.
Rights and permissions
About this article
Cite this article
Yu, G., Qi, L. & Dai, Y. On Nonmonotone Chambolle Gradient Projection Algorithms for Total Variation Image Restoration. J Math Imaging Vis 35, 143–154 (2009). https://doi.org/10.1007/s10851-009-0160-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10851-009-0160-3