Sunday, May 30, 2010

Compressed Sensing or Inpainting ? Part I





Since the Wired article came out, I and others have been of two minds about what compressive sensing is and how it can be portrayed to a wider audience. First to clear up the subject, I asked Jarvis Haupt the following question:
Dear Jarvis,

I just realized you were the person behind the Obama picture for the Wired article. Could you be kind enough and tell me what operation you did on this example? Right now, I can think of two:
  • Either you took a fourier transform of the Obama picture and then undersampled in the fourier space to get different levels of approximation of the full image
  • or you stayed in the pixel space and you essentially removed pixels in the original image. You then used an l_1 reconstruction with the sensing matrix being really a mask with zeros for those removed pixels.
In the former case, it would not fit too well because the lower resolution picture seems to clearly show missing pixels in the real space. The latter case might look like a more traditional inpainting process....
To what Jarvis kindly responded with:
Hi Igor,

Thanks for getting in touch. We did indeed use the second method you described for the example -- we randomly deleted pixels in the original image to obtain the "compressed" representation, then reconstructed assuming sparsity in a wavelet basis. The intermediate images were obtained essentially by using large(r) tolerance parameters for the solver. If you're interested in playing around with the code, I have posted it on under the "News" heading on my website (www.ece.rice.edu/~jdh6).

It is worth noting, as you point out, that what we did for this example fundamentally amounts to a kind of inpainting process. In that sense, there are a variety of existing techniques that could be employed for this kind of recovery task. Our goal here was only to provide an illustrative visual example of CS for the intended (diverse) audience.

Best regards,
Jarvis

The code used is here. It makes use of the GPSR code and the wavelet library at Rice. Thanks Jarvis for making the code available. Equivalently, Laura Balzano made available the code for the compressive sensing audio examples featured in the NPR piece.

4 comments:

Anonymous said...

I believe they did this experiment instead of "true" CS because an average Wired reader cannot understand the concept of random projections.

So they used random sub-sampling instead of random projection. Which does not make sense from CS perspective because pointwise measures are highly coherent with fine scale wavelets.

Igor said...

Anonymous,

Thanks for the feedback, as you can probably notice, this is part I. I am going to address your point but probably not in the direction you took. Lots of fun ahead :)

Cheers,

Igor.

Anonymous said...

The link pointing to the source code is incorrect :
http://www.blogger.com/goog_432066419

Igor said...

Thanks! It's fixed now.


Igor.

Printfriendly