The Wired article on Compressed Sensing has started a series of ripples on the interweb that has reached the mighty Slashdot. While I wanted to address this issue a little later, I think it is important to make a point that something in the Wired article has been missed by many readers.
What is described in the Wired article is mostly equivalent to the diverse traditional post-processing steps involved in what is called inpainting. There is a large amount of work in that area but it is just post-processing. In other words, if your hardware has not been able to pick up on details in the first place then it really is nearly impossible to have the kind of superresolution commonly found in CSI and other TV shows (from the video it looks like the problem started with Blade Runner)
The MRI example of the Wired article uses random "pixels" in the Fourier domain,:these pixels are not in the real domain as the Obama picture seems to indicate. This distinction is simply fundamental. For compressed sensing to work, the scene of interest has to be sampled in some incoherent fashion and only specific hardware can do that. Your average digicam is not incoherent (or not incoherent enough) as much money has been spent on lenses to make sure that a point in the real world was translated into a point in the focal plane. In other words, if the scene was acquired coherently (this is why your hard earned cash pays for a spiffy DSLR or a high resolution webcam in the first place) then there is very little in terms of inpainting or superresolution one can do.
If, on the other hand, the lenses of your digicam were to be badly broken, then there would be a chance to obtain superresolution or inpainting and this is why I referred to compressed sensing as a potential CSI technology in a previous entry (Going Hollywood with Compressive Sensing). In that entry, I mentioned the fantastic random lens imager: Here is what one can see with 90 percent "pixels" gone, the 10% of the "pixels" left contain enough information to allow the reconstruction of a sensible image (see reconstructed picture below in the right hand corner):
This is possible because the random lens has mixed different elements of the scene on one pixel and that powerful reconstruction techniques have been used to unmix these components. The whole field of compressed sensing is somehow devoted to defining exactly the randomness in the random lens and many research groups are in some arms race to find the most powerful new reconstruction solvers. To make it real, others are interested in applying all this to actual hardware and there is much competition there as well since a whole slew of Nobel Prizes have gone to imaging devices for the past hundred years.
Well for one, one could imagine a crime scene where a camera has been found and photos were taken by that camera with badly damaged lenses. The next step would be for the CSI team to take that camera and calibrate it by taking many known pictures. Compressed sensing helps there in making sure that they don't spend 200 years performing that calibration by reducing the number of known photos to be used as calibration in the lab. But while the imaging is indeed very appealing, compressed sensing also can be used to find elements in large crowds such as is the case with the Cylons and group testing. Yaniv Erlich's video presentation of the DNA sudoku paper mentioned earlier here also has potential. With some thoughts, we could even think of astounding sensing systems using nature :). All this to say that instead of being negative, compressed sensing can actually help in making scenari a whole lot more sci-fi and grounded in real science at the same time. I know a few accomplished scientists who were raised on Star Wars, Blade Runner or Minority Report.
Why am I writing this ?
What is described in the Wired article is mostly equivalent to the diverse traditional post-processing steps involved in what is called inpainting. There is a large amount of work in that area but it is just post-processing. In other words, if your hardware has not been able to pick up on details in the first place then it really is nearly impossible to have the kind of superresolution commonly found in CSI and other TV shows (from the video it looks like the problem started with Blade Runner)
The MRI example of the Wired article uses random "pixels" in the Fourier domain,:these pixels are not in the real domain as the Obama picture seems to indicate. This distinction is simply fundamental. For compressed sensing to work, the scene of interest has to be sampled in some incoherent fashion and only specific hardware can do that. Your average digicam is not incoherent (or not incoherent enough) as much money has been spent on lenses to make sure that a point in the real world was translated into a point in the focal plane. In other words, if the scene was acquired coherently (this is why your hard earned cash pays for a spiffy DSLR or a high resolution webcam in the first place) then there is very little in terms of inpainting or superresolution one can do.
If, on the other hand, the lenses of your digicam were to be badly broken, then there would be a chance to obtain superresolution or inpainting and this is why I referred to compressed sensing as a potential CSI technology in a previous entry (Going Hollywood with Compressive Sensing). In that entry, I mentioned the fantastic random lens imager: Here is what one can see with 90 percent "pixels" gone, the 10% of the "pixels" left contain enough information to allow the reconstruction of a sensible image (see reconstructed picture below in the right hand corner):
This is possible because the random lens has mixed different elements of the scene on one pixel and that powerful reconstruction techniques have been used to unmix these components. The whole field of compressed sensing is somehow devoted to defining exactly the randomness in the random lens and many research groups are in some arms race to find the most powerful new reconstruction solvers. To make it real, others are interested in applying all this to actual hardware and there is much competition there as well since a whole slew of Nobel Prizes have gone to imaging devices for the past hundred years.
What would a typical CSI scenario have to do to incorporate compressed sensing and be scientifically sound ?
Well for one, one could imagine a crime scene where a camera has been found and photos were taken by that camera with badly damaged lenses. The next step would be for the CSI team to take that camera and calibrate it by taking many known pictures. Compressed sensing helps there in making sure that they don't spend 200 years performing that calibration by reducing the number of known photos to be used as calibration in the lab. But while the imaging is indeed very appealing, compressed sensing also can be used to find elements in large crowds such as is the case with the Cylons and group testing. Yaniv Erlich's video presentation of the DNA sudoku paper mentioned earlier here also has potential. With some thoughts, we could even think of astounding sensing systems using nature :). All this to say that instead of being negative, compressed sensing can actually help in making scenari a whole lot more sci-fi and grounded in real science at the same time. I know a few accomplished scientists who were raised on Star Wars, Blade Runner or Minority Report.
Why am I writing this ?
- I have already crossed the path of clients with CSI like expectations, I would like to contribute to making compressive sensing a reality without undue expectations.
- If one of you write scripts for one of these TV shows, I can direct you to a willing academic on these matters or consult on these technical insights for a tiny fee.
Thank you to Jordan Ellenberg for getting people interested in the subject and for a great human interest story as well.
[Update: a continuation of this entry, albeit a little technical, can be found in Surely You Must Be Joking Mr. Screenwriter ]
If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store
Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from
8 comments:
A similar algorithm to the one described in the Wired article has been used to accelerate computer graphics rendering. See Sen and Darabi "Compressive Rendering" on IEEE Transactions on Vis and Computer Graphics.
Thank you for the explanation and the powerful demonstration images.
Now I will have to go through the rest of your blog to see if I can gain some sort of minimal understanding as to why a random lens works better. Also what exactly "random" lens means. :)
My thanks also - I still don't understand how this works, but your post was the first one that gave me an inkling of *why* it might.
Funny coincidence... your entry is titled "Why Compressed Sensing is NOT a CSI technology... yet!" but in the video you posted, there is a clip from the show Numb3rs where they use compressed sensing to solve a crime. Specifically, the clip (around 1:20) refers to the "Pradeep Sen method" and later picks up on that at 1:28. The full text from the show is:
"Maybe we can use the 'Pradeep Sen' method to see into the windows. He has taken illumination algorithms to the next level and I can use them to enhance this photograph."
The work they are referring to is Sen et al.'s dual photography (Siggraph05) and later work on compressive dual photography where they use compressed sensing to do single pixel imaging and novel illumination. So they ARE using some REAL CS algorithms to solve a virtual crime in shows like CSI!
Who knows, maybe Romberg told them about it, since you said he was an advisor to that show...
I saw the episode on TV, however, and the whole thing was ridiculously unfeasible, but at least they ARE citing current work in compressed sensing... :)
Dear Anonymous,
This is a good catch. However, it is not because you use someone's name that you automatically do the science right. Let me expand on that in an upcoming post.
Also, Justin may not have been the source of this, Siggraph 05 was in LA.
Cheers,
Igor.
Thank you; as a physics and mathematics student, I was disappointed at the imprecise explanation on Wired. It's too bad the author of that article didn't point out that the "noisy image" is fundamentally different from the "blurry" image e.g. 32x32 pixels in size with no space between them (or, equivalently, less precise coordinates).
I haven't gotten into understanding the research and proof(s) yet (if I can understand it, that is), but I would like to!
Does noise resulting from the ISO rating being turned way up on a digital camera qualify as "incoherence" for the purposes of compressive sensing?
That is, would compressive sensing be useful for "filtering out" that noise provided that the noisy image is known to be sparse in reality? I don't necessarily mean removing that noise to see what the picture would have looked like if it had been taken with a "perfect camera"; getting a plausible noiseless image is good enough.
How about JPG artifacts? Could those be "removed"?
Thanks for the clarification, especially since the Wired article demanded some clarification, especially in saying that compressed sensing is generally NOT an image problem or noise correction system, and also that it does NOT interpolate or "guess" data. Rather it uses special techniques to push the already present sampling technologies even further than previously thought possible. For example, similar techniques let you listen to scratched CDs or watch digital TV transmission crystal clear (a feature not available with older noisy analog TV transmission).
An important note that the Wired article glossed over is that most compressive sensing does not read normal data and then clean it up. Rather, it "mixes" the input data in a way that permits high resolution analysis even with low resolution data. For example, to a compressive camera one pixel usually looks like several pixels in different parts of the screen, and by analyzing which five pixels they are with some fancy math, you can tell where that one original pixel really was as if the camera has 2 or 3 times the resolution.
Post a Comment