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.

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

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

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

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

[6]

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

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

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

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

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

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

[12]

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

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

[14]

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

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

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

[17]

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

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

[19]

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

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

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

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

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

[24]

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

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

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

[27]

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

[28]

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

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

[30]

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

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

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

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

[34]

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

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

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

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

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

[39]

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

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

[41]

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

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.

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

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

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

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

[6]

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

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

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

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

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

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

[12]

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

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

[14]

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

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

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

[17]

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

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

[19]

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

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

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

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

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

[24]

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

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

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

[27]

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

[28]

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

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

[30]

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

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

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

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

[34]

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

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

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

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

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

[39]

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

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

[41]

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

[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

2017 Impact Factor: 1.465

Metrics

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

Other articles
by authors

[Back to Top]