Phase Transitions and Cosparse Tomographic Recovery of Compound Solid Bodies from Few Projections

• Autorzy: Denitiu A. , Petra S. , Schnörr C. , Schnörr Ch.

Identyfikatory

DOI

10.3233/FI-2014-1113

• Języki publikacji: EN

Abstrakty

EN

We study unique recovery of cosparse signals from limited-view tomographic measurements of two- and three-dimensional domains. Admissible signals belong to the union of subspaces defined by all cosupports of maximal cardinality l with respect to the discrete gradient operator. We relate l both to the number of measurements and to a nullspace condition with respect to the measurement matrix, so as to achieve unique recovery by linear programming. These results are supported by comprehensive numerical experiments that show a high correlation of performance in practice and theoretical predictions. Despite poor properties of the measurement matrix from the viewpoint of compressed sensing, the class of uniquely recoverable signals basically seems large enough to cover practical applications, like contactless quality inspection of compound solid bodies composed of few materials.

Słowa kluczowe

EN

compressed sensing; underdetermined systems of linear equations; cosparsity; total variation; discrete and limited-view tomography

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 1/2
• Strony: 73--102
• Opis fizyczny: Bibliogr. 35 poz., rys., tab., wykr.

Twórcy

autor

Denitiu A.

• Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany

autor

Petra S.

• Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany

autor

Schnörr C.

• University of Applied Sciences, Lothstr. 64, 80335 Munich, Germany

autor

Schnörr Ch.

• Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany

Bibliografia

