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 and 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-1229. 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-2356. 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-695. 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-148. 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-2434. 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-202.

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

[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-509. 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-188. 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-145. 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, CAM, UCLA, 2004.

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

[14]

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

[15]

D. C. Dobson and F. Santosa, Recovery of blocky images from noisy and blurred data, SIAM J. Appl. Math., 56 (1996), 1181-1198. 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-1306. 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, March 2008.

[19]

E. Esser, "Applications of Lagrangian-Based Alternatingdirection Methods and Connections to Split Bregman," TR09-31, CAM, UCLA, Los Angeles, CA, 2009.

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

[21]

M. A. T. Figueiredo and R. Nowak, An EM algorithm for wavelet-basedimage restoration, IEEE Trans. Image Process, 12 (2003), 906-916. 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-40.

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

[24]

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

[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-1130. 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-118. doi: 10.1007/s101070100280.

[27]

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

[28]

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

[29]

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

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems, in "Optimization" (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.

[31]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Phys. D, 60 (1992), 259-268. 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, Lecture Notes in Computer Science, 2009.

[33]

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

[34]

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

[35]

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.

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

[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-272. 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-592. 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-278.

[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-2865. doi: 10.1137/080732894.

[41]

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

show all references

References:
[1]

R. Acar and C. R. Vogel, Analysis of total variation penalty methods, Inverse Prob., 10 (1994), 1217-1229. 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-2356. 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-695. 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-148. 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-2434. 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-202.

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

[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-509. 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-188. 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-145. 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, CAM, UCLA, 2004.

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

[14]

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

[15]

D. C. Dobson and F. Santosa, Recovery of blocky images from noisy and blurred data, SIAM J. Appl. Math., 56 (1996), 1181-1198. 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-1306. 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, March 2008.

[19]

E. Esser, "Applications of Lagrangian-Based Alternatingdirection Methods and Connections to Split Bregman," TR09-31, CAM, UCLA, Los Angeles, CA, 2009.

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

[21]

M. A. T. Figueiredo and R. Nowak, An EM algorithm for wavelet-basedimage restoration, IEEE Trans. Image Process, 12 (2003), 906-916. 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-40.

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

[24]

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

[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-1130. 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-118. doi: 10.1007/s101070100280.

[27]

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

[28]

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

[29]

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

[30]

M. J. D. Powell, A method for nonlinear constraints in minimization problems, in "Optimization" (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.

[31]

L. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithm, Phys. D, 60 (1992), 259-268. 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, Lecture Notes in Computer Science, 2009.

[33]

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

[34]

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

[35]

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.

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

[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-272. 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-592. 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-278.

[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-2865. doi: 10.1137/080732894.

[41]

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

[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 and 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 and Management Optimization, 2020, 16 (4) : 1783-1799. 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 and 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 and 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 and 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 and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[7]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030

[8]

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

[9]

Mujibur Rahman Chowdhury, Jun Zhang, Jing Qin, Yifei Lou. Poisson image denoising based on fractional-order total variation. Inverse Problems and Imaging, 2020, 14 (1) : 77-96. doi: 10.3934/ipi.2019064

[10]

Haijuan Hu, Jacques Froment, Baoyan Wang, Xiequan Fan. Spatial-Frequency domain nonlocal total variation for image denoising. Inverse Problems and Imaging, 2020, 14 (6) : 1157-1184. doi: 10.3934/ipi.2020059

[11]

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

[12]

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

[13]

Sudeb Majee, Subit K. Jain, Rajendra K. Ray, Ananta K. Majee. A fuzzy edge detector driven telegraph total variation model for image despeckling. Inverse Problems and Imaging, 2022, 16 (2) : 367-396. doi: 10.3934/ipi.2021054

[14]

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

[15]

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

[16]

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

[17]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016

[18]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047

[19]

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

[20]

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

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (187)
  • HTML views (0)
  • Cited by (22)

Other articles
by authors

[Back to Top]