CS: The EPFL CMOS CS Imager, Compressive Sampling of Pulse Trains : Spread the Spectrum !

Today, we have two papers from EPFL in Switzerland. Both papers have been submitted to ICASSP '09. One of the author also provided me some context. Since I am very much interested in hardware development, I couldn't help myself from asking questions. I know it's a bad habit but there is a cure: it's called an answer and the authors were kind enough to provide one. woohoo.

The first paper is CMOS Compressed Imaging by Random Convolution (also here) by Laurent Jacques, Pierre Vandergheynst, Alexandre Bibet, Vahid Majidzadeh, Alexandre Schmid, Yusuf Leblebici. The abstract reads:

We present a CMOS imager with built-in capability to perform Compressed Sensing. The adopted sensing strategy is the random Convolution due to J. Romberg. It is achieved by a shift register set in a pseudo-random configuration. It acts as a convolutive filter on the imager focal plane, the current issued from each CMOS pixel undergoing a pseudo-random redirection controlled by each component of the filter sequence. A pseudo-random triggering of the ADC reading is finally applied to complete the acquisition model. The feasibility of the imager and its robustness under noise and non-linearities have been confirmed by computer simulations, as well as the reconstruction tools supporting the Compressed Sensing theory.

Laurent puts the paper in context:

The first paper is about the design of a CMOS imager embedding random measurements, i.e. in the electronic analog processing of the signal. The sensing strategy used is the recent Random Convolution of J. Romberg (working without Fourier however).
We have noticed that this sensing simplifies not only the decoding/reconstruction process (where any sensing matrix-vector multiplication is resumed to some FFTs) but is is also straightforward to implement in the electronics of an imager. The convolutive filter is provided here by a simple shift-register (SR) set in a pseudo-random (LFSR controlled) configuration. This shift register results simply from the linking of 1-bit memories, one per pixel, and the convolution is reached by shifting (in few clock signals) the SR pseudo-random configuration. The random filter acts on the light gathered by the CMOS photodiodes by flipping the direction of the output current according to the stored bit. Kirchoff's law allows then to gather the measurements by summing the currents on wires (here, column by column to limit the current value). There are of course similarities between our imager and other projects as the "one pixel camera" of Rice's group, or the Georgia Tech Imager. Our architecture is however characterized by its specialization to the convolutive aspect of the selected sensing.

I then asked Laurent the following:

In the CMOS imager paper, do I understand correctly that the \phi x operation is the one given under the figure 1.

[the reason I asked is that I feel it is important for the folks involved with hardware development to give as much detail as possible to the theoretical/applied community in order to maybe push some other boundaries].

To which Laurent responded:

Yes. A random convolution is random in two aspects : in the filter used in the convolution, and in the random sampling of the final convolution to provide M

In furthering this thought, I then asked if they thought that the RIP-1 random matrices of Indyk, Gilbert
et al could also be easily implemented in this technology (an implementation is here but there are others)

Laurent replied with:

Well. I'm not sufficiently familiar with this kind of sparse random matrices.
I'm not sure we could implement as simply with a shift-register as we do for the random convolution.
If big storage are needed for the sensing matrix, i.e. bigger than the number of pixels, then the Georgia Tech Analog imager is for me better (they included for instance the Noiselet sensing).
If this storage is smaller than N bits, e.g. if two rows of the sensing matrix are connected by a known permutation, then perhaps a particular SR configuration is possible. A careful study has to be done.

However, our system is very easily adaptable to Toeplitz sensing matrix (see Jarvis Haupt,Waheed Bajwa, Gil Raz and Robert Nowak , Toeplitz compressed sensing matrices with applications to sparse channel estimation). To reach that, it is sufficient to generate a pseudo-random sequence larger than the number of pixels, i.e. using a LFSR with a looping period larger than 2N (with N pixels).

Let us note that this Toeplitz matrix has also been used in the context of Coded aperture by Roummel Marcia and Rebecca Willett in Compressive Coded Aperture Superresolution Image Reconstruction (additional information can be found here)

Finally, I asked:

How can one map the trade study performed by the Rice folks on their camera to your camera ?
( http://nuit-blanche.blogspot.com/2007/12/compressed-sensing-single-pixel-imaging.html
) In other words, do you have issues with dynamical range since you seem to have limit on the current, etc...

