Abstract

The inherent redundancy in natural scenes forms the basis of compressive imaging where the number of measurements is less than the dimensionality of the scene. The compressed sensing theory has shown that a purely random measurement basis can yield good reconstructions of sparse objects with relatively few measurements. However, additional prior knowledge about object statistics that is typically available is not exploited in the design of the random basis. In this work, we describe a hybrid measurement basis design that exploits the power spectral density statistics of natural scenes to minimize the reconstruction error by employing an optimal combination of a nonrandom basis and a purely random basis. Using simulation studies, we quantify the reconstruction error improvement achievable with the hybrid basis for a diverse set of natural images. We find that the hybrid basis can reduce the reconstruction error up to 77% or equivalently requires fewer measurements to achieve a desired reconstruction error compared to the purely random basis. It is also robust to varying levels of object sparsity and yields as much as 40% lower reconstruction error compared to the random basis in the presence of measurement noise.

© 2011 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. E. T. Whittaker, “On the functions which are represented by the expansions of the interpolation theory,” Proc. R. Soc. Edinb., Sect. A, Math. 35, 181–194 (1915).
  2. H. Nyquist, “Certain topics in telegraph transmission theory,” Trans. AIEE 47, 617–644 (1928).
    [CrossRef]
  3. C. E. Shannon, “Communication in the presence of noise,” Proc. IRE 37, 10–21 (1949).
    [CrossRef]
  4. Y. Tsaig and D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory 52, 1289–1306 (2006).
    [CrossRef]
  5. D. Donoho and Y. Tsaig, “Extensions of compressed sensing,” Signal Process. 86, 549–571 (2006).
    [CrossRef]
  6. E. Candes and J. Romberg, “Signal recovery from random projections,” Proc. SPIE 5674, 76–86 (2005).
    [CrossRef]
  7. E. Candes and T. Tal, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Trans. Inf. Theory 52, 5406–5424 (2006).
    [CrossRef]
  8. F. Krahmer and R. Ward, “New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property,” submitted for publication (2010), arXiv:1009.0744v4.
  9. J. Romberg, “Imaging via compressing sampling,” IEEE Signal Process. Mag. 25, 14–20 (2008).
    [CrossRef]
  10. M. A. Neifeld and P. Shankar, “Feature-specific imaging,” Appl. Opt. 42, 3379–3389 (2003).
    [CrossRef] [PubMed]
  11. H. Pal and M. A. Neifeld, “Multispectral principal component imaging,” Opt. Express 11, 2118–2125 (2003).
    [CrossRef] [PubMed]
  12. M. A. Neifeld and J. Ke, “Optical architectures for compressive imaging,” Appl. Opt. 46, 5293–5303 (2007).
    [CrossRef] [PubMed]
  13. D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
    [CrossRef] [PubMed]
  14. D. L. Ruderman, “Origins of scaling in natural images,” Vision Res. 37, 3385–3398 (1997).
    [CrossRef]
  15. E. P. Simoncelli and B. A. Olshausen, “Natural image statistics and neural representation,” Annu. Rev. Neurosci. 24, 1193–1216(2001).
    [CrossRef] [PubMed]
  16. E. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Probl. 23, 969–986 (2007).
    [CrossRef]
  17. W. Chen and W. Pratt, “Scene adaptive coder,” IEEE Trans. Commun. 32, 225–232 (1984).
    [CrossRef]
  18. G. Wallace, “The JPEG still picture compression standard,” Commun. ACM 34, 30–44 (1991).
    [CrossRef]
  19. University of Southern California Signal and Image Processing Institute, “The USC-SIPI image database,” http://sipi.usc.edu/database.
  20. California Institute of Technology, “ℓ1-MAGIC,” http://www.acm.caltech.edu/l1magic/.
  21. S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
    [CrossRef]
  22. P. K. Baheti and M. A. Neifeld, “Feature-specific structured imaging,” Appl. Opt. 45, 7382–7391 (2006).
    [CrossRef] [PubMed]
  23. N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
    [CrossRef]
  24. D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).
  25. M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan, “Static two-dimensional aperture coding for multimodal multiplex spectroscopy,” Appl. Opt. 45, 2965–2974(2006).
    [CrossRef] [PubMed]

2009 (1)

S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
[CrossRef]

2008 (1)

J. Romberg, “Imaging via compressing sampling,” IEEE Signal Process. Mag. 25, 14–20 (2008).
[CrossRef]

2007 (2)

E. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Probl. 23, 969–986 (2007).
[CrossRef]

M. A. Neifeld and J. Ke, “Optical architectures for compressive imaging,” Appl. Opt. 46, 5293–5303 (2007).
[CrossRef] [PubMed]

2006 (5)

