August  2013, 7(3): 1031-1050. doi: 10.3934/ipi.2013.7.1031

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

1. 

School of Mathematics, Georgia Institute of Technology, Atlanta, GA 30308, United States

Received  May 2012 Revised  November 2012 Published  September 2013

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.
Citation: Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031
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, 10 (2001), 1200. 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. doi: 10.1093/imanum/8.1.141.

[3]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting,, In, (2000), 417. 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.

[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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1109/83.902288.

[17]

T. Chan and J. Shen, Mathematical models for local nontexture inpaintings,, SIAM J. Appl. Math., 62 (2002), 1019. doi: 10.1137/S0036139900368844.

[18]

T. Chan, J. Shen and H. Zhou, Total variation wavelet inpainting,, J. Math. Imaging Vis., 25 (2006), 107. 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. 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. 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. doi: 10.1007/BF01581204.

[22]

A. Efros and T. Leung, Texture synthesis by non-parametric sampling,, In, 2 (1999), 1033. 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. 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. 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. 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.

[27]

T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems,, SIAM J. Imag. Sci., 2 (2009), 323. 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. 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.

[30]

S. Masnou and J.-M. Morel, Level lines based discocclusion,, In, (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. doi: 10.1137/040605412.

[32]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM J. Control, 14 (1976), 877. doi: 10.1137/0314056.

[33]

L. Rudin, S. Osher and E. Fatemi, Non-linear total variation noise removal algorithm,, Physics D., 60 (1992), 259.

[34]

C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising,, SIAM J. Sci. Comput., 17 (1996), 227. 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. 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. 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, 4 (2010), 288.

[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.

[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.

[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. 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. 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. 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, (2008), 08.

show all references

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, 10 (2001), 1200. 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. doi: 10.1093/imanum/8.1.141.

[3]

M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester, Image inpainting,, In, (2000), 417. 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.

[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. 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. 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. 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. 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. 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. 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. 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. 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. 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. doi: 10.1109/83.902288.

[17]

T. Chan and J. Shen, Mathematical models for local nontexture inpaintings,, SIAM J. Appl. Math., 62 (2002), 1019. doi: 10.1137/S0036139900368844.

[18]

T. Chan, J. Shen and H. Zhou, Total variation wavelet inpainting,, J. Math. Imaging Vis., 25 (2006), 107. 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. 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. 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. doi: 10.1007/BF01581204.

[22]

A. Efros and T. Leung, Texture synthesis by non-parametric sampling,, In, 2 (1999), 1033. 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. 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. 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. 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.

[27]

T. Goldstein and S. Osher, The split Bregman method for L1 regularized problems,, SIAM J. Imag. Sci., 2 (2009), 323. 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. 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.

[30]

S. Masnou and J.-M. Morel, Level lines based discocclusion,, In, (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. doi: 10.1137/040605412.

[32]

R. T. Rockafellar, Monotone operators and the proximal point algorithm,, SIAM J. Control, 14 (1976), 877. doi: 10.1137/0314056.

[33]

L. Rudin, S. Osher and E. Fatemi, Non-linear total variation noise removal algorithm,, Physics D., 60 (1992), 259.

[34]

C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising,, SIAM J. Sci. Comput., 17 (1996), 227. 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. 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. 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, 4 (2010), 288.

[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.

[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.

[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. 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. 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. 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, (2008), 08.

[1]

Xiaoqun Zhang, Tony F. Chan. Wavelet inpainting by nonlocal total variation. Inverse Problems & Imaging, 2010, 4 (1) : 191-210. doi: 10.3934/ipi.2010.4.191

[2]

Yuyuan Ouyang, Yunmei Chen, Ying Wu. Total variation and wavelet regularization of orientation distribution functions in diffusion MRI. Inverse Problems & Imaging, 2013, 7 (2) : 565-583. doi: 10.3934/ipi.2013.7.565

[3]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[4]

Xavier Bresson, Tony F. Chan. Fast dual minimization of the vectorial total variation norm and applications to color image processing. Inverse Problems & Imaging, 2008, 2 (4) : 455-484. doi: 10.3934/ipi.2008.2.455

[5]

Nils Dabrock, Yves van Gennip. A note on "Anisotropic total variation regularized $L^1$-approximation and denoising/deblurring of 2D bar codes". Inverse Problems & Imaging, 2018, 12 (2) : 525-526. doi: 10.3934/ipi.2018022

[6]

Rustum Choksi, Yves van Gennip, Adam Oberman. Anisotropic total variation regularized $L^1$ approximation and denoising/deblurring of 2D bar codes. Inverse Problems & Imaging, 2011, 5 (3) : 591-617. doi: 10.3934/ipi.2011.5.591

[7]

Ke Chen, Yiqiu Dong, Michael Hintermüller. A nonlinear multigrid solver with line Gauss-Seidel-semismooth-Newton smoother for the Fenchel pre-dual in total variation based image restoration. Inverse Problems & Imaging, 2011, 5 (2) : 323-339. doi: 10.3934/ipi.2011.5.323

[8]

Rinaldo M. Colombo, Francesca Monti. Solutions with large total variation to nonconservative hyperbolic systems. Communications on Pure & Applied Analysis, 2010, 9 (1) : 47-60. doi: 10.3934/cpaa.2010.9.47

[9]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[10]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[11]

Yunho Kim, Paul M. Thompson, Luminita A. Vese. HARDI data denoising using vectorial total variation and logarithmic barrier. Inverse Problems & Imaging, 2010, 4 (2) : 273-310. doi: 10.3934/ipi.2010.4.273

[12]

Sören Bartels, Marijo Milicevic. Iterative finite element solution of a constrained total variation regularized model problem. Discrete & Continuous Dynamical Systems - S, 2017, 10 (6) : 1207-1232. doi: 10.3934/dcdss.2017066

[13]

Yunhai Xiao, Junfeng Yang, Xiaoming Yuan. Alternating algorithms for total variation image reconstruction from random projections. Inverse Problems & Imaging, 2012, 6 (3) : 547-563. doi: 10.3934/ipi.2012.6.547

[14]

Juan C. Moreno, V. B. Surya Prasath, João C. Neves. Color image processing by vectorial total variation with gradient channels coupling. Inverse Problems & Imaging, 2016, 10 (2) : 461-497. doi: 10.3934/ipi.2016008

[15]

Liyan Ma, Lionel Moisan, Jian Yu, Tieyong Zeng. A stable method solving the total variation dictionary model with $L^\infty$ constraints. Inverse Problems & Imaging, 2014, 8 (2) : 507-535. doi: 10.3934/ipi.2014.8.507

[16]

Lu Liu, Zhi-Feng Pang, Yuping Duan. Retinex based on exponent-type total variation scheme. Inverse Problems & Imaging, 2018, 12 (5) : 1199-1217. doi: 10.3934/ipi.2018050

[17]

Chunlin Wu, Juyong Zhang, Xue-Cheng Tai. Augmented Lagrangian method for total variation restoration with non-quadratic fidelity. Inverse Problems & Imaging, 2011, 5 (1) : 237-261. doi: 10.3934/ipi.2011.5.237

[18]

Florian Krügel. Some properties of minimizers of a variational problem involving the total variation functional. Communications on Pure & Applied Analysis, 2015, 14 (1) : 341-360. doi: 10.3934/cpaa.2015.14.341

[19]

Zhengmeng Jin, Chen Zhou, Michael K. Ng. A coupled total variation model with curvature driven for image colorization. Inverse Problems & Imaging, 2016, 10 (4) : 1037-1055. doi: 10.3934/ipi.2016031

[20]

Adriana González, Laurent Jacques, Christophe De Vleeschouwer, Philippe Antoine. Compressive optical deflectometric tomography: A constrained total-variation minimization approach. Inverse Problems & Imaging, 2014, 8 (2) : 421-457. doi: 10.3934/ipi.2014.8.421

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (5)

Other articles
by authors

[Back to Top]