Sign in to follow this  
redtea

Compressive Sensing

Recommended Posts

Ok, I'll bite again.

Let's say you want to compress an animation channel for a game. Would compressive sensing be fast enough to use at runtime? The articles talk about the various assumptions about the data, do you think motion capture / hand animation fits with these assumptions to make CS worthwhile here?

Share this post


Link to post
Share on other sites
Well compression of terrain maps. Compression of game state for transmission over the internet. Game AI where you would learn low dimensional manifolds from large but sparse data sets. What's the use in getting out of the bed in the morning?

Share this post


Link to post
Share on other sites
Well, there are plenty of situations where getting up in the afternoon is a provably optimal behavior :-)

The same goes for compressive sensing, if you're going to claim it's a good thing for games, then a bit more information is necessary. In particular my two original questions:

Quote:

Let's say you want to compress an animation channel for a game. Would compressive sensing be fast enough to use at runtime? The articles talk about the various assumptions about the data, do you think motion capture / hand animation fits with these assumptions to make CS worthwhile here?


Alex

Share this post


Link to post
Share on other sites
Quote:
Original post by redtea
Well compression of terrain maps. Compression of game state for transmission over the internet.

I don't think the cited technique is suited for these tasks which already benefit from traditional compression methods. As far as I can tell the main benefit is to avoid requiring a high resolution (and largely redundant) sample up front, which is not a problem with the examples given.

Share this post


Link to post
Share on other sites
I'm a rational person (I like to think). Maybe CS is not particularly relevant to games but it is better than another message on A* is it not?
I present it as an intellectual curiosity, if you like.
If you can use CS/Random projection to learn low dimensional manifolds then that is potentially a disruptive technology. We do live in a sparse world, the number of 256*256 images that represent anything understandable divided by the number of 256*256 images you can make at random is a number very, very close to zero.
However I take it a practical point that there may be nothing in CS that is of use in games yet.

Share this post


Link to post
Share on other sites
I certainly appreciate you posting on different topics; thanks for that!

However, the fact that you're so defensive rather than answering my simple questions leaves me very suspicious...


Once again, would it be fast enough for animation decompression at runtime, and does motion capture data fit well with the assumptions made by CS?

Alex

Share this post


Link to post
Share on other sites
Quote:
Original post by alexjc
Once again, would it be fast enough for animation decompression at runtime, and does motion capture data fit well with the assumptions made by CS?


To me, CS seems very cool, but for your mocap example it looks like a round peg in a square hole. It's not meant to be a general purpose compression algorithm, but a smart way of -- as the name says -- doing sensing.

The whole point of compressive sensing is that you can avoid taking tons of samples of the environment. A motivating question is, "Why do digital cameras acquire millions of samples of an image only to throw most of that data away with JPEG compression?" But for your mocap example, you already have the samples!!

Anyway, to answer your questions...

Sampling with CS is very fast of course, but reconstruction is the solution to a convex optimization problem and therefore slower*. Also, it's a batch process; it works on signals-as-a-whole, not individual samples. This throws a small wrench into your "on the fly" idea. That said, you could of course chop a signal into chunks or otherwise limit the support of your basis vectors, and operate on pieces independently.

* That said, convex optimization can be done quite fast these days!! In fact I attended a presentation by Stephen Boyd where he talked about a "convex program compiler" (I don't remember his precise phrase) that generates C code tailored to the specific sparsity patterns of a given convex optimization problem; with this he was able to generate each sample of a control signal for a mechanical system (at some reasonably-high rate) as a solution to a separate convex problem. So it is possible to do this quite fast.

Would y'all agree with this assessment?

Share this post


Link to post
Share on other sites
Thanks for your thoughts Emergent. My line of thinking was that there are always too many samples (60-120 Hz) reducing samples could/should be as sensible as compression. I think it is entirely fair to compare CS to other compression techniques since that's the most obvious application for games. (Even the CS literature emphasizes the efficiency of compression.)

red_tea suggested compression of terrain_maps. I guess you disagree with that application too?

Alex

Share this post


Link to post
Share on other sites
Quote:
Original post by alexjc
Thanks for your thoughts Emergent. My line of thinking was that there are always too many samples (60-120 Hz) reducing samples could/should be as sensible as compression. I think it is entirely fair to compare CS to other compression techniques since that's the most obvious application for games. (Even the CS literature emphasizes the efficiency of compression.)

red_tea suggested compression of terrain_maps. I guess you disagree with that application too?

Alex


So, I'm not really expert on this so maybe I'm being too opinionated... and I think my comments are based as much on how compressive sensing is sold in papers as on the actual math going on. But my gut tells me that, if you have all the data sitting in front of you, you might as well use a traditional compression algorithm -- since whereas compressive sensing is only probably good (albeit admittedly with extremely high probability); traditional algorithms are deterministically good. And it seems you should always be able to take advantage of full knowledge of the data (which compressive sensing doesn't have) to make a better algorithm.

But hey, maybe I'm misguided. Like I said, I've only skimmed a paper or two on it. If I'm wrong and you have some examples showing that it's effective as a general-purpose lossy compression scheme, I'd be curious to see them.

For now, however, I'll go with my gut. :-)

Share this post


Link to post
Share on other sites
I don't know much about CS, but I know a couple of things about L1 optimization, which I think is closely related.

The idea is always that you have a linear problem with more equations than data points. Obviously, there will be many solutions to such a system. The trick is that in some sense the most natural solution is the one with the fewest non-zero coefficients. You can word that as finding the solution with the smallest L0 norm. This turns out to be a difficult problem, but you can find the solution with the smallest L1 norm as a proxy, and under quite general conditions you'll get a solution that is small in the L0 sense. The advantage is that L1 optimization can be implemented as a linear programming problem, which is tractable.

CS happens to be a curious application of this method, which can come in handy in situations where there is a cost per sample that we would rather avoid. While this is very interesting, I can't imagine what part of game dev it could apply to.

I can see how L1 optimization could be used for filtering animation data and removing spikes, but not for compression per se.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this