PatchMatch: the algorithm behind Adobe’s CS5 Content Aware Fill in Photoshop
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.
Related
About this blog
EQN is a blog from Princeton University’s School of Engineering and Applied Science that highlights faculty, students and alumni who, through innovation and leadership, are changing the world.
Recent Entries
- Starshade deploys for first time
- Hale ’11 and Ohlendorf ’05 shine in the major leagues
- Flood risk study receives $2.3 million Rockefeller Foundation grant
- Ice cream social August 9 to feature vintage technology
- Jennifer Rexford ’91 one of top 10 ‘cloud trailblazers’
- Dan Boneh *96 wins prize for advances in cryptography
- Computer science researchers untangle a hairy problem
- Technology Review: mining cellphone data without violating privacy
- Dean H. Vincent Poor elected fellow of Royal Society of Edinburgh
- Bob Kahn wins Queen Elizabeth Prize for Engineering
Email EQN
Monthly Archives
- September 2013 (3)
- July 2013 (1)
- June 2013 (2)
- May 2013 (2)
- March 2013 (5)
- February 2013 (2)
- January 2013 (5)
- November 2012 (5)
- October 2012 (3)
- September 2012 (4)
- July 2012 (4)
- June 2012 (8)
- May 2012 (1)
- April 2012 (3)
- March 2012 (4)
- February 2012 (3)
- January 2012 (4)
- December 2011 (3)
- November 2011 (2)
- October 2011 (3)
- September 2011 (6)
- August 2011 (6)
- July 2011 (9)
- June 2011 (9)
- May 2011 (4)
- April 2011 (10)
- March 2011 (2)
- February 2011 (2)
- January 2011 (1)
- November 2010 (3)
- October 2010 (5)
- September 2010 (7)
- August 2010 (1)
- June 2010 (3)
- May 2010 (3)
- March 2010 (5)
- February 2010 (3)
- January 2010 (3)
- December 2009 (5)
- November 2009 (8)
- October 2009 (4)
- August 2009 (2)
- July 2009 (3)
- June 2009 (9)
- May 2009 (2)
- April 2009 (4)
- March 2009 (1)
- February 2009 (2)
- January 2009 (1)
- December 2008 (1)
- November 2008 (5)
- August 2008 (1)
- July 2008 (2)
- June 2008 (2)
- May 2008 (5)
- March 2008 (2)
- January 2008 (1)
- December 2007 (2)
- November 2007 (1)
- October 2007 (3)
- September 2007 (2)
- July 2007 (9)
- June 2007 (5)
- May 2007 (8)
- April 2007 (5)
- March 2007 (4)
- February 2007 (11)
- January 2007 (13)
- December 2006 (4)
- July 2006 (2)