Algorithms amplify — or remove — visual variation

At the Siggraph Asia conference this week, MIT researchers presented a pair of papers describing techniques for either magnifying or smoothing out small variations in digital images.

The techniques could be used to produce more polished images for graphic-design projects, or, applied in the opposite direction, they could disclose structural defects, camouflaged objects, or movements invisible to the naked eye that could be of scientific interest.

Conceptually, the work builds on a long line of research from several groups in MIT’s Computer Science and Artificial Intelligence Laboratory (CSAIL), which sought to amplify minute motions in digital video. “In motion magnification, the deviations are over time, and the model is deviation from being perfectly static,” says Tali Dekel, a postdoc in CSAIL and a co-author on both papers. “Our method takes as input only a single image, and it looks for deviation in space. We don’t need to know time history to do that.”

One of the two papers, on which Dekel is first author, presents an algorithm that looks for repeated forms within an image, such as the kernels of an ear of corn or bricks in a wall. It can then iron out differences across the image, producing idealized but still natural-looking corn ears or brick walls, or amplify the differences, making them more evident to the naked eye.

The algorithm works with color as well as shape. So, for instance, it can take an image in which a chameleon is concealed against the trunk of a tree and enhance subtle color differences so that the chameleon stands out blue against an orange background.

Joining Dekel on that paper are professor of computer science and engineering William Freeman, whose group she’s a member of, and colleagues from Israel’s Technion and Weizmann Institute.

Imperfect form

The algorithm described in the other paper amplifies deviations from ideal geometries. The roofline of a house, for instance, could look perfectly straight to the naked eye but still sag toward the middle. The algorithm can exaggerate that type of flaw, potentially drawing attention to structural problems.

In other experiments, the algorithm was able to identify a rippling in Saturn’s rings that could offer information about the orbital pattern of the planet’s moons, and by magnifying changes to a regular pattern projected on a screen behind a candle, it revealed thermal variations caused by the candle’s flame.

The first author on that paper is Neal Wadhwa, another MIT graduate student in electrical engineering and computer science. Joining him are Dekel, Freeman, graduate student Donglai Wei, and Frédo Durand, a professor of computer science and engineering.

The first algorithm — the one that recognizes repeated forms — begins by comparing patches of the source image, at different scales, and identifying those that seem to be visually similar. Then it averages out all the visually similar patches and uses the averages to construct a new, highly regular version of the image. This image may look unnatural, but its purpose is just to serve as an initial target.

Then the algorithm identifies a mathematical function that moves the pixels of the source image around, producing the best possible approximation of the target image. From that function, it creates a new target image. It then iterates back and forth, producing ever more natural-looking target images and ever more regular mathematical transformations, until the two converge.

Once the algorithm has a function that produces a regular image, it can simply invert it to produce a more distorted image.

Implications

The technique works not only with geometrically simple forms like corn kernels and bricks but with more complex forms as well. So, for instance, it can take an image of a line of dancers executing the same kick and standardize their heights and the distances between them.

If it’s implemented particularly aggressively, it can even cut irregularities out of an image — for instance, standardizing the size and shape of the cells of a honeycomb while deleting the bees crawling over it. As such, it could be a useful resource for image-manipulation programs like Photoshop.

In materials science, a standard technique for identifying defects in a material’s surface is to cover it with tiny soap bubbles and look for irregularities. The MIT researchers are also collaborating with materials scientists to use their algorithm to enhance that process.

The second algorithm uses existing techniques to identify the geometric shapes indicated by color gradations in an image. Then it excises a narrow band of the image that traces the curve defining each of those shapes. It then straightens the bands out, creating a uniform representation of all the shapes in the image.

At regular intervals, it considers local variations in color across the width of each band. These will typically vary, indicating deviations from the idealized geometry of the initial curve. From those deviations, the algorithm constructs a new, more erratic curve, which it can exaggerate and then reinsert into the image.

“Humans are extremely good at detecting regularities or deviations from them,” says Shai Avidan, an associate professor of computer science at Tel Aviv University. “Computers can do that quite well when the irregularities are at a fairly large scale. But images have a finite resolution, and detecting irregularities at a tiny scale — at sub-pixel accuracy — requires truly impressive engineering skills. I have no doubt that the methods presented here will be used in various fields such as material inspection, civil engineering, and astronomy.”