Efficient algorithm for isotropic and anisotropic total variation deblurring and denoising. (English) Zbl 1266.65039

Summary: A new deblurring and denoising algorithm is proposed, for isotropic total variation-based image restoration. The algorithm consists of an efficient solver for the nonlinear system and an acceleration strategy for the outer iteration. For the nonlinear system, the split Bregman method is used to convert it into linear system, and an algebraic multigrid method is applied to solve the linearized system. For the outer iteration, we have conducted formal convergence analysis to determine an auxiliary linear term that significantly stabilizes and accelerates the outer iteration. Numerical experiments demonstrate that our algorithm for deblurring and denoising problems is efficient.


65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: DOI


[1] L. I. Rudin, S. Osher, and E. Fatemi, “Nonlinear total variation based noise removal algorithms,” Physica D, vol. 60, no. 1-4, pp. 259-268, 1992. · Zbl 0780.49028
[2] R. Acar and C. R. Vogel, “Analysis of bounded variation penalty methods for ill-posed problems,” Inverse Problems, vol. 10, no. 6, pp. 1217-1229, 1994. · Zbl 0809.35151
[3] H. Birkholz, “A unifying approach to isotropic and anisotropic total variation denoising models,” Journal of Computational and Applied Mathematics, vol. 235, no. 8, pp. 2502-2514, 2011. · Zbl 1207.94005
[4] J. S. Moll, “The anisotropic total variation flow,” Mathematische Annalen, vol. 332, no. 1, pp. 177-218, 2005. · Zbl 1109.35061
[5] C. A. Z. Barcelos and Y. Chen, “Heat flows and related minimization problem in image restoration,” Computers & Mathematics with Applications, vol. 39, no. 5-6, pp. 81-97, 2000. · Zbl 0957.65069
[6] W. Zuo and Z. Lin, “A generalized accelerated proximal gradient approach for total-variation-based image restoration,” IEEE Transactions on Image Processing, vol. 20, no. 10, pp. 2748-2759, 2011. · Zbl 1372.94320
[7] M. Grasmair and F. Lenzen, “Anisotropic total variation filtering,” Applied Mathematics and Optimization, vol. 62, no. 3, pp. 323-339, 2010. · Zbl 1205.35152
[8] Y. Li and F. Santosa, “An affine scaling algorithm for minimizing total variation in image enhancement,” Tech. Rep. 12/94, Center for Theory and Simulation in Science and Engineering, Cornell University, 1994.
[9] R. Chan, T. Chan, and H. Zhou, “Advanced signal processing algorithms,” in Proceedings of the International Society of Photo-Optical Instrumentation Engineers, F. Luk, Ed., pp. 314-325, SPIE, 1995.
[10] M. E. Oman, “Fast multigrid techniques in total variation-based image reconstruction,” in Proceedings of the Copper Mountain Conference on Multigrid Methods, 1995.
[11] C. R. Vogel, “A multigrid method for total variation-based image denoising,” in Computation and Control, IV, vol. 20 of Progress in Systems and Control Theory, pp. 323-331, Birkhäuser, Boston, Mass, USA, 1995. · Zbl 0831.93062
[12] C. R. Vogel and M. E. Oman, “Iterative methods for total variation denoising,” SIAM Journal on Scientific Computing, vol. 17, no. 1, pp. 227-238, 1996. · Zbl 0847.65083
[13] C. R. Vogel and M. E. Oman, “Fast, robust total variation-based reconstruction of noisy, blurred images,” IEEE Transactions on Image Processing, vol. 7, no. 6, pp. 813-824, 1998. · Zbl 0993.94519
[14] M. K. Ng, R. H. Chan, and W.-C. Tang, “A fast algorithm for deblurring models with Neumann boundary conditions,” SIAM Journal on Scientific Computing, vol. 21, no. 3, pp. 851-866, 1999. · Zbl 0951.65038
[15] R. H. Chan, T. F. Chan, and C. K. Wong, “Cosine transform based preconditioned for total variation deblurring,” IEEE Transactions on Image Processing, vol. 8, no. 10, pp. 1472-1478, 1999.
[16] P. Blomgren and T. F. Chan, “Modular solvers for image restoration problems using the discrepancy principle,” Numerical Linear Algebra with Applications, vol. 9, no. 5, pp. 347-358, 2002. · Zbl 1071.68557
[17] C. A. Micchelli, L. Shen, and Y. Xu, “Proximity algorithms for image models: denoising,” Inverse Problems, vol. 27, no. 4, Article ID 045009, 2011. · Zbl 1216.94015
[18] T. F. Chan, G. H. Golub, and P. Mulet, “A nonlinear primal-dual method for total variation-based image restoration,” SIAM Journal on Scientific Computing, vol. 20, no. 6, pp. 1964-1977, 1999. · Zbl 0929.68118
[19] Q. Chang and I.-L. Chern, “Acceleration methods for total variation-based image denoising,” SIAM Journal on Scientific Computing, vol. 25, no. 3, pp. 982-994, 2003. · Zbl 1046.65048
[20] Y. Shi and Q. Chang, “Remark on convergence of algebraic multigrid in the form of matrix decomposition,” Applied Mathematics and Computation, vol. 170, no. 2, pp. 1170-1184, 2005. · Zbl 1095.65028
[21] Y. Shi and Q. Chang, “Acceleration methods for image restoration problem with different boundary conditions,” Applied Numerical Mathematics, vol. 58, no. 5, pp. 602-614, 2008. · Zbl 1162.65065
[22] T. Goldstein and S. Osher, “The split Bregman method for L1-regularized problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 2, pp. 323-343, 2009. · Zbl 1177.65088
[23] Q. Chang, L. Chien, W. Wang, and J. Xu, “A robust algorithm variation deblurring and denoising,” in Proceedings of the 2nd International Conference on Scale Space and Variational Methods in Computer Vision (SSVM ’09), vol. 5567 of Lecture Notes in Computer Science, Springer, 2009.
[24] Q. Chang, Y. S. Wong, and H. Fu, “On the algebraic multigrid method,” Journal of Computational Physics, vol. 125, no. 2, pp. 279-292, 1996. · Zbl 0857.65037
[25] Q. Chang and Z. Huang, “Efficient algebraic multigrid algorithms and their convergence,” SIAM Journal on Scientific Computing, vol. 24, no. 2, pp. 597-618, 2002. · Zbl 1027.65166
[26] J. W. Ruge and K. Stüben, “Algebraic multigrid,” in Multigrid Methods, S. F. McCormick, Ed., vol. 3 of Frontiers Appl. Math., pp. 73-130, SIAM, Philadelphia, Pa, USA, 1987.
[27] R.-Q. Jia, H. Zhao, and W. Zhao, “Convergence analysis of the Bregman method for the variational model of image denoising,” Applied and Computational Harmonic Analysis, vol. 27, no. 3, pp. 367-379, 2009. · Zbl 1194.68251
[28] A. Brandt and V. Mikulinsky, “On recombining iterants in multigrid algorithms and problems with small islands,” SIAM Journal on Scientific Computing, vol. 16, no. 1, pp. 20-28, 1995. · Zbl 0826.65022
[29] C. W. Oosterlee and T. Washio, “Krylov subspace acceleration of nonlinear multigrid with application to recirculating flows,” SIAM Journal on Scientific Computing, vol. 21, no. 5, pp. 1670-1690, 2000. · Zbl 0968.76061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.