The buzz about the newest version of Photoshop started back 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 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 throughout computer graphics and computer vision.
To the surprise of both Barnes and Finkelstein, their own rather dryly delivered research video explaining the mechanics of PatchMatch thus far has received almost 2 million hits on Youtube.
Barnes didn’t set out to invent a way to infuse Photoshop tools with magical powers. Rather, he and Finkelstein, together with collaborators at Adobe, were developing a video navigation technique 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 method generates a “tapestry” that acts as a visual summary that can be quickly scanned to get an overview of the narrative and to locate specific scenes. 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 story 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.
Finkelstein made a presentation on PatchMatch last month at the FMX conference on animation and special effects in Stuttgart, Germany. 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 this research might launch, take note: This August Barnes will be presenting a new paper at SIGGRAPH, coauthored by Finkelstein and the same Adobe engineers who collaborated on the PatchMatch paper. The subject of the new paper? Video tapestries.
The 2009 photo above is Barnes performing in a skit for the “Fast Forward Papers Preview” that opens the annual SIGGRAPH conference.“ Tongue in cheek, Barnes explained that he uses PatchMatch every morning to improve his personal appearance.
By the way, Finkelstein, who will spending his 2010-11 sabbatical year doing research at Adobe, is a co-organizer of Princeton’s Art of Science exhibit, which has gotten a lot of media play recently. As for Barnes, he writes not only code but also poetry and music. Oh, and he paints too.
