Compressed Sensing: Hardware Implementations in Computational Imaging, Coded Apertures and Random Materials

[Update Nov. 08: I have listed most of the Compressed Sensing Hardware in the following page]

I have mentioned some realization of hardware implementations of Compressed Sensing (or Compressive Sensing or Compressive Sampling) before ([L1], [L2],[L3],[L4],[L5],[L6]). However owing to my ignorance, I did not give full credit to some work that made the most contribution to the subject. I think it had mostly with the fact that some websites were not up at the time I looked at the issue or that too many articles required full access to some journals (some still do). Much work on the subject of Optical Compressed Sensing has been performed at the Duke Imaging and Spectroscopy Program or DISP led by David Brady and at the Optical Computing and Processing Laboratory led by Mark Neifeld at the University of Arizona.

To give some perspective on this new and evolving field here is the story is told by the Duke researchers in Compressive Imaging Sensors [1]

An optical image has been understood as an intensity field distribution representing a physical object or group of objects. The image is considered two dimensional because the detectors are typically planary, although the objects may not. This understanding of the optical intensity field as the image has persisted even as electronic focal planes have replaced photochemical films. Lately, however, more imaginative conceptions of the relationship between the detected field and the reconstructed image have emerged. Much of this work falls under the auspices of the “computational optical sensing and imaging”,1 which was pioneered in Cathey and Dowski’s use of deliberate image aberrations to extend the depth of field2, 3 and by computed spectral tomography as represented, for example, in the work by Descour and Derniak.4 More recently, both extended depth of field and spectral features in imaging systems have been considered by many research groups. Images of physical objects have many features, such as lines and curves as well as areas separated or segmented by lines and curves. The most fundamental feature of images is the fascinating fact that an image is not an array of independent random data values. Tremendous progress has been made in the past decade in feature extraction and compression of images via post digital processing. Only recently has intelligent sampling and compression at the physical layer become a major interest. The work of Neifeld is particularly pioneering in this regard.5, 6. The DISP group at Duke University has also focused in several studies on data representation at the optical sampling layer and on physical layer compression.7–12 The interest in data compression at physical layer is also encouraged by the mathematical results by Donoho et al., who measure general functionals of a compressible and discretized function and recover n values from O(n1/4 log5/2(n)) measurements. In particular, the 1-norm of the unknown signal in its representation with respect to an orthonormal basis is used as the minimization objective, subject to a condition on the sparsity in the representation coefficients.13, 14 Rapid progress along these lines by Candes, Baraniuk and others is summarized in publications on line www-dsp.rice.edu/CS/.

And therefore, it is becoming obvious that in the optics world, researchers have known for some time that one could get more information out of scenes as long as a physical layer allowed some type of interference between the signal and some physical device (preferably random). Before this entry, I had mentioned the Hyperspectral Imager at Duke and the page of Ashwin Wagadarikar but I had not seen the full list of publications at DISP that lists most of their work for the past five years on the subject. In line with the Random Lens Imager at MIT and the ability to detect movement as mentioned by Rich Baraniuk, here some articles that caught my eyes:


Multiple order coded aperture spectrometer by S. D. Feller, Haojun Chen, D. J. Brady, Michael Gehm, Chaoray Hsieh, Omid Momtahan, and Ali Adibi [2]. The abstract reads:

We introduce a multiple order coded aperture (MOCA) spectrometer. The MOCA is a system that uses a multiplex hologram and a coded aperture to increase the spectral range and throughput of the system over conventional spectrometers while maintaining spectral resolution. This results in an order of magnitude reduction in system volume with no loss in resolution.

This is, I believe, a follow-up of the work on Coded Aperture Snapshot Spectral Imaging (CASSI) mentioned before. At the end of this page there is a comparison between the two types of CASSI concept tried by the DISP group. Very informative. Then there is this series of papers in reference structure imaging, i.e. put something well designed in between the imager and the object and try to see what properties can be detected. In this case, they look at tracking objects:

Reference structure tomography, by David J. Brady, Nikos P. Pitsianis, and Xiaobai Sun, [3] The abstract reads:

Reference structure tomography (RST) uses multidimensional modulations to encode mappings between radiating objects and measurements. RST may be used to image source-density distributions, estimate source parameters, or classify sources. The RST paradigm permits scan-free multidimensional imaging, data-efficient and computation-efficient source analysis, and direct abstraction of physical features. We introduce the basic concepts of RST and illustrate the use of RST for multidimensional imaging based on a geometric radiation model.

Lensless sensor system using a reference structure by P. Potuluri, U. Gopinathan, J. R. Adleman, and D. J. Brady. The abstract reads:

We describe a reference structure based sensor system for tracking the motion of an object. The reference structure is designed to implement a Hadamard transformation over a range of angular perspectives. We implemented a reference structure with an angular resolution of 5o and a field of view of 40o

.

But then, after putting a well known object between the object and the imager, they insert random objects in Imaging with random 3D reference structures, by P. Potuluri, M. Xu, and D. J. Brady. The abstract reads:

Three dimensional (3D) reference structures segment source spaces based on whether particular source locations are visible or invisible to the sensor. A lensless 3D reference structure based imaging system measures projections of this source space on a sensor array. We derive and experimentally verify a model to predict the statistics of the measured projections for a simple 2D object. We show that the statistics of the measurement can yield an accurate estimate of the size of the object without ever forming a physical image. Further, we conjecture that the measured statistics can be used to determine the shape of 3D objects and present preliminary experimental measurements for 3D shape recognition.

and in Imaging with random 3D reference structures by Prasant Potuluri, Mingbo Xu and David J. Brady


The abstract reads:

We describe a sensor system based on 3D ‘reference structures’ which implements a mapping from a 3D source volume on to a 2D sensor plane. The reference structure used here is a random three dimensional distribution of polystyrene beads.We show how this bead structure spatially
segments the source volume and present some simple experimental results of 2D and 3D imaging.

And so they begin to detect size, shape and motion of objects! The shape feature has also been looked at by some folks at Rice in a small course on Compressed Sensing (course given on CNX.org).

The motion is studied in Coded apertures for efficient pyroelectric motion tracking, by U. Gopinathan, D. J. Brady, and N. P. Pitsianis

