×

Image deblurring by sparsity constraint on the Fourier coefficients. (English) Zbl 1342.65095

Summary: This paper is concerned with the image deconvolution problem. For the basic model, where the convolution matrix can be diagonalized by discrete Fourier transform, the Tikhonov regularization method is computationally attractive since the associated linear system can be easily solved by fast Fourier transforms. On the other hand, the provided solutions are usually oversmoothed and other regularization terms are often employed to improve the quality of the restoration. Of course, this weighs down on the computational cost of the regularization method. Starting from the fact that images have sparse representations in the Fourier and wavelet domains, many deconvolution methods have been recently proposed with the aim of minimizing the \(\ell_1\)-norm of these transformed coefficients. This paper uses the iteratively reweighted least squares strategy to introduce a diagonal weighting matrix in the Fourier domain. The resulting linear system is diagonal and hence the regularization parameter can be easily estimated, for instance by the generalized cross validation. The method benefits from a proper initial approximation that can be the observed image or the Tikhonov approximation. Therefore, embedding this method in an outer iteration may yield further improvement of the solution. Finally, since some properties of the observed image, like continuity or sparsity, are obviously changed when working in the Fourier domain, we introduce a filtering factor which keeps unchanged the large singular values and preserves the jumps in the Fourier coefficients related to the low frequencies. Numerical examples are given in order to show the effectiveness of the proposed method.

MSC:

65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
65T50 Numerical methods for discrete and fast Fourier transforms
65T60 Numerical methods for wavelets
65F22 Ill-posedness and regularization problems in numerical linear algebra
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aricò, A., Donatelli, M., Nagy, J.G., Serra-Capizzano, S.: The Anti-Reflective Transform and Regularization by Filtering. Numerical Linear Algebra in Signals, Systems, and Control. Lect. Notes Electr. Eng. 80, 1-21 (2011) · Zbl 1258.94014 · doi:10.1007/978-94-007-0602-6_1
[2] Bai, Z.J., Donatelli, M., Serra-Capizzano, S.: Fast Preconditioners for Total Variation Deblurring with Anti-Reflective Boundary Conditions, SIAM. J. Matrix Anal. Appl., 32-3, 785-805 (2011) · Zbl 1269.65144
[3] Björck, A.: Numerical Methods for Least Squares Problems. SIAM. Philadelphia (1996) · Zbl 0847.65023
[4] Cai, J.F., Osher, S., Shen, Z.: Linearized Bregman iterations for frame-based image deblurring. SIAM J. Imaging Sci. 2, 226-252 (2009) · Zbl 1175.94010 · doi:10.1137/080733371
[5] Donatelli, M.: Fast transforms for high order boundary conditions in deconvolution problems. BIT, 50-3, 559-576 (2010) · Zbl 1204.65151
[6] Donatelli, M., Neuman, A., Reichel, L.: Square regularization matrices for large linear discrete ill-posed problems. Numer. Linear Algebra Appl. 19(6), 896-913 (2012) · Zbl 1289.65096 · doi:10.1002/nla.1833
[7] Donatelli, M., Reichel, L.: Square smoothing regularization matrices with accurate boundary conditions. J. Comput. Appl. Math. 272, 334-349 (2014) · Zbl 1294.65099 · doi:10.1016/j.cam.2013.08.015
[8] Engl, H.W., Hanke, M., Neubauer, A.: Regularization methods for inverse problems. Kluwer, Dordrecht (1996) · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8
[9] Figueiredo, M.A.T., Nowak, R.D.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process 12, 906-916 (2003) · Zbl 1279.94015 · doi:10.1109/TIP.2003.814255
[10] Gazzola, S., Nagy, J.G.: Generalized Arnoldi-Tikhonov methods for sparse reconstruction. SIAM J. Imaging Sci. 36, 225-247 (2014) · Zbl 1296.65061 · doi:10.1137/130917673
[11] Hansen, P.C.: Regularization Tools: A Matlab package for analysis and solution of discrete ill-posed problems. Numer. Algorithms 6, 1-35 (1994) · Zbl 0789.65029 · doi:10.1007/BF02149761
[12] Hansen, P.C.: Rank-deficient and discrete ill-posed problems. SIAM. Philadelphia (1998) · Zbl 1258.94014
[13] Hansen, P.C., Nagy, J.G., O’Leary, D.P.: Deblurring images: matrices, spectra and filtering. SIAM. Philadelphia (2006) · Zbl 1112.68127
[14] Huckle, T., Sedlacek, M.: Data based regularization for discrete deconvolution problems. BIT 53, 459-473 (2013) · Zbl 1266.65066
[15] Huckle, T., Sedlacek, M.: Data based regularization matrices for the Tikhonov-Phillips regularization. Proc. Appl. Math. Mech. 12, 643-644 (2012) · Zbl 1245.65049 · doi:10.1002/pamm.201210310
[16] Huckle, T., Sedlacek, M.: Smoothing and regularization with modified sparse approximate inverses. J. Electr. Comput. Eng. 16 pages (2010) · Zbl 1229.65058
[17] Huckle, T., Sedlacek, M.: Tikhonov-Phillips regularization with operator dependent seminorms. Numer. Alg. 60, 339-35 (2012) · Zbl 1245.65049 · doi:10.1007/s11075-012-9575-9
[18] Mallat, S.: A wavelet tour of signal processing. Academic Press, California (1999) · Zbl 0998.94510
[19] Nagy, J.G.: Restore tools matlab package. http://www.mathcs.emory.edu/ nagy/RestoreTools/
[20] Ng, M., Chan, R., Tang, W.C.: A fast algorithm for deblurring models with Neumann boundary conditions. SIAM. J. Sci. Comput. 21, 851-866 (1999) · Zbl 0951.65038
[21] Reeves, S.J.: Fast image restoration without boundary artifacts. IEEE Trans. Image Process 14, 1448-1453 (2005) · doi:10.1109/TIP.2005.854474
[22] Rudin, L., Osher, S., Fatemi, E.: Nonlinear total variation based noise removal algorithms. Phys. D. 60, 259-268 (1992) · Zbl 0780.49028 · doi:10.1016/0167-2789(92)90242-F
[23] Serra-Capizzano, S.: A note on anti-reflective boundary conditions and fast deblurring models. SIAM. J. Sci. Comput. 25, 1307-1325 (2003) · Zbl 1062.65152
[24] Vogel, C.R.: Computational methods for inverse problems. SIAM. Philadelphia (2002) · Zbl 1008.65103
[25] Wohlberg, B., Rodríguez, P.: An iteratively reweighted norm algorithm for minimization of total variation functionals. IEEE Signal Process. Lett 14, 948-951 (2007) · doi:10.1109/LSP.2007.906221
[26] Wright, S.J., Figueiredo, M.A.T., Nowak, R.D.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Process 57, 2479-2493 (2009) · Zbl 1391.94442 · doi:10.1109/TSP.2009.2016892
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.