Empirical average-case relation between undersampling and sparsity in X-ray CT

Jakob S. Jørgensen; Emil Y. Sidky; Per Christian Hansen; Xiaochuan Pan

doi:10.3934/ipi.2015.9.431

Article Contents

2015, Volume 9, Issue 2: 431-446. Doi: 10.3934/ipi.2015.9.431 open access

This issue Previous Article A new nonlocal variational setting for image processing Next Article 4D-CT reconstruction with unified spatial-temporal patch-based regularization

Empirical average-case relation between undersampling and sparsity in X-ray CT

1.
Department of Applied Mathematics and Computer Science, Technical University of Denmark, Richard Petersens Plads, Building 324, 2800 Kgs. Lyngby
2.
Department of Radiology, University of Chicago, 5841 South Maryland Avenue, Chicago, IL 60637

Received: June 30, 2014

Revised: December 31, 2014

Published: April 2015

Abstract Related Papers Cited by

Abstract

In X-ray computed tomography (CT) it is generally acknowledged that reconstruction methods exploiting image sparsity allow reconstruction from a significantly reduced number of projections. The use of such reconstruction methods is inspired by recent progress in compressed sensing (CS). However, the CS framework provides neither guarantees of accurate CT reconstruction, nor any relation between sparsity and a sufficient number of measurements for recovery, i.e., perfect reconstruction from noise-free data. We consider reconstruction through 1-norm minimization, as proposed in CS, from data obtained using a standard CT fan-beam sampling pattern. In empirical simulation studies we establish quantitatively a relation between the image sparsity and the sufficient number of measurements for recovery within image classes motivated by tomographic applications. We show empirically that the specific relation depends on the image class and in many cases exhibits a sharp phase transition as seen in CS, i.e., same-sparsity images require the same number of projections for recovery. Finally we demonstrate that the relation holds independently of image size and is robust to small amounts of additive Gaussian white noise.

Keywords:

Mathematics Subject Classification: Primary: 90C90, 15A29, 44A12; Secondary: 94A08.

Citation:

Related Papers

Cited by

References

