Imaging Earth from 120,000 feet: Four Years Later.

Just the other day I was wondering how some off the shelf technology had evolved over the past four years. My gold standard is when we flew one of the best and one of the cheapest (less than $500) camera with the largest optical zoom aboard a NASA helium balloon. Four years ago, that camera was the Canon S2 IS (it is the camera in this box). It had a 5MP sensor and a 12X optical zoom and could take a 4GB SD disk. We set out to have a rig that could fire the camera every twenty seconds for the next nine hours (out of twenty, some of these hours are at night!). A little Rube Goldberg'ish set up, but it worked flawlessly:

And we got these beautiful pictures from 120,000 feet. The resolution for this 12X optical zoom at 120,000 feet was pretty like the notch before last in Google Maps as shown in this entry (or about a 1 meter resolution).  Here is a presentation my undergrad students presented then:

GeoCam An offtheshelf Imager for Rapid Response Remote Sensing Monitoring

View and share presentations on PowerShow.com

The site for GEOCAM is here. The attendant blog is here. All the photos can be used for research purposes and featured some interesting elements (like a plane in this shot)

What do we have for the same price four years later ? The Canon SX30IS : a 14.1MP Digital Camera with a  35x wide optical zoom. So about four years later, we can have a camera that is 3 times better in both resolution and zoom. Wow! If we could extrapolate, this camera could provide about 1 foot resolution (30 cm) or probably enough to see a larger sign than this one or this one. In terms of memory, our limit was 8GB (we got a 4GB instead and 1600 photos) but nowadays, you can buy a 32 GB card for less than $100 ( the Transcend 32 GB goes for $65, while the Sandisk 32GB goes for $85) and a 64GB for less than $300 (the SanDisk 64GB goes for $299, the Kingston 64 GB goes for $218 ).4GB got us 1600 photos at 5 MP, so a  32GB SD disk could shoot about 4200 photos and a 64GB could shoot about 8400 photos. Imagine the type of pictures and maps you could get flying this thing at 120,000 feet up. If you are in the U.S. working with some undergrad students you could probably do this as the HASP folks are looking for payloads for the upcoming HASP/NASA balloon. The difference between this balloon and a home made one is that this one will probably fly for 20 hours covering more than 200 miles of terrain. This means that you could probably beat our world record.

From Greg Guzik

Please find attached here the Call for Payloads (CFP) for the September 2011 flight of the High Altitude Student Platform (HASP).  HASP can support up to 12 student payloads (providing power, telemetry and commanding) during a flight to an altitude of 124,000 feet for up to 20 hours.  Details about previous HASP flights and the student payloads flown can be found on the “Flight Information” page of the HASP website at http://laspace.lsu.edu/hasp/Flightinfo-2010.php    Details on the payload constraints and interface with HASP can be found on the “Participant Info” page of the HASP website at http://laspace.lsu.edu/hasp/Participantinfo.php

Applications are due December 17, 2010 and selections will be announced by mid-January 2011.

If you have any questions about the application materials or HASP, feel free to contact us at guzik@phunds.phys.lsu.edu

We will also be conducting a Q&A Teleconference about HASP and the application process on Friday, November 12, 2010 at 10:00 am (central time).  Groups who have previously flown on HASP as well as new organizations should plan on attending this teleconference.  To participate, dial in to 1-866-717-2684 a few minutes prior to the conference time.  When requested enter the conference ID number 6879021 followed by the # key.

Also please forward this e-mail to any others that you fee might be interested in applying.

Cheers,

Greg Guzik

Ps: Please note that we are still intending to fly HASP 2010 payloads during May 2011.

