August  2012, 6(3): 547-563. doi: 10.3934/ipi.2012.6.547

Alternating algorithms for total variation image reconstruction from random projections

1. 

Institute of Applied Mathematics, Henan University, Kaifeng 475004, China

2. 

Department of Mathematics, Nanjing University, Nanjing, 210093

3. 

Department of Mathematics, Hong Kong Baptist University, Hong Kong, China

Received  February 2011 Revised  January 2012 Published  September 2012

Total variation (TV) regularization is popular in image reconstruction due to its edge-preserving property. In this paper, we extend the alternating minimization algorithm recently proposed in [37] to the case of recovering images from random projections. Specifically, we propose to solve the TV regularized least squares problem by alternating minimization algorithms based on the classical quadratic penalty technique and alternating minimization of the augmented Lagrangian function. The per-iteration cost of the proposed algorithms is dominated by two matrix-vector multiplications and two fast Fourier transforms. Convergence results, including finite convergence of certain variables and $q$-linear convergence rate, are established for the quadratic penalty method. Furthermore, we compare numerically the new algorithms with some state-of-the-art algorithms. Our experimental results indicate that the new algorithms are stable, efficient and competitive with the compared ones.
Citation: 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
References:
[1]

R. Acar and C. R. Vogel, Analysis of total variation penalty methods,, Inverse Prob., 10 (1994), 1217. doi: 10.1088/0266-5611/10/6/003. Google Scholar

[2]

M. V. Afonso, J. Bioucas-Dias and M. A. T. Figueiredo, Fastimage recovery using variable splitting and constrained optimization,, IEEE Trans. Image Process, 19 (2010), 2345. doi: 10.1109/TIP.2010.2047910. Google Scholar

[3]

M. V. Afonso, J. Bioucas-Dias and M. A. T. Figueiredo, A fast algorithm for the constrained formulation of compressive image reconstruction and other linear inverse problems,, IEEE Trans. Image Process, 20 (2011), 681. doi: 10.1109/TIP.2010.2076294. Google Scholar

[4]

J. Barzilai and J. M. Borwein, Two point step size gradient method,, IMA J. Numer. Anal., 8 (1988), 141. doi: 10.1093/imanum/8.1.141. Google Scholar

[5]

A. Beck and M. Teboulle, Fastgradient-based algorithms for constrained total variation image denoising and deblurring problmes,, IEEE Trans. Image Process, 18 (2009), 2419. doi: 10.1109/TIP.2009.2028250. Google Scholar

[6]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM J. Imaging Sci., 2 (2009), 183. Google Scholar

[7]

J. Bioucas-Dias and M. Figueiredo, A new TwIST: Two-step iterative thresholding algorithm for image restoration,, IEEE Trans. Image Process, 16 (2007), 2992. doi: 10.1109/TIP.2007.909319. Google Scholar

[8]

L. Bregman, The relaxation method of finding the common pointsof convex sets and its application to the solution of problems inconvex optimization,, USSR Computational Mathematics andMathematical Physics, 7 (1967), 200. Google Scholar

[9]

E. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequence information,, IEEE Trans. Inform. Theory, 52 (2006), 489. doi: 10.1109/TIT.2005.862083. Google Scholar

[10]

A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. Google Scholar

[11]

A. Chambolle and T. Pock, A first-order primal-dualalgorithm for convex problems with applications to imaging,, J. Math. Imaging Vis., 40 (2011), 120. doi: 10.1007/s10851-010-0251-1. Google Scholar

[12]

T. F. Chan, S. Esedoglu, F. Park and A. Yip, "Recent Developments in Total Variation Image Restoration,", TR05-01, (2004), 05. Google Scholar

[13]

R. H. Chan, J. Yang and X. Yuan, Alternating direction method for image inpainting in wavelet domain,, SIAM J. Imaging Sci., 4 (2011), 807. Google Scholar

[14]

P. L. Combettes and V. Wajs, Signal recoverty by proximal forward-backward splitting,, Multiscale Model. Simul., 4 (2005), 1168. Google Scholar

[15]

D. C. Dobson and F. Santosa, Recovery of blocky images from noisy and blurred data,, SIAM J. Appl. Math., 56 (1996), 1181. doi: 10.1137/S003613999427560X. Google Scholar

[16]

