Slashdot Mirror
Recovering Data From Noise
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."
Enhance!
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.
The algorithm then begins to modify the picture in stages by laying colored shapes over the randomly selected image. The goal is to seek what’s called sparsity, a measure of image simplicity.
The thing is in a medical image couldn't that actually remove a small growth or lesion? I know the article says:
That image isn’t absolutely guaranteed to be the sparsest one or the exact image you were trying to reconstruct, but Candès and Tao have shown mathematically that the chance of its being wrong is infinitesimally small.
but how often do analysis like this make assumptions about the data, like you are unlikely to get a small disruption in a regular shape and if you do it is not significant.
on the bright side, when Moore's law allows real-time processing we can look forward to night vision cameras which really are "as good as daylight", and for this sort of application the odd distortion really won't matter so much.
The military probably wants the ability to send/receive without revealing the data or the location of its source to the enemy. For example, its nuclear subs need to surface in order to communicate, and they don't want the enemy to be able to use triangulation to pinpoint the location of the subs. So, they make the data they're transmitting appear as noise. That way if the enemy happens to be listening on that frequency, they don't detect anything.
I seriously doubt that the Obama demo image is real. There is no way that the teeth and the little badge on his jacket are produced, and that no visual artifacts were created.
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.
After applying the Noise filter to mess up my image I hit Undo and my image is back to normal.
If something is so important that you feel the need to post it on the internet... It probably isn't that important.
Did we really need to refer to it as CS in the summary? A quick glance of the summary could lead one to think that this guy is the inventor of Computer Science, rather than the correct Compressed Sensing... In the summary of an article that is concerned (in part) with maintaining information after compression, we lost quite a bit of information in abbreviating the name of his algorithm.
Damn_registrars has no butt-hole. Damn_registrars has no use for a butt-hole.
Does this only apply to image data, or will we be able to use this to clean up other databases? Will it work with sampled sounds? Names and addresses and inventory?
Of course not. It's not magic. There are certain assumptions that can be made about most real-life images, mainly that they have small total variance. That means they have large areas of near-constant intensity/color distribution separated by interfaces with large jumps (like a cartoon image would have).
Though this method uses the l_1 norm and not total variation.
More importantly, HOW does it work?
See here.
MOD PARENT UP for this: "This algorithm doesn't create absent data nor does it infer it, it just makes the uncertainties it has "nicer" than the usual smoothing."
Fraud alert: The title, "Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples" should have been "A better smoothing algorithm".
The description of the algorithm in the article is quite poor. To reconstruct an MR image you effectively model it with wavelet basis functions, subject to someconstraints: a) the wavelet domain should be as sparse as possible, b) the Fourier coefficients you actually acquired (MR is acquired in the Fourier domain, not the image domain) have to match and usually c) the image should be real. You often also require that the total variation of the image should be as low as possible as well.
Since the image is acquired in the Fourier domain, every measurement you make contains information about all the pixels in the image. For reasonable* under acquisitions CS can produce a perfectly reconstructed image.
* the exact limits of "reasonable" are still under investigation, but typically you only need to acquire about a quarter of the data to be pretty much guaranteed you'll be able to get a perfect reconstruction.
Here's how Compressed Sensing works with standard JPGs.
First the program takes the target JPG (which you want to be very large), and treats it as random noise. Simply a field of random zeros and ones. Then, within that vast field, the program selects a pattern or frequency to look for variations in the noise pattern.
The variations in the noise pattern act as a beacon - sort of a signal that the payload is coming. Common variations include mathematical pulses at predictable intervals - say something that would easily be recognizable by a 5th-grader, like say a pattern of prime numbers.
Then it searches for a second layer, nested within the main signal. Some bits are bits to tell how to interpret the other bits. Use a gray scale with standard interpolation. Rotate the second layer 90 degrees. Make sure there's a string break every 60 characters, and search for an auxiliary sideband channel. Make sure that the second layer is zoomed out sufficiently, and using a less popular protocol language; otherwise it won't be easily recognizable upon first glance.
Here's the magical part: It then finds a third layer. Sort of like in ancient times when parchment was in short supply people would write over old writing... it was called a palimpsest. Here you can uncompress over 10,000 "frames" of data, which can enhance a simple noise pattern to be a recognizable political figure.
Further details on this method can be found here.
--
Recycle when possible!
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.
After cropping, I may end up with a 1-2 megapixel image (sometimes much lower)
Try image stacking. A program I've used successfully for this is PhotoAcute. Provided your body+lens combo is in their database, you can stack multiple near-identical images (use Burst or Auto-bracket mode) and get "super resolution". Of course, this doesn't work so well if your subject is moving. If your body+lens combo isn't in their database, you can volunteer a couple hours of your time to make a set of ~ 100 specific images they can use to create a profile for your gear. If they accept it, they'll offer you a free license for the software. I have no connection with the company other than being a satisfied customer.
--
.nosig