P. K. Baheti and M. A. Neifeld, “Feature-specific structured imaging,” Appl. Opt. 45, 7382–7391 (2006).
[CrossRef] [PubMed]

E. Candes and T. Tal, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Trans. Inf. Theory 52, 5406–5424 (2006).
[CrossRef]

Y. Tsaig and D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory 52, 1289–1306 (2006).
[CrossRef]

D. Donoho and Y. Tsaig, “Extensions of compressed sensing,” Signal Process. 86, 549–571 (2006).
[CrossRef]

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan, “Static two-dimensional aperture coding for multimodal multiplex spectroscopy,” Appl. Opt. 45, 2965–2974(2006).
[CrossRef] [PubMed]

2005 (2)

E. Candes and J. Romberg, “Signal recovery from random projections,” Proc. SPIE 5674, 76–86 (2005).
[CrossRef]

N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
[CrossRef]

2003 (2)

2001 (1)

E. P. Simoncelli and B. A. Olshausen, “Natural image statistics and neural representation,” Annu. Rev. Neurosci. 24, 1193–1216(2001).
[CrossRef] [PubMed]

1997 (1)

D. L. Ruderman, “Origins of scaling in natural images,” Vision Res. 37, 3385–3398 (1997).
[CrossRef]

1992 (1)

D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
[CrossRef] [PubMed]

1991 (1)

G. Wallace, “The JPEG still picture compression standard,” Commun. ACM 34, 30–44 (1991).
[CrossRef]

1984 (1)

W. Chen and W. Pratt, “Scene adaptive coder,” IEEE Trans. Commun. 32, 225–232 (1984).
[CrossRef]

1949 (1)

C. E. Shannon, “Communication in the presence of noise,” Proc. IRE 37, 10–21 (1949).
[CrossRef]

1928 (1)

H. Nyquist, “Certain topics in telegraph transmission theory,” Trans. AIEE 47, 617–644 (1928).
[CrossRef]

1915 (1)

E. T. Whittaker, “On the functions which are represented by the expansions of the interpolation theory,” Proc. R. Soc. Edinb., Sect. A, Math. 35, 181–194 (1915).

Babacan, S. D.

S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
[CrossRef]

Baheti, P. K.

Brady, D. J.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan, “Static two-dimensional aperture coding for multimodal multiplex spectroscopy,” Appl. Opt. 45, 2965–2974(2006).
[CrossRef] [PubMed]

N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
[CrossRef]

D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).

Candes, E.

E. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Probl. 23, 969–986 (2007).
[CrossRef]

E. Candes and T. Tal, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Trans. Inf. Theory 52, 5406–5424 (2006).
[CrossRef]

E. Candes and J. Romberg, “Signal recovery from random projections,” Proc. SPIE 5674, 76–86 (2005).
[CrossRef]

Chao, T.

D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
[CrossRef] [PubMed]

Chen, W.

W. Chen and W. Pratt, “Scene adaptive coder,” IEEE Trans. Commun. 32, 225–232 (1984).
[CrossRef]

Donoho, D.

Y. Tsaig and D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory 52, 1289–1306 (2006).
[CrossRef]

D. Donoho and Y. Tsaig, “Extensions of compressed sensing,” Signal Process. 86, 549–571 (2006).
[CrossRef]

Gehm, M. E.

Katsaggelos, A. K.

S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
[CrossRef]

Ke, J.

Krahmer, F.

F. Krahmer and R. Ward, “New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property,” submitted for publication (2010), arXiv:1009.0744v4.

McCain, S. T.

Molina, R.

S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
[CrossRef]

Neifeld, M. A.

Nyquist, H.

H. Nyquist, “Certain topics in telegraph transmission theory,” Trans. AIEE 47, 617–644 (1928).
[CrossRef]

Olshausen, B. A.

E. P. Simoncelli and B. A. Olshausen, “Natural image statistics and neural representation,” Annu. Rev. Neurosci. 24, 1193–1216(2001).
[CrossRef] [PubMed]

Pal, H.

Pitsianis, N. P.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan, “Static two-dimensional aperture coding for multimodal multiplex spectroscopy,” Appl. Opt. 45, 2965–2974(2006).
[CrossRef] [PubMed]

N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
[CrossRef]

D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).

Potuluri, P.

M. E. Gehm, S. T. McCain, N. P. Pitsianis, D. J. Brady, P. Potuluri, and M. E. Sullivan, “Static two-dimensional aperture coding for multimodal multiplex spectroscopy,” Appl. Opt. 45, 2965–2974(2006).
[CrossRef] [PubMed]

D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).

Pratt, W.

W. Chen and W. Pratt, “Scene adaptive coder,” IEEE Trans. Commun. 32, 225–232 (1984).
[CrossRef]

Romberg, J.

