Compressed Sensing in Python (2016)(pyrunner.com)
pyrunner.com
Compressed Sensing in Python (2016)
http://www.pyrunner.com/weblog/2016/05/26/compressed-sensing-python/
4 comments
The best real application of compressed sensing (that I know of) is subsampled reconstruction of magnetic resonance imaging.
MR scanners actually sample data from the frequency spectrum to build a visible image by using several techniques involving electromagnetic fields and pulses that are applied to some organic body. One could think of it like taking a picture of the Fourier Transform of the actual image you want to see, to which you later take the inverse FT and get the image.
This is done "pixel-by-pixel" where each of them is a specific sample of an specific set of frequencies, and for each of them a different set of physical parameters need to change in the scanner, a process that takes some non-negligible time. As we would like to have big pictures with lots of details we need to do this as fast as we can, but there are physical limitations on the scanner and the actual scanned region (we can't have a person lying still for hours to get an image of their brain). So in order to get a good image we have to balance image quality and resolution with scan times.
Using compressed sensing, we can "skip" some of these pixels in some smart way (usually in some random fashion), and be able to reconstruct the image with virtually no loss of quality, there are some beautiful mathematical results that guarantee us that if the reconstructed image is sparse in some domain (e.g. organic images are usually sparse in DCT or several wavelet domains. This is actually what allows us to compress several megapixel images in a few megabytes without loss of percieved quality), you can reconstruct the image with no theoretical loss of information. Think of it like having to guess an image from a subset of its pixels. If I tell you that it can be any possible image, you won't be able to guess anything until I give you all its pixels. But if I tell you that the image is of a cat, you'll maybe need half, or a quarter of the pixels and then you can start guessing some of the missing pixels, as you know how cats look like.
In a practical sense, this techniques have allowed us to generate high quality MR images with an incredibly low subset of the samples (10% or even less). In my opinion it is one of the most beautiful applications of a theoretical mathematical result in a real life problem with real impact.
If you want to see some more information about it you should check this presentation from Terrence Tao on the topic https://terrytao.files.wordpress.com/2009/08/compressed-sens...
MR scanners actually sample data from the frequency spectrum to build a visible image by using several techniques involving electromagnetic fields and pulses that are applied to some organic body. One could think of it like taking a picture of the Fourier Transform of the actual image you want to see, to which you later take the inverse FT and get the image.
This is done "pixel-by-pixel" where each of them is a specific sample of an specific set of frequencies, and for each of them a different set of physical parameters need to change in the scanner, a process that takes some non-negligible time. As we would like to have big pictures with lots of details we need to do this as fast as we can, but there are physical limitations on the scanner and the actual scanned region (we can't have a person lying still for hours to get an image of their brain). So in order to get a good image we have to balance image quality and resolution with scan times.
Using compressed sensing, we can "skip" some of these pixels in some smart way (usually in some random fashion), and be able to reconstruct the image with virtually no loss of quality, there are some beautiful mathematical results that guarantee us that if the reconstructed image is sparse in some domain (e.g. organic images are usually sparse in DCT or several wavelet domains. This is actually what allows us to compress several megapixel images in a few megabytes without loss of percieved quality), you can reconstruct the image with no theoretical loss of information. Think of it like having to guess an image from a subset of its pixels. If I tell you that it can be any possible image, you won't be able to guess anything until I give you all its pixels. But if I tell you that the image is of a cat, you'll maybe need half, or a quarter of the pixels and then you can start guessing some of the missing pixels, as you know how cats look like.
In a practical sense, this techniques have allowed us to generate high quality MR images with an incredibly low subset of the samples (10% or even less). In my opinion it is one of the most beautiful applications of a theoretical mathematical result in a real life problem with real impact.
If you want to see some more information about it you should check this presentation from Terrence Tao on the topic https://terrytao.files.wordpress.com/2009/08/compressed-sens...
I agree, it seems impossible. I actually find the 10% example most impressive - how can it possibly reconstruct things like the coral, or the railing? Doesn't it violate Nyquist somehow? Evidently not, but I can't see where the information comes from. I wouldn't believe it if full source code were not provided!
Wait you mean after all these years of scoffing every time a movie included a scene with the protagonist sifting through surveillance images, and someone says, "enhance that image", revealing someone's face from blurry pixels, that WASN'T just wishful Hollywood thinking?! That's bonkers!
What are some applications of this technique? I was trying to think of real world examples, but most real world problems have a lot of noise, and reconstructing from sparse data seems extremely sensitive to noise.
0. https://www.youtube.com/watch?v=eTUmmW4ispA