The abstract reads

Coded apertures may be designed to modulate the visibility between source and measurement spaces such that the position of a source among N resolution cells may be discriminated using logarithm of N measurements. We use coded apertures as reference structures in a pyroelectric motion tracking system. This sensor system is capable of detecting source motion in one of the 15 cells uniformly distributed over a 1.6microns × 1.6microns domain using 4 pyroelectric detectors.

The size and shape are investigated in Size and shape recognition using measurement statistics and random 3D reference structures by Arnab Sinha and David J. Brady


The abstract reads

Three dimensional (3D) reference structures segment source spaces based on whether particular source locations are visible or invisible to the sensor. A lensless 3D reference structure based imaging system measures projections of this source space on a sensor array. We derive and experimentally verify a model to predict the statistics of the measured projections for a simple 2D object. We show that the statistics of the measurement can yield an accurate estimate of the size of the object without ever forming a physical image. Further, we conjecture that the measured statistics can be used to determine the shape of 3D objects and present preliminary experimental measurements for 3D shape recognition.

A similar argument was used by the folks at University of Arizona to obtain Superresolution when they looked at the pseudorandom phase-enhanced lens (PRPEL) imager in Pseudorandom phase masks for superresolution imaging from subpixel shifting by Amit Ashok and Mark A. Neifeld [9]. The abstract reads:

We present a method for overcoming the pixel-limited resolution of digital imagers. Our method combines optical point-spread function engineering with subpixel image shifting. We place an optimized pseudorandom phase mask in the aperture stop of a conventional imager and demonstrate the improved performance that can be achieved by combining multiple subpixel shifted images. Simulation results show that the pseudorandom phase-enhanced lens (PRPEL) imager achieves as much as 50% resolution improvement over a conventional multiframe imager. The PRPEL imager also enhances reconstruction root-mean-squared error by as much as 20%. We present experimental results that validate the predicted PRPEL imager performance.

The idea is to, through the use of a random phase materials, spread out the Point Spread Function (it is generally a point/dirac in normal cameras) so that it is bigger and more easily delineated from other points. The expectation is that the diffraction limit is pushed since now one can delineate more easily one "spread" peak from another one (the two peaks are not spread symmetrically thanks to the random materials). The ability to have higher resolution will then come from the ability in compressed sensing to find the sparsest dictionary of Point Spread Functions that can explain the image.


Some more explanative figures (see above) can be found in Imager Design using Object-Space Prior Knowledge a presentation at IMA 2005 by Mark Neifeld.

All in all, it seems to me that the major issue when designing these random imagers is the calibration issue that seems to be very cumbersome. Is there a way to do this faster ? Can Machine learning help ?

On a related note, Dharmpal Takhar will defend his thesis on Compressed Sensing for Imaging Applications. It'll be on Monday, February 4, 2008, from 10:00 AM to 12:00 PM in 3076 Duncan Hall at Rice University.

His abstract is:

Compressed sensing is a new sampling theory which allows reconstructing signals using sub-Nyquist measurements/sampling. This can significantly reduce the computation required for image/video acquisition/encoding, at least at the sensor end. Compressed sensing works on the concept of sparsity of the signal in some known domain, which is incoherent with the measurement domain. We exploit this technique to build a single pixel camera based on an optical modulator and a single photosensor. Random projections of the signal (image) are taken by optical modulator, which has random matrix displayed on it corresponding to the measurement domain (random noise). This random projected signal is collected on the photosensor and later used for reconstructing the signal. In this scheme we are making a tradeoff between the spatial extent of sampling array and a sequential sampling over time with a single detector. In addition to this method, we will also demonstrate a new design which overcomes this shortcoming by parallel collection of many random projections simultaneously. Applications of this technique in hyperspectral and infrared imaging will be discussed.

This is going to be interesting, I can't wait to see how the random projections are gathered simultaneously. Good luck Dharmpal!


References:
[1] N. Pitsianis, D. Brady, A. Portnoy, X. Sun, M. Fiddy, M. Feldman, R. TeKolste, Compressive Imaging Sensors, ," Proceedings of SPIE. Vol. SPIE-6232,pp. 43-51. (2006)

[2] Multiple order coded aperture spectrometer, S. D. Feller, Haojun Chen, D. J. Brady, M. E. Gehm, Chaoray Hsieh, Omid Momtahan, and Ali Adibi , Optics Express, Vol. 15, Issue 9, pp. 5625-5630

[3] David J. Brady, Nikos P. Pitsianis, and Xiaobai Sun, Reference structure tomography, J. Opt. Soc. Am. A/Vol. 21, No. 7/July 2004

[4] P. Potuluri, U. Gopinathan, J. R. Adleman, and D. J. Brady, ‘‘Lensless sensor system using a reference structure,’’ Opt. Express 11, 965–974 (2003).

[5] Coded apertures for efficient pyroelectric motion tracking, U. Gopinathan, D. J. Brady, and N. P. Pitsianis Opt. Express 11, 2142–2152 (2003).

[6] Size and shape recognition using measurement statistics and random 3D reference structures, Arnab Sinha and David J. Brady

[8] Pseudorandom phase masks for superresolution imaging from subpixel shifting by Amit Ashok and Mark A. Neifeld Applied Optics, Vol. 46, Issue 12, pp. 2256-2268

[9] A. Ashok and M. A. Neifeld, " Pseudorandom phase masks for superresolution imaging from subpixel shifting," Appl. Opt. 46, 2256-2268 (2007)

Compressed Sensing: Hardware Implementation, Part III, The explosive birth of coded aperture.