Laurent responded with the following insight:

BTW, I think that Georgia Tech imager met the same issue and this is probably one reason they use a 16x16 block separation (This is not the only reason for such block: the basis functions stored in their imager take also less memory). However, we are currently in discussion with our collaborators in the EPFL Microelectronic lab (LSM) to see how to increase the number of summed pixels (this will be mandatory for a new prototype with a larger number of pixels, e.g. 256x256)

For the rest, we haven't yet realized a deep trade study of this CS imager. What we can say however :

* this CS imager is definitely **not** the kind of imager that will be put inside an end-user device (e.g. mobile phone). CS cannot fight with imaging device able to embed a coder like JPEG2K.

* following the key principles of CS and the conclusions arose by other groups, we foresee that such a camera will be perfect for devices with low CPU power and targeting low energy consumption. I have in mind applications like a small "camera pill" designed to visualize the whole digestive system (see [1]), or flying robotic system that need a very light camera (e.g. for egomotion analysis)

* the system we use is very flexible in the sense that it could be translated to other 2-D grid of sensors currently limited in resolution because of each "pixel" circuitry. For instance, as mentionned in our paper, in collaboration with the LSM lab, we are going to apply this system to a grid of biosensors recording the electrical signal produced by a network of neuronal cells grown on the grid. Some studies proves that the signal to record will be both sparse in space and time [2]. Current CMOS biosensors recording such signals are limited in their resolution since each pixel needs a very complex electronic. A "CS analog electronic" could give access to higher resolution by reducing this complexity, i.e. a kind of economy of scale by working on a group of pixels, using random linear combinations of currents, instead of duplicating the same circuitry for each pixels.


References :

[1] : http://query.nytimes.com/gst/fullpage.html?res=9C00E6DC163CF933A05756C0A9669C8B63&sec=&spon=&pagewanted=1

[2] : M Jenkner, M Tartagni, A Hierlemann, and R Thewes, “Cell-based cmos sensor and actuator arrays,” IEEE Journ. Solid-State Circuits, vol. 39, no. 12, pp. 2431 – 2437, Dec 2004.

This hardware is now listed in the Compressive Sensing Hardware page.

The second paper is Compressive Sampling of Pulse Trains : Spread the Spectrum ! (also here) by Farid Naini, Rémi Gribonval, Laurent Jacques and Pierre Vandergheynst. The abstract reads:

In this paper we consider the problem of sampling far below the Nyquist rate signals that are sparse linear superpositions of shifts of a known, potentially wide-band, pulse. This signal model is key for applications such as Ultra Wide Band (UWB) communications or neural signal processing. Following the recently proposed Compressed Sensing methodology, we study several acquisition strategies and show that the approximations recovered via minimization are greatly enhanced if one uses Spread Spectrum modulation prior to applying random Fourier measurements. We complement our experiments with a discussion of possible hardware implementation of our technique.

To give some context, Laurent points out the following:

The second paper aims at showing how the use of a simple spread spectrum method can lead to good compressive measurements of Ultra WideBand Signals (UWB). Our study is restricted to the model of a pulse train signal, i.e. sparse in a shift-invariant dictionary generated by a short pulse. We show experimentally that, for this signal model, a SS strategy combined with the random selection of Fourier frequencies is as good as a Gaussian random sensing when the reconstruction quality is expressed in the signal domain (rather than in the dictionary coefficients). In addition, replacing the Fourier matrix by a Walsh-Hadamard transform reduces only slightly the performance and the robustness of the method, while this alternative is more appealing for the building of an analog UWB sensor (for which we provide also an idealized electronic scheme). On the theoretical side, it seems that our approach is very similar to the one of T. Do et al. about "Fast compressive sampling with structurally random matrices" (ICASSP'08), recently quoted on NB. Unfortunately, we were not aware of this work at the writing of our ICASSP paper and we will add for sure a reference to it in the revision.

On top what was kindly said about the utility of this blog, I note the use of SPARCO and SPGL1.

Finally, the Terahertz imaging technique devised at Rice and using the one pixel camera ( we mentioned it here ) has hit the wires here and here.