research-article

Snapshot Compressed Sensing: Performance Bounds and Algorithms

Authors:

Xin YuanAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 65, Issue 12

Pages 8005 - 8024

https://doi.org/10.1109/TIT.2019.2940666

Published: 01 December 2019 Publication History

Abstract

Snapshot compressed sensing (CS) refers to compressive imaging systems in which multiple frames are mapped into a single measurement frame. Each pixel in the acquired frame is a noisy linear mapping of the corresponding pixels in the frames that are combined together. While the problem can be cast as a CS problem, due to the very special structure of the sensing matrix, standard CS theory cannot be employed to study such systems. In this paper, a compression-based framework is employed for theoretical analysis of snapshot CS systems. It is shown that this framework leads to two novel, computationally-efficient and theoretically-analyzable compression-based recovery algorithms. The proposed methods are iterative and employ compression codes to define and impose the structure of the desired signal. Theoretical convergence guarantees are derived for both algorithms. In the simulations, it is shown that, in the cases of both noise-free and noisy measurements, combining the proposed algorithms with a customized video compression code, designed to exploit nonlocal structures of video frames, significantly improves the state-of-the-art performance.

References

[1]

S. Jalali and X. Yuan, “Compressive imaging via one-shot measurements,” in Proc. IEEE Int. Symp. Inf. Theory, Jun. 2018, pp. 416–420.

[2]

E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb. 2006.

Digital Library

[3]

D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1289–1306, Apr. 2006.

Digital Library

[4]

M. F. Duarteet al., “Single-pixel imaging via compressive sampling,” IEEE Signal Process. Mag., vol. 25, no. 2, pp. 83–91, Mar. 2008.

[5]

L. Gao, J. Liang, C. Li, and L. V. Wang, “Single-shot compressed ultrafast photography at one hundred billion frames per second,” Nature, vol. 516, pp. 49–57, Dec. 2014.

[6]

M. E. Gehm, R. John, D. J. Brady, R. M. Willett, and T. J. Schulz, “Single-shot compressive spectral imaging with a dual-disperser architecture,” Opt. Express, vol. 15, no. 21, pp. 14013–14027, 2007.

[7]

Y. Hitomi, J. Gu, M. Gupta, T. Mitsunaga, and S. K. Nayar, “Video from a single coded exposure photograph using a learned over-complete dictionary,” in Proc. IEEE Int. Conf. Comp. Vis. (ICCV), Nov. 2011, pp. 287–294.

[8]

P. Llullet al., “Coded aperture compressive temporal imaging,” Opt. Express, vol. 21, no. 9, pp. 10526–10545, May 2013.

[9]

D. Reddy, A. Veeraraghavan, and R. Chellappa, “P2C2: Programmable pixel compressive camera for high speed imaging,” in Proc. IEEE Comp. Vis. Pattern Rec. (CVPR), Jun. 2011, pp. 329–336.

[10]

A. Wagadarikar, R. John, R. Willett, and D. Brady, “Single disperser design for coded aperture snapshot spectral imaging,” App. Opt., vol. 47, no. 10, pp. B44–B51, 2008.

[11]

A. A. Wagadarikar, N. P. Pitsianis, X. Sun, and D. J. Brady, “Video rate spectral imaging using a coded aperture snapshot spectral imager,” Opt. Express, vol. 17, no. 8, pp. 6368–6388, 2009.

[12]

G. Huang, H. Jiang, K. Matthews, and P. Wilford, “Lensless imaging by compressive sensing,” in Proc. IEEE Int. Conf. Image Process., Sep. 2013, pp. 2101–2105.

[13]

A. C. Sankaranarayanan, L. Xu, C. Studer, Y. Li, K. Kelly, and R. G. Baraniuk, “Video compressive sensing for spatial multiplexing cameras using motion-flow models,” SIAM J. Imag. Sci., vol. 8, no. 3, pp. 1489–1518, 2015.

[14]

W. U. Bajwa, J. D. Haupt, G. M. Raz, S. J. Wright, and R. D. Nowak, “Toeplitz-structured compressed sensing matrices,” in Proc. IEEE/SP 14th Workshop Stat. Signal Process., Aug. 2007, pp. 294–298.

Digital Library

[15]

J. Romberg, “Compressive sensing by random convolution,” SIAM J. Imag. Sci., vol. 2, no. 4, pp. 1098–1128, Nov. 2009.

Digital Library

[16]

E. J. Candès and Y. Plan, “A probabilistic and RIPless theory of compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 7235–7254, Nov. 2011.

Digital Library

[17]

A. Eftekhari, H. L. Yap, C. J. Rozell, and M. B. Wakin, “The restricted isometry property for random block diagonal matrices,” Appl. Comput. Harmon. Anal., vol. 38, no. 1, pp. 1–31, Jan. 2014.