{Update Nov. '08, I have made a list of most Compressed Sensing Hardware here ]

Before we start on the subject of hardware implementation, there is a new and comprehensive tutorial on Compressed Sensing by Mike Wakin and Justin Romberg.

I initially started the listing of hardware implementation in compressed sensing though the presentation of the single pixel camera at Rice, the random lens imager at MIT, and some spectrometer work at Duke, then there was a hyperspectral imager at Yale and an analog imager at Georgia Tech. I have seldom mentioned the obvious hardware implementation of the whole MRI work spearheaded at Stanford but this one doesn't require hardware modification per se, rather a change of operation of the hardware. There is also the whole work surrounding the design of new A/D hardware named A/I (analog to information) that will be useful for capturing very high frequency signals either through a Nonuniform sampler (NUS) or a Random pre-integrator (RPI) .

More work has been performed on some of these concepts by looking at how one can use the sparsity of spectral measurement and spatial information. At MIT, I had mentioned the Random Lens Imager ( Random Lens Imaging, Rob Fergus, Antonio Torralba, Bill Freeman ). In that project, they mentioned the fact that using machine learning techniques one could provide depth information from single shots. Instead of doing that, they have resorted to putting additional filters in a lens to eventually provide depth information:

Image and Depth from a Conventional Camera with a Coded Aperture by Anat Levin, Rob Fergus, Fredo Durand, and Bill Freeman
the abstract reads:

A conventional camera captures blurred versions of scene information away from the plane of focus. Camera systems have been proposed that allow for recording all-focus images, or for extracting depth, but to record both simultaneously has required more extensive hardware and reduced spatial resolution. We propose a simple modi_cation to a conventional camera that allows for the simultaneous recovery of both (a) high resolution image information and (b) depth information adequate for semi-automatic extraction of a layered depth representation of the image. Our modification is to insert a patterned occluder within the aperture of the camera lens, creating a coded aperture. We introduce a criterion for depth discriminability which we use to design the preferred aperture pattern. Using a statistical model of images, we can recover both depth information and an all-focus image from single photographs taken with the modified camera. A layered depth map is then extracted, requiring user-drawn strokes to clarify layer assignments in some cases. The resulting sharp image and layered depth map can be combined for various photographic applications, including automatic scene segmentation, post-exposure refocussing, or re-rendering of the scene from an alternate viewpoint.

One can see the similarity with the work performed by Andrew Ng and Ashutosh Saxena on learning depth from monocular images where a MAP estimation using Laplacian (sparse) priors is performed to infer depth. The point is that this technique can be readily using reconstruction techniques of compressed sensing in order to reconstruct the data.

Also using coded aperture and mentioned in another post is the work performed at Duke on spectrometers and hyperspectral imagers. The paper of Ashwin Wagadarikar, Renu John, Rebecca Willett, David Brady, entitled "Single disperser design for compressive, single-snapshot spectral imaging," in Adaptive Coded Aperture Imaging and Non-imaging Sensors, D. Casasent and T. Clark, eds., Proc. SPIE 6714 (2007) is still not available. However we know that the reconstruction of the spectral cube is performed using Gradient Projection for Sparse Reconstruction (GPSR) method (please note there is new version: GPSR 3.0) . While it is not yet released, Scott (a commenter) pointed out that there is another paper out on a similar subject: Michael Gehm, Renu John, David Brady, Rebecca Willett, and Tim Schulz, "Single-shot compressive spectral imaging with a dual-disperser architecture," Opt. Express 15, 14013-14027 (2007)

This paper describes a single-shot spectral imaging approach based on the concept of compressive sensing. The primary features of the system design are two dispersive elements, arranged in opposition and surrounding a binary-valued aperture code. In contrast to thin-film approaches to spectral filtering, this structure results in easily-controllable, spatially-varying, spectral filter functions with narrow features. Measurement of the input scene through these filters is equivalent to projective measurement in the spectral domain, and hence can be treated with the compressive sensing frameworks recently developed by a number of groups. We present a reconstruction framework and demonstrate its application to experimental data.

Where the solution is reconstructed using an Expectation-Maximization algorithm (e.g. a regularized version of the Richardson-Lucy algorithm). Other related information can be found in references [1] [2] [3].

With Hyper-GeoCam, a random lens imager based on the MIT design, we used random elements that would diffract wavelengths in different spatial locations, thereby enabling a random spectral-spatial mixing akin to the Duke design. The unmixing of these components is therefore directly amenable to Compressed Sensing reconstruction techniques. The main difference between those carefully crafted coded aperture imagers (Duke) and that of the random lens imager reside in the complexity of the reconstruction technique. The reason the random lens imager is not "taking off"(ahah) has to do with the fact that, in the calibration process, one cannot perform a matrix reconstruction with 10^6 elements even tough most of them are sparse. The current techniques just do not allow for it yet (they do not scale well above some hundreds constraints/variables). The crafted coded aperture imager provides an idea of where those terms are hence facilitating the location of the non-zero component of the calibration matrix. Another aspect of the problem is that with random materials, reflection may be wavelength sensitive and the whole calibration process is instrument specific. I am wondering aloud if the technique on Graph Laplacian Regularization for Large-Scale Semidefinite Programming [6] would not much help with respect to the calibration of the random lens imager.

References of interest:
[1] David Brady's lectures on computational imaging
[2] Coded aperture spectroscopy and spectral tomography
[3] Optical Imaging
[4] Ashwin Wagadarikar, Renu John, Rebecca Willett, and David Brady, "Single disperser design for coded aperture snapshot spectral imaging," Submitted to a feature issue on Computational Optical Sensing and Imaging (COSI), Applied Optics (2007)
[5]Ashwin Wagadarikar, Michael Gehm, and David Brady, "Performance comparison of aperture codes for multimodal, multiplex spectroscopy," Applied Optics 46, 4932-4942 (2007)
[6] Graph Laplacian Regularization for Large-Scale Semidefinite Programming, K. Q. Weinberger, F. Sha, Q. Zhu and L. K. Saul (2007). In B. Schoelkopf, J. Platt, and T. Hofmann (eds.), Advances in Neural Information Processing Systems 19. MIT Press: Cambridge, MA

Single-sensor multispeaker listening with acoustic metamaterials / Spectral-temporal compressive imaging

The idea of compressive sensing is to project a signal onto a specific basis such that any sparse signal can be recovered with few measurements. From the very beginning, the field has been focused on finding ways of changing the first layer of data acquisition devices. Here are two examples today from the DISP group of David Brady at Duke. One uses a single sensor and 3D printing to enhance  acoustic recording while the other continues earlier work on getting a multispectral video camera on a single camera. wow!

      Single-sensor multispeaker listening with acoustic metamaterials by Yangbo Xie, Tsung-Han Tsai, Adam Konneker, Bogdan-Ioan Popa, David J. Brady, and Steven A. Cummer

Designing a “cocktail party listener” that functionally mimics the selective perception of a human auditory system has been pursued over the past decades. By exploiting acoustic metamaterials and compressive sensing, we present here a single-sensor listening device that separates simultaneous overlapping sounds from different sources. The device with a compact array of resonant metamaterials is demonstrated to distinguish three overlapping and independent sources with 96.67% correct audio recognition. Segregation of the audio signals is achieved using physical layer encoding without relying on source characteristics. This hardware approach to multichannel source separation can be applied to robust speech recognition and hearing aids and may be extended to other acoustic imaging and sensing applications.

I note from the methods,

The design process was aided with a commercial full-wave simulation package COMSOL Multiphysics. Three-dimensional simulations with Pressure Acoustics Module were conducted to extract the frequency responses of all of the waveguides.

Spectral-temporal compressive imaging by Tsung-Han Tsai, Patrick Llull, Xin Yuan, Lawrence Carin, and David Brady

We present a compressive camera that combines mechanical translation and spectral dispersion to compress a multi-spectral, high-speed scene onto a monochrome, video-rate detector. Single-frame reconstructions of 15 spectral channels and 10 temporal frames are reported.

previously we had:

Coded aperture compressive temporal imaging by Patrick Llull, Xuejun Liao, Xin Yuan, Jianbo Yang, David Kittle,Lawrence Carin, Guillermo Sapiro, and David J. Brady

We use mechanical translation of a coded aperture for code division multiple access compression of video. We present experimental results for reconstruction at 148 frames per coded snapshot.

  Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

CS: The readers' corner, GPU/Multicore for SPIRiT, Lower Bounds in Sparse Recovery, Spectral microscopy and compressive millimeter-wave holography.

The bad news is Phoenix won't revive itself after the Martian winter. It looks like the solar panels did not make it. The good news is we have many readers who wanted to share their contribution with the rest of the community, here we go:

Miki Lustig, now at Berkeley sent me the following:

Hi Igor,

FYI, my student Mark Murphy has just released a GPGPU + multicore implementation of our compressed sensing parallel MRI code.

It is linked http://www.eecs.berkeley.edu/~mlustig/Software.html

-- Miki
..

For more information on SPIRiT refer to this paper M. Lustig and J. Pauly “SPIRiT: Iterative Self-Consistent Parallel Imaging Reconstruction from Arbitrary k-Space Sampling”, Magnetic Resonance in Medicine, 2010, In Press. The L1SPIRiT page is here. From the introduction of the page:

Michael Lustig's l1-SPIRiT is a robust, iterative algorithm for artifact-free reconstruction of MR images acquired with Parallel Imaging and Compressed Sensing acceleration. In the MRI community, there is some reluctance to adopt iterative approaches to image reconstruction due to the computationally intense nature of the algorithms. This software package demonstrates that the recent "manycore" processors, in particular General-Purpose GPUs and multi-core CPUs, provide more than enough computational throughput to make iterative reconstruction algorithms feasible.

Thanks Miki. I'll add that to the compressive sensing hardware page (in the category where GPUs are used for reconstruction).

Mergen Nachin a fourth year undergraduate student at MIT double majoring in Computer Science and Mathematics just released his Undergraduate Advanced Project (undergraduate "thesis") supervised by Piotr Indyk, entitled: Lower Bounds on the Column Sparsity of Sparse Recovery Matrices. Beyond, this interesting news, I believe this is the first time we have somebody from Ulan Bator as a contributor to the field of compressive sensing. This is awesome. Here is the thesis: Lower Bounds on the Column Sparsity of Sparse Recovery Matrices by Mergen Nachin. The abstract reads:

It was recently shown that the following algorithms [BGI+08], [BI09] can approximately recover n-dimensional signal x from its sketch Ax, where the sketch length is O(k log(n/k)) and the column sparsity of A is O(log(n/k)). Our main goal in this report is to show that this column sparsity bound is tight when A is an m x n matrix with m = O(k log(n/k)).

Thanks Mergen for the heads-up and congratulations on your degree.

Christy Fernandez-Cull at Duke, sent me the following:

Hey Igor,

... I noticed on your blog that you mention work from a CS workshop at Duke related to "Image segmentation with a compressive snapshot spectral imager." Just wanted to let you know that this work was also conducted in the Duke Imaging and Spectroscopy Program and that other people were also indicated on the poster (Kerkil Choi and David Brady). Also, in case you're interested a paper related to that work was recently released - "Identification of fluorescent beads using a coded aperture snapshot spectral imager"
http://www.opticsinfobase.org/abstract.cfm?uri=ao-49-10-B59
On a tangential note, a millimeter-wave application to compressive holography has also been recently published - "Millimeter-wave compressive holography"
http://www.opticsinfobase.org/abstract.cfm?uri=ao-49-19-E67

I enjoy your blog.

Have a great week.

The paper being refered to is: Identification of fluorescent beads using a coded aperture snapshot spectral imager by Christy Fernandez-Cull, Kerkil Choi, David J. Brady, and Tim Oliver. The abstract reads:

We apply a coded aperture snapshot spectral imager (CASSI) to fluorescence microscopy. CASSI records a two-dimensional (2D) spectrally filtered projection of a three-dimensional (3D) spectral data cube. We minimize a convex quadratic function with total variation (TV) constraints for data cube estimation from the 2D snapshot. We adapt the TV minimization algorithm for direct fluorescent bead identification from CASSI measurements by combining a priori knowledge of the spectra associated with each bead type. Our proposed method creates a 2D bead identity image. Simulated fluorescence CASSI measurements are used to evaluate the behavior of the algorithm. We also record real CASSI measurements of a ten bead type fluorescence scene and create a 2D bead identity map. A baseline image from filtered-array imaging system verifies CASSI's 2D bead identity map.

the other one is behind a paywall: Millimeter-wave compressive holography by Christy Fernandez-Cull, David Wikner, Joseph Mait, Michael Mattheiss, and David Brady. The abstract reads:

We describe an active millimeter-wave holographic imaging system that uses compressive measurements for three-dimensional (3D) tomographic object estimation. Our system records a two-dimensional (2D) digitized Gabor hologram by translating a single pixel incoherent receiver. Two approaches for compressive measurement are undertaken: nonlinear inversion of a 2D Gabor hologram for 3D object estimation and nonlinear inversion of a randomly subsampled Gabor hologram for 3D object estimation. The object estimation algorithm minimizes a convex quadratic problem using total variation (TV) regularization for 3D object estimation. We compare object reconstructions using linear backpropagation and TV minimization, and we present simulated and experimental reconstructions from both compressive measurement strategies. In contrast with backpropagation, which estimates the 3D electromagnetic field, TV minimization estimates the 3D object that produces the field. Despite undersampling, range resolution is consistent with the extent of the 3D object band volume.

I also found: Sparse Fourier Sampling in Millimeter-Wave Compressive Holography by Christy Fernandez, David Brady, Joseph N. Mait, and David A. Wikner. The abstract reads:

We analyze the impact of sparse sampling on millimeter-wave (MMW) two-dimensional (2-D) holographic measurements for three-dimensional (3-D) object reconstruction. Simulations address 3-D object estimation efficacy. We present 3-D object reconstructions from experimental data.

While looking around, Google also found Christy's recently released PhD thesis :


Computational spectral microscopy and compressive millimeter-wave holography. The abstract reads:

This dissertation describes three computational sensors. The first sensor is a scanning multi-spectral aperture-coded microscope containing a coded aperture spectrometer that is vertically scanned through a microscope intermediate image plane. The spectrometer aperture-code spatially encodes the object spectral data and nonnegative least squares inversion combined with a series of reconfigured two-dimensional (2D spatial-spectral) scanned measurements enables three-dimensional (3D) (x, y, λ) object estimation. The second sensor is a coded aperture snapshot spectral imager that employs a compressive optical architecture to record a spectrally filtered projection of a 3D object data cube onto a 2D detector array. Two nonlinear and adapted TV-minimization schemes are presented for 3D (x,y,λ) object estimation from a 2D compressed snapshot. Both sensors are interfaced to laboratory-grade microscopes and applied to fluorescence microscopy. The third sensor is a millimeter-wave holographic imaging system that is used to study the impact of 2D compressive measurement on 3D (x,y,z) data estimation. Holography is a natural compressive encoder since a 3D parabolic slice of the object band volume is recorded onto a 2D planar surface. An adapted nonlinear TV-minimization algorithm is used for 3D tomographic estimation from a 2D and a sparse 2D hologram composite. This strategy aims to reduce scan time costs associated with millimeter-wave image acquisition using a single pixel receiver.

Thanks Christy, and congratulations on your Ph.D.

Finally, a reader of the blog sent me the following:

Hello Igor,
Thank you for sharing your codes with the world people.
I wish to build a measurement matrix by scrambled block hadamard ensemble. I use the code sbhe.m . It always shows :
Error using ==> cat CAT arguments dimensions are not consistent Error in ==> sbhe at 37 v2 = cat(2,vv,round(1+rand(mt,1)*(ntotal-1)));
I don't know what's wrong.
Attached is the code I downloaded from your homepage.
Can you help me to solve this problem? Thank you.

I don't know what is wrong either, last time I used it, it worked, so I really need to have the parameters used to get this error otherwise I am spending too much time on something that is not really what I want to do for the day. In any case, if somebody has a better implementation or can find the "bug" please come forward and I'll advertize it on the blog.

Image credit: NASA/JPL-Caltech/University of Arizona. Two images of the Phoenix Mars lander taken from Martian orbit in 2008 and 2010. The 2008 lander image shows two relatively blue spots on either side corresponding to the spacecraft's clean circular solar panels. In the 2010 image scientists see a dark shadow that could be the lander body and eastern solar panel, but no shadow from the western solar panel.

CS: CASSI Experimental Benchmark now available.

David Brady and Ashwin Wagadarikar at the DISP lab at Duke University just released the experimental data associated with the Coded Aperture Snapshot Spectral Imager (CASSI). It's all here. From David Brady's blog, more information can be found in his new book, Optical Imaging and Spectroscopy, in particular:

....Coded aperture snapshot spectral imaging is discussed in section 10.6 of Optical Imaging and Spectroscopy and in several DISP publications. Code for 2D spatio-spectral slice estimation from simulated data is included in the chapter 10 figures....

This is outstanding. So let's see where we are right now:

• Rich Baraniuk and Marco Duarte at Rice had their experimental data from the single pixel camera here.
  
• David Brady and Ashwin Wagadarikar at Duke just made available the experimental data of the CASSI hyperspectral imager here.
• Andriyan Suksmono and his group at IT Bandung will soon be making available their experimental data from the Compressive Sensing Ground Penetrating Radar. He has already sent me non-CS GPR data.
  
• Ori Katz and the Ultrafast Optics group at Weizman will soon release some data they gathered with the Ghost Imaging experiment.

I am sure some other groups will follow through as well. This is outstanding. Big kudos to all who made these data available.

Video: David Brady, Coded Aperture X-Ray Scatter Imaging

.  David Brady, Duke University
Coded Aperture X-Ray Scatter Imaging

You probably recall that in Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? by Xiaochuan Pan, Emil Sidky, and Michael Vannier, it was mentioned that coded aperture could be used for X-rays as it could probably yield additional information if one were to use the ideas of compressive sensing. The central idea of compressive sensing, as you recall, is that the reconstruction solver actually use the fact that the field of view is sparse in some basis. Thanks to Greg and his start-up which enabled and sponsored the CMU Next Generation Medical Imaging Workshop, we had the pleasure of watching David Brady 's presentation on Coded Aperture X-Ray Scatter Imaging. The idea of coded aperture in x-ray in not new, see for instance the discussion we had with Gerry Skinner, a Specialist in Coded Aperture Imaging. However, the deconvolution step using the fact that the scene is compressible is. There is much to be worked out beyond the simple models shown in this video but I submit that with the right use of codes like MCNP or GEANT4, we ought to be able to extract much more information from X-rays than we currently are. 
Join our Reddit Experiment, Join the CompressiveSensing subreddit and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Compressed Sensing: Compressive Coded Aperture Superresolution Image Reconstruction, TOMBO, CASSI

It's Friday and you thought that you'd go home tonight being bored and all. Too bad, you started reading this entry. The good stuff just came out from the DISP group at Duke and other researchers working with them.

First and foremost, Roummel Marcia and Rebecca Willett introduce us to Compressive Coded Aperture Superresolution Image Reconstruction. It was presented at ICASSP last week. The abstract reads:

Recent work in the emerging field of compressive sensing indicates that, when feasible, judicious selection of the type of distortion induced by measurement systems may dramatically improve our ability to perform reconstruction. The basic idea of this theory is that when the signal of interest is very sparse (i.e., zero-valued at most locations) or compressible, relatively few incoherent observations are necessary to reconstruct the most significant non-zero signal components. However, applying this theory to practical imaging systems is challenging in the face of several measurement system constraints. This paper describes the design of coded aperture masks for superresolution image reconstruction from a single, low-resolution, noisy observation image. Based upon recent theoretical work on Toeplitz structured matrices for compressive sensing, the proposed masks are fast and memory-efficient to compute. Simulations demonstrate the effectiveness of these masks in several different settings.

There is a good explanation of Coded Aperture Imaging (a subject covered before here, here and here), they then make a very illuminating statement on MURAs and then continue with how compressed sensing is literally changing the hardware (in particular masks) but notice:

However, there currently exist few guiding principles for designing coded aperture masks for nonlinear reconstruction methods.

and then they get on to

extend these results [on Toeplitz matrices mentioned here] to pseudo-circulant matrices and use them to motivate our mask design.

The conclusion state:

This paper has demonstrated that coded apertures designed to meet the Restricted Isometry Property [7] can improve our ability to perform superresolution image reconstruction from noisy, low resolution observations. In particular, building from the theory of RIPs for Toeplitz-structured matrices for compressive sensing [10], we establish a method for generating coded aperture masks in both the conventional coded aperture setting and a Fourier imaging setting; these random masks can be shown to result in an observation matrix which, with high probability, satisfies the RIP. Furthermore, simulations demonstrate that these masks combined with l2 - l1 minimization reconstruction methods yield superresolution reconstructions with crisper edges and improved feature resolution over reconstructions
achieve without the benefit of coded apertures.

A very good paper to ponder over the week-end.

Mohan Shankar, Rebecca Willett, Nikos Pitsianis, Timothy Schulz, Robert Gibbons, Robert Te Kolste, J. Carriere, C. Chen, D. Prather, David Brady write about TOMBO: Thin infrared imaging systems through multi-channel sampling.

The abstract reads:

The size of infrared camera systems can be reduced by collecting low-resolution images in parallel with multiple narrow-aperture lenses rather than collecting a single high-resolution image with one wide aperture lens. We describe an infrared imaging system that uses a three-by-three lenslet array with an optical system length of 2.3mmand achieves Rayleigh criteria resolution comparable with a conventional single-lens system with an optical system length of 26 mm. The high-resolution final image generated by this system is reconstructed from the low-resolution images gathered by each lenslet. This is accomplished using superresolution reconstruction algorithms based on linear and nonlinear interpolation algorithms. Two implementations of the ultrathin camera are demonstrated and their performances are compared with that of a conventional infrared camera.

We talked about this article of Ashwin Wagadarikar, Renu John, Rebecca Willett, and David Brady before but I never put the abstract on. Here it is: Single disperser design for coded aperture snapshot spectral imaging,

We present a single disperser spectral imager that exploits recent theoretical work in the area of compressed sensing to achieve snapshot spectral imaging. An experimental prototype is used to capture the spatiospectral information of a scene that consists of two balls illuminated by different light sources. An iterative algorithm is used to reconstruct the data cube. The average spectral resolution is 3.6 nm per spectral channel. The accuracy of the instrument is demonstrated by comparison of the spectra acquired with the proposed system with the spectra acquired by a nonimaging reference spectrometer.

And now, I am impatiently waiting for these two papers:

• Compressive coded aperture video reconstruction, Roummel F. Marcia and Rebecca M. Willett, Submitted to 2008 European Signal Processing Conference (EUSIPCO).
• Fast disambiguation of superimposed images for increased field of view, Roummel F. Marcia, Changsoon Kim, Jungsang Kim, David Brady, and Rebecca M. Willett, Submitted to 2008 IEEE International Conference on Image Processing (ICIP).

CS: The long entry of the week

[Dear Boing Boing readers; Nuit Blanche does not fulfill the Physics.org criteria as that criteria asks for a "non-specialist audience". The audience of this blog is nothing but made up of specialists. The fact that compressed sensing is at the heart of a potential revolution in sensors is of interest to a larger audience but these people are specialists nonetheless. Sorry!. And yes we occasionally have fluff stories here, here or here.]

Today we have an exciting and long entry made up of the different tidbits orbiting the compressed sensing world. Let us first check the blogs:

• Bob; A Briefly Annotated Timeline of Similarity in Audio Signals
• Alex: How well do you know your basic facts about convexity? (interesting :-))
• Frank: Bregman operator divergence
• Christian: In{s}a(ne)!!
• David: Adaptive Lenses
• Gonzalo: How does a Cognitive Radio job look like?

