Beta

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Recovering Data From Noise

kdawson posted more than 4 years ago | from the sparse-world-after-all dept.

Math 206

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."

cancel ×

206 comments

Sorry! There are no comments related to the filter you selected.

CSI (5, Funny)

fuzzyfuzzyfungus (1223518) | more than 4 years ago | (#31328740)

Enhance!

Re:CSI (2)

El_Muerte_TDS (592157) | more than 4 years ago | (#31328780)

Enhance!

Re:CSI (0)

Anonymous Coward | more than 4 years ago | (#31329052)

Rotate!

Re:CSI (1)

ceoyoyo (59147) | more than 4 years ago | (#31328962)

Seriously, watching a CS reconstruction is actually visually more impressive than what they do on CS. I coded up a demo and everyone calls it the magic algorithm.

Re:CSI (0)

Anonymous Coward | more than 4 years ago | (#31329150)

Pics or it didn't happen!

Re:CSI (2, Interesting)

ceoyoyo (59147) | more than 4 years ago | (#31329650)

Your AC wish is my command [robbtech.com] .

Re:CSI (0)

Anonymous Coward | more than 4 years ago | (#31329402)

Which keyboard button did you choose for the Kill Switch?

Deckard (1, Funny)

Anonymous Coward | more than 4 years ago | (#31329188)

Enhance 34 to 36. Pan right and pull back. Stop. Enhance 34 to 46. Give me a hard copy right there.

Re:CSI (1)

halcyon1234 (834388) | more than 4 years ago | (#31329252)

[geek mode]

It actually reminds me more of that ST:TNG episode with Yuta. They're able to take a picture with someone's face half-blocked out by scenery and other people. They're able to reconstruct the rest of the face based on the patterns that are there.

Overview of Algorithm (3, Funny)

Chapter80 (926879) | more than 4 years ago | (#31329482)

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. [imsdb.com]

--
Recycle when possible!

Why not... (4, Insightful)

jbb999 (758019) | more than 4 years ago | (#31328778)

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.

Re:Why not... (0)

Anonymous Coward | more than 4 years ago | (#31328848)

Whoosh.

(a) JPEG doesn't know either, as you can tell from JPEG images
(b) RTFA

Re:Why not... (3, Informative)

petermgreen (876956) | more than 4 years ago | (#31329244)

(a) JPEG doesn't know either
JPEG is built on the assumption that the higher frequency components are less important, so it spends less bits on representing those components than it does on the lower frequency ones.

It's a pretty crude model (not least because of the block based architecture that makes it simple to implement but introduces artifacts at block boundries) but it still does a lot better than just throwing away pixels and/or reducing the bits per pixel in the original image.

Re:Why not... (4, Insightful)

Chrisq (894406) | more than 4 years ago | (#31328856)

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%.

Re:Why not... (-1, Troll)

Anonymous Coward | more than 4 years ago | (#31329424)

You would use it where you have only managed to capture a small amount of data, not capture the lot and throw away 90%.

Well, I guess that rules out its usefulness for Creation Scientists.

Re:Why not... (0, Troll)

Chrisq (894406) | more than 4 years ago | (#31329456)

You would use it where you have only managed to capture a small amount of data, not capture the lot and throw away 90%.

Well, I guess that rules out its usefulness for Creation Scientists.

They have the opposite problem. They want to take a lot of real data and process it in such a way that the result bears no resemblance to reality.

Re:Why not... (4, Interesting)

eldavojohn (898314) | more than 4 years ago | (#31328888)

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.

Re:Why not... (1)

hitmark (640295) | more than 4 years ago | (#31328966)

so in other words, real life "zoom in and enhance"?

or could it get as far as a esper like system?

Re:Why not... (2, Interesting)

Bakkster (1529253) | more than 4 years ago | (#31329412)

Kind-of.

This technique is taking the noisy or incomplete data, and inferring the details already captured but only on a few pixels. So, if there's a line or square on the image but you only catch a few pixels on it, this technique can infer the shape from those few pixels. So, it will enhance the detail on forms you can almost see, but not create the detail from scratch.

Rather than 'enhancing' the image, a better term would be 'upsampling'. The example used in the article was of a musical performance. This technique could take a 44.1kHz sample of a musical instrument at 8-bit resolution and upsample it to 96kHz and 32-bit resolution. Since instruments create predictable frequencies (aside from percussion, the same frequency is usually present for many times the wavelength) the algorithm can determine which frequencies are present, at which times, and at which amplitude and phase. That information can then be used to 'fill in the gaps' more accurately than normal upsampling (usually done with a Sinc filter [wikipedia.org] ). However, it can't recreate information that wasn't recorded in the first place, so if the audio was recorded at 20kHz you would only get output of audio below 10kHz (the Nyquist frequency [wikipedia.org] in this case), although it's conceivable that even more advanced algorithms could infer these frequencies as most instruments have a predictable distribution of harmonics.

It also seems that most compression algorithms (JPG for example) would destroy these bits of detail that the algorithm would use, so raw data is likely to be needed in most cases. I'm just going off of my knowledge of DSP, I don't know any particulars of this technique beyond this article, but it looks legitimate and very useful as long as you aren't expecting CSI-level miracles.

Re:Why not... (1)

idontgno (624372) | more than 4 years ago | (#31329870)

Ok. The gross simplification makes this sound like pixel homeopathy. Or the Total Perspective Vortex. "We can reliably infer almost anything from almost nothing" lies down that road.

I remain unconvinced.

Re:Why not... (4, Interesting)

Idbar (1034346) | more than 4 years ago | (#31328992)

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:Why not... (3, Interesting)

girlintraining (1395911) | more than 4 years ago | (#31329714)

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.

You people think in such limited terms. The military uses rapid frequency shifting and spread spectrum communications to avoid jamming. Such technology could be used to more rapidly identify the keys and encoding of such transmissions, as well as decreasing the amount of energy required to create an effective jamming signal by several orders of magnitude across the spectrum used if any pattern could be identified. Currently, massive antenna arrays are required to provide the resolution necessary to conduct such an attack. This makes the jamming equipment more mobile, and more effective at the same time. A successful attack on that vector could effectively kill most low-power communications capabilities of a mobile force, or at least increase the error rate (hello Shannon's Law) to the point where the signal becomes unusable. The Air Force is particularily dependent on realtime communications that rely on low-power signal sources.

If nothing else, getting a signal lock would at least tell you what's in the air. Stealth be damned -- you get a signal lock on the comms, which are on most of the time these days, and you don't need radar. Just shoot in the general direction of Signal X and *bang*. Anything that reduces the noise floor generates a greater exposure area for these classes of sigint attacks. Cryptologists need not apply.

Re:Why not... (0)

Anonymous Coward | more than 4 years ago | (#31330016)

Yes, true, most people here think not in terms of applications for killing people.

Re:Why not... (1)

Idbar (1034346) | more than 4 years ago | (#31330048)

You people think in such limited terms.

I talk about what I know and I work on. I am not in the military, and couldn't care less about such kind of applications. Of course there are tons of applications, including several of dimensionality reduction for faster intrusion detection mechanisms, but I find photography more appealing.

Re:Why not... (2, Interesting)

gravis777 (123605) | more than 4 years ago | (#31329526)

Truthfully, I was thinking along the lines of taking a high resolution camera and making it better, rather than taking a low resolution camera and making it high. My aging Nikon is a 7.1 megapixel, with only a 3x optical zoom. There have been times I wanted to take a picture of something quick, so do not necessaraly have time to zoom or move closer to the object. After cropping, I may end up with a 1-2 megapixel image (sometimes much lower). For the longest, I thought I just needed more megapixels, and a faster and higher powered optical zoom. However, looking at the pictures I have, I am like, if someone could just come up with something to make this look better... There is usually plenty of detail there for my eye, if something would come in and soften jaggie edges, sharpen the overall picture, and understand textures (such as clothing)...

Truthfully, with what I just talked about, I am looking for them to implement this in Photoshop so I can clean up some existing crappy photography of mine.

Re:Why not... (1)

SQLGuru (980662) | more than 4 years ago | (#31329902)

And in fact, were that camera orbiting Jupiter, it would only have to send the 10% data back to Earth where the reconstruction could take place. It turns into "real-time" compression.

Re:Why not... (1, Informative)

Anonymous Coward | more than 4 years ago | (#31329462)

You have to understand that the digital camera example is a toy example, i.e., the theory works beautifully but it has little use in practice (in this particular configuration). The other example that is mentioned in the article (MRI) better showcases the advantages of CS. When it takes about 200s to take a full acquisition of the image, you can take much fewer measurements in ~40s and then reconstruct the image using a CS algorithm. There are other examples where using CS brings similar advantages in practice; mostly when acquiring a single measurement is either expensive or takes a long time.

Re:Why not... (2, Interesting)

Matje (183300) | more than 4 years ago | (#31329628)

RTFA that's the point of the algorithm: the camera sensors don't need to calculate what is interesting about the picture, they just need to sample a randomly distributed set of pixels. The algorithm calculates the highres image from that sample.

The idea behind the algorithm is really very elegant. To parafrase their approach: imagine a 1000x1000 pixel image with 24 bit color. There are 24 ^ 1000000 unique pixel configurations to fill that image. The vast majority of those configuration will look like noise. In real life you generally take pictures of non-noise things, like portraits etc. You might define a non-noise image as one where knowing the actual value of a given pixel allows a probability of predicting the value of a neighboring pixel that is greater than chance. A noisy image is one where knowing a given pixel value gives you no information about neighboring pixels at all.

The algorithm provides a way to distinguish between image configurations that depict random noise and those that depict something non-random. Since, apparently, the ratio of non-random image configurations is so small compared to the noisy image configurations, you need only a couple of hints to figure out which of the non-random image configurations you need. What the algoritm does is take a random sample of a non-random image (10% of the original pixels), and calculates a non-random image configuration that fits the given sample. Even though in theory you might end up with Madonna from a picture of E-T, in practice you don't (and I believe they claim they can prove that the chance of accidentally ending up with Madonna is extremely small).

It's all about entropy really.

Re:Why not... (1)

yodleboy (982200) | more than 4 years ago | (#31329832)

"Even though in theory you might end up with Madonna from a picture of E-T"

and how would anyone be able to tell the difference?

i do hope something like this makes it into a photoshop plugin.

Re:Why not... (2, Interesting)

wfolta (603698) | more than 4 years ago | (#31329802)

Actually, you don't process and throw away information. You are not Sensing and then Compressing, you are Compressed Sensing, so you take in less data in the first place.

A canonical example is a 1-pixel camera that uses a grid of micro-mirrors, each of which can be set to reflect onto the pixel or not. By setting the grid randomly, you are essentially doing a Random Projection of the data before it's recorded, so you are Compressed Sensing. With a sufficient number of these 1-pixel images, each with a different random mirror setup you can reproduce the original image to some level of accuracy, using fewer bits than a JPEG/etc of similar quality. Unlike JPEG, you are not taking in a full set of data, then compressing, so it takes LESS processing power, not more.

So you save in image transmission bandwidth if the sensor is, say, orbiting Jupiter. And you save energy expended in compressing the image. And you could perhaps afford to make a VERY expensive single pixel imager that has an incredibly wide frequency range, which might be prohibitively expensive, or even impossible to fabricate in a larger array.

Personally, I think there's a lot of hype to CS, but it's definitely not the same as JPEG/Wavelet/etc compression after taking a full-resolution image.

Wouldn't it be easier... (1)

bsDaemon (87307) | more than 4 years ago | (#31328792)

to just subscribe to Cinemax instead of going through all this trouble to de-scramble the pr0n?

Re:Wouldn't it be easier... (0)

Anonymous Coward | more than 4 years ago | (#31328932)

A true geek never pays for pr0n!

You Pr0n addicts (1)

Chrisq (894406) | more than 4 years ago | (#31329558)

You pr0n addicts should really get a grip on yourselves

..... oh wait!

Come again? (1)

Errol backfiring (1280012) | more than 4 years ago | (#31328824)

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? ..

That's what a digital camera is about, isn't it?

Re:Come again? (0)

Anonymous Coward | more than 4 years ago | (#31328862)

I don't know what he's on about. I shoot RAW.

Re:Come again? (1)

rnturn (11092) | more than 4 years ago | (#31329884)

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? ..

That's what a digital camera is about, isn't it?

Perhaps if you're using some low-end digital camera but not if your camera allows you to save images in RAW format. Sort of like it was in the days you might have spent in the darkroom: if it ain't on the negative you're not going to get it back in the darkroom. Why throw information away before even viewing it? The only reason to compress images (IMHO) is if you're going to put them up on a web site or transmit them via email. Yeah, compressed images allow you to save more on the memory card but memory card prices are such that you can throw a much bigger card than the one that shipped with the camera and shoot all day long. (I have an older camera that only takes up to 4GB cards and I still haven't been able to fill it up in less than a day.)

I guess I don't see the advantage to throwing away imagery information and praying that a mathematical algorithm might be able to get it back.

I am a bit worried about the "fill in the shapes" (3, Insightful)

Chrisq (894406) | more than 4 years ago | (#31328826)

From TFA

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.

Re:I am a bit worried about the "fill in the shape (4, Insightful)

Yvanhoe (564877) | more than 4 years ago | (#31328872)

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.

Typical science fraud (3, Interesting)

Futurepower(R) (558542) | more than 4 years ago | (#31329166)

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".

Re:Typical science fraud (0)

Anonymous Coward | more than 4 years ago | (#31329240)

Yeah, because as the typical Slashdotter, you're such an expert.

Re:Typical science fraud (3, Interesting)

timeOday (582209) | more than 4 years ago | (#31329936)

No, not just "nicer." It fills in the data with what was most likely to have been there in the first place, given the prior probabilities on the data. The axiom of being unable to regain information that was lost or never captured is, as commonly applied, mostly wrong. The fact is, almost all of our data collection is on samples that we already know a LOT about what they look like. Does this let you recapture a license plate from a 4 pixel image, no, but given a photo of Barack Obama's face with half of it blacked out, you can estimate with great accuracy what was in the other half.

Not smoothing (4, Insightful)

nten (709128) | more than 4 years ago | (#31329996)

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 [caltech.edu]

Fill in the blanks (1)

wurp (51446) | more than 4 years ago | (#31329586)

It started off with pixels missing; when done the pixels are filled. How is that not creating absent data by inferring it?

Any algorithm that generates more data than was sent in is inferring. That's not to say it isn't useful, but if, for example, all of the pixels of the bile duct blockage (FTFA) were missing, the picture would have to have been reconstituted with no blockage. If the only three pixels in an area were discolored, then that whole area (or some significant portion of it) would be discolored.

The algorithm is very impressive, but when you fill in the blanks, that's pretty much the definition of creating absent data. (Barring examples like e.g. knowing three values of a degree 2 polynomial and inferring the whole polynomial, but in cases like those the data you have really is a complete description.)

Re:Fill in the blanks (1)

Yvanhoe (564877) | more than 4 years ago | (#31329762)

The difference between inference and guessing is that in inference you use clues in the data you have in order to rebuild a data that is not measured. It is like using the movement in a video in order to infer the parameters of the lens used : the data is here, but you have to extract it from the other data it is mixed with.

1 bit in, 10 bits out does not mean that you have created 9 bits of correct data. Look at Obama's teeth in the example. The algorithm understands it is better to put white pixels instead of black one when it doesn't know the color, but the separation between the teeth is smoothed out. If he had a missing tooth it would be replaced. The idea that we could use this algorithm for medical diagnosis is just nonsense.

Re:Fill in the blanks (1)

wurp (51446) | more than 4 years ago | (#31329974)

I completely misread your response before your reply. We're arguing the same position :-)

Although I disagree regarding inference - it is inferring the absent data (my my definition of inference), and in some cases that will be useful. However, I suspect if used for medical images it would give confidence to a wrong answer more often than it would give enough information to get the right answer.

Re:I am a bit worried about the "fill in the shape (0)

Anonymous Coward | more than 4 years ago | (#31329090)

It is clear that in order for this to work it needs a "model" of the real world. In his simple case the model is "everything has smooth colours" which matches his test image really well. Trying to find an unexpected detail in a large image would be impossible with this model.

However if you have a good model of what you expect then it will probably find it. Much like voice compression is very efficient because we know what to expect, if you have a good model of what you expect it will reconstruct it from limited data.

From a legal point of view it is creating what you expect to find from nothing so it may have a tendency to find what you are expecting! So not much use in court where it just proves your assumptions.

Re:I am a bit worried about the "fill in the shape (0)

Anonymous Coward | more than 4 years ago | (#31329098)

The Medical Imaging has enough "artefacts" in the image as it is.

Re:I am a bit worried about the "fill in the shape (2, Insightful)

ceoyoyo (59147) | more than 4 years ago | (#31329206)

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.

Re:I am a bit worried about the "fill in the shape (1)

John Hasler (414242) | more than 4 years ago | (#31329340)

Perhaps we want cameras that produce Fourier coefficients instead of images?

Re:I am a bit worried about the "fill in the shape (1)

ceoyoyo (59147) | more than 4 years ago | (#31329842)

Some of the designs for CS cameras basically do just that. You can do CS just as well with images acquired in the image domain though, the intuitive reasoning for why it works just gets a little... less intuitive.

I'm not sure CS is going to quickly catch on in your common camera because it doesn't really solve a pressing problem but it will certainly find lots of applications.

Re:I am a bit worried about the "fill in the shape (1)

rickyars (619739) | more than 4 years ago | (#31329792)

i agree, the description of the algorithm is too vague to really understand what is going on.

30 seconds of googling turned up this brief lecture on compressed sensing. written for undergrads, "the prerequisites for understanding this lecture note material are linear algebra, basic optimization, and basic probability."
http://dsp.rice.edu/sites/dsp.rice.edu/files/cs/baraniukCSlecture07.pdf [rice.edu]

side note: rich baraniuk was one of the best professors i had in undergrad

Re:I am a bit worried about the "fill in the shape (1)

ZeroSumHappiness (1710320) | more than 4 years ago | (#31329510)

Why in the world would you use this in a medical image? That seems like quite the straw man.

Re:I am a bit worried about the "fill in the shape (1)

Chrisq (894406) | more than 4 years ago | (#31329572)

RTFA!

Re:I am a bit worried about the "fill in the shape (1)

ortholattice (175065) | more than 4 years ago | (#31329692)

The thing is in a medical image couldn't that actually remove a small growth or lesion?

While I'm certainly no expect on this, it seems almost everyone here is being mislead by the word "noise". From what I gather, this is not cleaning up noise, it is filling in missing pieces in data whose samples are assumed to be noise-free. This is drastically different from "smoothing" that is intended to filter out noise.

So, in the case of a small growth or lesion, as long as there is at least one sample of it that is different from the surrounding area, the "sparsity" (this is my guess based on a quick reading of the article and some related ones) would result in an identifiable spot of some kind. This would be due to the fact that that the one pixel sample of the lesion is different from its closest available neighbors. This difference would be assumed by the algorithm to be an accurate representation of that pixel, not a random speck of noise. So, something would show up, say a small blob, that would be obviously different in the reconstructed image. Now the less pixels you have of this lesion, the less accurate the shape and size of that blob will be, but nonetheless it is something that would stand out and warrant further investigation.

Re:I am a bit worried about the "fill in the shape (1)

ascari (1400977) | more than 4 years ago | (#31329898)

In the old movie "The Conversation" Gene Hackman walks right into that trap when he infers away all the nuances inside the spotty data of a surveillance recording. Two lessons: 1 - Same dangers, different application. 2 - Same fundamental method, different decade, nothing really new here.

Compressed message (0)

Anonymous Coward | more than 4 years ago | (#31328830)

fgr ts ot no bch!

Re:Compressed message (1)

theIsovist (1348209) | more than 4 years ago | (#31328910)

In all seriousness, the AC has a point. given 10% of anythingand extrapolating the other 90% is a difficult task at best. This is assuming that the 10% are the most important parts. As with all low res images, any subtleties will be lost.

Re:Compressed message (1)

ceoyoyo (59147) | more than 4 years ago | (#31329216)

No. For typically levels of undersampling CS reconstructs the image perfectly. Yes, it's not exactly intuitive, but it does work.

Military applications (3, Interesting)

rcb1974 (654474) | more than 4 years ago | (#31328842)

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.

forgot to mention... it works both ways (1)

rcb1974 (654474) | more than 4 years ago | (#31328876)

If the enemy uses this same technology against us, then the military wants to be able to recover as much information as they can.

Re:forgot to mention... it works both ways (1)

silverglade00 (1751552) | more than 4 years ago | (#31329758)

So then they are sending out noise and we are sending out noise. They are turning it back into the complete message and so are we. Back to square one, but at least we spent enough money to justify the budget.

applications (0)

Anonymous Coward | more than 4 years ago | (#31328854)

Digital photography - compensate for noisy sensors.

Code breaking

Code making

telecommunications

video compression

I see some really interesting products coming down the line.

Re:applications (1)

maxwell demon (590494) | more than 4 years ago | (#31329164)

This should be the perfect upscaling algorithm. Get perfect HD material from your old VHS cam!

Demo image (3, Insightful)

ChienAndalu (1293930) | more than 4 years ago | (#31328864)

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.

Re:Demo image (4, Informative)

sammyF70 (1154563) | more than 4 years ago | (#31328928)

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

Re:Demo image (0)

Anonymous Coward | more than 4 years ago | (#31329018)

Like CSI they started at image 5, and worked backwards..

Re:Demo image (1, Insightful)

Anonymous Coward | more than 4 years ago | (#31329548)

It absolutely could be, just read the article: "Eventually it creates an image that will almost certainly be a near-perfect facsimile of a hi-res one."!

Where's the plug-in? (1)

voodoo cheesecake (1071228) | more than 4 years ago | (#31328882)

It would be nice to have a GIMP plug-in for this.

Questions... (0, Redundant)

mcgrew (92797) | more than 4 years ago | (#31328944)

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?

More importantly, HOW does it work?

Sorry of TFA answers these questions, but I've never known Wired to get into any kind of detail on stuff like this.

Re:Questions... (1)

Idbar (1034346) | more than 4 years ago | (#31329084)

It works at the moment of acquiring the signal. Let's say for example that when you use Fourier you project your signal into the frequency domain using sinusoidals as orthogonal bases. In this case, you project into another domain using random orthogonal projections.

Thus, "compressing" signals requires of a knowledge of the sparsity of the signal acquired, that helps to design those "random" bases. Using those random bases to acquire the signal ensure that it will be recoverable.

Re:Questions... (2, Insightful)

azaris (699901) | more than 4 years ago | (#31329158)

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 [arxiv.org] .

Re:Questions... (1)

Bakkster (1529253) | more than 4 years ago | (#31329576)

More importantly, HOW does it work?

Sorry of TFA answers these questions, but I've never known Wired to get into any kind of detail on stuff like this.

From TFA:

The key to finding the single correct representation is a notion called sparsity, a mathematical way of describing an image’s complexity, or lack thereof. A picture made up of a few simple, understandable elements — like solid blocks of color or wiggly lines — is sparse; a screenful of random, chaotic dots is not. It turns out that out of all the bazillion possible reconstructions, the simplest, or sparsest, image is almost always the right one or very close to it.

So any dataset that is likely to be smooth can be improved with this technique. They give the example in TFA of piano music (except for percussion, the frequencies present are consistent for a significant period of time). Names, addresses, and inventory are for all intents and purposes here random. You can't determine the address of someone in a database by looking at the adjacent entries.

What if you feed it noise? (0)

Anonymous Coward | more than 4 years ago | (#31329020)

So, if I feed this algorithm an image that actually IS noise, what do I get?

Pictures of angels?

Re:What if you feed it noise? (1)

maxwell demon (590494) | more than 4 years ago | (#31329360)

So finally we can do a Rorschach test on computers?

Useful but don't overdo it (1)

davidwr (791652) | more than 4 years ago | (#31329060)

When it comes to art photography, I for one would rather have a RAW image than a compressed one.

Why? What the camera takes is not my final output. I want to be able to choose what to manipulate and remove.

Now, for everyday snapshots, there might be something here. But as others pointed out, it might be less efficient to do the compression in the sensor than the way it's being done today.

As for other applications, time will tell.

Re:Useful but don't overdo it (1)

John Hasler (414242) | more than 4 years ago | (#31329404)

> But as others pointed out, it might be less efficient to do the compression
> in the sensor than the way it's being done today.

Compression is done in the camera today. The proposal is to have the camera simply throw away a random subset of the pixels instead of compressing and then use this algorithm later on a computer to "restore" the image.

Re:Useful but don't overdo it (0)

BetterSense (1398915) | more than 4 years ago | (#31329430)

When it comes to art photography, I for one would rather have an original film copy that I can choose to scan or optically print rather than only a digital image, raw or otherwise.

I could do this in PhotoShop. (3, Funny)

jellomizer (103300) | more than 4 years ago | (#31329120)

After applying the Noise filter to mess up my image I hit Undo and my image is back to normal.

Holy Bad Acronym Batman (3, Insightful)

damn_registrars (1103043) | more than 4 years ago | (#31329140)

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.

Re:Holy Bad Acronym Batman (0)

Anonymous Coward | more than 4 years ago | (#31329270)

Actually, I'm in an EECS department and to me CS means Compressive Sensing.. I guess it depends on which side you are ;-)

Re:Holy Bad Acronym Batman (1)

Dunbal (464142) | more than 4 years ago | (#31329346)

Aft first I thought he was referring to Credit Suisse. Then I thought no, this is an article about Counter Strike. Then perhaps I thought it meant CS gas. Then perhaps, having been betrayed by an uncooperative context, I thought like you it meant Computer Science. But no - lo and behold "CS" stands for "Compressed Sensing", a new algorithm called "CS" by 1) those working on it and 2) those who have absolutely no idea what it is or how it works, but want to sound cool anyway because hey, what's cooler than using an acronym that ABSOLUTELY NO ONE has ever heard of? Forget the fact that this whole language thing is about "communication" and if you start inserting RA into your MF then NWFU!

(RA = Random Acronyms, MF = Message Format, NWFU = No-one Will Fucking Understand)

Re:Holy Bad Acronym Batman (1)

Bakkster (1529253) | more than 4 years ago | (#31329614)

As long as the acronym is explicitly defined, it doesn't matter how obscure it is. That's proper writing style.

That was the beginning of compressed sensing, or CS

And there it is in the article, what are you complaining about again? Oh right, TFA and slashdot editors. Carry on, then.

Re:Holy Bad Acronym Batman (1)

damn_registrars (1103043) | more than 4 years ago | (#31329868)

And there it is in the article, what are you complaining about again? Oh right, TFA and slashdot editors. Carry on, then.

Precisely. Because while it was defined in the article, it was not defined in the summary. The summary jumped immediately from the name of the algorithm to using the shorthand, without ever saying that the shorthand would be used in place of the full name. And being as there are other uses of the CS acronym - especially in the slashdot community - the slashdot editors failed miserably by not stating that they were going to reuse a commonly used acronym.

Re:Holy Bad Acronym Batman (1)

unitron (5733) | more than 4 years ago | (#31329442)

Yes, but a quick application of the Compressed Sensing Algorithm to the lettters CS will shortly reveal that it stands for Compressed Sensing.

If it stood for Computer Science instead, the algorithm would have been able to sense that, in a compressed sort of way.

Re:Holy Bad Acronym Batman (1)

natehoy (1608657) | more than 4 years ago | (#31329646)

I'd like you all to know I'm feeling very compressed.

  - Marvin.

Rather like most climate science (1)

DeathToBill (601486) | more than 4 years ago | (#31329202)

It doesn't add information, it just fills in what you already expected to see.

Re:Rather like most climate science (0)

Anonymous Coward | more than 4 years ago | (#31329324)

Get back under your bridge, there's a good troll.

Wrong. (1)

Hurricane78 (562437) | more than 4 years ago | (#31329238)

These are fancy words, for what is nothing else that automated educated guessing. (And re-vectorization.)

Yes, you can guess that a round shape is round, even when a couple of pixels are missing. But you can not guess that one of these missing pixels actually was a dent. So this mechanism here would still make that dent vanish. Just in a less-obvious way. (Which can be very bad, if that dent was critical.)

Essentially if you have a lossy process, you are always going to have a lack of details, and that’s not going to change.
Just that this process does to images when compared to e.g JPEG, what MP3 does to music when compared to analog recordings.

In analog recordings, loss is audible noise. In MP3 it’s the opposite. Usually mostly not audible, but still missing.
In JPEG, loss is visible artifacts. In this method it’s the opposite. Usually mostly not visible, but still missing.

Possibly fraud (1)

junglebeast (1497399) | more than 4 years ago | (#31329356)

I could not find any examples showing similar image reconstructions on Jarvis Haupt or Robert Nowak's websites/publication histories -- the researchers credited with the Obama restoration photo.

Therefore, I am skeptical that this wired article is not to be trusted.

Other applications (1)

zmaragdus (1686342) | more than 4 years ago | (#31329466)

I wonder if this can somehow be extended to other forms of data scrubbing besides two-dimensional color images. I've got a waveform capture of a really small, and really noisy, electric motor current that I want scrubbed without losing the shape I think I'm supposed to get out of it.

yes, but... (0)

Anonymous Coward | more than 4 years ago | (#31329582)

"If it sees four adjacent green pixels, it may add a green rectangle there."

Which is brilliant...unless the tumor you were looking for is a white dot in the middle of those 4 pixels. Now it's all just a smooth green field.

This is an important tool! (1)

natehoy (1608657) | more than 4 years ago | (#31329596)

I can finally stop reading the articles and the summaries, and apply this algorithm to the first post to understand the article instead. What a time saver!

Portal (0)

Anonymous Coward | more than 4 years ago | (#31329606)

Just in time to help decipher Valve's latest update...

http://www.rockpapershotgun.com/2010/03/02/portal-theres-something-going-on/

Magic (BS) (1)

Ractive (679038) | more than 4 years ago | (#31329642)

I've been working with digital images for a long time and I can tell you this: this is too good to be true
You can't get professional results even when trying to interpolate 5% extra data, and even though I guess this is not oriented to professional quality images, it will just make crappy images good enough to recognize the points of interest, it will be acceptable to that point but then there's the Obama sample, I have seen the printed image (in the dead tree version of the mag) and it certanly looks faked, there's some detail that couldn't have beeen retrieved, not with the current algorithms, actually as some have pointed out, the lapel pin data is not present at all so how could you recreate that, sounds to me like something more from the realm of magic than math, hence fake!

Caution: don't mis-apply this idea! (1)

MessyBlob (1191033) | more than 4 years ago | (#31329830)

From the referenced reports, it looks like people might get the wrong idea about the possible applications. This algorithm starts with discrete data points with gaps in-between, and works out the remaining arbitrary data points in a pleasing way, as if it were a continuous field (represented as a fourier transform, for example).

In other words, it works with data where the signal is already separated from the noise. My last sentence is crucial for an understanding of the possible applications: it will not infer elements that are absent in the measured signal, but will instead repeat elements that are already present. I expect this story will be mis-reported in future, by reporters who do not understand how it really works (and I might count myself in that, as I've only glanced at a couple of the arxiv papers).

You can't create something from nothing - can you? (1)

YourExperiment (1081089) | more than 4 years ago | (#31329856)

As soon as I read the article, it seemed fishy to me. How can you create data where it doesn't already exist? If you take a scan of a patient, a tumour will either show up or not show up in the data. If it shows up, there's no need for enhancement. If it doesn't show up, no amount of enhancement can cause it to do so.

Then I came across this blog post [wordpress.com] by Terence Tao, one of the researchers mentioned in the Wired article.

It has some very interesting explanations of how this is supposed to work. I'm still not sure that I'm convinced though. Common sense is still screaming at me "this cannot possibly work" - but then that happens with quantum mechanics too.

Quantum state tomography (1)

iris-n (1276146) | more than 4 years ago | (#31329980)

Relevant information: I'm a physicist, and my research group is actively researching quantum state tomography via compressed sensing.

This technique is quite useful also in quantum state tomography. Consider a qubyte. We represent it by an 2^8 x 2^8 matrix of complex numbers. Now we want to measure it. We have to make 2^16 measurements (keep in mind that a quantum measurement is a nontrivial task), and use this data to reconstruct the original matrix, which again is a very intensive task, if done right (there are quick-and-dirty algorithms to do it, but they don't work very well). It is just plain impossible to process so much data, in a day-by-day basis.

But here comes compressed sensing! Normally, we are interested in states that are pure, or quasi-pure. That is, are represented by a sparse matrix, in the correct basis. So, using this technique, we only need to do a quantity of measurements that scale linearly with the dimension of the state (as opposed to the quadratic growth that a full measurement requires), and the amount of processing that we need is also proportional to the amount of measurements.

So, we can shift the limiar of impossibility. Before we needed O(2^(2d)) measurements, now only O(2^d). Still unpleasant, but makes the problem tractable today.

I wonder... (1)

tech_fixer (1541657) | more than 4 years ago | (#31330052)

Could this be applied to radiotelescope data sets? SETI Anyone?

Nobody thought of this? Is this still /.?

Uncrop! (0)

Anonymous Coward | more than 4 years ago | (#31330062)

Great, now we only need the "uncrop" algorithm [youtube.com] to be on-par with TV shows!

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?
or Connect with...

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>