FTVD | New LADMM | TVAL3 | ||||
Noise Ratio | time | SNR | time | SNR | time | SNR |
60% | 3.806 | 20.894 | 20.155 | 23.594 | 14.212 | 11.806 |
80% | 8.174 | 8.751 | 19.687 | 15.226 | 26.442 | 7.106 |
In this paper, we propose a partial convolution model for image deblurring and denoising. We also devise a new linearized alternating direction method of multipliers (ADMM) with an extension step. As the computation of its subproblem is simple enough to have closed-form solutions, its per-iteration cost is low; however, the relaxed parameter condition together with the extra extension step inspired by Ye and Yuan's ADMM enables faster convergence than the original linearized ADMM. Preliminary experimental results show that our algorithm can produce better quality results than some existing efficient algorithms within a similar computation time. The performance advantage of our algorithm is particularly evident at high noise ratios.
Citation: |
Table 1. Numerical results of basic test
FTVD | New LADMM | TVAL3 | ||||
Noise Ratio | time | SNR | time | SNR | time | SNR |
60% | 3.806 | 20.894 | 20.155 | 23.594 | 14.212 | 11.806 |
80% | 8.174 | 8.751 | 19.687 | 15.226 | 26.442 | 7.106 |
[1] |
R. Acar and C. R. Vogel, Analysis of total variation penalty methods, Inverse Probl., 10 (1994), 1217-1229.
doi: 10.1088/0266-5611/10/6/003.![]() ![]() ![]() |
[2] |
S. Alliney, Digital filters as absolute norm regularizers, IEEE Trans. Signal Proces., 40 (1992), 1548-1562.
![]() |
[3] |
J. Barzilai and J.M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.
doi: 10.1093/imanum/8.1.141.![]() ![]() ![]() |
[4] |
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.![]() ![]() ![]() |
[5] |
S. Becker, J. Bobin and E. Candes, Nesta: A fast and accurate first-order method for sparse recovery, SIAM J. Imaging Sci., 4 (2011), 1-39.
doi: 10.1137/090756855.![]() ![]() ![]() |
[6] |
D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982.
![]() ![]() |
[7] |
J. Bioucas-Dias and M. Figueiredo, A new twist: Two-step iterative shrinkage/thresholding algorithms for image restoration, IEEE Trans. Image Proces., 16 (2007), 2992-3004.
doi: 10.1109/TIP.2007.909319.![]() ![]() ![]() |
[8] |
S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2011), 1-122.
![]() |
[9] |
J. Cai, R.H. Chan and M. Nikolova, Two phase methods for deblurring images corrupted by impulse plus gaussian noise, Inverse Probl. Imag., 2 (2008), 187-204.
doi: 10.3934/ipi.2008.2.187.![]() ![]() ![]() |
[10] |
A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging Vis., 40 (2011), 120-145.
doi: 10.1007/s10851-010-0251-1.![]() ![]() ![]() |
[11] |
R.H. Chan, C.W. Ho and M. Nikolova, Salt-and-pepper noise removal by median-type noise detector and detail-preserving regularization, IEEE Trans. Imag. Process., 14 (2005), 1479-1485.
![]() |
[12] |
R.H. Chan, M. Tao and X. Yuan, Linearized alternating direction method of multipliers for constrained linear least-squares problem, E. Asian J. Appl. Math., 2 (2012), 326-341.
doi: 10.4208/eajam.270812.161112a.![]() ![]() ![]() |
[13] |
T.F. Chan and S. Esedoglu, Aspects of total variation regularized l1 function approximation, SIAM J. Appl. Math., 65 (2005), 1817-1837.
doi: 10.1137/040604297.![]() ![]() ![]() |
[14] |
T.F. Chan, G. Golub and P. Mulet, A nonlinear primal-dual method for total variation-based image restoration, SIAM J. Sci. Comput., 20 (1999), 1964-1977.
doi: 10.1137/S1064827596299767.![]() ![]() ![]() |
[15] |
C. Chen, B. He, Y. Ye and X. Yuan, The direct extension of admm for multi-block convex minimization problems is not necessarily convergent, Math. Program. Series A, 155 (2016), 57-79.
doi: 10.1007/s10107-014-0826-5.![]() ![]() ![]() |
[16] |
C. Chen, Y. Shen and Y. You, On the convergence analysis of the alternating direction method of multipliers with three blocks, Abstr. Appl. Anal., 2013 (2013), Art. ID 183961, 7 pp.
![]() ![]() |
[17] |
S. W.J. Cho and S. Lee, Handling outliers in non-blind image deconvolution, International Conference on Computer Vision, (2011), 495-502.
![]() |
[18] |
I. Daubechies, M. Defrise and C. DeMol, 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.![]() ![]() ![]() |
[19] |
J. Douglas and H.H. Rachford, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Trans. Amer. Math. Soc., 82 (1956), 421-439.
doi: 10.1090/S0002-9947-1956-0084194-4.![]() ![]() ![]() |
[20] |
E. Esser, Applications of lagrangian-based alternating direction methods and connections to split bregman, Manuscript, (2009), ftp://ftp.math.ucla.edu/pub/camreport/cam09-31.pdf.
![]() |
[21] |
M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, North-Holland, Amsterdam, 1983.
![]() ![]() |
[22] |
D. Gabay, Applications of the method of multipliers to variational inequalities, In Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, M. Fortin and R. Glowinski, Eds. Horth-Hollan, Amsterdam, 1983.
![]() ![]() |
[23] |
D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximations, Comput. Math. Appl., (1976), 17-40.
![]() |
[24] |
R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag, New York, Berlin, Heidelberg, Tokyo, 1984.
![]() ![]() |
[25] |
R. Glowinski and A. Marrocco, Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de dirichlet nonlineaires, Rev. Francaise dAut. Inf. Rech. Oper., 9 (1975), 41-76.
![]() ![]() |
[26] |
B. He, M. Tao and X. Yuan, Alternating direction method with gaussian back substitution for separable convex programming, SIAM J. Optim., 22 (2012), 313-340.
doi: 10.1137/110822347.![]() ![]() ![]() |
[27] |
B. He and X. Yuan, On the convergence rate of douglas-rachford operator splitting method, Math. Program., 153 (2015), 715-722.
doi: 10.1007/s10107-014-0805-x.![]() ![]() ![]() |
[28] |
M. Hong and Z. Luo, On the linear convergence of the alternating direction method of multipliers, arXiv preprint, arXiv: 1208.3922, (2013).
![]() |
[29] |
Y. Huang, M. K. Ng and Y.-W. Wen, A fast total variation minimization method for image restoration, Multiscale Model. Sim., 7 (2008), 774-795.
doi: 10.1137/070703533.![]() ![]() ![]() |
[30] |
Y. Jiao, Q. Jin, X. Lu and W. Wang, Alternating direction method of multipliers for linear inverse problems, SIAM J. Numer. Anal., 54 (2016), 2114-2137.
doi: 10.1137/15M1029308.![]() ![]() ![]() |
[31] |
Y. Jiao, Q. Jin, X. Lu and W. Wang, Preconditioned alternating direction method of multipliers for inverse problems with constraints, nverse Probl., 33 (2017), 025004(34pp).
![]() ![]() |
[32] |
C. Li, W. Yin and Y. Zhang, Tv Minimization by Augmented Lagrangian and Alternating Direction Algorithms, Tech. rep., Department of CAAM, Rice University, Houston, Texas, 77005, 2009. http://www.caam.rice.edu/~optimization/L1/TVAL3/.
![]() |
[33] |
P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16 (1979), 964-979.
doi: 10.1137/0716071.![]() ![]() ![]() |
[34] |
D. Mumford and J. Shah, Optimal approximations by piecewise smooth functions and associated variational problems, Comm. Pure Appl. Math., 42 (1989), 577-685.
doi: 10.1002/cpa.3160420503.![]() ![]() ![]() |
[35] |
Y. Nesterov, Smooth minimization of non-smooth functions, Math. Program., 103 (2005), 127-152.
doi: 10.1007/s10107-004-0552-5.![]() ![]() ![]() |
[36] |
Y. Ouyang, Y. Chen, G. Lan and E.J. Pasiliao, An accelerated linearized alternating direction method of multipliers, SIAM J Imaging Sci., 8 (2015), 644-681.
doi: 10.1137/14095697X.![]() ![]() ![]() |
[37] |
L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.
doi: 10.1016/0167-2789(92)90242-F.![]() ![]() ![]() |
[38] |
A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, Winston, New York, 1977.
![]() ![]() |
[39] |
C. Vogel and M. Oman, Fast, robust total variation-based reconstruction of noisy, blurred images, IEEE Trans. Image Proces., 7 (1998), 813-824.
doi: 10.1109/83.679423.![]() ![]() ![]() |
[40] |
X. Wang and X. Yuan, The linearized alternating direction method of multipliers for dantzig selector, SIAM J. Sci. Comput., 34 (2012), 2792-2811.
doi: 10.1137/110833543.![]() ![]() ![]() |
[41] |
Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Image Sci., 1 (2008), 248-272.
doi: 10.1137/080724265.![]() ![]() ![]() |
[42] |
T. Wu, Variable splitting based method for image restoration with impulse plus gaussian noise, Math. Probl. Eng., 2016 (2016), Article ID 3151303, 16 pages.
![]() |
[43] |
J. Yang and Y. Zhang, Alternating direction algorithms for $\ell_1$-problems in compressive sensing, SIAM J. Sci. Comput., 33 (2011), 250-278.
doi: 10.1137/090777761.![]() ![]() ![]() |
[44] |
J. Yang, Y. Zhang and W. Yin, An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise, SIAM J. Sci. Comput., 31 (2009), 2842-2865.
doi: 10.1137/080732894.![]() ![]() ![]() |
[45] |
C. Ye and X. Yuan, A descent method for structured monotone variational inequalities, Optim. Methods Softw., 22 (2007), 329-338.
doi: 10.1080/10556780600552693.![]() ![]() ![]() |
[46] |
W. Yin, D. Goldfarb and S. Osher, The total variation regularized $L^1$ multiscale decomposition, Multiscale Model. Sim., 6 (2007), 190-211.
doi: 10.1137/060663027.![]() ![]() ![]() |
From left to right are the results of FTVD, New algorithm, TVAL3, and SNR history plot. First row:
Performance v.s. noise ratio. Left: time; right: SNR. First row:
Performance v.s. indices matrix quality. Left: time, right: SNR. First row:
From left to right to below are the results of FTVD, New algorithm, and TVAL3, and SNR history plot. First row: "average" kernel with dirichlet boundary condition; second row: "Gaussian" kernel; third row: "Disk" kernel; fourth row: "motion" kernel