[1]	H. H. Barrett and K. J. Myers, Foundations of Image Science, John Wiley & Sons, Hoboken, NJ, 2004.
[2]	J. Bian, J. H. Siewerdsen, X. Han, E. Y. Sidky, J. L. Prince, C. A. Pelizzari and X. Pan, Evaluation of sparse-view reconstruction from flat-panel-detector cone-beam CT, Phys. Med. Biol., 55 (2010), 6575-6599.doi: 10.1088/0031-9155/55/22/001.
[3]	E. Candès and J. Romberg, Sparsity and incoherence in compressive sampling, Inverse Probl., 23 (2007), 969-985.doi: 10.1088/0266-5611/23/3/008.
[4]	E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inf. Theory, 52 (2006), 489-509.doi: 10.1109/TIT.2005.862083.
[5]	E. J. Candès, J. K. Romberg and T. Tao, Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59 (2006), 1207-1223.doi: 10.1002/cpa.20124.
[6]	A. Cohen, W. Dahmen and R. DeVore, Compressed sensing and best k-term approximation, J. Am. Math. Soc., 22 (2009), 211-231.doi: 10.1090/S0894-0347-08-00610-3.
[7]	D. Donoho and J. Tanner, Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 367 (2009), 4273-4293.doi: 10.1098/rsta.2009.0152.
[8]	D. L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52 (2006), 1289-1306.doi: 10.1109/TIT.2006.871582.
[9]	D. L. Donoho and M. Elad, Optimally sparse representation in general (non-orthogonal) dictionaries via L1 minimization, Proc. Natl. Acad. Sci. U.S.A., 100 (2003), 2197-2202.doi: 10.1073/pnas.0437847100.
[10]	D. L. Donoho and J. Tanner, Sparse nonnegative solution of underdetermined linear equations by linear programming, Proc. Natl. Acad. Sci. U.S.A., 102 (2005), 9446-9451.doi: 10.1073/pnas.0502269102.
[11]	D. Donoho and J. Tanner, Neighborliness of randomly projected simplices in high dimensions, Proc. Natl. Acad. Sci. U.S.A., 102 (2005), 9452-9457.doi: 10.1073/pnas.0502258102.
[12]	C. Dossal, G. Peyré and J. Fadili, A numerical exploration of compressed sampling recovery, Linear Algebra Appl., 432 (2010), 1663-1679.doi: 10.1016/j.laa.2009.11.022.
[13]	L. A. Feldkamp, L. C. Davis and J. W. Kress, Practical cone-beam algorithm, J. Opt. Soc. Am. A, 1 (1984), 612-619.doi: 10.1364/JOSAA.1.000612.
[14]	S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing, Springer, New York, NY, 2013.doi: 10.1007/978-0-8176-4948-7.
[15]	E. Gouillart, F. Krzakala, M. Mézard and L. Zdeborová, Belief-propagation reconstruction for discrete tomography, Inverse Probl., 29 (2013), 035003, 22pp.doi: 10.1088/0266-5611/29/3/035003.
[16]	M. Grasmair, M. Haltmeier and O. Scherzer, Necessary and sufficient conditions for linear convergence of L1-regularization, Commun. Pure Appl. Math., 64 (2011), 161-182.doi: 10.1002/cpa.20350.
[17]	J. Hadamard, Lectures on Cauchy's Problem in Linear Partial Differential Equations, Yale University Press, New Haven, CT, 1953.doi: 10.1063/1.3061337.
[18]	X. Han, J. Bian, D. R. Eaker, T. L. Kline, E. Y. Sidky, E. L. Ritman and X. Pan, Algorithm-enabled low-dose micro-CT imaging, IEEE Trans. Med. Imaging, 30 (2011), 606-620.doi: 10.1109/TMI.2010.2089695.
[19]	P. C. Hansen and M. Saxild-Hansen, AIR Tools - A MATLAB package of algebraic iterative reconstruction methods, J. Comput. Appl. Math., 236 (2012), 2167-2178.doi: 10.1016/j.cam.2011.09.039.
[20]	P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems: Numerical aspects of linear inversion, SIAM, Philadelphia, PA, 1998.doi: 10.1137/1.9780898719697.
[21]	G. T. Herman and A. Kuba (eds.), Discrete Tomography: Foundations, Algorithms, and Applications, Springer, New York, NY, 1999.doi: 10.1007/978-1-4612-1568-4.
[22]	J. S. Jørgensen and E. Y. Sidky, How little data is enough? Phase-diagram analysis of sparsity-regularized X-ray CT, Philos. Trans. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci.,
[23]	J. S. Jørgensen, E. Y. Sidky and X. Pan, Quantifying admissible undersampling for sparsity-exploiting iterative image reconstruction in x-ray CT, IEEE Trans. Med. Imaging, 32 (2013), 460-473.doi: 10.1109/TMI.2012.2230185.
[24]	J. Jørgensen, C. Kruschel and D. Lorenz, Testable uniqueness conditions for empirical assessment of undersampling levels in total variation-regularized X-ray CT, Inverse Probl. Sci. Eng., (2014), 1-23.doi: 10.1080/17415977.2014.986724.
[25]	M. Li, H. Yang and H. Kudo, An accurate iterative reconstruction algorithm for sparse objects: application to 3D blood vessel reconstruction from a limited number of projections, Phys. Med. Biol., 47 (2002), 2599-2609.doi: 10.1088/0031-9155/47/15/303.
[26]	H. Monajemi, S. Jafarpour, M. Gavish, Stat-330-CME-362 Collaboration and D. L. Donoho, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, Proc. Natl. Acad. Sci. U.S.A., 110 (2013), 1181-1186.doi: 10.1073/pnas.1219540110.
[27]	MOSEK ApS, MOSEK Optimization Software, version 6.0.0.122, 2011. Available from: http://www.mosek.com.
[28]	F. Natterer, The Mathematics of Computerized Tomography, John Wiley & Sons, New York, NY, 1986.
[29]	D. Needell and R. Ward, Stable image reconstruction using total variation minimization, SIAM J. Imaging Sci., 6 (2013), 1035-1058.doi: 10.1137/120868281.
[30]	X. Pan, E. Y. Sidky and M. Vannier, Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction?, Inverse Probl., 25 (2009), 123009, 36pp.doi: 10.1088/0266-5611/25/12/123009.
[31]	S. Petra and C. Schnörr, Average case recovery analysis of tomographic compressive sensing, Linear Algebra Appl., 441 (2014), 168-198.doi: 10.1016/j.laa.2013.06.034.
[32]	N. Pustelnik, C. Dossal, F. Turcu, Y. Berthoumieu and P. Ricoux, A greedy algorithm to extract sparsity degree for L1/L0-equivalence in a deterministic context, in Proc. EUSIPCO, Bucharest, Romania, 2012.
[33]	I. Reiser and R. M. Nishikawa, Task-based assessment of breast tomosynthesis: Effect of acquisition parameters and quantum noise, Med. Phys., 37 (2010), 1591-1600.doi: 10.1118/1.3357288.
[34]	L. Ritschl, F. Bergner, C. Fleischmann and M. Kachelrieß, Improved total variation-based CT image reconstruction applied to clinical data, Phys. Med. Biol., 56 (2011), 1545-1561.doi: 10.1088/0031-9155/56/6/003.
[35]	L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D, 60 (1992), 259-268.doi: 10.1016/0167-2789(92)90242-F.
[36]	E. Y. Sidky, M. A. Anastasio and X. Pan, Image reconstruction exploiting object sparsity in boundary-enhanced X-ray phase-contrast tomography, Opt. Express, 18 (2010), 10404-10422.doi: 10.1364/OE.18.010404.
[37]	E. Y. Sidky, C.-M. Kao and X. Pan, Accurate image reconstruction from few-views and limited-angle data in divergent-beam CT, J. Xray Sci. Technol., 14 (2006), 119-139.
[38]	E. Y. Sidky and X. Pan, Image reconstruction in circular cone-beam computed tomography by constrained, total-variation minimization, Phys. Med. Biol., 53 (2008), 4777-4807.doi: 10.1088/0031-9155/53/17/021.
[39]	A. M. Tillmann and M. E. Pfetsch, The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing, IEEE Trans. Inf. Theory, 60 (2014), 1248-1259.doi: 10.1109/TIT.2013.2290112.
[40]	L. Yu, X. Liu, S. Leng, J. M. Kofler, J. C. Ramirez-Giraldo, M. Qu, J. Christner, J. G. Fletcher and C. H. McCollough, Radiation dose reduction in computed tomography: Techniques and future perspective, Imaging Med., 1 (2009), 65-84.doi: 10.2217/iim.09.5.