B. Dong, J. Li and Z. Shen, X-ray CTimage reconstruction via wavelet frame based regularization and Radon domain inpainting,, J. Sci. Comput.., (). doi: 10.1007/s10915-012-9579-6. Google Scholar

[17]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar

[18]

M. F. Duarte, M. A. Davenport, D. Takhar, J. N. Laska, T. Sun, K. F. Kelly and R. G. Baraniuk, Single Pixel Imaging via compressive sampling,, IEEE Signal Processing Magazine, (2008). Google Scholar

[19]

E. Esser, "Applications of Lagrangian-Based Alternatingdirection Methods and Connections to Split Bregman,", TR09-31, (2009), 09. Google Scholar

[20]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science,, SIAM J. Imaging Sci., 3 (2010), 1015. Google Scholar

[21]

M. A. T. Figueiredo and R. Nowak, An EM algorithm for wavelet-basedimage restoration,, IEEE Trans. Image Process, 12 (2003), 906. doi: 10.1109/TIP.2003.814255. Google Scholar

[22]

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. Google Scholar

[23]

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., 2 (1975), 41. Google Scholar

[24]

T. Goldstein and S. Osher, The split Bregman method for$L_1$-Regularized Prolbems,, SIAM J. Imaging Sci., 2 (2009), 323. Google Scholar

[25]

E. T. Hale, W. Yin and Y. Zhang, A fixed-point continuation method for l1-regularized minimization with applications to compressed sensing,, SIAM J. Optim, 19 (2008), 1107. doi: 10.1137/070698920. Google Scholar

[26]

B. He, L. Z. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities,, Math. Program, 92 (2002), 103. doi: 10.1007/s101070100280. Google Scholar

[27]

M. R. Hestenes, Multiplier and gradient methods,, J. Optim.Theory Appl., 4 (1969), 303. Google Scholar

[28]

C. Li, "An Efficient Algorithm for Total Variation Regularization with Applications to the Single Pixelcamera and Compressive Sensing,", Master thesis, (2009). Google Scholar

[29]

M. Defrise and C. De Mol, A note on wavelet-based inversion algorithms,, Contemp. Math., 313 (2002), 85. doi: 10.1090/conm/313/05370. Google Scholar

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in, (1969), 283. Google Scholar

[31]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm,, Phys. D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[32]

S. Setzer, "Split Bregman Algorithm, Douglas-Rachford Splittingand Frame Shrinkage,", Proc. 2nd International Conference on ScaleSpace Methods and Variational Methods in Computer Vision, (2009). Google Scholar

[33]

J. L. Starck, M. Nguyen and F. Murtagh, Wavelets and curvelets forimage deconvolution: A combined approach,, Signal Processing, 83 (2003), 2279. doi: 10.1016/S0165-1684(03)00150-6. Google Scholar

[34]

A. Tikhonov and V. Arsenin, "Solution of Ill-Posed Problems,", Winston, (1977). Google Scholar

[35]

C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising,, SIAM J. Sci. Comput., 17 (1996), 227. doi: 10.1137/0917016. Google Scholar

[36]

C. R. Vogel and M. E. Oman, A fast, robust total variation based reconstruction of noisy, blurred images,, IEEE Trans. ImageProcess., 7 (1998), 813. Google Scholar

[37]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction,, SIAM J. Imaging Sci., 1 (2008), 248. doi: 10.1137/080724265. Google Scholar

[38]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A fast algorithm for edge-preserving variational multichannel image restoration,, SIAM J. Imaging Sci., 2 (2009), 569. doi: 10.1137/080730421. Google Scholar

[39]

J. Yang, and Y. Zhang, Alternating direction algorithms forL1-problems in compressive sensing,, SIAM J. Sci. Comput., 33 (2011), 250. Google Scholar

[40]

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. doi: 10.1137/080732894. Google Scholar

[41]

Y. Zhang, "Theory of Compressive Sensing Via$l_1$-Minimization: A Non-RIP Analysis and Extensions,", TR08-11, (2008), 08. Google Scholar

show all references

References:
[1]

R. Acar and C. R. Vogel, Analysis of total variation penalty methods,, Inverse Prob., 10 (1994), 1217. doi: 10.1088/0266-5611/10/6/003. Google Scholar

[2]

M. V. Afonso, J. Bioucas-Dias and M. A. T. Figueiredo, Fastimage recovery using variable splitting and constrained optimization,, IEEE Trans. Image Process, 19 (2010), 2345. doi: 10.1109/TIP.2010.2047910. Google Scholar

