Fast total variation wavelet inpaintingvia approximated primal-dual hybridgradient algorithm

Xiaojing Ye; Haomin Zhou

doi:10.3934/ipi.2013.7.1031

Article Contents

2013, Volume 7, Issue 3: 1031-1050. Doi: 10.3934/ipi.2013.7.1031

This issue Previous Article General convergent expectation maximization (EM)-type algorithms for image reconstruction Next Article The Gaussian beam method for the wigner equation with discontinuous potentials

Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm

Xiaojing Ye^1, and
Haomin Zhou^1,

1.
School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30308

Received: April 30, 2012

Revised: October 31, 2012

Published: July 2013

Abstract Related Papers Cited by

Abstract

The primal-dual hybrid gradient (PDHG) algorithm has been successfully applied to a number of total variation (TV) based image reconstruction problems for fast numerical solutions. We show that PDHG can also effectively solve the computational problem of image inpainting in wavelet domain, where high quality images are to be recovered from incomplete wavelet coefficients due to lossy data transmission. In particular, as the original PDHG algorithm requires the orthogonality of encoding operators for optimal performance, we propose an approximated PDHG algorithm to tackle the non-orthogonality of Daubechies 7-9 wavelet which is widely used in practice. We show that this approximated version essentially alters the gradient descent direction in the original PDHG algorithm, but eliminates its orthogonality restriction and retains low computation complexity. Moreover, we prove that the sequences generated by the approximated PDHG algorithm always converge monotonically to an exact solution of the TV based image reconstruction problem starting from any initial guess. We demonstrate that the approximated PDHG algorithm also works on more general image reconstruction problems with total variation regularizations, and analyze the condition on the step sizes that guarantees the convergence.

Keywords:

Mathematics Subject Classification: Primary: 65K15, 49K35; Secondary: 90C25.

Citation:

Related Papers

Cited by

References

