Thursday, July 21, 2011

Compressive Sensing in Bandwidth-Limited Media

You don't have to have a space probe near Saturn, or Herschel at L2 to be limited by bandwidth issues, here are two other areas that are traditionally limited in bandwidth by the medium and where compressive sensing solutions are being investigated:

In the underwater video case, there is a short attempt at comparing MPEG4 with compressed sensing (see section 2.3.3) and as expected with a plain vanilla compressive sensing approach, you cannot get better or rival MPEG4 (0.45% compression ratio versus 15% for CS). It need to be said often, plain vanilla CS will not compete head to head with MPEG4. The current expectation though would be for some sort of structured sparsity to actually get to the numbers of MPEG4. 

I am much more endeared by the prospect of CS being useful in the home though. PLC is a very old technology (my parents were using audio based PLC systems forty years ago) and it would be an interesting twist if some of this technology could come out of the niche market it is in thanks to new techniques like compressive sensing.

Especially, if CS could use the framework developed in cognitive radio (that seems to go nowhere for broadcast if I am reading Gonzalo Vazquez-Vilar's blog correctly)


Eric Tramel said...

It also doesn't help that the comparison in that thesis was against the most strawman of CS video recovery approaches :(

But, then again, our best stuff doesn't top MPEG-4 anyway (as far as I'm aware), it would just make it look like less of a thrashing :P

Igor said...


Using the most advanced techniques in cs video compression what sort of compression ratio would you attain ?


Eric Tramel said...
This comment has been removed by the author.
Eric Tramel said...

It depends on how you achieve the quantization of the measurements. This is still a pretty open question. Since there isn't really a set way, most of my thinking is still in measurements to quality rather than bits to quality.

It all depends on how much motion you have going on in the sequence as well...low motion is pretty easy, in these settings you can get low to no perceptual difference (~ 40dB PSNR) at around 20% sub-sampling (M/N). Scenes with more complicated motion seem to need on the order of ~50% subsampling for the same quality.

If you don't mind a perceptual quality hit, then you can go lower, something like 10% subsampling for a quality in the range of 30-35 dB PSNR for most of the sequences I've tested.

In the end though, for any kind of "real compression" you'll need to tackle the quantization problem. This is where bits get gobbled up since the CS measurements have a much larger dynamic range. Also, using too few bits can cause additional error (problematic when you're already using so few measurements).

Most simple approaches I've seen use something between 8 and 16 bit uniform scalar quantization for measurements. If you tailor your recovery procedure to quantization step size & error (I'm thinking of the 1-bit CS and other quantized CS approaches), then you can lower the BPM and get acceptable quality.

So, improvement in this area can be gained from improving the hard coding side (i.e. quantization strategies to reduce the BPM) and from improving the video recovery model (To increase the dB per M): frame prediction, 3D transforms, motion aided transforms, geometrical approaches (ala Frossard et al @ EPFL), warping, manifolds, etc.

JM Thiesse said...

Interesting post!
First, note that H.264/AVC will have a successor (HEVC) which will be 50% better in compression so even if CS comes nearer to MPEG-4, it will be far from HEVC...

Second, I'm agree with the quantization problem which seems difficult to combine with CS approach.
Also, does this experiments takes into account the transmission of the "sensing mask" to believe decodable? This seems to be very expensive in addition of the measurements?

Third, an other solution is to define CS as a coding mode through others classical modes (Intra, Inter). This as been tried by someones (J.Sole) and myself but remains the quantization process!

@Eric and others: I'm interested to talk and work on this subject if you want!

Igor said...

Jean-Marc your web address is not


JMThiesse said...

Thanks Igor and sorry for the mistake.

A question which raises to me about Eric'post : which range of bitrate did you associate to each "number of measurements" to present your work? (ie: a low bitrate for a cif sequence = ? measurements)