How L1-minimization can recover highly degraded images
wired.com
wired.com
From the article: "Compressed sensing was discovered by chance... Candes... was experimenting with a badly corrupted version of the phantom meant to simulate the noisy, fuzzy images you get when an MRI isn’t given enough time to complete a scan. Candes thought a mathematical technique called l1 minimization might help clean up the streaks a bit... Candes expected the phantom on his screen to get slightly cleaner. But then suddenly he saw it sharply defined and perfect in every detail..."
"At present, most of our audiovisual info is stored in sophisticated compression formats. If, or when, the format becomes obsolete, you’ve got a painful conversion project on your hands. But in the CS future, Candès believes, we’ll record just 20 percent of the pixels in certain images, like expensive-to-capture infrared shots of astronomical phenomena. Because we’re recording so much less data to begin with, there will be no need to compress. And instead of steadily improving compression algorithms, we’ll have steadily improving decompression algorithms that reconstruct the original image more and more faithfully from the stored data."
Someone, Candès or the author, doesn't seem to understand what they're talking about.
I can't imagine trusting to this technique for pictures of the galaxy. After spending a bazillion dollars on a space telescope we aren't going to "throw away 80% of the pixels".
[1] - I'm not certain of this deduction. Can somebody with more background confirm or deny?
By the way, those bazillion dollars aren't wasted, because if you take the image, don't throw away pixels, but do as if it were a bigger image which had lost pixels, you can get something useful out of it.
Most real world pictures are not random. So you can guess what it looks like from areas near it.
A saw a presentation on this technique in college. Some of the details I saw escaped me, but one thing I remember is that the L1 decompression is optimal when it is "orthogonal" to the compression that it is reversing. Fourier-based compression schemes (including JPEG and MPEG, and even MP3) are "orthogonal" in the correct sense because they select based on size, preserving large structures better. Random sampling is "orthogonal" to basically all compression schemes, and tends to select more information from large structures as well.
With a high-res bazilion-dollar space telescope, you're not going to throw away 80% of the pixels and reconstruct an approximation. Rather, you'll take all of the recorded pixels, and then reconstruct even more impressive astronomer porn at five times the resolution!
[1] Well, close enough. If you store the circle as the (x,y) of the center and an integer radius R, then 2R takes 1 more bit. Storing R as floating-point means no difference. I don't know about other representations. Anyways, the point is, the image size of the feature is not strongly coupled to data size of the feature.
As long as we keep in mind that the filled in regions of space or background match the assumed entropy, I think it's worth doing. The applications of L1 appear to be limited to cases where the structure and assumptions match the dataset.
Maybe there's an underlying pattern we're recreating? Something inherent to physical laws, fractal replication, etc.
Your comment helped me to see that L1 isn't just a matter of interpolation but an assumed underlying pattern that is used to fill in or estimate the unknown data. Thanks.
It seems like a great bit of technology, I don't think the author needed to sex it up with mention of compressing images. The applications where its actually hard to do sensing at all (like the MRI example in the article) are much more compelling. It seems like its main use seems to be in turning sparse data into its most human friendly form, but I do wonder about making clinical decisions based on such an aggressive interpolation rather than actual data.
One important way in which I think the Wired piece is Just Plain Wrong: you don't sample a small fraction of the individual image pixels. You take a small number of samples, each of which is a kinda-random combination of image pixels.
Some examples and further quite-friendly explanation here: http://www.acm.caltech.edu/l1magic/examples.html .
More from Tao: http://terrytao.wordpress.com/2008/12/05/the-uniform-uncerta... and http://terrytao.wordpress.com/2009/05/25/reflections-on-comp... both of which are mostly links to more detailed things, well worth reading if you don't mind mathematics.
Imagine you have a pixel image, with missing data, and with noise. Imagine you know a-priori that the image was generated simply by placing a few white circles against a black background. Then data was lost/discarded, and white noise was added to the remaining data.
(The white circles are cross sections of the patient's blood vessels or some such feature (bile ducts, in this case), and contain a contrast agent. The contrast agent appears white on the MRI, everything else appears black. )
Now that you know the pixel image has such a simple form, you don't need to do fancy noise removal to clean it up. All you need to do is figure out where the white circles are. Once you know where the are, you can just redraw the image based on your calculated locations of circles instead of reprocessing the old one.
You can play the same trick in k-space, which gives you a potent MRI reconstruction algorithm.
In practice, this doesn't work as well for more complicated images such as brains or abdomens. There is just much more to draw, and the images cease to be sparse.
Compressed sensing works just fine for brains, abdomens etc.. because the images need to be sparse in some basis (e.g. wavelets), not in the original space.
The best I've seen is Candes/Donoho's reconstruction based on curvelets, but they don't offer any real improvement over regular reconstruction.
http://yonit.stanford.edu/cgi-bin/axs/ax.pl?http://www-mrsrl...
That seems to be what the scientists are doing for the MRI, but the author seems to think this would be useful in that it would allow people to throw away a lot of data. I think it would be much better for extrapolating even farther from the data we have.
I could be wrong, though -- I only did this back-of-the-envelope a few months ago. I never really tried that hard to make it work.
This is most likely true. Additionally, raytracing just might produce samples that are too regular for this to work well. I haven't really thought about it :)
One application he mentions is sensor networks that can withstand a loss of a large number of nodes.
As soon as I saw the article my first thought was: "real-time raytracing?"
The reason is that MRI sampling is prohibitively time-expensive: you need to keep the sample still for a long time to sample many points. In the article's case, that would require the patient to end up dead. ;) Sparsely sampling the volume takes much less time and allows for a reasonable reconstruction.
I'm not intimately familiar with MRI processing, but there may also be some intricacy of the imaging process (possibly related to the time-to-spatial-frequency conversion?) that makes the lower-res sampling especially suited for this algorithm.
L1 minimization here refers to trying to represent the image as a linear combination of basis functions a1 f1+a2 f2+ ... by minimizing objective function fit(a1,a2,...)+sum_i |a_i| where "fit" represents how closely the reconstruction fits the image (for instance, squared distance). The second term in the sum is the L1 norm of the parameter vector, and it has a special property of being non-differentiable at 0, and often causing individual components a_i to become exactly 0 during minimization, hence resulting in "sparse" solution vector.
Compressed sensing refers to the idea that when the image is sparse in the chosen basis {fi}, it's sufficient to take a small number of random measurements of the image. We can then compute "fit" approximately which gives us a different objective function that we minimize. The result will be close to what we'd get if we used the original (full) "fit" function
If you're interested in a blog solely focussed on CS, here's one: http://nuit-blanche.blogspot.com/
For compressed sensing to work when one needs to know in advance that the signal (image or anything else really) is sparse or compressible, Once this is known, one needs two findings that are just plain surprising and are the reason there is so much excitement in this area:
- the signal needs to be acquired "incoherently" and there is much work going on in that area, Most hardware is currently not designed to do this incoherent acquisition (this can be done cheaply in MRI which is why you see some applications there) and much work is currently going into designing new sensors that can performed this new kind of acquisition, Much of them are listed here: http://igorcarron.googlepages.com/compressedsensinghardware
- once it is "incoherently" acquired, then one can reconstruct the original signal using linear programming technique solving an l1 problem, But after four years of intense competition between different groups, we now have faster solvers that are approximately solving the l1 problem without linear programming or the lp (p between 0 and 1) and even L0 problems..
For more information, you may want to check the blog or the big picture site: http://igorcarron.googlepages.com/cs
edit: Also, they present all of compressed sensing as if it were just that one algorithm for image reconstruction (which samples in the original space, rather than an incoherent basis). Tech media fail?
Suppose you have an image which you already know is a cartoon. Compressed sensing can clean it up, but uses explicit knowledge of what cartoons look like. Similarly, if you know the image is scanned text, a different compressed sensing algorithm based on scanned text can clean it up.
But if you don't know where the image comes from to begin with, compressed sensing won't work.
http://www.acm.caltech.edu/l1magic/
Seven examples using compressive sensing:
What effects will this have on the storage of photos?
Can this principal be extrapolated to other forms of data?
The fundamental breakthrough here is that we can acquire signals (photos, recordings, MRI volumetric images, etc...) using a much smaller number of samples than previously thought possible. A useful application: let radiologists accurately image the body in less time. A weird application: Single-pixel cameras (http://physicsbuzz.physicscentral.com/2006/10/single-pixel-c...)
I would imagine one of the most powerful applications would be compression of files. Might make things easy for big websites like facebook. Or allow zip to make files smaller. Or a flash card that hold more information.
I'd had to learn more about the technology. But EE standpoint there are two big questions:
How fast is the process? I'd imagine that it work fast enough for images, voice and but not fast enough for video. I'd imagine the speed will increase as people start playing with it.
And does the photo have to be compressed using the algorithm? The single pixel camera idea and many other signal capture operations really open up if you can just take a swab of the signal at random intervals. Perhaps a cool little program could be written to hunt for the necessary data points and capture them.
This technology will definitely bring improvement to many fields over time.