A few issues ago Wired had an interesting article on the use of a sophisticated algorithm that can create hi-res images out of lo-res originals:
Vasanawala needed a phenomenally hi-res scan, but if he was going to get it, his young patient would have to remain perfectly still. If Bryce took a single breath, the image would be blurred. That meant deepening the anesthesia enough to stop respiration. It would take a full two minutes for a standard MRI to capture the image, but if the anesthesiologists shut down Bryce’s breathing for that long, his glitchy liver would be the least of his problems.
However, Vasanawala and one of his colleagues, an electrical engineer named Michael Lustig, were going to use a new and much faster scanning method. Their MRI machine used an experimental algorithm called compressed sensing — a technique that may be the hottest topic in applied math today. In the future, it could transform the way that we look for distant galaxies. For now, it means that Vasanawala and Lustig needed only 40 seconds to gather enough data to produce a crystal-clear image of Bryce’s liver.
So how does it work?
You’ve got a picture — of a kidney, of the president, doesn’t matter. The picture is made of 1 million pixels. In traditional imaging, that’s a million measurements you have to make. In compressed sensing, you measure only a small fraction — say, 100,000 pixels randomly selected from various parts of the image. From that starting point there is a gigantic, effectively infinite number of ways the remaining 900,000 pixels could be filled in.
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.
…[T]he algorithm takes the incomplete image and starts trying to fill in the blank spaces with large blocks of color. If it sees a cluster of green pixels near one another, for instance, it might plunk down a big green rectangle that fills the space between them. If it sees a cluster of yellow pixels, it puts down a large yellow rectangle. In areas where different colors are interspersed, it puts down smaller and smaller rectangles or other shapes that fill the space between each color. It keeps doing that over and over. Eventually it ends up with an image made of the smallest possible combination of building blocks and whose 1 million pixels have all been filled in with colors.
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. It might still take a few hours of laptop time, but waiting an extra hour for the computer is preferable to shutting down a toddler’s lungs for an extra minute.
For some reason I keep thinking about weather forecasting. To me, it’s akin to why predictions about the weather get better the closer one gets to a particular day. There are a number of variables that affect the weather on a given day, and each one can vary greatly depending on how each is affected by other variables (such is life in a complex system). What that means is the farther out one tries to predict the weather, the less likely that prediction will be accurate since the possible range of outcomes increases the farther away from a particular day one finds themselves. However, the closer one gets to, say, Wednesday, the more narrow the range of values for those variables becomes. This allows for a more accurate prediction and a clearer “picture” of what the weather will be that day. The algorithm keeps narrowing down the number of possible variations with each iteration until a clear picture emerges.
Needless to say the potential applications are abundant; military intelligence, law enforcement, health care, astronomy. Cool stuff.