Monday, January 28, 2008

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)

No comments:

Printfriendly