×

A fast alternating minimization algorithm for total variation deblurring without boundary artifacts. (English) Zbl 1308.94010

Summary: Recently, a fast alternating minimization algorithm for total variation image deblurring (FTVd) has been presented by Wang, Yang, Yin, and Zhang [Y. Wang et al., SIAM J. Imaging Sci. 1, No. 3, 248–272 (2008; Zbl 1187.68665)]. The method in a nutshell consists of a discrete Fourier transform-based alternating minimization algorithm with periodic boundary conditions and in which two fast Fourier transforms (FFTs) are required per iteration. In this paper, we propose an alternating minimization algorithm for the continuous version of the total variation image deblurring problem. We establish convergence of the proposed continuous alternating minimization algorithm. The continuous setting is very useful to have a unifying representation of the algorithm, independently of the discrete approximation of the deconvolution problem, in particular concerning the strategies for dealing with boundary artifacts. Indeed, an accurate restoration of blurred and noisy images requires a proper treatment of the boundary. A discrete version of our continuous alternating minimization algorithm is obtained following two different strategies: the imposition of appropriate boundary conditions and the enlargement of the domain. The first one is computationally useful in the case of a symmetric blur, while the second one can be efficiently applied for a nonsymmetric blur. Numerical tests show that our algorithm generates higher quality images in comparable running times with respect to the Fast Total Variation deconvolution algorithm.

MSC:

94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
49M15 Newton-type methods

Citations:

Zbl 1187.68665

Software:

