Regularization preconditioners for frame-based image deblurring with reduced boundary artifacts. (English) Zbl 1382.94010

Summary: Thresholding iterative methods were recently successfully applied to image deblurring problems. In this paper, we investigate the modified linearized Bregman algorithm (MLBA) used in image deblurring problems, with a proper treatment of the boundary artifacts. We consider two standard approaches: the imposition of boundary conditions and the use of the rectangular blurring matrix. The fast convergence of the MLBA depends on a regularizing preconditioner that could be computationally expensive and hence it is usually chosen as a block circulant circulant block (BCCB) matrix, diagonalized by the discrete Fourier transform. We show that the standard approach based on the BCCB preconditioner may provide low-quality restored images and we propose different preconditioning strategies that improve the quality of the restoration and save some computational cost at the same time. Motivated by a recent nonstationary preconditioned iteration, we propose a new algorithm that combines such a method with the MLBA. We prove that it is a regularizing and convergent method. A variant with a stationary preconditioner is also considered. Finally, a large number of numerical experiments show that our methods provide accurate and fast restorations when compared with the state of the art.


94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65F08 Preconditioners for iterative methods
65F22 Ill-posedness and regularization problems in numerical linear algebra
65F10 Iterative numerical methods for linear systems
65T60 Numerical methods for wavelets


RestoreTools; RecPF
Full Text: DOI arXiv


