Nonstationary iterated thresholding algorithms for image deblurring

Jie Huang; Marco Donatelli; Raymond H. Chan

doi:10.3934/ipi.2013.7.717

Article Contents

2013, Volume 7, Issue 3: 717-736. Doi: 10.3934/ipi.2013.7.717

This issue Previous Article Non-Gaussian dynamics of a tumor growth system with immunization Next Article A local mesh method for solving PDEs on point clouds

Nonstationary iterated thresholding algorithms for image deblurring

1.
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, Sichuan, 611731
2.
Dipartimento di Scienza e Alta Tecnologia, Università dell'Insubria, Como 22100
3.
Department of Mathematics, Chinese University of Hong Kong, Shatin, Hong Kong

Received: April 2013

Revised: June 2013

Published: August 2013

Abstract / Introduction Related Papers Cited by

Abstract

We propose iterative thresholding algorithms based on the iterated Tikhonov method for image deblurring problems. Our method is similar in idea to the modified linearized Bregman algorithm (MLBA) so is easy to implement. In order to obtain good restorations, MLBA requires an accurate estimate of the regularization parameter $\alpha$ which is hard to get in real applications. Based on previous results in iterated Tikhonov method, we design two nonstationary iterative thresholding algorithms which give near optimal results without estimating $\alpha$. One of them is based on the iterative soft thresholding algorithm and the other is based on MLBA. We show that the nonstationary methods, if converge, will converge to the same minimizers of the stationary variants. Numerical results show that the accuracy and convergence of our nonstationary methods are very robust with respect to the changes in the parameters and the restoration results are comparable to those of MLBA with optimal $\alpha$.

Keywords:

Mathematics Subject Classification: Primary: 94A08, 49N45; Secondary: 65T60, 65F08.

Citation:

Related Papers

Cited by

References

