The Photoshop Healing Brush
by Dave Story
I travel around the world talking with Photoshop users, and one question that users repeatedly ask me is, "How do you keep coming up with new features?" While we’ve come a long way over the years, there has never been more we can do to enable Photoshop to solve new imaging problems than there is today. After all, multiple domains are converging: image processing and computer vision, 2D and 3D, and still and video imaging. And as a result, there is amazing research happening at Adobe and all around the world that feeds features that push boundaries.
Innovation comes from everywhere, if you recognize it and if you are ready to take advantage of it. Take the example of the Photoshop Healing Brush, an overnight success that took years to develop. The Healing Brush gives users the ability to correct imperfections, causing the flaws to disappear into the surrounding image. It matches the texture, lighting, transparency, and shading of sampled pixels to the pixels being healed. As a result, the repaired pixels blend seamlessly into the rest of the image.
The inspiration for the Healing Brush came from something you might hear in a Physics 101 lecture: When you place a piece of metal on a heated surface, heat diffuses through the metal until it reaches a steady state. But what does heat diffusion have to do with pixel restoration? More than you might think.
Top left shows a portion of an image (highlighted in red box) that needs to be restored;
to the right is a close-up of that region. Lower left shows results using Laplace cloning, and
to the right shows co-variant cloning (Adobe’s Healing Brush technology).A Culture of Innovation
Adobe Photoshop, first released in 1990, was ahead of its time. It was conceived as a program to display grayscale images when our development machines had only black-and-white bitmap monitors. Over the past 16 years, it has evolved to become the industry standard for image editing, delivering a long sequence of innovation firsts to the desktop world and enabling creative professionals and scientists alike to do things they never thought possible.
In the early days of Photoshop, innovation was the product of caffeine and sleep deprivation. As my colleague Marc Pawliger, senior director of engineering, explains it, all-nighters used to be a badge of honor. These days, we strive for a better balance between work and life, and innovation comes from less-caffeinated sources.
Adobe has internal groups such as Adobe Labs that engage in applied research, research we endeavor to translate directly into new features in shipping versions of Photoshop. We rely on partnerships with universities and other groups doing basic research, and we also do research within the product team.
Which brings us back to heat diffusion.
Making of the Healing Brush
While most people were at home celebrating the holidays in December 1999, a handful of Photoshop computer scientists were busy grappling with the question of how to repair cracks, gaps, and scratches in an image using information from surrounding pixels. One of those computer scientists was Todor Georgiev. Georgiev thought about how heat diffuses across a surface. He reasoned that if pixels could "diffuse" in a similar way, cracks and scratches in an image could be filled in using the characteristics of surrounding pixels.
A partial differential equation known as the Laplace equation describes the state of equilibrium that is reached in heat diffusion as well as in other physical applications related to electromagnetism and fluid dynamics. The way to solve the equation is to perform iterations that eventually converge on a solution.
But there was a problem. At the time, Photoshop provided full internal support for 8-bit images only (it now supports up to 32-bit-per-color images). But 8-bit processing proved too limited, and the equation wouldn’t converge. Finer iterations were needed. A co-worker of Georgiev’s, Mark Hamburg, built a special 16-bit environment so research could continue.
Georgiev faced another challenge, this time of the mathematical sort. The Laplace equation wasn’t giving him the results he had hoped for. Even worse, the math textbooks lining his bookshelf suggested that a solution whereby the edges of the "healed" area would be perfectly smooth was impossible. Georgiev discovered the answer was to go to higher-order differential equations: The higher the order (up to a point), the better the results.
Progress was being made, but the results weren’t perfect enough for Photoshop. Using Georgiev’s method, the healed area of an image appeared overly smooth because it failed to accurately represent the texture of the surrounding pixels. The smoothness made the cloned area look blurry. At this point, the Healing Brush feature had been added to the list of features committed for Photoshop 7.0. But Georgiev still needed a way to perfect the technology, and with deadlines looming, he was under the gun.
Inspiration from Einstein
When we look at an image, we don’t perceive pixel attributes, such as brightness, for what they are. Our visual system interprets the image through a process called "adaptation." For example, if you look at a gray band that has a constant pixel value but is surrounded by a variable background, it appears to vary in lightness, in opposition to its surroundings. The variance we perceive is the result of visual adaptation.
Georgiev realized that his restoration method needed to employ the mechanism of visual adaptation. And for that, he turned to Albert Einstein. It turns out that the math that describes visual adaptation is the same as the math that describes movement in gravitational fields. This math has its roots in Einstein’s general theory of relativity, and more specifically, Einstein and Marcel Grossman’s theory of co-variant derivatives. Another area where co-variant derivatives have been used, in a manner similar to the Healing Brush, is Hermann Weyl’s theory of electromagnetic interactions, which led to today’s gauge theories of all fundamental forces in physics.
At each point in an image, there exist an infinite number of different rules for calculating perceived changes in pixel value—known mathematically as co-variant derivatives (or connections). Georgiev theorized that by expressing the original differential equation in terms of co-variant derivatives, generated from a second "neutral" area in the image, he could produce the desired result. The method would clone not the pixels themselves, but their structure and texture. His theory worked perfectly.
The equation Georgiev developed is usually approximated by Poisson’s equation, and the type of restoration is referred to as Poisson image editing. With the help of Photoshop computer scientist Jeff Chien, who did the challenging and essential work of turning Georgiev’s research into actual code, the Healing Brush shipped as a major feature in Photoshop 7.0 in 2002.
Looking Forward
The digital imaging realm is changing faster than ever. We have to constantly look ahead and develop for the world as it will be, rather than how it is today. To remain nimble and able to adapt to the newest algorithms, Adobe spends approximately 20 percent of its resources every product cycle refactoring the Photoshop code. And to stay abreast of the latest research, we spend time and resources collaborating with Adobe Labs and outside researchers on new ideas, some of them a lot crazier than heat diffusion and healing scratches.
For the Photoshop family of products, the possible areas of research far outpace the number of resources we have to do that research and to convert it into shipping features. To focus our work, the Photoshop team listens carefully to customers. Their challenges have led us to a set of "holy grails," achievements that would create real breakthroughs for our customers. We hope to solve all of them, but if we can solve even a few of them, we think we’ll again revolutionize how artists interact with digital images.
David Story, vice president of product development for Digital Imaging at Adobe Systems, is responsible for the delivery of Adobe’s Digital Imaging product family, which includes Photoshop, Photoshop Elements, Photoshop Album, Photoshop Album SE, Adobe Photoshop Services, Adobe Camera Raw, and Photoshop Lightroom. He oversees several research teams in areas related to the future of digital imaging and software development methodologies. Story’s teams at Adobe have filed numerous patents and have won several awards for innovation.