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]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[2]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[3]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[4]

Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020169

[5]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[6]

Shiqi Ma. On recent progress of single-realization recoveries of random Schrödinger systems. Electronic Research Archive, , () : -. doi: 10.3934/era.2020121

[7]

Djamel Aaid, Amel Noui, Özen Özer. Piecewise quadratic bounding functions for finding real roots of polynomials. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 63-73. doi: 10.3934/naco.2020015

[8]

Yangrong Li, Shuang Yang, Qiangheng Zhang. Odd random attractors for stochastic non-autonomous Kuramoto-Sivashinsky equations without dissipation. Electronic Research Archive, 2020, 28 (4) : 1529-1544. doi: 10.3934/era.2020080

[9]

Yongge Tian, Pengyang Xie. Simultaneous optimal predictions under two seemingly unrelated linear random-effects models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020168

[10]

Jia Cai, Guanglong Xu, Zhensheng Hu. Sketch-based image retrieval via CAT loss with elastic net regularization. Mathematical Foundations of Computing, 2020, 3 (4) : 219-227. doi: 10.3934/mfc.2020013

[11]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[12]

Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076

[13]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[14]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[15]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[16]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[17]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[18]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[19]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 1.373

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (18)

Other articles
by authors

[Back to Top]