[1]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202.doi: 10.1137/080716542.
[2]	M. Bertalmío, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, SIGGRAPH, 34 (2000), 417-424.doi: 10.1145/344779.344972.
[3]	M. Bertero and P. Boccacci, "Introduction to Inverse Problems in Imaging," Institute of Physics Publishing, Bristol, 1998.doi: 10.1887/0750304359.
[4]	N. Bose and K. Boo, High-resolution image reconstruction with multisensors, International Journal of Imaging Systems and Technology, 9 (1998), 294-304.
[5]	L. M. Bregman, A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, (Russian) Z . Vycisl. Mat. i Mat. Fiz., 7 (1967), 620-631.
[6]	M. Brill and E. Schock, Iterative solution of ill-posed problems: A survey, in "Model Optimization in Exploration Geophysics" (Berlin, 1986), 13-37, Theory Practice Appl. Geophys., 1, Vieweg, Braunschweig, 1987.
[7]	J. F. Cai, R. H. Chan and Z. Shen, A framelet-based image inpainting algorithm, Appl. Comput. Harmon. Anal., 24 (2008), 131-149.doi: 10.1016/j.acha.2007.10.002.
[8]	J. F. Cai, S. Osher and Z. Shen, Linearized BRegman iterations for frame-based image deblurring, SIAM J. Imaging Sci., 2 (2009), 226-252.doi: 10.1137/080733371.
[9]	J. F. Cai, S. Osher and Z. Shen, Split Bregman methods and frame based image restoration, Multiscale Model. Simul., 8 (2009), 337-369.doi: 10.1137/090753504.
[10]	J. F. Cai, S. Osher and Z. Shen, Convergence of the linearized Bregman iteration for $l_1$-norm minimization, Math. Comput., 78 (2009), 2127-2136.doi: 10.1090/S0025-5718-09-02242-X.
[11]	J. F. Cai, S. Osher and Z. Shen, Linearized Bregman iterations for compressed sensing, Math. Comput., 78 (2009), 1515-1536.doi: 10.1090/S0025-5718-08-02189-3.
[12]	E. J. Candés and J. Romberg, Practical signal recovery from random projections, Wavelet Applications in Signal and Image Processing XI Proc. SPIE Conf. 5914 (2004).
[13]	A. Chai and Z. Shen, Deconvolution: A wavelet frame approach, Numer. Math., 106 (2007), 529-587.doi: 10.1007/s00211-007-0075-0.
[14]	A. Chambolle, R. A. De Vore, N. Y. Lee and B. J. Lucier, Nonlinear wavelet image processing: Variational problems, compression, and noise removal through wavelet shrinkage, IEEE Trans. Image Process., 7 (1998), 319-335.doi: 10.1109/83.661182.
[15]	R. H. Chan, T. F. Chan, L. Shen and Z. Shen, Wavelet algorithms for high-resolution image reconstruction, SIAM J. Sci. Comput., 24 (2003), 1408-1432.doi: 10.1137/S1064827500383123.
[16]	R. H. Chan, S. D. Riemenschneider, L. Shen and Z. Shen, Tight frame: An efficient way for high-resolution image reconstruction, Appl. Comput. Harmon. Anal., 17 (2004), 91-115.doi: 10.1016/j.acha.2004.02.003.
[17]	R. H. Chan, Z. Shen and T. Xia, A framelet algorithm for enhancing video stills, Appl. Comput. Harmon. Anal., 23 (2007), 153-170.doi: 10.1016/j.acha.2006.10.003.
[18]	T. Chan and J. H. Shen, "Image Processing and Analysis-Variational, PDE, Wavelet, and Stochastic Methods," Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2005.doi: 10.1137/1.9780898717877.
[19]	T. Chan, J. H. Shen and H. M. Zhou, Total variation wavelet inpainting, J. Math. Imaging Vision, 25 (2006), 107-125.doi: 10.1007/s10851-006-5257-3.
[20]	P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200.doi: 10.1137/050626090.
[21]	I. Daubechies, M. Defrise and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Comm. Pure Appl. Math., 57 (2004), 1413-1457.doi: 10.1002/cpa.20042.
[22]	I. Daubechies, M. Fornasier and I. Loris, Accelerated projected gradient method for linear inverse problems with sparsity constraints, J. Fourier Anal. Appl. 14 (2008), 764-792.doi: 10.1007/s00041-008-9039-8.
[23]	I. Daubechies, B. Han, A. Ron and Z. Shen, Framelets: MRA-based constructions of wavelet frames, Appl. Comput. Harmon. Anal., 14 (2003), 1-46.doi: 10.1016/S1063-5203(02)00511-0.
[24]	I. Daubechies, G. Teschke and L. Vese, Iteratively solving linear inverse problems under general convex constraints, Inverse Problems Imaging, 1 (2007), 29-46.doi: 10.3934/ipi.2007.1.29.
[25]	M. Donatelli, Fast transforms for high order boundary conditions in deconvolution problems, BIT, 50 (2010), 559-576.doi: 10.1007/s10543-010-0266-4.
[26]	M. Donatelli, On nondecreasing sequences of regularization parameters for nonstationary iterated tikhonov, Numer. Algor., 60 (2012), 651-668.doi: 10.1007/s11075-012-9593-7.
[27]	M. Donatelli and M. Hanke, Fast nonstationary preconditioned iterative methods for ill-posed problems, with application to image deblurring, Inverse Problems, 29 (2013), 095008.doi: 10.1088/0266-5611/29/9/095008.
[28]	M. Elad and A. Feuer, Restoration of a single superresolution image from several blurred, noisy and undersampled measured images, IEEE Trans. Image Process, 6 (1997), 1646-1658.doi: 10.1109/83.650118.
[29]	H. W. Engl, M. Hanke and A. Neubauer, "Regularization of Inverse Problems," Mathematics and its Applications, 375. Kluwer Academic Publishers Group, Dordrecht, 1996.doi: 10.1007/978-94-009-1740-8.
[30]	M. J. Fadili and J. L. Starck, Sparse representations and Bayesian image inpainting, Proc. SPARS'05, Vol. I, Rennes, France, 2005.
[31]	A. G. Fakeev, A class of iterative processes for solving degenerate systems of linear algebraic equations, U. S. S. R. Comput. Math. Math. Phys., 21 (1981), 15-22.
[32]	M. Figueiredo and R. Nowak, An EM algorithm for wavelet-based image restoration, IEEE Trans. Image Process., 12 (2003), 906-916.doi: 10.1109/TIP.2003.814255.
[33]	E. Hale, W. Yin and Y. Zhang, Fixed-point continuation for $l_1$-minimization: Methodology and convergence, SIAM J. Optim., 19 (2008), 1107-1130.doi: 10.1137/070698920.
[34]	M. Hanke and C. W. Groetsh, Nonstationary iterated tikhonov regularization, J. Optim. Theory Appl., 98 (1998), 37-53.doi: 10.1023/A:1022680629327.
[35]	M. Hanke and P. C. Hansen, Regularization methods for large-scale problems, Surveys Math. Indust., 3 (1993), 253-315.
[36]	P. C. Hansen, "Rank-Deficient and Discrete Ill-Posed Problems," SIAM, Philadelphia, 1997.doi: 10.1137/1.9780898719697.
[37]	J. T. King and D. Chillingworth, Approximation of generalized inverses by iterated regularization, Numer. Func. Anal. Opt., 1 (1979), 499-513.doi: 10.1080/01630567908816031.
[38]	A. V. Kryanev, An iterative method for solving incorrectly posed problems, U. S. S. R. Comput. Math. Math. Phys., 14 (1974), 25-35.doi: 10.1016/0041-5553(74)90133-5.
[39]	L. Landweber, An iteration formula for fredholm integral equations of the first kind, Am. J. Math., 73 (1951), 615-624.doi: 10.2307/2372313.
[40]	I. Loris, M. Bertero, C. De Mol, R. Zanella and L. Zanni, Accelerating gradient projection methods for $l_1$-constrained signal recovery by steplength selection rules, Appl. Comput. Harmon. Anal., 27 (2009), 247-254.doi: 10.1016/j.acha.2009.02.003.
[41]	S. Mallat, "A Wavelet Tour of Signal Processing," 2nd edition, Academic Press: San Diego, 1999.
[42]	V. A. Morozov, On the solution of functional equations by the method of regularization, Dokl. Akad. Nauk SSSR 167 510-512 (Russian), translated as Soviet Math. Dokl., 7 (1966), 414-417.
[43]	F. Natterer, "The Mathematics of Computerized Tomography," Reprint of the 1986 original. Classics in Applied Mathematics, 32. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.doi: 10.1137/1.9780898719284.
[44]	M. K. Ng, R. H. Chan and W. C. Tang, A fast algorithm for deblurring models with Neumann boundary conditions, SIAM J. Sci. Comput., 21 (1999), 851-866.doi: 10.1137/S1064827598341384.
[45]	S. Osher, Y. Mao, B. Dong and W. Yin, Fast linearized Bregman iteration for compressed sensing and sparse denoising, Commun. Math. Sci., 8 (2010), 93-111.
[46]	M. Piana and M. Bertero, Projected landweber method and preconditioning, Inverse Problems, 13 (1997), 441-464.doi: 10.1088/0266-5611/13/2/016.
[47]	O. N. Strand, Theory and methods related to the singular-function expansion and landweber's iteration for integral equations of the first kind, SIAM J. Numer. Anal, 11 (1974), 798-825.doi: 10.1137/0711066.
[48]	A. N. Tikhonov, Solution of incorrectly formulated problems and the regularization method, Soviet Math. Dokl., 4 (1963), 1035-1038.
[49]	C. R. Vogel, "Computational Methods for Inverse Problems," With a foreword by H. T. Banks. Frontiers in Applied Mathematics, 23. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2002.doi: 10.1137/1.9780898717570.
[50]	W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM J. Imaging Sci., 1 (2008), 143-168.doi: 10.1137/070703983.