[3]

M. V. Afonso, J. Bioucas-Dias and M. A. T. Figueiredo, A fast algorithm for the constrained formulation of compressive image reconstruction and other linear inverse problems,, IEEE Trans. Image Process, 20 (2011), 681. doi: 10.1109/TIP.2010.2076294. Google Scholar

[4]

J. Barzilai and J. M. Borwein, Two point step size gradient method,, IMA J. Numer. Anal., 8 (1988), 141. doi: 10.1093/imanum/8.1.141. Google Scholar

[5]

A. Beck and M. Teboulle, Fastgradient-based algorithms for constrained total variation image denoising and deblurring problmes,, IEEE Trans. Image Process, 18 (2009), 2419. doi: 10.1109/TIP.2009.2028250. Google Scholar

[6]

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems,, SIAM J. Imaging Sci., 2 (2009), 183. Google Scholar

[7]

J. Bioucas-Dias and M. Figueiredo, A new TwIST: Two-step iterative thresholding algorithm for image restoration,, IEEE Trans. Image Process, 16 (2007), 2992. doi: 10.1109/TIP.2007.909319. Google Scholar

[8]

L. Bregman, The relaxation method of finding the common pointsof convex sets and its application to the solution of problems inconvex optimization,, USSR Computational Mathematics andMathematical Physics, 7 (1967), 200. Google Scholar

[9]

E. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequence information,, IEEE Trans. Inform. Theory, 52 (2006), 489. doi: 10.1109/TIT.2005.862083. Google Scholar

[10]

A. Chambolle and P. L. Lions, Image recovery via total variation minimization and related problems,, Numer. Math., 76 (1997), 167. doi: 10.1007/s002110050258. Google Scholar

[11]

A. Chambolle and T. Pock, A first-order primal-dualalgorithm for convex problems with applications to imaging,, J. Math. Imaging Vis., 40 (2011), 120. doi: 10.1007/s10851-010-0251-1. Google Scholar

[12]

T. F. Chan, S. Esedoglu, F. Park and A. Yip, "Recent Developments in Total Variation Image Restoration,", TR05-01, (2004), 05. Google Scholar

[13]

R. H. Chan, J. Yang and X. Yuan, Alternating direction method for image inpainting in wavelet domain,, SIAM J. Imaging Sci., 4 (2011), 807. Google Scholar

[14]

P. L. Combettes and V. Wajs, Signal recoverty by proximal forward-backward splitting,, Multiscale Model. Simul., 4 (2005), 1168. Google Scholar

[15]

D. C. Dobson and F. Santosa, Recovery of blocky images from noisy and blurred data,, SIAM J. Appl. Math., 56 (1996), 1181. doi: 10.1137/S003613999427560X. Google Scholar

[16]

B. Dong, J. Li and Z. Shen, X-ray CTimage reconstruction via wavelet frame based regularization and Radon domain inpainting,, J. Sci. Comput.., (). doi: 10.1007/s10915-012-9579-6. Google Scholar

[17]

D. Donoho, Compressed sensing,, IEEE Trans. Inform. Theory, 52 (2006), 1289. doi: 10.1109/TIT.2006.871582. Google Scholar

[18]

M. F. Duarte, M. A. Davenport, D. Takhar, J. N. Laska, T. Sun, K. F. Kelly and R. G. Baraniuk, Single Pixel Imaging via compressive sampling,, IEEE Signal Processing Magazine, (2008). Google Scholar

[19]

E. Esser, "Applications of Lagrangian-Based Alternatingdirection Methods and Connections to Split Bregman,", TR09-31, (2009), 09. Google Scholar

[20]

E. Esser, X. Zhang and T. F. Chan, A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science,, SIAM J. Imaging Sci., 3 (2010), 1015. Google Scholar

[21]

M. A. T. Figueiredo and R. Nowak, An EM algorithm for wavelet-basedimage restoration,, IEEE Trans. Image Process, 12 (2003), 906. doi: 10.1109/TIP.2003.814255. Google Scholar

[22]

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. Google Scholar

[23]

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., 2 (1975), 41. Google Scholar

[24]

T. Goldstein and S. Osher, The split Bregman method for$L_1$-Regularized Prolbems,, SIAM J. Imaging Sci., 2 (2009), 323. Google Scholar

[25]

