Summary of Block Compressed Sensing on Image

Last article, I briefly introduce existing cs method on image. This article aims to summary how block cs worked on image.

Before I go on, I need to introduce something about measurement matrix.

Currently, there are several way to generate a measurement matrix. For a complete list of possible measurement matrix, please refer to  https://sites.google.com/site/igorcarron2/cs . Here I only discuss three of them: 

• Random Fourier Ensemble: The signal is a discrete function f on Z/NZ, and the measurements are the Fourier coefficients at a randomly selected set Omega of frequencies of size M ( A is an M x N matrix.)
• Gaussian ensemble: A is an M x N matrix (M x N Gaussian variables).
• Bernoulli ensemble: A is an M x N matrix (M x N Bernoulli variables). 

It should be noticed that for most of the case, the measurement matrix should be orthonormal.

For 1d signal, Gaussian ensemble is enough to reconstruct the signal[1]. However, for 2d image,  N can be fairly large, which makes the storage and computations of a Gaussian ensemble very difficult. Thus, [2] suggested to apply a partial random Fourier matrix。For sparse basis, it employed wavelet. Besides, it uses min tv instead of l1norm as recon strategy. However, I've found no simulation code available for [2].

Another possible way to solve the problem addressed before is to sample the image block by block. This is quite similar with what JPEG did. [3] gives out corresponding research. For measurement matrix, the paper uses i.i.d Gaussian ensembles. For sparse basis, it uses LT. The reconstruction is based on PoCS and Hard Thresholding . No simulation code available now. But you may refer to https://sites.google.com/site/igorcarron2/cscodes. There is a code called sbhe.m, 

Implemented from Fast compressive imaging using scrambled block Hadamard ensemble by Lu Gan, Thong Do and Trac Tran. This is another algorithm proposed by the same author. It may help you.

To improve the performance of [3], [4] proposed to first decompose the coefficients into dense and sparse component. For dense component, it uses conventional encoding; for sparse component, it uses cs. For measurement matrix, it didn't clearly indicate in the paper. But from inference, it should use i.i.d Gaussian ensembles as in [3]. It still employs wavelet as sparse basis. The reconstruction is based on PoCS[2] and prediction by adaptive interpolation. The paper gives out the detailed reconstruction scheme. No simulation code available now.


After that, [5] gives some interesting simulation results. Here for measurement matrix, it should still use i.i.d Gaussian ensembles.But for sparse basis, it proposed to use Directional Transformation(CT and DDWT).The reconstruction is based on SPL. Simulation code is available at http://www.ece.msstate.edu/~fowler/BCSSPL/. Besides I am quite interested in analyzing the EXPERIMENTAL RESULTS part in this paper. It compares with several other methods.
1. To compare the effectiveness of CT and DDWT, it compares to BCS-SPL-DWT, BCS-SPL-DCT. The simulation code is not available now.
2. To compare SPL with TV, it compares with BCS-TV. The implementation is using l1-Magic(http://acm.caltech.edu/l1magic/). I have implemented the code at http://www.ualberta.ca/~hfang2/pub/Block CS-TV.zip .
3. To compare SPL with GPSR and SAMP, it uses the implementation provided by their respective authors(http://www.lx.it.pt/~mtf/GPSR/ http://thongdojhu.googlepages.com/samp_intro/ ).

The last one is [6]. It perform random permutation among blocks to achieve better performance. It uses DCT as sparse basis. For measurement matrix, it uses i.i.d Gaussian ensembles.It uses min l1-norm instead of min tv as reconstruction method. I recommend you use cvx_toolbox(http://cvxr.com/cvx/download/) for simulation.

If you find any simulation code published, or any error in the article, please contact me.
Thanks a lot.


[1] Robust uncertainty principles: Exact signal reconstruction form highly incomplete frequency information
[2] Practical Signal Recovery from Random Projections
[3] Block Compressed Sensing of Natural Images
[4] Image Representation by Compressed Sensing
[5] Block compressed sensing of images using directional transforms
[6] Compressive Sampling With Coefficients Random Permutations for Image Compression