Physics insight sparks photo-editing innovation: 'Content-Aware Fill' in Adobe Photoshop

Graduate student Connelly Barnes in 2009 performs in a skit at the opening of the annual SIGGRAPH computer graphics conference. Tongue in cheek, Barnes explained that he uses the PatchMatch photo-editing tool every morning to improve his personal appearance.


The buzz about the newest version of Photoshop started in mid-March when Adobe released a sneak-peak video, which received millions of hits on YouTube, demonstrating how users would soon be able to manipulate images with magic-like speed. The new tool, called “Content-Aware Fill,” also was featured widely on technology websites such as Popular Science, Slashdot, Gizmodo and PC Magazine.

The technology driving the new eye-popping photo-editing feature was developed by Princeton computer science graduate student Connelly Barnes, who interned three times at Adobe Systems Inc. In Seattle, Washington.

“What Connelly invented is an algorithm for quickly identifying correspondences in images,” said Adam Finkelstein, associate professor of computer science and Barnes’s thesis adviser. The core algorithm, called PatchMatch, turns out to have many potential applications, from computer vision to video search.

Indeed, Barnes didn’t set out to invent a way to infuse Photoshop tools with magical powers. Rather, he and Finkelstein were developing a video search algorithm inspired by medieval tapestries.

“We call these video tapestries because their continuous nature is akin to narrative depictions predating the advent of motion pictures” Barnes said. The algorithm generates a “tapestry” that acts as a visual summary. However, unlike a filmstrip the images have no hard boundaries. And when you click on a given spot in the tapestry you can zoom in to see the image in ever greater detail.

Barnes, whose undergraduate degrees are in computational physics and mathematics from Oregon State University, said the inspiration for PatchMatch came from the Ising model and the Metropolis-Hastings algorithm, which are well-known in physics but not in the computer graphics world. “I think a lot of innovation happens when you take an idea from one field and apply it to a totally different field,” he said.

Barnes first publicly presented the PatchMatch algorithm that gave rise to the new Photoshop wizardry last August at SIGGRAPH, the premier annual computer graphics convention.  So if you are looking for clues about what future consumer applications Barnes’s research might launch, take note: This August Barnes will be presenting a new paper at SIGGRAPH. The subject? Video tapestries.