[18]

S. Foucart and H. Rauhut, “A mathematical introduction to compressive sensing,” in Bulletin of the American Mathematical Society, vol. 54. 2017, pp. 151–165.

[19]

B. Adcock, A. C. Hansen, C. Poon, and B. Roman, “Breaking the coherence barrier: A new theory for compressed sensing,” in Forum of Mathematics, Sigma, vol. 5. Cambridge, U.K.: Cambridge Univ. Press, 2017.

[20]

C. Boyer, J. Bigot, and P. Weiss, “Compressed sensing with structured sparsity and structured acquisition,” Appl. Comput. Harmon. Anal., vol. 46, no. 2, pp. 312–350, 2017.

[21]

P. Llull, X. Yuan, L. Carin, and D. J. Brady, “Image translation for single-shot focal tomography,” Optica, vol. 2, no. 9, pp. 822–825, 2015.

[22]

X. Yuanet al., “Low-cost compressive sensing for color video and depth,” in Proc. IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), Jun. 2014, pp. 3318–3325.

[23]

T.-H. Tsai, X. Yuan, and D. J. Brady, “Spatial light modulator based color polarization imaging,” Opt. Express, vol. 23, no. 9, pp. 11912–11926, May 2015.

[24]

T.-H. Tsai, P. Llull, X. Yuan, L. Carin, and D. J. Brady, “Spectral-temporal compressive imaging,” Opt. Lett., vol. 40, no. 17, pp. 4054–4057, 2015.

[25]

S. Jalali and A. Maleki, “From compression to compressed sensing,” Appl. Comput. Harmon. Anal., vol. 40, no. 2, pp. 352–385, 2015.

[26]

J. Yanget al., “Video compressive sensing using Gaussian mixture models,” IEEE Trans. Image Process., vol. 23, no. 11, pp. 4863–4878, Nov. 2014.

[27]

J. Yanget al., “Compressive sensing by learning a Gaussian mixture model from measurements,” IEEE Trans. Image Process., vol. 24, no. 1, pp. 106–119, Jan. 2015.

[28]

X. Yuan, T.-H. Tsai, R. Zhu, P. Llull, D. Brady, and L. Carin, “Compressive hyperspectral imaging with side information,” IEEE J. Sel. Topics Signal Process., vol. 9, no. 6, pp. 964–976, Sep. 2015.

[29]

E. Candès and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, vol. 23, no. 3, pp. 969–985, 2007.

[30]

J. Huang, T. Zhang, and D. Metaxas, “Learning with structured sparsity,” in Proc. 26th Annu. Int. Conf. Mach. Learn. (ICML), 2009, pp. 417–424.

[31]

R. G. Baraniuk, V. Cevher, M. F. Duarte, and C. Hegde, “Model-based compressive sensing,” IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 1982–2001, Apr. 2010.

Digital Library

[32]

W. Dong, G. Shi, X. Li, Y. Ma, and F. Huang, “Compressive sensing via nonlocal low-rank regularization,” IEEE Trans. Image Process., vol. 23, no. 8, pp. 3618–3632, Aug. 2014.

[33]

C. A. Metzler, A. Maleki, and R. G. Baraniuk, “From denoising to compressed sensing,” IEEE Trans. Inf. Theory, vol. 62, no. 9, pp. 5117–5144, Sep. 2016.

Digital Library

[34]

D. Taubman and M. W. Marcellin, JPEG2000: Image Compression Fundamentals, Standards and Practice. Norwell, MA, USA: Kluwer Academic Publishers, 2002.

Digital Library

[35]

S. Beygi, S. Jalali, A. Maleki, and U. Mitra, “An efficient algorithm for compression-based compressed sensing,” Inf. Inference, A J. IMA, vol. 8, no. 2, pp. 343–375, 2018.

[36]

J. Holloway, A. C. Sankaranarayanan, A. Veeraraghavan, and S. Tambe, “Flutter shutter video camera for compressive sensing of videos,” in Proc. IEEE Int. Conf. Comput. Photogr. (ICCP), Apr. 2012, pp. 1–9.

[37]

H. Arguello, H. Rueda, Y. Wu, D. W. Prather, and G. R. Arce, “Higher-order computational model for coded aperture spectral imaging,” Appl. Opt., vol. 52, no. 10, pp. D12–D21, Apr. 2013.

[38]

R. G. Baraniuk, T. Goldstein, and A. C. Sankaranarayanan, “Compressive video sensing: Algorithms, architectures, and applications,” IEEE Signal Process. Mag., vol. 34, no. 1, pp. 52–66, Jan. 2017.