How does the Johnson-Lindenstrauss Lemma implies the Restricted Isometry Property ? Well you need to read the interesting: New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property by Felix Krahmer and Rachel Ward. The abstract reads:

Consider a set E of O(e^k) points in R^N, and an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, (1 - delta) || x ||_2^2 <= || Phi x ||_2^2 <= (1 + delta) || x ||_2^2 for all k-sparse x in R^N. We show that with high probability, such a matrix with randomized column signs embeds E into R^m without distorting the distance between any two points by more than a factor of 1 +- epsilon, with epsilon = 4delta. Consequently, matrices with the Restricted Isometry Property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. Our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices, optimizing the dependence on the distortion epsilon. In particular, for partial Fourier and partial Hadamard matrices, we improve the recent bound m = O(epsilon^(-4) log(p) log^4(N)) appearing in Ailon and Liberty to m = O(epsilon^(-2) log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also yield new Johnson-Lindenstrauss bounds for several deterministic matrices with randomized column signs.

Also on arxiv: A* Orthogonal Matching Pursuit: Best-First Search for Compressed Sensing Signal Recovery by Nazim Burak Karahanoglu, Hakan Erdogan. The abstract reads:

Compressed sensing is a recently developing area which is interested in reconstruction of sparse signals acquired in reduced dimensions. Acquiring the data with a small number of samples makes the reconstruction problem under-determined. The required solution is the one with minimum $l_0$ norm due to sparsity, however it is not practical to solve the $l_0$ minimization problem. Some methods, such as Basis Pursuit (BP) propose casting the problem as an $l_1$ minimization. Greedy pursuit algorithms, such as Orthogonal Matching Pursuit (OMP) and Subspace Pursuit (SP), perform a greedy search among the vectors in the basis with the goal of stagewise constrained minimization of the residual error. This manuscript proposes a new semi-greedy algorithm which employs a best-first search technique, the A* search. This approach searches for the solution on several paths of a search tree, where the paths are evaluated and extended according to some cost function, which should be carefully selected to compensate for paths with different lengths. Each path on the tree grows similar to the Orthogonal Matching Pursuit algorithm, hence this new approach is called A* Orthogonal Matching Pursuit (A*OMP). In this manuscript, A*OMP algorithm is introduced and three different cost functions are discussed. We show that novel dynamic auxiliary cost functions provide improved results as compared to a conventional choice. Finally, we provide reconstruction results on both synthetically generated data and real images which show that the proposed scheme outperforms well-known CS reconstruction methods, BP, SP and OMP.

Fast Overlapping Group Lasso by Jun Liu, Jieping Ye. The abstract reads:

The group Lasso is an extension of the Lasso for feature selection on (predefined) non-overlapping groups of features. The non-overlapping group structure limits its applicability in practice. There have been several recent attempts to study a more general formulation, where groups of features are given, potentially with overlaps between the groups. The resulting optimization is, however, much more challenging to solve due to the group overlaps. In this paper, we consider the efficient optimization of the overlapping group Lasso penalized problem. We reveal several key properties of the proximal operator associated with the overlapping group Lasso, and compute the proximal operator by solving the smooth and convex dual problem, which allows the use of the gradient descent type of algorithms for the optimization. We have performed empirical evaluations using the breast cancer gene expression data set, which consists of 8,141 genes organized into (overlapping) gene sets. Experimental results demonstrate the efficiency and effectiveness of the proposed algorithm.

From the same group here is a tutorial on Mining Sparse Representations: Formulations, Algorithms, and Applications. Jun Liu and  Jieping Ye are also the originators of the SLEP package which should be in the reconstruction section of the Big Picture. As you probably recall:

The SLEP (Sparse Learning with Efficient Projections) package provides a set of programs for sparse learning:

•  ℓ1-regularized (constrained) sparse learning
•  ℓ1/ℓq-regularized sparse learning (q>1)
•  Fussed Lasso
•  Sparse inverse covariance estimation
•  Trace norm regularized learning

I also found: Compressive Coded Aperture Computed Tomography — Part I: Coded Aperture Snapshot Spectral Imager (CASSI) by  Kerikil Choi, Ryoichi Horisaki, Ashwin Wagadarikar, and David Brady. The abstract reads:

Diverse physical measurements can be modeled by X-ray transforms. While X-ray tomography is the canonical example, reference structure tomography (RST) and coded aperture snapshot spectral imaging (CASSI) are examples of physically unrelated but mathematically equivalent sensor systems. Historically, most X-ray transform based systems sample continuous distributions and apply analytical inversion processes. On the other hand, RST and CASSI generate discrete multiplexed measurements implemented with coded apertures. Multiplexing of coded measurements allows for compressive sensing (CS). Using CS, an object sparse on some basis may be accurately described by fewer measurements than predicted by Nyquist sampling. This paper investigates the role of coded apertures in X-ray transform measurement systems (XTMs) in terms of data efficiency and reconstruction fidelity from a CS perspective. We construct a unified analysis using RST and CASSI measurement models. Using this analysis, we perform a qualitative study on how coded apertures can be exploited to implement physical compressive measurements by “regularizing” the measurement systems. Numerical studies and simulation results demonstrate several examples of the impact of coding.

Compressive Coded Aperture Computed Tomography — Part II: Compressive X-ray Tomography (CXT)  by  Kerikil Choi, Ryoichi Horisaki, Ashwin Wagadarikar, and David Brady. The abstract reads:

In the companion paper (Part I), we propose an analysis model for x-ray transform measurement systems. In particular, the model is applied to two compressive measurement systems that our group has recently developed: coded aperture snapshot spectral imagers and reference structure tomography. These modalities exploit the concepts of coding and multiplexing to create compressive sensing (CS) measurements. This second part of our paper extends the idea of coding and multiplexing to computed X-ray tomography to propose a novel compressive Xray tomography. We also propose a method of creating synthetic CS measurements that fall on the category of incoherent measurements in CS theory. These synthetic measurements combined with the proposed analysis model provides a means for evaluating and investigating the performance of CXT as a compressive sensing system. Various numerical studies illustrate the potential performance of our proposed system and suggest useful criteria for designing physical systems.

and (no link to the paper just the abstract): Sparse aperture coding for compressive sampling by David Brady, Alexander Mrozack, and Kerikil Choi. The abstract reads:

For many years, the basic goal of sparse aperture design has been to maximize the support of the modulation transfer function (MTF). Golay apertures and related nonredundant arrays are typically used to achieve this objective. Unfortunately, maximizing the support of the MTF has the necessary effect of decreasing the magnitude of the MTF at mid-band spatial frequencies. Fienup has shown that the decreased magnitude of the MTF for nonredundant arrays contributes as much as reduced throughput to the loss of SNR in sparse apertures relative to full aperture systems. This paper considers the use of periodic sparse arrays to improve the mid-band MTF at the cost of reduced spatial frequency coverage. We further consider methods to recover lost spatial frequencies using multispectral and multiframe sampling and decompressive inference.

The following poster proposes a different algorithm than the one based on compressed sensing/l1 reconstruction which it qualifies as the state of the art in this area. However, it uses an OMP greedy algorithm!

Rapid Face Recognition Using Hashing by Qinfeng Shi, Hanxi Li, Chunhua Shen. The abstract reads:

We propose a face recognition approach based on hashing. The approach yields comparable recognition rates with the random `1 approach [5], which is considered the state-of-the-art. But our method is much faster: it is up to 150 times faster than [5] on the YaleB dataset. We show that with hashing, the sparse representation can be recovered with a high probability because hashing preserves the restrictive isometry property. Moreover, we present a theoretical analysis on the recognition rate of the proposed hashing approach. Experiments show a very competitive recognition rate and significant speedup compared with the state-of-the art.

Sub-Nyquist Audio Fingerprinting for Song Identification by Kaichun K. Chang, Solon P. Pissis, Jyh-Shing R. Jang, Costas S. Iliopoulos. The abstract reads:

In recent years, Compressive Sampling (CS), a new research topic in signal processing, has piqued interest of a wide range of researchers in different fields. In this paper, we present a sub-Nyquist Audio Fingerprinting (AF) system for song identification, which utilizes CS theory to generate a compact signature, and to achieve significant reduction of the dimensionality of the input signal. The presented experimental results demonstrate that by using the CS-based AF system, which downsamples to 30%, the average accuracy is 93.43% under various distorted environments, compared to Nyquist sampling methods. The advantages of the proposed process lie in the comparable performance under sub-Nyquist sampling rate and more compact audio fingerprint.

In the upcoming NVIDIA GPU Technology Conference in San Diego, I found the following :

2300 - High-Performance Compressive Sensing using Jacket

This talk will present the ongoing work that I am doing in the L1-optimization group at Rice Universtiy. The purpose of the work is to merge both compressive sensing, for image/signal reconstructions and GPU computation, using NVIDIA’s GPUs to enhance the technology of CS. This talk will cover basic concepts in compressive sensing and the easy adaptation of operating on the GPU, in particular working with Jacket (by AccelerEyes). We willthen cover some of our numerical experiments that encompass the use of different flavors of algorithms.

Speaker:

Nabor Reyna

Topics:

Imaging, Tools & Libraries

Time:

Wednesday, September, 22nd, 10:30 - 10:50

Humm, Jacket, GPU and Compressed Sensing, we noted these subjects in one entry a while back. This is good, somebody had the same idea and implemented it, woohoo. The folks making Jacket are talking about it on their blog.

I also caught this:

Call for Papers: A Special Issue of Physical Communication on “Compressive Sensing in Communications”

Over the past few years, compressive sensing, also known as compressive sampling, has made a tremendous impact on signal processing and statistical learning, and has facilitated numerous applications in areas ranging from medical imaging and computational biology to astronomy. Recently, there has been a growing interest in applying the principles of compressive sensing to an even wider range of topics, including those in communications and networking. The basic thesis of compressive sensing—and its powerful appeal for many applications—is that under certain conditions, it suffices to collect only a small number of observations (linear projections of the signal of interest such as image, field, map, etc.) and still be able to efficiently reconstruct the signal in its entirety when the signal admits a sparse representation. This statement has a profound impact on the way in which a communication system can be designed. From compression of data —as necessitated by wireless transmission over band-limited channels, to estimation of channels that are naturally sparse, to active or passive delay, angle, and Doppler estimation of specific targets, to opportunistic spectrum sensing and collection of data in large sensor networks, the principles of compressive sensing can be applied to provide system designs that are more efficient than traditional ones. This special issue is devoted to those areas of communication system and network design where compressive sensing brings new insights, visions and tools to yield effective solutions for the problems of interest. We invite original, high-quality submissions in all such areas, ranging from physical link to system-level design, that offer innovative methodologies, algorithms, and/or theoretical results by appealing to or extending the existing results in the field of compressive sensing.

Manuscript submission:

December 15, 2010

Acceptance notification:

April 30, 2011

Final manuscript due:

June 30, 2011

Publication: 3rd quarter

2011

And finally two theses of relevance to our subject of interest:

• Derivative Compressive Sampling with Application to Inverse Problems and Imaging by Mahdi S. Hosseini

• VISUAL TRACKING AND ILLUMINATION RECOVERY VIA SPARSE REPRESENTATION by Mei Xue

At NIST there was an interesting presentation on September 1 :

10:30 AM - SIGMA XI / OPTICAL TECHNOLOGY SEMINAR: Hyperspectral Imaging, Compressive Sensing and Entrepreneurship?

The founding CEO of InView Technology Corporation, Bob Bridge, is an experienced entrepreneur, having worked in venture-capital backed technology start-ups since 1985. InView has licensed Compressive Sensing technology from Rice University, and is building high-performance infrared cameras and hyperspectral imagers based upon that technology. In contrast to Bob' earlier ventures which were venture capital funded, InView is receiving the bulk of its initial financing from various government sources. Bob has raised $51M in venture funding since 2001, including initial funding for three start-up companies. Before InView, Bob took Zilker Labs, a semiconductor start-up providing power management ICs to companies such as Cisco, from a marketing concept in 2002 to successful acquisition by public semiconductor company Intersil in 2008. Bob has also served as an Entrepreneur in Residence at Austin Ventures, vice president of marketing at Agere (a network processor IC startup), and vice president and general manager for communications ICs at Crystal Semiconductor/Cirrus Logic. Additionally, Bob has held engineering and management positions at Motorola, AT&T corporate headquarters and AT&T Bell Labs. Bob holds a Ph.D. in Electrical Engineering from The University of Texas at Austin and a bachelor's degree in Mathematical Sciences from Rice University. ***Dr. Bridges will describe his unique career path as well as the exciting new technology upon which is latest venture is based.*** Compressive Sensing technology allows InView to employ a low-cost sensor architecture to deliver unmatched camera/imager capabilities across the electromagnetic spectrum. For example, InView will offer a 2 mega-pixel Short Wavelength Infrared (SWIR) camera; the highest resolution SWIR available in the marketplace is 0.3 mega-pixels. High resolution images are reconstructed computationally from a set of measurements taken by a single element sensor. Each of these single-element measurements occurs after light from the entire image has been modulated by a random pattern and then focused onto the sensor. Mathematical processing then constructs the image using both the multiple sensor readings and the knowledge of the unique modulation pattern used to create each sensor reading as inputs to the algorithm.

Dr. Bob Bridges , CEO InView Technology.

Photo: Map of the last 100 readers who came to the new page on CS courses yesterday.