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]

Inverse Prob., 10 (1994), 1217-1229. doi: 10.1088/0266-5611/10/6/003.  Google Scholar

[2]

IEEE Trans. Image Process, 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.  Google Scholar

[3]

IEEE Trans. Image Process, 20 (2011), 681-695. doi: 10.1109/TIP.2010.2076294.  Google Scholar

[4]

IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[5]

IEEE Trans. Image Process, 18 (2009), 2419-2434. doi: 10.1109/TIP.2009.2028250.  Google Scholar

[6]

SIAM J. Imaging Sci., 2 (2009), 183-202.  Google Scholar

[7]

IEEE Trans. Image Process, 16 (2007), 2992-3004. doi: 10.1109/TIP.2007.909319.  Google Scholar

[8]

USSR Computational Mathematics andMathematical Physics, 7 (1967), 200-217.  Google Scholar

[9]

IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.  Google Scholar

[10]

Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[11]

J. Math. Imaging Vis., 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[12]

TR05-01, CAM, UCLA, 2004. Google Scholar

[13]

SIAM J. Imaging Sci., 4 (2011), 807-826.  Google Scholar

[14]

Multiscale Model. Simul., 4 (2005), 1168-1200.  Google Scholar

[15]

SIAM J. Appl. Math., 56 (1996), 1181-1198. 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]

IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.  Google Scholar

[18]

IEEE Signal Processing Magazine, March 2008. Google Scholar

[19]

TR09-31, CAM, UCLA, Los Angeles, CA, 2009. Google Scholar

[20]

SIAM J. Imaging Sci., 3 (2010), 1015-1046.  Google Scholar

[21]

IEEE Trans. Image Process, 12 (2003), 906-916. doi: 10.1109/TIP.2003.814255.  Google Scholar

[22]

Comput. Math. Appl., 2 (1976), 17-40. Google Scholar

[23]

Rev. Francaise dAut. Inf. Rech. Oper., 2 (1975), 41-76.  Google Scholar

[24]

SIAM J. Imaging Sci., 2 (2009), 323-343.  Google Scholar

[25]

SIAM J. Optim, 19 (2008), 1107-1130. doi: 10.1137/070698920.  Google Scholar

[26]

Math. Program, 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[27]

J. Optim.Theory Appl., 4 (1969), 303-320.  Google Scholar

[28]

Master thesis, Rice University, 2009. Google Scholar

[29]

Contemp. Math., 313 (2002), 85-96. doi: 10.1090/conm/313/05370.  Google Scholar

[30]

in "Optimization" (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.  Google Scholar

[31]

Phys. D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[32]

Proc. 2nd International Conference on ScaleSpace Methods and Variational Methods in Computer Vision, Lecture Notes in Computer Science, 2009. Google Scholar

[33]

Signal Processing, 83 (2003), 2279-2283. doi: 10.1016/S0165-1684(03)00150-6.  Google Scholar

[34]

Winston, Washington, DC, 1977.  Google Scholar

[35]

SIAM J. Sci. Comput., 17 (1996), 227-238. doi: 10.1137/0917016.  Google Scholar

[36]

IEEE Trans. ImageProcess., 7 (1998), 813-824  Google Scholar

[37]

SIAM J. Imaging Sci., 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[38]

SIAM J. Imaging Sci., 2 (2009), 569-592. doi: 10.1137/080730421.  Google Scholar

[39]

SIAM J. Sci. Comput., 33 (2011), 250-278.  Google Scholar

[40]

SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[41]

TR08-11, CAAM, Rice University, 2008. Google Scholar

show all references

References:
[1]

Inverse Prob., 10 (1994), 1217-1229. doi: 10.1088/0266-5611/10/6/003.  Google Scholar

[2]

IEEE Trans. Image Process, 19 (2010), 2345-2356. doi: 10.1109/TIP.2010.2047910.  Google Scholar

[3]

IEEE Trans. Image Process, 20 (2011), 681-695. doi: 10.1109/TIP.2010.2076294.  Google Scholar

[4]

IMA J. Numer. Anal., 8 (1988), 141-148. doi: 10.1093/imanum/8.1.141.  Google Scholar

[5]

IEEE Trans. Image Process, 18 (2009), 2419-2434. doi: 10.1109/TIP.2009.2028250.  Google Scholar

[6]

SIAM J. Imaging Sci., 2 (2009), 183-202.  Google Scholar

[7]

IEEE Trans. Image Process, 16 (2007), 2992-3004. doi: 10.1109/TIP.2007.909319.  Google Scholar

[8]

USSR Computational Mathematics andMathematical Physics, 7 (1967), 200-217.  Google Scholar

[9]

IEEE Trans. Inform. Theory, 52 (2006), 489-509. doi: 10.1109/TIT.2005.862083.  Google Scholar

[10]

Numer. Math., 76 (1997), 167-188. doi: 10.1007/s002110050258.  Google Scholar

[11]

J. Math. Imaging Vis., 40 (2011), 120-145. doi: 10.1007/s10851-010-0251-1.  Google Scholar

[12]

TR05-01, CAM, UCLA, 2004. Google Scholar

[13]

SIAM J. Imaging Sci., 4 (2011), 807-826.  Google Scholar

[14]

Multiscale Model. Simul., 4 (2005), 1168-1200.  Google Scholar

[15]

SIAM J. Appl. Math., 56 (1996), 1181-1198. 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]