J. Romberg, “Imaging via compressing sampling,” IEEE Signal Process. Mag. 25, 14–20 (2008).
[CrossRef]

E. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Probl. 23, 969–986 (2007).
[CrossRef]

E. Candes and J. Romberg, “Signal recovery from random projections,” Proc. SPIE 5674, 76–86 (2005).
[CrossRef]

Ruderman, D. L.

D. L. Ruderman, “Origins of scaling in natural images,” Vision Res. 37, 3385–3398 (1997).
[CrossRef]

Shankar, P.

Shannon, C. E.

C. E. Shannon, “Communication in the presence of noise,” Proc. IRE 37, 10–21 (1949).
[CrossRef]

Simoncelli, E. P.

E. P. Simoncelli and B. A. Olshausen, “Natural image statistics and neural representation,” Annu. Rev. Neurosci. 24, 1193–1216(2001).
[CrossRef] [PubMed]

Sullivan, M. E.

Sun, X.

N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
[CrossRef]

D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).

Tadmor, Y.

D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
[CrossRef] [PubMed]

Tal, T.

E. Candes and T. Tal, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Trans. Inf. Theory 52, 5406–5424 (2006).
[CrossRef]

Tolhurst, D. J.

D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
[CrossRef] [PubMed]

Tsaig, Y.

Y. Tsaig and D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory 52, 1289–1306 (2006).
[CrossRef]

D. Donoho and Y. Tsaig, “Extensions of compressed sensing,” Signal Process. 86, 549–571 (2006).
[CrossRef]

Wallace, G.

G. Wallace, “The JPEG still picture compression standard,” Commun. ACM 34, 30–44 (1991).
[CrossRef]

Ward, R.

F. Krahmer and R. Ward, “New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property,” submitted for publication (2010), arXiv:1009.0744v4.

Whittaker, E. T.

E. T. Whittaker, “On the functions which are represented by the expansions of the interpolation theory,” Proc. R. Soc. Edinb., Sect. A, Math. 35, 181–194 (1915).

Annu. Rev. Neurosci. (1)

E. P. Simoncelli and B. A. Olshausen, “Natural image statistics and neural representation,” Annu. Rev. Neurosci. 24, 1193–1216(2001).
[CrossRef] [PubMed]

Appl. Opt. (4)

Commun. ACM (1)

G. Wallace, “The JPEG still picture compression standard,” Commun. ACM 34, 30–44 (1991).
[CrossRef]

IEEE Signal Process. Mag. (1)

J. Romberg, “Imaging via compressing sampling,” IEEE Signal Process. Mag. 25, 14–20 (2008).
[CrossRef]

IEEE Trans. Commun. (1)

W. Chen and W. Pratt, “Scene adaptive coder,” IEEE Trans. Commun. 32, 225–232 (1984).
[CrossRef]

IEEE Trans. Image Process. (1)

S. D. Babacan, R. Molina, and A. K. Katsaggelos, “Variational Bayesian blind deconvolution using a total variation prior,” IEEE Trans. Image Process. 18, 12–26 (2009).
[CrossRef]

IEEE Trans. Inf. Theory (2)

Y. Tsaig and D. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory 52, 1289–1306 (2006).
[CrossRef]

E. Candes and T. Tal, “Near-optimal signal recovery from random projections: universal encoding strategies?” IEEE Trans. Inf. Theory 52, 5406–5424 (2006).
[CrossRef]

Inverse Probl. (1)

E. Candes and J. Romberg, “Sparsity and incoherence in compressive sampling,” Inverse Probl. 23, 969–986 (2007).
[CrossRef]

Ophthalmic. Physiol. Opt. (1)

D. J. Tolhurst, Y. Tadmor, and T. Chao, “Amplitude spectra of natural images,” Ophthalmic. Physiol. Opt. 12, 229–232 (1992).
[CrossRef] [PubMed]

Opt. Express (1)

Proc. IRE (1)

C. E. Shannon, “Communication in the presence of noise,” Proc. IRE 37, 10–21 (1949).
[CrossRef]

Proc. R. Soc. Edinb., Sect. A, Math. (1)

E. T. Whittaker, “On the functions which are represented by the expansions of the interpolation theory,” Proc. R. Soc. Edinb., Sect. A, Math. 35, 181–194 (1915).

Proc. SPIE (2)

E. Candes and J. Romberg, “Signal recovery from random projections,” Proc. SPIE 5674, 76–86 (2005).
[CrossRef]

N. P. Pitsianis, D. J. Brady, and X. Sun, “Sensor-layer image compression based on the quantized cosine transform,” Proc. SPIE 5817, 250–257 (2005).
[CrossRef]

Signal Process. (1)

D. Donoho and Y. Tsaig, “Extensions of compressed sensing,” Signal Process. 86, 549–571 (2006).
[CrossRef]