RecPF
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, R. A.; Fournier, J. J.F., Sobolev Spaces, Pure Appl. Math., vol. 140 (2003), Elsevier · Zbl 1098.46001
[2] Afonso, M.; Bioucas-Dias, J.; Figueiredo, M., Fast image recovery using variable splitting and constrained optimization, IEEE Trans. Image Process., 19, 2345-2356 (2010) · Zbl 1371.94018
[3] Afonso, M.; Bioucas-Dias, J.; Figueiredo, M., An augmented Lagrangian approach to the constrained optimization formulation of imaging inverse problems, IEEE Trans. Image Process., 20, 681-695 (2011) · Zbl 1372.94004
[4] Almeida, M. S.C.; Figueiredo, M. A.T., Deconvolving images with unknown boundaries using the alternating direction method of multipliers, IEEE Trans. Image Process., 22, 3074-3086 (2013) · Zbl 1373.94019
[5] Aricò, A.; Donatelli, M.; Serra-Capizzano, S., Spectral analysis of the anti-reflective algebra, Linear Algebra Appl., 428, 657-675 (2008) · Zbl 1140.15005
[6] Aricò, A.; Donatelli, M.; Nagy, J.; Serra-Capizzano, S., The anti-reflective transform and regularization by filtering, (Bhattacharyya, S.; Chan, R.; Olshevsky, V.; Routray, A.; Van Dooren, P., Numerical Linear Algebra in Signals, Systems, and Control. Numerical Linear Algebra in Signals, Systems, and Control, Lect. Notes Electr. Eng., vol. 80 (2011), Springer Verlag), 1-21 · Zbl 1258.94014
[7] 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, 785-805 (2011) · Zbl 1269.65144
[8] Bertero, M.; Boccacci, P., A simple method for the reduction of boundary effects in the Ricardson-Lucy approach to image deconvolution, Astron. Astrophys., 437, 369-374 (2005)
[9] Chan, T.; Shen, J., Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods (2005), SIAM · Zbl 1095.68127
[10] Chan, R.; Chan, T.; Wong, C., Cosine transform based preconditioners for total variation deblurring, IEEE Trans. Image Process., 8, 1472-1478 (1999)
[11] Csiszár, I.; Tusnády, G., Information geometry and alternating minimization procedures, Statist. Decisions Suppl., 1, 205-237 (1984) · Zbl 0547.60004
[12] Donatelli, M., Fast transforms for high order boundary conditions in deconvolution problems, BIT, 50, 3, 559-576 (2010) · Zbl 1204.65151
[13] Donatelli, M.; Serra-Capizzano, S., Anti-reflective boundary conditions and re-blurring, Inverse Problems, 21, 1, 169-182 (2005) · Zbl 1088.94510
[14] Donatelli, M.; Serra-Capizzano, S., Antireflective boundary conditions for deblurring problems, J. Electr. Comput. Eng., 2010 (2010), Article ID 241467, 18 pp. (survey) · Zbl 1229.94007
[15] Donatelli, M.; Serra-Capizzano, S., On the treatment of boundary artifacts in image restoration by reflection and/or anti-reflection, (Olshevsky, V.; Tyrtyshnikov, E., Matrix Methods: Theory, Algorithms and Applications (2010), World Scientific), 227-237 · Zbl 1216.94011
[16] Donatelli, M.; Estatico, C.; Martinelli, A.; Serra-Capizzano, S., Improved image deblurring with anti-reflective boundary conditions and re-blurring, Inverse Problems, 22, 2035-2053 (2006) · Zbl 1167.65474
[17] Ekeland, I.; Temam, R., Convex Analysis and Variational Problems, Classics Appl. Math. (1999), Society for Industrial Mathematics · Zbl 0939.49002
[18] Evans, L. C., The 1-Laplacian, the ∞-Laplacian and Differential Games, Contemp. Math., vol. 446 (2007), Amer. Math. Soc. · Zbl 1200.35114
[19] Fan, Y. W.; Nagy, J. G., Synthetic boundary conditions for image deblurring, Linear Algebra Appl., 434, 2244-2268 (2011) · Zbl 1210.94013
[20] Groetsch, C., Inverse Problems in the Mathematical Sciences (1993), Vieweg: Vieweg Wiesbaden, Germany · Zbl 0779.45001
[21] Hansen, P. C.; Nagy, J.; O’Leary, D. P., Deblurring Images Matrices, Spectra and Filtering (2005), SIAM Publications: SIAM Publications Philadelphia
[22] Kawohl, B.; Fridman, V., Isoperimetric estimates for the first eigenvalue of the \(p\)-Laplace operator and the Cheeger constant, Comment. Math. Univ. Carolin., 44, 659-667 (2003) · Zbl 1105.35029
[23] Matakos, A.; Ramani, S.; Fessler, J. A., Accelerated edge-preserving image restoration without boundary artifacts, IEEE Trans. Image Process., 22, 2019-2029 (2013) · Zbl 1373.94278
[24] 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
[25] Nocedal, J.; Wright, S. J., Numerical Optimization (1999), Springer: Springer New York · Zbl 0930.65067
[26] Reeves, S. J., Fast image restoration without boundary artifacts, IEEE Trans. Image Process., 14, 1448-1453 (2005)
[27] Serra-Capizzano, S., A note on anti-reflective boundary conditions and fast deblurring models, SIAM J. Sci. Comput., 25, 3, 1307-1325 (2003) · Zbl 1062.65152
[28] Sorel, M., Removing boundary artifacts for real-time iterated shrinkage deconvolution, IEEE Trans. Image Process., 21, 2329-2334 (2012) · Zbl 1373.94012
[29] Temam, R., Problemes mathématiques en plasticité, Méthodes Math. Inform., vol. 12 (1983), Gauthier-Villars · Zbl 0547.73026
[30] Vio, R.; Bardsley, J.; Donatelli, M.; Wamsteker, W., Dealing with edge effects in least-squares image deconvolution problems, Astron. Astrophys., 442, 397-403 (2005)
[31] Vogel, C. R., Computational Methods for Inverse Problems (2002), SIAM · Zbl 1008.65103
[32] Wang, Y.; Yang, J.; Yin, W.; Zhang, Y., A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imaging Sci., 1, 248-272 (2008) · Zbl 1187.68665
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.