[39]

G. R. Arce, D. J. Brady, L. Carin, H. Arguello, and D. S. Kittle, “Compressive coded aperture spectral imaging: An introduction,” IEEE Signal Process. Mag., vol. 31, no. 1, pp. 105–115, Jan. 2014.

[40]

X. Caoet al., “Computational snapshot multispectral cameras: Toward dynamic capture of the spectral world,” IEEE Trans. Signal Process. Mag., vol. 33, no. 5, pp. 95–108, Sep. 2016.

[41]

Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, vol. 87. New York, NY, USA: Springer, 2013.

Digital Library

[42]

H. Attouch, J. Bolte, and B. F. Svaiter, “Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods,” Math. Program., vol. 137, nos. 1–2, pp. 91–129, 2013.

[43]

X. Liao, H. Li, and L. Carin, “Generalized alternating projection for weighted- $\ell_{2,1}$ minimization with applications to model-based compressive sensing,” SIAM J. Imag. Sci., vol. 7, no. 2, pp. 797–823, 2014.

[44]

X. Yuan, “Adaptive step-size iterative algorithm for sparse signal recovery,” Sig. Process., vol. 152, pp. 273–285, Nov. 2018.

[45]

M. Iliadis, L. Spinoulas, and A. K. Katsaggelos, “Deep fully-connected networks for video compressive sensing,” Digit. Sig. Process., vol. 72, pp. 9–18, Jan. 2018.

[46]

K. Xu and F. Ren, “CSVideoNet: A real-time end-to-end learning framework for high-frame-rate video compressive sensing,” Dec. 2016, arXiv:1612.05203. [Online]. Available: https://arxiv.org/abs/1612.05203

[47]

X. Yuan, “Generalized alternating projection based total variation minimization for compressive sensing,” in Proc. IEEE Int. Conf. Image Process. (ICIP), Sep. 2016, pp. 2539–2543.

[48]

D. Le Gall, “MPEG: A video compression standard for multimedia applications,” Commun. ACM, vol. 34, no. 4, pp. 46–58, 1991.

Digital Library

[49]

J. A. Nelder and R. Mead, “A simplex method for function minimization,” Comput. J., vol. 7, no. 4, pp. 308–313, 1965.

[50]

A. Buades, B. Coll, and J.-M. Morel, “A non-local algorithm for image denoising,” in Proc. IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recognit., vol. 2, Jun. 2005, pp. 60–65.

[51]

K. Dabov, A. Foi, V. Katkovnik, and K. Egiazarian, “Image denoising by sparse 3D transform-domain collaborative filtering,” IEEE Trans. Image Process., vol. 16, no. 8, pp. 2080–2095, Aug. 2007.

[52]

M. Maggioni, G. Boracchi, A. Foi, and K. Egiazarian, “Video denoising, deblocking, and enhancement through separable 4-D nonlocal spatiotemporal transforms,” IEEE Trans. Image Process., vol. 21, no. 9, pp. 3952–3966, Sep. 2012.

Digital Library

[53]

Y. Liu, X. Yuan, J. Suo, D. Brady, and Q. Dai, “Rank minimization for snapshot compressive imaging,” IEEE Trans. Pattern Anal. Mach. Intell., to be published.

[54]

W. Dong, L. Zhang, G. Shi, and X. Li, “Nonlocally centralized sparse representation for image restoration,” IEEE Trans. Image Process., vol. 22, no. 4, pp. 1620–1630, Apr. 2013.

Digital Library

[55]

H. Liu, R. Xiong, J. Zhang, and W. Gao, “Image denoising via adaptive soft-thresholding based on non-local samples,” in Proc. IEEE Int. Conf. Comput. Vis. Pattern Recognit., Jun. 2015, pp. 484–492.

[56]

Runner Data. Accessed: Jul. 4, 2018. [Online]. Available: https://www.videvo.net/video/elite-runner-slow-motion/4541/

[57]

R. Vershynin, “Introduction to the non-asymptotic analysis of random matrices,” Nov. 2010, arXiv:1011.3027. [Online]. Available: https://arxiv.org/abs/1011.3027

[58]

Y. Sun, X. Yuan, and S. Pang, “High-speed compressive range imaging based on active illumination,” Opt. Express, vol. 24, no. 20, pp. 22836–22846, Oct. 2016.

[59]

Y. Sun, X. Yuan, and S. Pang, “Compressive high-speed stereo imaging,” Opt. Express, vol. 25, no. 15, pp. 18182–18190, Jul. 2017.

[60]

D. Huanget al., “Optical coherence tomography,” Science, vol. 254, no. 5035, pp. 1178–1181, 1991.

[61]

