Recovering Data From Noise

← Back to Stories (view on slashdot.org)

Posted by kdawson on Tuesday March 2, 2010 @01:14AM from the sparse-world-after-all dept.

An anonymous reader tips an account up at Wired of a hot new field of mathematics and applied algorithm research called "compressed sensing" that takes advantage of the mathematical concept of sparsity to recreate images or other datasets from noisy, incomplete inputs. "[The inventor of CS, Emmanuel] Candès can envision a long list of applications based on what he and his colleagues have accomplished. He sees, for example, a future in which the technique is used in more than MRI machines. Digital cameras, he explains, gather huge amounts of information and then compress the images. But compression, at least if CS is available, is a gigantic waste. If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? ... The ability to gather meaningful data from tiny samples of information is also enticing to the military."

8 of 206 comments (clear)

Min score:

Reason:

Sort:

CSI by fuzzyfuzzyfungus · 2010-03-02 01:15 · Score: 5, Funny

Enhance!
Why not... by jbb999 · 2010-03-02 01:19 · Score: 4, Insightful

If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? ..

Because it's hard to know what is needed and what isn't to produce a photograph that still looks good to a human, and pushing that computing power down to the camera sensors where power is more limited than a computer is unlikely to save either time or power.
1. Re:Why not... by Chrisq · 2010-03-02 01:28 · Score: 4, Insightful
  
  I think you are missing the point, throwing away 90% of the image was a demonstration of the capabilities of this algorithm. You would use it where you have only managed to capture a small amount of data, not capture the lot and throw away 90%.
2. Re:Why not... by eldavojohn · 2010-03-02 01:31 · Score: 4, Interesting
  
  If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? ..
  Because it's hard to know what is needed and what isn't to produce a photograph that still looks good to a human, and pushing that computing power down to the camera sensors where power is more limited than a computer is unlikely to save either time or power.
  If you read the article, the rest of that quote makes a lot more sense. Here it is in context:
  
  If your camera is going to record a vast amount of data only to throw away 90 percent of it when you compress, why not just save battery power and memory and record 90 percent less data in the first place? For digital snapshots of your kids, battery waste may not matter much; you just plug in and recharge. “But when the battery is orbiting Jupiter,” Candès says, “it’s a different story.” Ditto if you want your camera to snap a photo with a trillion pixels instead of a few million.
  So, while this strategy might not be implemented in my Canon Powershot anytime soon, it sounds like a really great idea for exploration or just limited resources in general. I was thinking more along the lines of making really crappy resolution low power cameras that are very cheap but distributing them with this software that takes the images on your computer and processes them to make them highly defined images.
  
  --
  My work here is dung.
3. Re:Why not... by Idbar · 2010-03-02 01:42 · Score: 4, Interesting
  
  In fact, it's expected to be used to increase the aperture of cameras. The advantage of this, is that using random patterns you could be able to determine the kernel of the convolving pattern in the picture, therefore, you would be able to re-focus the image after it was taken. In regular photography that kernel is normally Gaussian and very hard to de-blur. But using certain patterns when taking the picture (probably implemented as micro-mirrors), you could, easily do this in post processing.
Re:I am a bit worried about the "fill in the shape by Yvanhoe · 2010-03-02 01:30 · Score: 4, Insightful

Exactly. This algorithm doesn't create absent data nor does it infer it, it just makes the uncertainties it has "nicer" than the usual smoothing.

--
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
Re:Demo image by sammyF70 · 2010-03-02 01:36 · Score: 4, Informative

indeed. check the caption :
"Photos: Obama: Corbis; Image Simulation: Jarvis Haupt/Robert Nowak" (emphasis added by me)

--
"DRM is like the Ford Pinto: it's a smooth ride, right up the point at which it explodes and ruins your day."-C.Doctorow
Not smoothing by nten · 2010-03-02 03:08 · Score: 4, Insightful

The article was a bit poor. The data sets aren't really incomplete in most cases. They only seem that way from a traditional standpoint. The missing samples often contain absolutely no information, in which case the original image/signal can be reconstructed perfectly. In brief, nyquist is a rule about sampling non-sparse data, so if you rotate your sparse data into a basis in which it is non-sparse, and you satisfy the nyquist rule in that basis (though not in the original one), you are still fine.
I like this link better l1 magic

--
refactor the law, its bloated, confusing and unmaintainable.