E. T. Hale, W. Yin and Y. Zhang, A fixed-point continuation method for l1-regularized minimization with applications to compressed sensing,, SIAM J. Optim, 19 (2008), 1107. doi: 10.1137/070698920. Google Scholar

[26]

B. He, L. Z. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities,, Math. Program, 92 (2002), 103. doi: 10.1007/s101070100280. Google Scholar

[27]

M. R. Hestenes, Multiplier and gradient methods,, J. Optim.Theory Appl., 4 (1969), 303. Google Scholar

[28]

C. Li, "An Efficient Algorithm for Total Variation Regularization with Applications to the Single Pixelcamera and Compressive Sensing,", Master thesis, (2009). Google Scholar

[29]

M. Defrise and C. De Mol, A note on wavelet-based inversion algorithms,, Contemp. Math., 313 (2002), 85. doi: 10.1090/conm/313/05370. Google Scholar

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems,, in, (1969), 283. Google Scholar

[31]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm,, Phys. D, 60 (1992), 259. doi: 10.1016/0167-2789(92)90242-F. Google Scholar

[32]

S. Setzer, "Split Bregman Algorithm, Douglas-Rachford Splittingand Frame Shrinkage,", Proc. 2nd International Conference on ScaleSpace Methods and Variational Methods in Computer Vision, (2009). Google Scholar

[33]

J. L. Starck, M. Nguyen and F. Murtagh, Wavelets and curvelets forimage deconvolution: A combined approach,, Signal Processing, 83 (2003), 2279. doi: 10.1016/S0165-1684(03)00150-6. Google Scholar

[34]

A. Tikhonov and V. Arsenin, "Solution of Ill-Posed Problems,", Winston, (1977). Google Scholar

[35]

C. R. Vogel and M. E. Oman, Iterative methods for total variation denoising,, SIAM J. Sci. Comput., 17 (1996), 227. doi: 10.1137/0917016. Google Scholar

[36]

C. R. Vogel and M. E. Oman, A fast, robust total variation based reconstruction of noisy, blurred images,, IEEE Trans. ImageProcess., 7 (1998), 813. Google Scholar

[37]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A new alternating minimization algorithm for total variation image reconstruction,, SIAM J. Imaging Sci., 1 (2008), 248. doi: 10.1137/080724265. Google Scholar

[38]

Y. Wang, J. Yang, W. Yin and Y. Zhang, A fast algorithm for edge-preserving variational multichannel image restoration,, SIAM J. Imaging Sci., 2 (2009), 569. doi: 10.1137/080730421. Google Scholar

[39]

J. Yang, and Y. Zhang, Alternating direction algorithms forL1-problems in compressive sensing,, SIAM J. Sci. Comput., 33 (2011), 250. Google Scholar

[40]

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. doi: 10.1137/080732894. Google Scholar

[41]

Y. Zhang, "Theory of Compressive Sensing Via$l_1$-Minimization: A Non-RIP Analysis and Extensions,", TR08-11, (2008), 08. Google Scholar

[1]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[2]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019029

[3]

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

[4]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[5]

Yonggui Zhu, Yuying Shi, Bin Zhang, Xinyan Yu. Weighted-average alternating minimization method for magnetic resonance image reconstruction based on compressive sensing. Inverse Problems & Imaging, 2014, 8 (3) : 925-937. doi: 10.3934/ipi.2014.8.925

[6]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[7]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067

[8]

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

[9]

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

[10]

Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems & Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010

[11]

Chengxiang Wang, Li Zeng, Yumeng Guo, Lingli Zhang. Wavelet tight frame and prior image-based image reconstruction from limited-angle projection data. Inverse Problems & Imaging, 2017, 11 (6) : 917-948. doi: 10.3934/ipi.2017043

[12]

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

[13]

Johnathan M. Bardsley. An efficient computational method for total variation-penalized Poisson likelihood estimation. Inverse Problems & Imaging, 2008, 2 (2) : 167-185. doi: 10.3934/ipi.2008.2.167

[14]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[15]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[16]

Baoli Shi, Zhi-Feng Pang, Jing Xu. Image segmentation based on the hybrid total variation model and the K-means clustering strategy. Inverse Problems & Imaging, 2016, 10 (3) : 807-828. doi: 10.3934/ipi.2016022

[17]

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

[18]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[19]

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

[20]

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

2018 Impact Factor: 1.469

Metrics

  • PDF downloads (11)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]