Alternating algorithms for total variation image reconstructionfrom random projections

Yunhai Xiao; Junfeng Yang; Xiaoming Yuan

doi:10.3934/ipi.2012.6.547

Article Contents

2012, Volume 6, Issue 3: 547-563. Doi: 10.3934/ipi.2012.6.547

This issue Previous Article Non rigid geometric distortions correction - Application to atmospheric turbulence stabilization Next Article

Alternating algorithms for total variation image reconstruction from random projections

1.
Institute of Applied Mathematics, Henan University, Kaifeng 475004
2.
Department of Mathematics, Nanjing University, Nanjing, 210093
3.
Department of Mathematics, Hong Kong Baptist University, Hong Kong

Received: January 31, 2011

Revised: December 31, 2011

Published: July 2012

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 94A08; Secondary: 90C30.

Citation:

Related Papers

Cited by

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.