HOMEPAGE PARTNERS PEOPLE WORKPLAN PUBLICATIONS MANAGEMENT RESOURCES
THz Imaging Compressive sensing Hadamard spectroscopy THz Laser DMD Hadamard matrices Experimental model v1.0 Experimental model v2.0 Experimental model v3.0
Compressive Sensing (CS)
At the origin of compressive sampling/sensing (CS) stands the assertion that an image with a rare representation in a base can be reconstructed from relatively few samples, if they are well chosen. Rare representation means that a large number of coefficients are zero or close to zero, resulted by projecting the image in that base.
In classical compression, although these bases lead to rare representations, yet the coefficients are fully encoded, for the simple fact that the position of those different from zero is unknown. Compressive sam-pling eliminates this shortcoming by measuring, in certain conditions, a reduced number M = K log N of samples from which, one can estimate all the coefficients of K order followed by the reconstruction of the image f through reverse transformation.
CS reconstruction algorithms
CS provides an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K<< N elements from an N-dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm.
In matrix notation, the measurements M are given by y = Φx, where the rows of the M × N matrix Φ contain the measurement vectors. The challenge in CS is to reconstruct the vector x based on measurement vector y and matrix Φ. The major algorithmic challenge in CS is to approximate the signal x given a vector of noisy measurements y= Φx+e (e is the noise). The literature describes a high number of approaches to solving this problem. They fall into three rough categories:
  • Greedy pursuits: These methods build up an approximation one step at a time by making locally optimal choices at each step. Examples include Orthogonal Matching Pursuit (OMP), stagewise OMP (StOMP), and regularized OMP (ROMP).
  • Convex relaxation: These techniques solve a convex program whose minimizer is known to approximate the target signal. Many algorithms have been proposed to complete the optimization, including interior-point methods, projected gradient methods, and iterative thresholding.
  • Combinatorial algorithms: These methods acquire highly structured samples (measurements) of the signal that support rapid reconstruction via group testing. This class includes Fourier sampling, chaining pursuit, and HHS pursuit, as well as some algorithms of Cormode–Muthukrishnan and Iwen.
CoSaMP algorithm
CoSaMP is a greedy pursuit algorithm that uses an approach inspired by the restricted isometry property. For an s-sparse signal x, the vector y = Φ*Φx can serve as a proxy for the signal because the energy in each set of s components of y approximates the energy in the corresponding s components of x. By Φ*, it is denoted the transpose of the conjugate of Φ. If Φ is real, then Φ* is the transpose ΦT. In particular, the largest s entries of the proxy y point toward the largest s entries of the signal x. Since the samples have the form u = Φx, we can obtain the proxy just by applying the matrix Φ* to the samples. The algorithm invokes this idea iteratively to approximate the target signal. At each iteration, the current approximation induces a residual, the part of the target signal that has not been approximated. As the algorithm progresses, the samples are updated so that they reflect the current residual. These samples are used to construct a proxy for the residual, which permits us to identify the large components in the re-sidual. This step yields a tentative support for the next approximation. We use the samples to estimate the approximation on this support set using least squares. This process is repeated until we have found the recoverable energy in the signal.
As input, the CoSaMP algorithm requires 4 pieces of information:
  • access to the sampling operator Φ via matrix–vector multiplication
  • a vector y of (noisy) samples of the unknown signal
  • the sparsity s of the approximation to be produced
  • a halting criterion
During each iteration, CoSaMP performs five major steps:
  1. Identification. The algorithm forms a proxy of the residual from the current samples and locates the largest components of the proxy (steps 6 and 7 in the image bellow)
  2. Support Merger. The set of newly identified components is united with the set of components that appear in the current approximation (step 8)
  3. Estimation. The algorithm solves a least-squares problem to approximate the target signal on the merged set of components (step 9)
  4. Pruning. The algorithm produces a new approximation by retaining only the s largest entries in this least-squares signal approximation (step 10).
  5. Sample Update. Finally, the samples are updated so that they reflect the residual, the part of the signal that has not been approximated

Design and test of camera software
The main goal was in finding the appropriate couple of Sensing matrix - Transform, for CS algorithm.
For this, the method of couple evaluation by Rate-Distortion curve was used. The experiments were carried out on two test images, namely, cameraman and Lena.

As tested sensing matrices we recall: Binary Random, Binary Sparse, and Low Density Parity Code (LDPC); and as transform, we mention: Discrete Cosine Transform, Wavelet Transform, and Total Variation (TV).


The softwares used in these tests are CS Toolbox and L1 Magic.
The solution was to use LDPC as the Sensing Matrix and TV as the Transform.
REFERENCES:
  1. M. Unser, Sampling - 50 Years after Shannon, Proc. of the IEEE, 88(4), 569–587 (2000)
  2. R.Baraniuk, V.Cevher, M.Duarte, Model-Based Compressive Sensing, IEEE Transactions on Information Theory 56(4) (2010)
  3. R.Baraniuk, V.Cevher, Ma.Duarte, C.Hegde, Model-based Compressive Sensing Toolbox v1.1. » Link to download the CS Toolbox, from Rice University
  4. Needell, D., Tropp, J. A., CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. ACM Technical Report 2008--01, California Institute of Technology, Pasadena (July 2008)
  5. J. A. Tropp and A. C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, IEEE Trans. Info. Theory, 53(12), 4655–4666 (2007)
  6. G. Cormode and S. Muthukrishnan, Combinatorial algorithms for compressed sensing, Technical report, DIMACS (2005)
  7. M. Iwen, A deterministic sub-linear time sparse Fourier algorithm via non-adaptive compressed sensing methods, Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008)
  8. Graeme Pope, Compressive Sensing. A Summary of Reconstruction Algorithms, Masters Thesis, Department of Computer Science Eidgenossische Technische Hochschule, Zurich (2009)
∴ Facts
Title: Compressive THz Imaging and Hadamard Spectroscopy for Space Applications
Project No: 17/19.11.2012
Project type: CDI STAR Project
Starting date: Nov 2012
Duration: 36 months
Partners: 2
INFLPR - Coordinator
CEO Space Tech - Partner
⇒ Latest News