[1] A. Aricò, M. Donatelli, and S. Serra-Capizzano, {\it Spectral analysis of the anti-reflective algebra}, Linear Algebra Appl., 428 (2008), pp. 657-675. · Zbl 1140.15005
[2] M. S. C. Almeida and M. A. T. Figueiredo, {\it Deconvolving images with unknown boundaries using the alternating direction method of multipliers}, IEEE Trans. Image Process., 22 (2013), pp. 3074-3086. · Zbl 1373.94019
[3] Z. J. Bai, D. Cassani, M. Donatelli, and S. Serra Capizzano, {\it A fast alternating minimization algorithm for total variation deblurring without boundary artifacts}, J. Math. Anal. Appl., 415 (2014), pp. 373-393. · Zbl 1308.94010
[4] J.-F. Cai, R. Chan, L. Shen, and Z. Shen, {\it Wavelet algorithms for high-resolution image reconstruction}, SIAM J. Sci. Comput., 24 (2003), pp. 1408-1432. · Zbl 1031.68127
[5] J. F. Cai, S. Osher, and Z. Shen, {\it Linearized Bregman iterations for frame-based image deblurring}, SIAM J. Imaging Sci., 2 (2009), pp. 226-252. · Zbl 1175.94010
[6] J. F. Cai, S. Osher, and Z. Shen, {\it Split Bregman methods and frame based image restoration}, Multiscale Model. Simul., 8 (2009), pp. 337-369. · Zbl 1189.94014
[7] J. F. Cai, S. Osher, and Z. Shen, {\it Convergence of the linearized Bregman iteration for \(ℓ_1\)-norm minimization}, Math. Comput., 78 (2009), pp. 2127-2136. · Zbl 1198.65103
[8] R. H. Chan, S. D. Riemenschneider, L. Shen, and Z. Shen, {\it Tight frame: An efficient way for high-resolution image reconstruction}, Appl. Comput. Harmon. Anal., 17 (2004), pp. 91-115. · Zbl 1046.42026
[9] R. H. Chan and M. K. Ng, {\it Conjugate gradient method for Toeplitz systems}, SIAM Rev., 38 (1996), pp. 427-482. · Zbl 0863.65013
[10] R. H. Chan and X. Q. Jin, {\it An Introduction to Iterative Toeplitz Solvers}, SIAM, Philiphadia, 2007. · Zbl 1146.65028
[11] T. F. Chan, {\it An optimal circulant preconditioner for Toeplitz systems}, SIAM J. Sci. Statist. Comput., 9 (1988), pp. 766-771. · Zbl 0646.65042
[12] M. Christiansen and M. Hanke, {\it Deblurring methods using antireflective boundary conditions}, SIAM J. Sci. Comput., 30 (2008), pp. 855-872. · Zbl 1167.65361
[13] I. Daubechies, M. Defrise, and C. De Mol, {\it An iterative thresholding algorithm for linear inverse problems with a sparsity constraint}, Comm. Pure Appl. Math., 57 (2004), pp. 1413-1457. · Zbl 1077.65055
[14] I. Daubechies, B. Han, A. Ron, and Z. Shen, {\it Framelets: MRA-based constructions of wavelet frames}, Appl. Comput. Harmon. Anal., 14 (2003), pp. 1-46. · Zbl 1035.42031
[15] P. Dell’Acqua, M. Donatelli, and C. Estatico, {\it Preconditioners for image restoration by reblurring techniques}, J. Comput. Appl. Math., 272 (2014), pp. 313-333. · Zbl 1294.65026
[16] M. Donatelli, C. Estatico, A. Martinelli, and S. Serra-Capizzano, {\it Improved image deblurring with anti-reflective boundary conditions and re-blurring}, Inverse Problems, 22 (2006), pp. 2035-2053. · Zbl 1167.65474
[17] M. Donatelli, C. Estatico, J. Nagy, L. Perrone, and S. Serra-Capizzano, {\it Anti-reflective boundary conditions and fast 2D deblurring models}, in Advanced Signal Processing Algorithms, Architectures and Implementations XIII, F. T. Luk, ed., Proceedings of SPIE 5205, 2003, pp. 380-389.
[18] M. Donatelli and M. Hanke, {\it Fast nonstationary preconditioned iterative methods for ill-posed problems, with application to image deblurring}, Inverse Problems, 29 (2013), 095008. · Zbl 1285.65030
[19] M. Donatelli and S. Serra-Capizzano, {\it Anti-reflective boundary conditions and re-blurring}, Inverse Problems, 21 (2005), pp. 169-182. · Zbl 1088.94510
[20] M. Donatelli and S. Serra-Capizzano, {\it On the treatment of boundary artifacts in image restoration by reflection and/or anti-reflection}, in Matrix Methods: Theory, Algorithms and Applications, V. Olshevsky and E. Tyrtyshnikov, eds., World Scientific, River Edge, NJ, 2010, pp. 227-237. · Zbl 1216.94011
[21] M. Donatelli and S. Serra-Capizzano, {\it Antireflective boundary conditions for deblurring problems}, J. Electr. Comput. Eng., 2010 (2010), 241467. · Zbl 1229.94007
[22] H. W. Engl, M. Hanke, and A. Neubauer, {\it Regularization Methods for Inverse Problems}, Kluwer, Dordrecht, the Netherlands, 1996. · Zbl 0859.65054
[23] M. Figueiredo and R. Nowak, {\it An EM algorithm for wavelet-based image restoration}, IEEE Trans. Image Process., 12 (2003), pp. 906-916. · Zbl 1279.94015
[24] M. Hanke and P. C. Hansen, {\it Regularization methods for large-scale problems}, Surveys Math. Indust., 3 (1993), pp. 253-315. · Zbl 0805.65058
[25] M. Hanke and J. Nagy, {\it Restoration of atmospherically blurred images by symmetric indefinite conjugate gradient techniques}, Inverse Problems, 12 (1996), pp. 157-173. · Zbl 0859.65141
[26] M. Hanke, J. Nagy, and R. Plemmons, {\it Preconditioned iterative regularization for ill-posed problems}, in Numerical Linear Algebra. Proceedings of the Conference in Numerical Linear Algebra and Scientific Computation, Kent, OH, 1992, de Gruyter, Berlin, 1993, pp. 141-163. · Zbl 0794.65039
[27] P. C. Hansen, J. Nagy, and D. P. O’Leary, {\it Deblurring Images Matrices, Spectra and Filtering}, SIAM, Philadelphia, 2005. · Zbl 1112.68127
[28] J. Huang, M. Donatelli, and R. Chan, {\it Nonstationary iterated thresholding algorithms for image deblurring}, Inverse Problems Imaging, 7 (2013), pp. 717-736. · Zbl 1318.94015
[29] J. Kamm and J. G. Nagy, {\it Kronecker product and SVD approximations in image restoration}, Linear Algebra Appl., 284 (1998), pp. 177-192. · Zbl 0936.65052
[30] J. Nagy, K. Palmer and L. Perrone, {\it RestoreTools: An Object Oriented MATLAB Package for Image Restoration}, http://www.mathcs.emory.edu/ nagy/RestoreTools (2002).
[31] M. Ng, R. Chan, and W. C. Tang, {\it A fast algorithm for deblurring models with Neumann boundary conditions}, SIAM J. Sci. Comput., 21 (1999), pp. 851-866. · Zbl 0951.65038
[32] L. Perrone, {\it Kronecker product approximations for image restoration with antireflective boundary conditions}, Numer. Linear Algebra Appl., 13 (2006), pp. 1-22. · Zbl 1174.94309
[33] J. G. Nagy, K. Palmer, and L. Perrone, {\it Iterative methods for image deblurring: A MATLAB object oriented approach}, Numer. Algorithms, 36 (2004), pp. 73-93; also available from http://www.mathcs.emory.edu/˜nagy/RestoreTools. · Zbl 1048.65039
[34] S. J. Reeves, {\it Fast image restoration without boundary artifacts}, IEEE Trans. Image Process., 14 (2005), pp. 1448-1453.
[35] L. Rudin, S. Osher, and E. Fatemi, {\it Nonlinear total variation based noise removal algorithms}, Phys. D, 60 (1992), pp. 259-268. · Zbl 0780.49028
[36] S. Serra-Capizzano, {\it A note on antireflective boundary conditions and fast deblurring models}, SIAM J. Sci. Comput., 25 (2003), pp. 1307-1325. · Zbl 1062.65152
[37] Z. Shen, K. C. Toh, and S. Yun, {\it An accelerated proximal gradient algorithm for frame-based image restoration via the balanced approach}, SIAM J. Imaging Sci., 4 (2011), pp. 573-596. · Zbl 1219.94012
[38] M. Sorel, {\it Removing boundary artifacts for real-time iterated shrinkage deconvolution}, IEEE Trans. Image Process., 21 (2012), pp. 2329-2334. · Zbl 1373.94012
[39] P. H. Van Cittert, {\it Zum einfluss der Spaltbreite auf die Intensitatsverteilung in Spektrallinen} II, Z. Phys., 69 (1931).
[40] R. Vio, J. Bardsley, M. Donatelli, and W. Wamsteker, {\it Dealing with edge effects in least-squares image deconvolution problems}, Astronom. Astrophys., 442 (2005), pp. 397-403.
[41] Y. Wang, J. Yang, W. Yin, and Y. Zhang, {\it A new alternating minimization algorithm for total variation image reconstruction}, SIAM J. Imaging Sci., 1 (2008), pp. 248-272. · Zbl 1187.68665
[42] W. Yin, S. Osher, D. Goldfarb, and J. Darbon, {\it Bregman iterative algorithms for \(l1\)-minimization with applications to compressed sensing}, SIAM J. Imaging Sci., 1 (2008), pp. 143-168. · Zbl 1203.90153
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.