IEEE Trans. Inform. Theory, 52 (2006), 1289-1306. doi: 10.1109/TIT.2006.871582.  Google Scholar

[18]

IEEE Signal Processing Magazine, March 2008. Google Scholar

[19]

TR09-31, CAM, UCLA, Los Angeles, CA, 2009. Google Scholar

[20]

SIAM J. Imaging Sci., 3 (2010), 1015-1046.  Google Scholar

[21]

IEEE Trans. Image Process, 12 (2003), 906-916. doi: 10.1109/TIP.2003.814255.  Google Scholar

[22]

Comput. Math. Appl., 2 (1976), 17-40. Google Scholar

[23]

Rev. Francaise dAut. Inf. Rech. Oper., 2 (1975), 41-76.  Google Scholar

[24]

SIAM J. Imaging Sci., 2 (2009), 323-343.  Google Scholar

[25]

SIAM J. Optim, 19 (2008), 1107-1130. doi: 10.1137/070698920.  Google Scholar

[26]

Math. Program, 92 (2002), 103-118. doi: 10.1007/s101070100280.  Google Scholar

[27]

J. Optim.Theory Appl., 4 (1969), 303-320.  Google Scholar

[28]

Master thesis, Rice University, 2009. Google Scholar

[29]

Contemp. Math., 313 (2002), 85-96. doi: 10.1090/conm/313/05370.  Google Scholar

[30]

in "Optimization" (ed. R. Fletcher), Academic Press, New York, 1969, 283-298.  Google Scholar

[31]

Phys. D, 60 (1992), 259-268. doi: 10.1016/0167-2789(92)90242-F.  Google Scholar

[32]

Proc. 2nd International Conference on ScaleSpace Methods and Variational Methods in Computer Vision, Lecture Notes in Computer Science, 2009. Google Scholar

[33]

Signal Processing, 83 (2003), 2279-2283. doi: 10.1016/S0165-1684(03)00150-6.  Google Scholar

[34]

Winston, Washington, DC, 1977.  Google Scholar

[35]

SIAM J. Sci. Comput., 17 (1996), 227-238. doi: 10.1137/0917016.  Google Scholar

[36]

IEEE Trans. ImageProcess., 7 (1998), 813-824  Google Scholar

[37]

SIAM J. Imaging Sci., 1 (2008), 248-272. doi: 10.1137/080724265.  Google Scholar

[38]

SIAM J. Imaging Sci., 2 (2009), 569-592. doi: 10.1137/080730421.  Google Scholar

[39]

SIAM J. Sci. Comput., 33 (2011), 250-278.  Google Scholar

[40]

SIAM J. Sci. Comput., 31 (2009), 2842-2865. doi: 10.1137/080732894.  Google Scholar

[41]

TR08-11, CAAM, Rice University, 2008. Google Scholar

[1]

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 & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030

[2]

Xianchao Xiu, Ying Yang, Wanquan Liu, Lingchen Kong, Meijuan Shang. An improved total variation regularized RPCA for moving object detection with dynamic background. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1685-1698. doi: 10.3934/jimo.2019024

[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017

[4]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018

[5]

Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196

[6]

Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184

[7]

Andreas Neubauer. On Tikhonov-type regularization with approximated penalty terms. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021027

[8]

Habib Ammari, Josselin Garnier, Vincent Jugnon. Detection, reconstruction, and characterization algorithms from noisy data in multistatic wave imaging. Discrete & Continuous Dynamical Systems - S, 2015, 8 (3) : 389-417. doi: 10.3934/dcdss.2015.8.389

[9]

Lekbir Afraites, Abdelghafour Atlas, Fahd Karami, Driss Meskine. Some class of parabolic systems applied to image processing. Discrete & Continuous Dynamical Systems - B, 2016, 21 (6) : 1671-1687. doi: 10.3934/dcdsb.2016017

[10]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2543-2557. doi: 10.3934/dcds.2020374

[11]

Scott Schmieding, Rodrigo Treviño. Random substitution tilings and deviation phenomena. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3869-3902. doi: 10.3934/dcds.2021020

[12]

Zhihua Zhang, Naoki Saito. PHLST with adaptive tiling and its application to antarctic remote sensing image approximation. Inverse Problems & Imaging, 2014, 8 (1) : 321-337. doi: 10.3934/ipi.2014.8.321

[13]

Israa Mohammed Khudher, Yahya Ismail Ibrahim, Suhaib Abduljabbar Altamir. Individual biometrics pattern based artificial image analysis techniques. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2020056

[14]

Linyao Ge, Baoxiang Huang, Weibo Wei, Zhenkuan Pan. Semi-Supervised classification of hyperspectral images using discrete nonlocal variation Potts Model. Mathematical Foundations of Computing, 2021  doi: 10.3934/mfc.2021003

[15]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[16]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045

[17]

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

[18]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141

[19]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

[20]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046

2019 Impact Factor: 1.373

Metrics

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

Other articles
by authors

[Back to Top]