A. Kirmaniet al., “First-photon imaging,” Science, vol. 343, no. 6166, pp. 58–61, 2014.

Cited By

Shi BLi DWang YSu YLian Q(2024)Provable deep video denoiser using spatial–temporal information for video snapshot compressive imagingSignal Processing10.1016/j.sigpro.2023.109236214:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.sigpro.2023.109236
Zhao YZheng SYuan XWilliams BChen YNeville J(2023)Deep equilibrium models for snapshot compressive imagingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i3.25475(3642-3650)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i3.25475
Du HWang JNiyato DKang JXiong ZZhang JShen X(2023)Semantic Communications for Wireless Sensing: RIS-Aided Encoding and Self-Supervised DecodingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2023.328823141:8(2547-2562)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/JSAC.2023.3288231
Show More Cited By

Index Terms

Snapshot Compressed Sensing: Performance Bounds and Algorithms
1. Hardware

Index terms have been assigned to the content through auto-classification.

Recommendations

Orthonormal Expansion $\ell_{1}$ -Minimization Algorithms for Compressed Sensing

Compressed sensing aims at reconstructing sparse signals from significantly reduced number of samples, and a popular reconstruction approach is $\ell_{1}$-norm minimization. In this correspondence, a method called orthonormal expansion is presented to ...
Efficient Parameters for Compressed Sensing Recovery Algorithms

Compressed sensing CS has been an effective research area which it plays an efficient role in many applications such as cognitive radio, imaging, radar and many other applications. The main part of CS system is to recover an input signal by using ...
Image compressed sensing based on non-convex low-rank approximation

Nonlocal sparsity and structured sparsity have been evidenced to improve the reconstruction of image details in various compressed sensing (CS) studies. The nonlocal processing is achieved by grouping similar patches of the image into the groups. To ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Information Theory

IEEE Transactions on Information Theory Volume 65, Issue 12

Dec. 2019

688 pages

ISSN:0018-9448

Issue’s Table of Contents

0018-9448 © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 December 2019

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shi BLi DWang YSu YLian Q(2024)Provable deep video denoiser using spatial–temporal information for video snapshot compressive imagingSignal Processing10.1016/j.sigpro.2023.109236214:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.sigpro.2023.109236
Zhao YZheng SYuan XWilliams BChen YNeville J(2023)Deep equilibrium models for snapshot compressive imagingProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i3.25475(3642-3650)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i3.25475
Du HWang JNiyato DKang JXiong ZZhang JShen X(2023)Semantic Communications for Wireless Sensing: RIS-Aided Encoding and Self-Supervised DecodingIEEE Journal on Selected Areas in Communications10.1109/JSAC.2023.328823141:8(2547-2562)Online publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1109/JSAC.2023.3288231
Meng ZYuan XJalali S(2023)Deep Unfolding for Snapshot Compressive ImagingInternational Journal of Computer Vision10.1007/s11263-023-01844-4131:11(2933-2958)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1007/s11263-023-01844-4
Wu ZYang CSu XYuan X(2023)Adaptive Deep PnP Algorithm for Video Snapshot Compressive ImagingInternational Journal of Computer Vision10.1007/s11263-023-01777-y131:7(1662-1679)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s11263-023-01777-y
Yang CZhang SYuan X(2022)Ensemble Learning Priors Driven Deep Unfolding for Scalable Video Snapshot Compressive ImagingComputer Vision – ECCV 202210.1007/978-3-031-20050-2_35(600-618)Online publication date: 23-Oct-2022
https://dl.acm.org/doi/10.1007/978-3-031-20050-2_35
Yang PKong LQiu MLiu XChen G(2021)Compressed Imaging Reconstruction with Sparse Random ProjectionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/344743117:1(1-25)Online publication date: 16-Apr-2021
https://dl.acm.org/doi/10.1145/3447431
Lu RChen BLiu GCheng ZQiao MYuan X(2021)Dual-view Snapshot Compressive Imaging via Optical Flow Aided Recurrent Neural NetworkInternational Journal of Computer Vision10.1007/s11263-021-01532-1129:12(3279-3298)Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11263-021-01532-1
Yuan X(2021)Various Plug-and-Play Algorithms with Diverse Total Variation Methods for Video Snapshot Compressive ImagingArtificial Intelligence10.1007/978-3-030-93046-2_29(335-346)Online publication date: 5-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-93046-2_29
Yang PKong LLiu XYuan XChen G(2020)Shearlet Enhanced Snapshot Compressive ImagingIEEE Transactions on Image Processing10.1109/TIP.2020.298955029(6466-6481)Online publication date: 30-Jun-2020
https://dl.acm.org/doi/10.1109/TIP.2020.2989550
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents