zbMATH — the first resource for mathematics

A multigrid frame based method for image deblurring. (English) Zbl 07192775
Summary: Iterative soft thresholding algorithms combine one step of a Landweber method (or accelerated variants) with one step of thresholding of the wavelet (framelet) coefficients. In this paper, we improve these methods by using the framelet multilevel decomposition for defining a multigrid deconvolution with grid transfer operators given by the low-pass filter of the frame. Assuming that an estimate of the noise level is available, we combine a recently proposed iterative method for \(\ell_2\)-regularization with linear framelet denoising by soft-thresholding. This combination allows a fast frequency filtering in the Fourier domain and produces a sparse reconstruction in the wavelet domain. Moreover, its employment in a multigrid scheme ensures stable convergence and a reduced noise amplification. The proposed multigrid method is independent of the imposed boundary conditions, and the iterations can be easily projected onto a closed and convex set, e.g., the nonnegative cone. We study the convergence of the proposed algorithm and prove that it is a regularization method. Several numerical results prove that this approach is able to provide highly accurate reconstructions in several different scenarios without requiring the setting of any parameter.
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65T60 Numerical methods for wavelets
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Full Text: DOI Link
[1] M. S. C. ALMEIDA ANDM. A. T. FIGUEIREDO,Deconvolving images with unknown boundaries using the alternating direction method of multipliers, IEEE Trans. Image Process., 22 (2013), pp. 3074-3086. · Zbl 1373.94019
[2] A. ARICÒ ANDM. DONATELLI,AV-cycle multigrid for multilevel matrix algebras: proof of optimality, Numer. Math., 105 (2007), pp. 511-547. · Zbl 1114.65033
[3] A. ARICÒ, M. DONATELLI, J. NAGY,ANDS. SERRA-CAPIZZANO,The anti-reflective transform and regularization by filtering, in Numerical Linear Algebra in Signals, Systems and Control, P. Van Dooren, S. P. Bhattacharyya, R. H. Chan, V. Olshevsky, and A. Routray, eds., vol. 80 of Lect. Notes Electr. Eng., Springer, Dordrecht, 2011, pp. 1-21.
[4] Z.-J. BAI, D. CASSANI, M. DONATELLI,ANDS. SERRA-CAPIZZANO,A fast alternating minimization algorithm for total variation deblurring without boundary artifacts, J. Math. Anal. Appl., 415 (2014), pp. 373-393. · Zbl 1308.94010
[5] A. B. BAKUSHINSKI˘I,Remarks on the choice of regularization parameter from quasioptimality and relation tests, Zh. Vychisl. Mat. i Mat. Fiz., 24 (1984), pp. 1258-1259. · Zbl 0575.65059
[6] W. L. BRIGGS, V. E. HENSON,ANDS. F. MCCORMICK,A Multigrid Tutorial, 2nd ed., SIAM, Philadelphia, 2000.
[7] A. BUCCINI,Regularizing preconditioners by non-stationary iterated Tikhonov with general penalty term, Appl. Numer. Math., 116 (2017), pp. 64-81. · Zbl 1372.65161
[8] A. BUCCINI, M. DONATELLI,ANDL. REICHEL,Iterated Tikhonov regularization with a general penalty term, Numer. Linear Algebra Appl., 24 (2017), Art. e2089, 12 pages. · Zbl 1424.65045
[9] A. BUCCINI ANDL. REICHEL,An‘2−‘qregularization method for large discrete ill-posed problems, J. Sci. Comput., 78 (2019), pp. 1526-1549. · Zbl 07074397
[10] J.-F. CAI, R. H. CHAN,ANDZ. SHEN,A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal., 24 (2008), pp. 131-149. · Zbl 1135.68056
[11] J.-F. CAI, S. OSHER,ANDZ. SHEN,Linearized Bregman iterations for frame-based image deblurring, SIAM J. Imaging Sci., 2 (2009), pp. 226-252. · Zbl 1175.94010
[12] ,Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009/10), pp. 337-369. · Zbl 1189.94014
[13] Y. CAI, M. DONATELLI, D. BIANCHI,ANDT.-Z. HUANG,Regularization preconditioners for frame-based image deblurring with reduced boundary artifacts, SIAM J. Sci. Comput., 38 (2016), pp. B164-B189. · Zbl 1382.94010
[14] R. H. CHAN, T. F. CHAN,ANDW. L. WAN,Multigrid for differential-convolution problems arising from image processing, in Scientific Computing, G. H. Golub, S. H. Lui, F. T. Luk, and R. J. Plemmons, eds., Springer, Singapore, 1997, pp. 58-72. · Zbl 0922.65097
[15] R. H. CHAN ANDK. CHEN,A multilevel algorithm for simultaneously denoising and deblurring images, SIAM J. Sci. Comput., 32 (2010), pp. 1043-1063. · Zbl 1217.68235
[16] P. DELL’ACQUA,A note on Taylor boundary conditions for accurate image restoration, Adv. Comput. Math., 43 (2017), pp. 1283-1304. · Zbl 1387.94014
[17] M. DONATELLI,An algebraic generalization of local Fourier analysis for grid transfer operators in multigrid based on Toeplitz matrices, Numer. Linear Algebra Appl., 17 (2010), pp. 179-197. · Zbl 1240.65353
[18] ,Fast transforms for high order boundary conditions in deconvolution problems, BIT, 50 (2010), pp. 559-576. · Zbl 1204.65151
[19] ,An iterative multigrid regularization method for Toeplitz discrete ill-posed problems, Numer. Math. Theory Methods Appl., 5 (2012), pp. 43-61. · Zbl 1265.65074
[20] ,On nondecreasing sequences of regularization parameters for nonstationary iterated Tikhonov, Numer. Algorithms, 60 (2012), pp. 651-668. · Zbl 1254.65135
[21] M. DONATELLI, C. ESTATICO, A. MARTINELLI,ANDS. SERRA-CAPIZZANO,Improved image deblurring with anti-reflective boundary conditions and re-blurring, Inverse Problems, 22 (2006), pp. 2035-2053. · Zbl 1167.65474
[22] M. DONATELLI ANDM. HANKE,Fast nonstationary preconditioned iterative methods for ill-posed problems, with application to image deblurring, Inverse Problems, 29 (2013), Art. 095008, 16 pages. · Zbl 1285.65030
[23] M. DONATELLI ANDS. SERRA-CAPIZZANO,On the regularizing power of multigrid-type algorithms, SIAM J. Sci. Comput., 27 (2006), pp. 2053-2076. · Zbl 1103.65043
[24] ,Filter factor analysis of an iterative multilevel regularizing method, Electron. Trans. Numer. Anal., 29 (2007/08), pp. 163-177. http://etna.ricam.oeaw.ac.at/vol.29.2007-2008/pp163-177.dir/ pp163-177.pdf · Zbl 1171.65369
[25] ,Antireflective boundary conditions for deblurring problems, J. Electr. Comput. Eng., (2010), Art. 241467, 18 pages. · Zbl 1229.94007
[26] D. L. DONOHO,De-noising by soft-thresholding, IEEE Trans. Inform. Theory, 41 (1995), pp. 613-627. · Zbl 0820.62002
[27] H. W. ENGL, M. HANKE,ANDA. NEUBAUER,Regularization of Inverse Problems, Kluwer, Dordrecht, 1996. · Zbl 0859.65054
[28] M. I. ESPAÑOL ANDM. E. KILMER,Multilevel approach for signal restoration problems with Toeplitz matrices, SIAM J. Sci. Comput., 32 (2010), pp. 299-319. · Zbl 1228.65060
[29] ,A wavelet-based multilevel approach for blind deconvolution problems, SIAM J. Sci. Comput., 36 (2014), pp. A1432-A1450.
[30] G. FIORENTINO ANDS. SERRA,Multigrid methods for Toeplitz matrices, Calcolo, 28 (1991), pp. 283-305 (1992). · Zbl 0778.65021
[31] S. GAZZOLA, P. C. HANSEN,ANDJ. G. NAGY,IR Tools: a MATLAB package of iterative regularization methods and large-scale test problems, Numer. Algorithms, 81 (2019), pp. 773-811. · Zbl 1415.65003
[32] M. HANKE,A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), pp. 79-95. · Zbl 0873.65057
[33] M. HANKE ANDP. C. HANSEN,Regularization methods for large-scale problems, Surveys Math. Indust., 3 (1993), pp. 253-315. · Zbl 0805.65058
[34] M. HANKE ANDC. R. VOGEL,Two-level preconditioners for regularized inverse problems. I. Theory, Numer. Math., 83 (1999), pp. 385-402. · Zbl 0941.65056
[35] P. C. HANSEN, J. G. NAGY,ANDD. P. O’LEARY,Deblurring Images. Matrices, Spectra, and Filtering, SIAM, Philadelphia, 2006.
[36] G. HUANG, L. REICHEL,ANDF. YIN,Projected nonstationary iterated Tikhonov regularization, BIT, 56 (2016), pp. 467-487. · Zbl 1341.65017
[37] T. HUCKLE ANDJ. STAUDACHER,Multigrid preconditioning and Toeplitz matrices, Electron. Trans. Numer. Anal., 13 (2002), pp. 81-105. http://etna.ricam.oeaw.ac.at/vol.13.2002/pp81-105.dir/pp81-105.pdf · Zbl 1065.65063
[38] B. KALTENBACHER,On the regularizing properties of a full multigrid method for ill-posed problems, Inverse Problems, 17 (2001), pp. 767-788. · Zbl 0993.65061
[39] J. T. KING,Multilevel algorithms for ill-posed problems, Numer. Math., 61 (1992), pp. 311-334. · Zbl 0768.65091
[40] S. MORIGI, L. REICHEL, F. SGALLARI,ANDA. SHYSHKOV,Cascadic multiresolution methods for image deblurring, SIAM J. Imaging Sci., 1 (2008), pp. 51-74. · Zbl 1144.65092
[41] M. K. NG, R. H. CHAN,ANDW.-C. TANG,A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21 (1999), pp. 851-866. · Zbl 0951.65038
[42] S. REEVES,Fast image restoration without boundary artifacts, IEEE Trans. Image Process., 14 (2005), pp. 1448-1453.
[43] L. REICHEL ANDA. SHYSHKOV,Cascadic multilevel methods for ill-posed problems, J. Comput. Appl. Math., 233 (2010), pp. 1314-1325. · Zbl 1186.65069
[44] A. RIEDER,A wavelet multilevel method for ill-posed problems stabilized by Tikhonov regularization, Numer. Math., 75 (1997), pp. 501-522. · Zbl 0878.65039
[45] J. W. RUGE ANDK. STÜBEN,Algebraic multigrid, in Multigrid methods, S. F. McCormick, ed., vol. 3 of Frontiers Appl. Math., SIAM, Philadelphia, 1987, pp. 73-130.
[46] S. SERRA-CAPIZZANO,A note on antireflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25 (2003/04), pp. 1307-1325. · Zbl 1062.65152
[47] U. TROTTENBERG, C. W. OOSTERLEE,ANDA. SCHÜLLER,Multigrid, Academic Press, Inc., San Diego, 2001.
[48] R. VIO, J. BARDSLEY, M. DONATELLI,ANDW. WAMSTEKER,Dealing with edge effects in least-squares image deconvolution problems, Astronom. and Astrophys., 442 (2005), pp. 397-403.
[49] Z. WANG, A. C. BOVIK, H. R. SHEIKH,ANDE. P. SIMONCELLI,Image quality assessment: from error visibility to structural similarity, IEEE Trans. Image Process., 13 (2004), pp. 600-612.
[50] E.
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.