Trans. AIEE (1)

H. Nyquist, “Certain topics in telegraph transmission theory,” Trans. AIEE 47, 617–644 (1928).
[CrossRef]

Vision Res. (1)

D. L. Ruderman, “Origins of scaling in natural images,” Vision Res. 37, 3385–3398 (1997).
[CrossRef]

Other (4)

F. Krahmer and R. Ward, “New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property,” submitted for publication (2010), arXiv:1009.0744v4.

D. J. Brady, N. P. Pitsianis, X. Sun, and P. Potuluri, “Compressive sampling and signal inference,” U.S. patents 7283231 (16 Oct. 2007), 7432843 (7 Oct. 2008), 7463174 (9 Dec. 2008), 7463179 (9 Dec. 2008), 7616306 (10 Nov. 2009).

University of Southern California Signal and Image Processing Institute, “The USC-SIPI image database,” http://sipi.usc.edu/database.

California Institute of Technology, “ℓ1-MAGIC,” http://www.acm.caltech.edu/l1magic/.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (13)

Fig. 1
Fig. 1

Radial power spectral density function and a power-law fit for natural images.

Fig. 2
Fig. 2

Distribution of energy in DCT coefficients for a 64 × 64 image patch of a natural image.

Fig. 3
Fig. 3

Samples from the image set used in the simulation study.

Fig. 4
Fig. 4

Reference image and corresponding sparse image ( α = 70 % ).

Fig. 5
Fig. 5

Reconstruction error versus the number of DCT projections ( M 1 ) comprising the hybrid basis and DCT/random projections with M = 400 .

Fig. 6
Fig. 6

Reconstruction error versus the number of measurements for hybrid, DCT, and random bases.

Fig. 7
Fig. 7

Optimal number of DCT ( M 1 ) and random ( M 2 ) projections comprising the hybrid basis.

Fig. 8
Fig. 8

Example reconstructions obtained with M = 400 compressive measurements. Clockwise from top left: reference image and reconstructions with hybrid basis, random basis, and DCT basis.

Fig. 9
Fig. 9

Example reconstructions obtained with M = 400 compressive measurements. Clockwise from top left: reference image and reconstructions with hybrid basis, random basis, and DCT basis.

Fig. 10
Fig. 10

Reconstruction error versus the number of measurements for hybrid, DCT, and random bases for four different sparsity levels: (a)  α = 95 % , (b)  α = 90 % , (c)  α = 80 % , and (d)  α = 70 % .

Fig. 11
Fig. 11

Reconstruction RMSE versus the number of noisy measurements with a noise strength σ n = 0.5 % .

Fig. 12
Fig. 12

Example reconstructions obtained with M = 460 noisy compressive measurements. Clockwise from top left: reference image and reconstructions with hybrid basis, random basis, and DCT basis.

Fig. 13
Fig. 13

Example reconstructions obtained with M = 460 noisy compressive measurements. Clockwise from top left: reference image and reconstructions with hybrid basis, random basis, and DCT basis.

Tables (3)

Tables Icon

Table 1 RMSE Performance of Three Compressive Measurement Bases for Various Values of M a

Tables Icon

Table 2 Number of Measurements M ( N = 1024 ) Required to Achieve a Desired RMSE Performance for Objects with Five Different Sparsity Levels a

Tables Icon

Table 3 RMSE Performance of the Three Measurement Bases for Noisy Measurements a

Equations (19)

Equations on this page are rendered with MathJax. Learn more.

θ = D f ,
| θ ˙ n | R · n 1 p ,
θ ˙ θ ˙ ^ K 2 C p · R · K ( 1 p 1 2 ) ,
f f ^ K 2 C p · R · K ( 1 p 1 2 ) ,
M = C k ( μ ) · K · log ( N ) ,
f f ^ K 2 C p · R · ( M C K · log ( N ) ) ( 1 p 1 2 ) .
K 2 = M 2 C K · log ( N ) .
K = X M 1 + M 2 C K · log ( N ) ,
f f ^ K 2 C p · R · ( E ( X M 1 ) + M M 1 C K · log ( N ) ) ( 1 p 1 2 ) .
g = H f ,
θ = D f f = D T θ .
E ( X M ) = K ( 1 exp ( M β ) ) ,
g = [ g d g c ] = [ H dct H rand ] D T [ θ d θ c ] ,
min | θ c | ^ 1 s.t. H rand D T θ c ^ = g c .
θ d ^ = D H dct T ( D H dct T H dct D T ) 1 g d .
g = H f + n ,
H = H * C M ,
min TV ( θ ^ ) s.t. H D T θ ^ g 2 ϵ ,
θ ^ = σ s 2 D H T ( σ s 2 D H T H D T + σ n 2 I ) 1 g ,

Metrics