• [1] R. Baraniuk, Compressive Sensing, IEEE Signal Processing Magazine 24 (2007), no. 4, 118–121.
• [2] B. Bollobás and I. Leader, Edge-Isoperimetric Inequalities in the Grid, Combinatorica 11 (1991), no. 4, 299–314.
• [3] E. J. Candès, The Restricted Isometry Property and its Implications for Compressed Sensing, Comptes Rendus Mathematique 346 (2008), no. 9-10, 589–592.
• [4] S. Carmignato, Computed Tomography as a Promising Solution for Industrial Quality Control and Inspection of Castings, Metallurgical Science and Technology 30-1 (2012), 5–14.
• [5] E. J. Candès, Y. C. Eldar, and D. Deanna Needell, Compressed Sensing with Coherent and Redundant Dictionaries, Applied and Computational Harmonic Analysis 31 (2010), no. 1, 59–73.
• [6] V. Chandar, A Negative Result Concerning Explicit Matrices with the Restricted Isometry Property, 2008, Preprint http://dsp.rice.edu/files/cs/Venkat CS.pdf.
• [7] E. J. Candès, J. Romberg, and T. Tao, Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information, IEEE Transactions on Information Theory 52 (2006), no. 2, 489–509.
• [8] E. J. Candès, J. K. Romberg, and T. Tao, Stable Signal Recovery from Incomplete and Inaccurate Measurements, Communications on Pure and Applied Mathematics 59 (2006), no. 8, 1207–1223.
• [9] E. J. Candès and M.Wakin, An Introduction to Compressive Sampling, IEEE Signal Processing Magazine 25 (2008), no. 2, 21–30.
• [10] D.L. Donoho and J. Tanner, Counting Faces of Randomly Projected Polytopes when the Projection Radically Lowers Dimension, Journal of American Mathematical Society 22 (2009), 1–53.
• [11] D. L. Donoho and J. Tanner, Counting the Faces of Randomly-Projected Hypercubes and Orthants, with Applications, Discrete & Computational Geometry 43 (2010), no. 3, 522–541.
• [12] M. Elad, Sparse Representations Are Most Likely to Be the Sparsest Possible, EURASIP J. Adv. Sig. Proc. 2006 (2006), 1–12.
• [13] R.J. Gardner and P. Gritzmann, Discrete Tomography: Determination of Finite Sets by X-Rays, Transactions of the American Mathematical Society 349 (1997), no. 6, 2271–2295.
• [14] C. Grünzweig, D. Mannes, A. Kaestner, F. Schmid, V. Vontobel, J. Hovind, S. Hartmann, S. Peetermans, and E. Lehmann, Progress in Industrial Applications using Modern Neutron Imaging Techniques, Physics Procedia 43 (2013), 231–242.
• [15] B. Goris, W. Van den Broek, K.J. Batenburg, H.H. Mezerji, and S. Bals, Electron Tomography Based on a Total Variation Minimization Reconstruction Techniques, Ultramicroscopy 113 (2012), 120–130.
• [16] G. T. Herman and R. Davidi, Image Reconstruction from a Small Number of Projections, Inverse Problems 24 (2008), no. 4, 45011–45028.
• [17] G. T. Herman and A. Kuba, Discrete Tomography: Foundations, Algorithms and Applications, Birkhäuser, 1999.
• [18] S. Jafarpour, M. F. Duarte, and A. R. Calderbank, Beyond Worst-Case Reconstruction in Deterministic Compressed Sensing., ISIT, IEEE, 2012, pp. 1852–1856.
• [19] J. H. Jorgensen, E. Y. Sidky, P. C. Hansen, and P. Xiaochuan, Quantifying Admissible Undersampling for Sparsity-Exploiting Iterative Image Reconstruction in X-Ray CT., IEEE Transactions on Medical Imaging 32 (2013), no. 2, 460–473.
• [20] Y. M. Lu and M. N. Do, A Theory for Samping Signals From a Union of Subspaces, IEEE Transactions on Signal Processing 56 (2008), no. 6, 2334–2345.
• [21] F. Lim and V. M. Stojanovic, On U-Statistics and Compressed Sensing i: Non-Asymptotic Average-Case Analysis, IEEE Transactions on Signal Processing 61 (2013), no. 10, 2473–2485.
• [22] ___ , On U-Statistics and Compressed Sensing ii: Non-Asymptotic Worst-Case Analysis, IEEE Transactions on Signal Processing 61 (2013), no. 10, 2486–2497.
• [23] O. L. Mangasarian, Uniqueness of Solution in Linear Programming, Linear Algebra and its Applications 25 (1979), no. 0, 151–162.
• [24] S. Nam, M.E. Davies, M. Elad, and R. Gribonval, The Cosparse Analysis Model and Algorithms, Applied and Computational Harmonic Analysis 34 (2013), no. 1, 30–56.
• [25] F. Natterer and F. Wübbeling, Mathematical Methods in Image Reconstruction, SIAM, 2001.
• [26] D. Needell and R. Ward, Near-Optimal Compressed Sensing Guarantees for Total Variation Minimization, IEEE Transactions on Image Processing 22 (2013), 3941–3949.
• [27] D. Needell and R. Ward, Stable Image Reconstruction Using Total Variation Minimization, SIAM Journal on Imaging Sciences 6 (2013), no. 2, 1035–1058.
• [28] V. M Patel, R. Maleh, Gilbert A. C., and Chellappa R., Gradient-Based Image Recovery Methods From Incomplete Fourier Measurements, IEEE Transactions on Image Processing 21 (2012), no. 1, 94–105.
• [29] S. Petra and C. Schnörr, TomoPIV meets Compressed Sensing, Pure Mathematics and Applications 20 (2009), no. 1-2, 49–76.
• [30 __] , Average Case Recovery Analysis of Tomographic Compressive Sensing, Linear Algebra and its Applications 441 (2014), 168–198, Special Issue on Sparse Approximate Solution of Linear Systems, in press, http://www.sciencedirect.com/science/article/pii/S0024379513004333.
• [31] S. Petra, A. Schröder, and C. Schnörr, 3D Tomography from Few Projections in Experimental Fluid Mechanics, Imaging Measurement Methods for Flow Analysis (W. Nitsche and C. Dobriloff, eds.), Notes on Numerical Fluid Mechanics and Multidisciplinary Design, vol. 106, Springer, 2009, pp. 63–72.
• [32] S. Petra, C. Schnörr, and A. Schröder, Critical Parameter Values and Reconstruction Properties of Discrete Tomography: Application to Experimental Fluid Dynamics, Fundamenta Informaticae 125 (2013), 285–312.
• [33] O. Scherzer (ed.), Handbook of Mathematical Methods in Imaging, Springer, 2011.
• [34] E. Y. Sidky and X. Pan, Image Reconstruction in Circular Cone-Beam Computed Tomography by Constrained, Total-Variation Minimization, Physics in Medicine and Biology 53 (2008), no. 17, 47–77.
• [35] W.P. Ziemer, Weakly Differentiable Functions, Springer, 1989.