The main reason the photographs taken during our flight are unique revolves around the fact that the data is free for anybody to use and because satellite imagery uses push broom technology as opposed to full square CCDs. The big difference between these types of shots and those taken from low flying drones and planes is the ability to image a larger swath of land (the balloons at an altitude three times higher than the altitude flown by long range commercial aircrafts) and a low cost camera that does not require GPS or compass ( In When You Become the Map I made the case that if you stitch enough photos together then you don't need to be integrated to Google Earth/Maps, you have just produced a new map yourself) making it a potential tool for rapid imaging by the citizenry in case of disaster. We showed that the making of maps could be done very simply by feeding all our stock photos directly to Autopano Pro (that still costs about $100). We actually pushed the envelope of that software (and talked at length with their dev people) then but I think looking at what it can do nowadays, it could handle 8000 x 14 MP photos.

CS: Twitter, Several news and findings, A Non-Iterative Procedure for Undetermined Systems, Molecular imaging, Super-resolution X-ray

For those of who know what this is, I am on Twitter.

Thomas Blumensath sent me a kind e-mail :

As an avid reader of your blog, I thought I clarify the following points raised in one of your previous entries regarding the OLS algorithm.

Firstly, we did not propose the method in our paper. This method has been around with many names and in many guises. Our paper actually gives a good historical overview (which was its main purpose). A better reference for the OLS algorithm would be:

S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification.,” International Journal of Control, vol. 50, no. 5, pp. 1873–1896, 1989.

Secondly, I would like to point out that ols is also available in my Sparsify toolbox (greed_ols).

Thanks Thomas for the clarification.


Svetlana Avramov-Zamurovic presented a tutorial on Compressive Sensing in a course at the USNA. She also made a video of it. It is here. The slides and attendant paper by Richard Baraniuk on which the presentation is based. I'll add it to the Compressive Sensing Videos page.

Jort Gemmeke let me know that the schedule and list of presentation of the Compressive Sensing Workshop is now available here. Lots of goodies.

Andryian Suksmono has just released a draft e-book on Compressive Sensing. The mild caveat is that it is in Indonesian. No worry, Google Translate now has Indonesian to English translation services.

Felix J. Herrmann, Yogi Erlangga, Tim Lin have released a new version of Compressive simultaneous full-waveform simulation.

A passing thought: when you hear about an imaging system that is diffraction-limited, you are really hearing that the analog way of combining light rays together to form an image has limits. If you have read the previous entry on compressive phase retrieval featuring Ab Initio Compressive Sensing Phase retrieval by Stefano Marchesini and Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg and Richard Baraniuk, you know by now that every time you hear about an indirect measurement system or have the ability to engineer the PSF (Point Spread Function), it is likely you should be able to use the strength of compressive sensing to perform measurements.

Here are three papers that I think are interesting in different respect:

Sparse image reconstruction for molecular imaging by Michael Ting, Raviv Raichand, Alfred O. Hero III. The abstract reads:

The application that motivates this paper is molecular imaging at the atomic level. When discretized at subatomic distances, the volume is inherently sparse. Noiseless measurements from an imaging technology can be modeled by convolution of the image with the system point spread function (psf). Such is the case with magnetic resonance force microscopy (MRFM), an emerging technology where imaging of an individual tobacco mosaic virus was recently demonstrated with nanometer resolution. We also consider additive white Gaussian noise (AWGN) in the measurements. Many prior works of sparse estimators have focused on the case when H has low coherence; however, the system matrix H in our application is the convolution matrix for the system psf. A typical convolution matrix has high coherence. The paper therefore does not assume a low coherence H. A discrete-continuous form of the Laplacian and atom at zero (LAZE) p.d.f. used by Johnstone and Silverman is formulated, and two sparse estimators derived by maximizing the joint p.d.f. of the observation and image conditioned on the hyperparameters. A thresholding rule that generalizes the hard and soft thresholding rule appears in the course of the derivation. This so-called hybrid thresholding rule, when used in the iterative thresholding framework, gives rise to the hybrid estimator, a generalization of the lasso. Unbiased estimates of the hyperparameters for the lasso and hybrid estimator are obtained via Stein’s unbiased risk estimate (SURE). A numerical study with a Gaussian psf and two sparse images shows that the hybrid estimator outperforms the lasso.

a related (older) presentation can be found in A. O. Hero, R. Raich, and M. Ting, Finding dust in space: localizing atoms from noisy projections.

Here is another interesting and somewhat surprising paper: A Non-Iterative Procedure for Computing Sparse and Sparsifiable Solutions to Slightly Underdetermined Linear Systems of Equations by Andrew Yagle. The abstract reads:

We consider the problem of reconstructing a sparse image from a few of its 2-D DFT frequency values. A sparse image has pixel values that are mostly zero, with a few non-zero values at unknown locations. The number of known 2-D DFT values must exceed four times the number of non-zero pixel values. We unwrap the 2-D problem to a 1-D problem using the Good-Thomas FFT, and apply Prony's method to compute the non-zero pixel value locations. Thus we reformulate the problem as a dual 2-D harmonic retrieval problem. Our solution has three advantages over direct application of 2-D ESPRIT: (1) Instead of solving a huge generalized eigenvalue problem, we compute the roots on the unit circle of a huge polynomial; (2) the locations of the known 2-D DFT values need not form a centrosymmetric region; and (3) there are no matching issues. Our algorithm is also applicable to 2-D beamforming.

and New Atomicity-Exploiting Algorithms for Super-Resolution X-Ray Crystallography by Andrew Yagle. The abstract reads:

The X-ray crystallography problem is to reconstruct a crystalline structure from the Fourier magnitude of its diffracted scattering data. This has three major difficulties: (1) Only Fourier magnitude (not phase) data are known; (2) There is no support constraint (since the crystal is periodic); and (3) only low-wavenumber scattering data are available. But it also has two major advantages: (1) the crystal is sparse (atomicity) since it consists of isolated atoms; and (2) the crystal structure often has even symmetry. We exploit atomicity to show that the crystal can be reconstructed easily from only low wavenumber Fourier data. We also propose new algorithms for reconstruction of crystals with even or no symmetry from low-wavenumber Fourier magnitude data using two or one isomorphic replacements (4 algorithms). Small numerical examples illustrate the algorithms.

Sparse Imputation for Noise Robust Speech Recognition Using Soft Masks by Jort Gemmeke, Bert Cranen. The abstract reads:

In previous work we introduced a new missing data imputation method for ASR, dubbed sparse imputation. We showed that the method is capable of maintaining good recognition accuracies even at very low SNRs provided the number of mask estimation errors is sufficiently low. Especially at low SNRs, however, mask estimation is difficult and errors are unavoidable. In this paper, we try to reduce the impact of mask estimation errors by making soft decisions, i.e., estimating the probability that a feature is reliable. Using an isolated digit recognition task (using the AURORA-2 database), we demonstrate that using soft masks in our sparse imputation approach yields a substantial increase in recognition accuracy, most notably at low SNRs.

Credit: NASA/JPL/Space Science Institute, Photo of Saturn's rings taken by Cassini the day before yesterday.

Compressed Sensing: What Can Nonlinear Reconstruction Techniques Bring to Coded Aperture in Space and in Nuclear Medicine ?

Last week, at a presentation Jean-Luc Starck mentioned the French-Chinese ECLAIRs mission [1] still on the drawing board (it is actually very advanced as it will launch in 2009) that may benefit from some of the thinking that currently goes in the reconstruction techniques used in Compressed Sensing. As mentioned before here and here, coded aperture masks have been used in the past forty years because there was a linear reconstruction technique available. Compressed Sensing now enlarges this field by providing non-linear reconstruction techniques. And so the question is: How far will the field change because of these new reconstruction techniques ? Let me try to mention the issues that may be aided and the attendant questions that may need trade studies evaluations.

* In the current configuration of ECLAIRs, it seems that the current mask is not optimal with regards to the linear reconstruction paradigm, can the nonlinear reconstruction technique provided better recovery with the same mask or with a different mask that does not rely on the linear results ?


* In Roberto Accorsi's thesis [2], it is painfully obvious that one needs to think of the coded aperture in nuclear systems in a slightly different way than when considering light based instrumentation. This is because radiation goes through everything. Using Olivier Godet's thesis [3] one can see that similar issues pop up in the space based system. In the case of ECLAIRs, some of the weight added to the camera has to do with shielding the camera on the side. On top of this, the mask itself has to be designed so that it removes 95% of the rays passing through it in the 4-50 keV band.


Since, we can model most of the rays going through the camera (Olivier Godet's thesis used Geant and other Monte Carlo codes), is the mask over-designed ? Since radiation is a linear process, could we get more information by delineating some of the signal going through the mask, in other words, can we reduce the 95% mark down to 50% and use the nonlinear reconstruction techniques. This could initially be a mass saving issue but I am sure that this type of activity would do in advancing the state of the art in gamma ray camera for medical purposes on earth.

* Finally, as shown in the presentation of ECLAIRs, the satellite is there to respond to unanticipated bursts. Most data goes through the X-band for transmission, but the VHF band is used to alert the ground that an event is unfolding.


Can the alert system be a simple one based on the smaller number of compressed measurements directly taken by the coded aperture ?


References:
[1] The ECLAIRs micro-satellite for multi-wavelength studies of gamma-ray burst prompt emission
[2] Roberto Accorsi, Design of near-field coded aperture cameras for high resolution medical and industrial gamma-ray imaging. June 2001, MIT.
[3] Olivier Godet, Simulations de la Camera d'imagerie grand champ d'ECLAIRs

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).

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: Learning Bases from Scratch, an Optical Heterodyning Camera and RandomTime Coded Imaging

[Somebody at Honeywell is downloading this entry every four seconds. If you are that person, Please stop this] In line with the previous statement that one has to first find a sparse basis to then contemplate some hardware capability to eventually perform Compressed Sensing, Jort Gemmeke mentions to me that the Matlab implementation of Efficient sparse coding algorithms by Honglak Lee, Alexis Battle, Rajat Raina, Andrew Ng is here. The abstract reads:

Sparse coding provides a class of algorithms for finding succinct representations of stimuli; given only unlabeled input data, it discovers basis functions that capture higher-level features in the data. However, finding sparse codes remains a very difficult computational problem. In this paper, we present efficient sparse coding algorithms that are based on iteratively solving two convex optimization problems: an L1-regularized least squares problem and an L2-constrained least squares problem. We propose novel algorithms to solve both of these optimization problems. Our algorithms result in a significant speedup for sparse coding, allowing us to learn larger sparse codes than possible with previously described algorithms. We apply these algorithms to natural images and demonstrate that the inferred sparse codes exhibit end-stopping and non-classical receptive field surround suppression and, therefore, may provide a partial explanation for these two phenomena in V1 neurons.

This algorithm has the advantage over previous algorithms that it is very fast.


They then used this technique to produce a new machine learning algorithm called "Self Taught Learning". The paper is written by Honglak Lee, Alexis Battle, Rajat Raina, Benjamin Packer and Andrew Ng and is entitled Self-taught Learning: Transfer Learning from Unlabeled Data. The abstract reads:

We present a new machine learning framework called "self-taught learning" for using unlabeled data in supervised classification tasks. We do not assume that the unlabeled data follows the same class labels or generative distribution as the labeled data. Thus, we would like to use a large number of unlabeled images (or audio samples, or text documents) randomly downloaded from the Internet to improve performance on a given image (or audio, or text) classification task. Such unlabeled data is significantly easier to obtain than in typical semi-supervised or transfer learning settings, making self-taught learning widely applicable to many practical learning problems. We describe an approach to self-taught learning that uses sparse coding to construct higher-level features using the unlabeled data. These features form a succinct input representation and significantly improve classification performance. When using an SVM for classification, we further show how a Fisher kernel can be learned for this representation.

The subject of coded aperture in compressed sensing was mentioned before here and here. I found an other series of intriguing papers on Coded Aperture for Cameras. They do not perform Compressed Sensing per se, but it gives a pretty good view on how Compressed Sensing could be implemented. The project page is here, the paper is entitled Dappled Photography: Mask Enhanced Cameras for Heterodyned Light Fields and Coded Aperture Refocusing by Ashok Veeraraghavan, Ramesh Raskar, Amit Agrawal, Ankit Mohan and Jack Tumblin

The abstract reads:

We describe a theoretical framework for reversibly modulating 4D light fields using an attenuating mask in the optical path of a lens based camera. Based on this framework, we present a novel design to reconstruct the 4D light field from a 2D camera image without any additional refractive elements as required by previous light field cameras. The patterned mask attenuates light rays inside the camera instead of bending them, and the attenuation recoverably encodes the rays on the 2D sensor. Our mask-equipped camera focuses just as a traditional camera to capture conventional 2D photos at full sensor resolution, but the raw pixel values also hold a modulated 4D light field. The light field can be recovered by rearranging the tiles of the 2D Fourier transform of sensor values into 4D planes, and computing the inverse Fourier transform. In addition, one can also recover the full resolution image information for the in-focus parts of the scene. We also show how a broadband mask placed at the lens enables us to compute refocused images at full sensor resolution for layered Lambertian scenes. This partial encoding of 4D ray-space data enables editing of image contents by depth, yet does not require computational recovery of the complete 4D light field.

A Frequently Asked Questions section on the two cameras is helpful to a person who has never heard of these 4D light fields cameras. The 4D refers to the fact that we have 2D spatial information as for any image but thanks to the masking mechanism, one can also obtain information about where the light rays are coming from, i.e. the angle: the four dimensions therefore imply 2 spatial dimension (y,x) and 2 angles. Most interesting is the discussion on the Optical Heterodyning Camera. It points out (see figure above) that in normal cameras with lenses, one samples the restricted version of the full Fourier transform of the image field. In the heterodyning camera, the part of the Fourier transform that is normally cut off from the sensor is "heterodyned" back into the sensor. For more information, the derivation of the Fourier Transform of the Mask for Optical Heterodyning is here. One may foresee how a different type of sampling could provide a different Cramer-Rao bound on object range. One should notice that we already have a bayesian approach to range estimation from a single shot as featured by Ashutosh Saxena and Andrew Ng , while on the other hand in the Random Lens Imaging approach, one could already consider depth if some machine learning techniques were used.

Of related interest is the work of Ramesh Raskar and Amit Agrawal on Resolving Objects at Higher Resolution from a Single Motion-Blurred Image where now one uses random coded exposure i.e. random projection in time.



The abstract reads

Motion blur can degrade the quality of images and is considered a nuisance for computer vision problems. In this paper, we show that motion blur can in-fact be used for increasing the resolution of a moving object. Our approach utilizes the information in a single motion-blurred image without any image priors or training images. As the blur size increases, the resolution of the moving object can be enhanced by a larger factor, albeit with a corresponding increase in reconstruction noise.

Traditionally, motion deblurring and super-resolution have been ill-posed problems. Using a coded-exposure camera that preserves high spatial frequencies in the blurred image, we present a linear algorithm for the combined problem of deblurring and resolution enhancement and analyze the invertibility of the resulting linear system. We also show a method to selectively enhance the resolution of a narrow region of high-frequency features, when the resolution of the entire moving object cannot be increased due to small motion blur. Results on real images showing up to four times resolution enhancement are presented.

The project webpage is here. In traditional cameras, blurring occurs because the shutter remains open while the dynamic scene takes place.
In coded exposure, the shutter is open/closed while the dynamic scene occurs.

The research by Ramesh Raskar and Amit Agrawal shows that random coded exposure allows the retrieval of the static object.


I believe this is the first time where random time coded imaging is used.


Unrelated: Laurent Duval me fait savoir que deux presentations auront lieu a Paris sur des sujets recontres sur ce blog. Elles auront lieu dans la serie de seminaires organises par Albert Cohen et Patrick Louis Combettes:

Demain, Mardi 22 janvier 2008,
À 11h30 : Jalil Fadili (ENSI, Caen) "Une exploration des problèmes inverses en traitement d'images par les représentations parcimonieuses"

Mardi 19 février 2008
À 10h15 : Yves Meyer (ENS, Cachan) "Échantillonnage irrégulier et «compressed sensing»"

Do you feel lucky ahead of time ?

When I last mentioned the issue of super-resolution, I was under the impression that turbulence aided micro-lensing could not be used to do astronomy because the atmosphere layer was too thick. It looks as though, one can wait longer in astronomy and also obtain similar results as explained in the Lucky Image Website. But while the CCD technology is indeed impressive, much of the post processing is essential to the construction of full images. One needs to figure out automatically where the turbulence helped you and where it didn't:

There are several newsgroups that are interested in Lucky Imaging with video sources. They include:

http://groups.yahoo.com/group/videoastro/ , http://www.astronomy-chat.com/astronomy/ and http://www.qcuiag-web.co.uk/

QCUIAG is a very friendly group and visitors wanting to learn more about the techniques are pretty much guaranteed answers to their questions. Coupled with image post processing algorithms, these techniques are producing images of remarkable quality. In the UK Damian Peach is probably the most experienced in using these techniques. Some examples of his work can be seen here: http://www.damianpeach.com/

Programmes such as Astrovideo, which was originally designed to support the video stacking process developed by Steve Wainwright, the founder of QCUIAG, have frames selection algorithms, see: http://www.coaa.co.uk/astrovideo.htm

A working automated system was developed in the program K3CCDTools by QCUIAG member Peter Katreniak in 2001, see: http://qcuiag-archive.technoir.org/2001/msg03113.html

You can see the home page for K3CCDTools here: www.pk3.org/Astro/k3ccdtools.htm

And so one wonders if there would be a way to first acquire the part of the image of interest and then expect it to grow to the full image as turbulence keeps on helping you. The application would not be about astronomy where the stacking of images essentially reduce the noise to signal ratio but could be used to do imaging on earth. When observing the sky, we mostly have point-like features. If one were to decompose one of these images using wavelets, it is likely that the clearest part of the images would have the highest frequency content (besides noise). And so one of the ways to accomplish this task would be to look for parts of images with the sparsest low frequency components. Eventually when one deals with high resolution astronomy images, one is also bound to deal with curvelets and so the reasoning I just mentioned would need to be revised.


References: [1] Damien Peach's breathtaking lunar photographs.
[2] Jean-Luc Starck page.
[3] Palomar observatory lucky image press release.

Finite Rate of Innovation is the reason why S_n works in Neutron Transport ?

One of the most annoying issue with respect to neutron transport using the Linear Bolztmann equation, is the very large family of solution techniques. One of the underlying reason is the dimensionality of the problem. At the very least the problem is dimension 2 but it can go all the way to dimension 7. Another reason is the flurry of solution techniques being used. One of them is Caseology wherein one devises the solution of a problem by projecting it on a set of eigenfunctions known as Case eigenfunctions. Other solution techniques that are more ad-hoc include projection onto a set of Spherical Harmonic functions (P_N solution technique) or a set of Dirac functions (S_N solution or Discrete Ordinates). Yet in neither cases is there a good way to stop these computations except through the use of ad-hoc criterias. Then compressed sensing happened with its flurry of unusual results. This next one looks like one of those.

Pier Luigi Dragotti, Martin Vetterli Thierry Blu just wrote on Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang-Fix [1] were they show that if you were to project a certain number of diracs onto a family of scaling and wavelet functions, all the information you need to reconstruct the full signal (all the diracs) is already "stored" in the scaling functions coefficients. This is obviously of clear interest to people who want to do superresolution and is also probably the reason why P_n or S_n actually work.

It may even provide a good starting point to solving the transport equation using the multi-dimensional polynomials found by Jacques Devooght [2].


On a side note, there is also this nagging ressemblance between the kernels used by Dragotti, Vetterli and Blu and the Placzek function central to neutron thermalization in neutron transport. The uptake from this is that most sources are dirac-like and the Placzek function is really the Green's function providing an idea on how that source will downscatter in some infinite medium. In other words, the "simplified" linear transport equation (in energy) is one of these Finite-rate innovation kernels found by Dragotti, Vetterli and Blu.

[1] Sampling Moments and Reconstructing Signals of Finite Rate of Innovation: Shannon Meets Strang-Fix, P.L. Dragotti, M. Vetterli, T. Blu, IEEE Transactions on Signal Processing, vol. 55, no. 5, part 1, pp. 1741-1757, May 2007.

[2] Jacques Devooght, New elementary solutions of the monoenergetic Boltzmann equation result Transport Theory and Statistical Physics; Volume 20 No. 5 Page 383