[1]	C. Ballester, M. Bertalmio, V. Caselles, G. Sapiro and J. Verdera, Filling-in by joint interpolation of vector fields and gray levels, Image Processing, IEEE Transactions on, 10 (2001), 1200-1211.doi: 10.1109/83.935036.
[2]	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.
[3]	M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting, In "SIGGRAPH," page 417-424, (2000).doi: 10.1145/344779.344972.
[4]	M. Bertalmio, L. Vese, G. Sapiro and S. Osher, Simultaneous structure and texture image inpainting, IEEE Trans. Image Process., 12 (2003), 882-889.
[5]	D. Bertsekas, "Parallel and Distributed Computation," Prentice Hall, 1989.
[6]	M. Burger, L. He and C.-B. Schönlieb, Cahn-Hilliard inpainting and a generalization for grayvalue images, SIAM J. Imag. Sci., 2 (2009), 1129-1167.doi: 10.1137/080728548.
[7]	J.-F. Cai, R. 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, H. Ji, F. Shang and Z. Shen, Inpainting for compressed images, Appl. Comput. Harmon. Anal., 29 (2010), 368-381.doi: 10.1016/j.acha.2010.01.005.
[9]	A. Chambolle, An algorithm for total variation minimization and applications, Special issue on mathematics and image analysis. J. Math. Imaging Vis., 20 (2004), 89-97.doi: 10.1023/B:JMIV.0000011321.19549.88.
[10]	A. Chambolle, V. Caselles, M. Novaga, D. Cremers and T. Pock, "An Introduction to Total Variation for Image Analysis," Technical Report, 2009.
[11]	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.
[12]	R. Chan, Y. Wen and A. Yip, A fast optimization transfer algorithm for image inpainting in wavelet domains, IEEE Trans. Image Process., 18 (2009), 1467-1476.doi: 10.1109/TIP.2009.2019806.
[13]	R. Chan, Y. Wen and A. Yip, A primal-dual method for total variation-based wavelet domain inpainting, IEEE Trans. Image Process, 21 (2012), 106-114.doi: 10.1109/TIP.2011.2159983.
[14]	R. H. Chan, J. Yang and X. Yuan, Alternating direction method for image inpainting in wavelet domains, SIAM J. Imag. Sci., 4 (2012), 807-826.doi: 10.1137/100807247.
[15]	T. Chan, S. Kang and J. Shen, Euler's elastica and curvature-based inpainting, SIAM J. Appl. Math., 63 (2002), 564-592.doi: 10.1137/S0036139901390088.
[16]	T. Chan, S. Osher and J. Shen, The digital TV filter and nonlinear denoising, IEEE Trans. Image Process., 10 (2001), 231-241.doi: 10.1109/83.902288.
[17]	T. Chan and J. Shen, Mathematical models for local nontexture inpaintings, SIAM J. Appl. Math., 62 (2002), 1019-1043.doi: 10.1137/S0036139900368844.
[18]	T. Chan, J. Shen and H. Zhou, Total variation wavelet inpainting, J. Math. Imaging Vis., 25 (2006), 107-125.doi: 10.1007/s10851-006-5257-3.
[19]	T. F. Chan, G. H. Golub and P. Mulet, A nonlinear primal-dual method for total variationbased image restoration, SIAM J. Optim., 20 (1999), 1964-1977.doi: 10.1137/S1064827596299767.
[20]	Y. Chen, W. W. Hager, F. Huang, D. T. Phan, X. Ye and W. Yin, Fast algorithms for image reconstruction with application to partially parallel MR imaging, SIAM J. Imag. Sci., 5 (2012), 90-118.doi: 10.1137/100792688.
[21]	J. Eckstein and D. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318.doi: 10.1007/BF01581204.
[22]	A. Efros and T. Leung, Texture synthesis by non-parametric sampling, In "Computer Vision, 1999. The Proceedings of the Seventh IEEE International Conference on," 2 (1999), 1033-1038.doi: 10.1109/ICCV.1999.790383.
[23]	S. Esedoglu and J. Shen, Digital inpainting based on the Mumford-Shah-Euler image model, European J. Appl. Math., 13 (2002), 353-370.doi: 10.1017/S0956792502004904.
[24]	E. Esser, X. Zhang and T. Chan, A general framework for a class of first order primal-dual algorithms for tv minimization, SIAM J. Imag. Sci., 3 (2010), 1015-1046.doi: 10.1137/09076934X.
[25]	D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appl., 2 (1976), 17-40.doi: 10.1016/0898-1221(76)90003-1.
[26]	R. Glowinski and A. Marrocco, Sur l'approximation par éléments finis d'ordre un, et la résolution par pénalisation-dualité d'une classe de problèmes de dirichlet nonlinéaires, RAIRO Analyse Numérique, 9 (1975), 41-76.
[27]	T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems, SIAM J. Imag. Sci., 2 (2009), 323-343.doi: 10.1137/080725891.
[28]	B. He and X. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imag. Sci., 5 (2011), 119-149.doi: 10.1137/100814494.
[29]	B. Martinet, Régularisation d'inéquations variationnelles par approximations successives, Rev. Francaise Inform. Rech. Oper. Ser. R-3, 4 (1970), 154-158.
[30]	S. Masnou and J.-M. Morel, Level lines based discocclusion, In "Proc. of Intl. Conf. Imag. Proc.," (1998).doi: 10.1109/ICIP.1998.999016.
[31]	S. Osher, M. Burger, D. Goldfarb, J. Xu and W. Yin, An iterative regularization method for total variation-based image restoration, Multiscale Model. Simul., 4 (2005), 460-489.doi: 10.1137/040605412.
[32]	R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control, 14 (1976), 877-898.doi: 10.1137/0314056.
[33]	L. Rudin, S. Osher and E. Fatemi, Non-linear total variation noise removal algorithm, Physics D., 60 (1992), 259-268.
[34]	C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising, SIAM J. Sci. Comput., 17 (1996), 227-238.doi: 10.1137/0917016.
[35]	Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction, SIAM J. Imag. Sci., 1 (2008), 248-272.doi: 10.1137/080724265.
[36]	C. Wu and X.-C. Tai, Augmented Lagrangian method, dual methods, and split Bregman iteration for ROF, vectorial TV, and high order models, SIAM J. Imag. Sci., 3 (2010), 300-339.doi: 10.1137/090767558.
[37]	J. Yang, Y. Zhang and W. Yin, A fast TVL1-L2 minimization algorithm for signal reconstruction from partial Fourier data, IEEE Journal of Selected Topics in Signal Processing, Special Issue on Compressed Sensing, 4 (2010), 288-297.
[38]	X. Ye, Y. Chen and F. Huang, Computational acceleration for MR image reconstruction in partially parallel imaging, IEEE Trans. Med. Imag., 30 (2011), 1055-1063.
[39]	X. Ye, Y. Chen, W. Lin and F. Huang, Fast MR image reconstruction for partially parallel imaging with arbitrary k-space trajectories, IEEE Trans. Med. Imag., 30 (2011), 575-585.
[40]	X. Zhang, M. Burger, X. Bresson and S. Osher, Bregmanized nonlocal regularization for deconvolution and sparse reconstruction, SIAM J. Imag. Sci., 3 (2010), 253-276.doi: 10.1137/090746379.
[41]	X. Zhang, M. Burger and S. Osher, A unified primal-dual algorithm framework based on bregman iteration, J. Sci. Comput., 46 (2011), 20-46.doi: 10.1007/s10915-010-9408-8.
[42]	X. Zhang and T. Chan, Wavelet inpainting by nonlocal total variation, Inverse Probl. Imag., 4 (2010), 191-210.doi: 10.3934/ipi.2010.4.191.
[43]	M. Zhu and T. Chan, "An Efficient Primal-Dual Hybrid Gradient Algorithm for Total Variation Image Restoration," Technical Report 08-34, CAM UCLA, 2008.