Todor Georgiev

Sr. Research Scientist, Photoshop Group, Adobe Systems
tgeorgie at adobe dot com

Classical diffusion equations inspired my work on the Healing Brush. When you place a metal plate on a heated surface, heat diffuses across the metal until its temperatures reach a steady state. Let’s think about heat in relation to digital images: If we "diffuse" pixel values we can fill in cracks and scratches in an image from surrounding pixels. The Laplace equation describes the state of equilibrium that is reached as a result of diffusion. The same equation is used in relation to other physical applications such as electromagnetism and fluid dynamics, and is well-studied. One way to solve the equation is to perform iterations that converge on a solution depending on the boundary conditions.

Back in 1999 my diffusion experiments repaired small areas in images very well. However, the Laplace equation did not produce sufficiently smooth results at the boundary of bigger areas. Pixel values were continuous (due to the Dirichlet boundary conditions), but the derivatives were discontinuous. The math textbooks clearly stated that area reconstruction with both continuous boundary pixel values and boundary derivatives would be impossible. I found a way to avoid that problem: General textbooks consider only second order partial differential equations, which admit either Dirichlet, or Neumann boundary conditions. Since reconstruction needed to achieve both continuities at the same time, we needed higher-order differential equations. We tested this idea on the bi-Laplace (4-th order) equation, and our experiments produced great results!

This was a clear progress. It was also encouraging to see similar higher-order results appearing in new publications under the name inpainting. But with these methods the healed image area appeared overly smooth. Contrary to some overoptimistic claims, higher-order differential equations failed to accurately represent the texture of the surrounding pixels. For big image areas they produced blurry-looking results. We needed a better solution for the upcoming release of Photoshop 7. I decided to go back to fundamentals and consider the deeper mechanisms of how the human visual system works.

When we look at an image, we don’t perceive pixel attributes, such as brightness or color, 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 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. Figure to be included: The central strip has constant color.

At that time (2001) I realized something important: In order to achieve correct restoration the method needed to somehow employ the mechanism of visual adaptation. Having background in theoretical physics, I turned to some ideas originally developed to describe general relativity (the Grossman-Einstein theory of “covariant derivatives”). It turns out that the math that describes visual adaptation could be presented in the same general form as the math that describes movement in gravitational fields. Related mathematical methods are widely used in different areas of theoretical physics today. My approach is based on an idea that originates from Hermann Weyl’s theory of electromagnetic interactions (see Yang, Gravitation and Electricity), which had led to today’s gauge theories of all fundamental forces in physics.

Link: [Covariant derivatives in Relativity] describing: Free fall in gravitational field. The moon moves in the straightest possible line in spacetime, which is bending in a helix. In a similar way the constant color strip is changing color inside our vision. An interesting discussion on the history of relativity.

The covariant derivative (or connection) is a generalization of the concept of derivative. The special case of zero connection corresponds to the conventional derivative. My idea was that in images covariant derivatives could be interpreted as the perceived gradient, as opposed to the true pixel gradient. Depending on the state of adaptation of the visual system, there exist an infinite number of different covariant derivatives at each point. They define different perceived gradients in an image. A given state of adaptation chooses just one.

Following similar approaches in physics (gauge theory), I believed that by replacing the partial derivatives in the original differential equation by covariant derivatives, we could produce the desired perceptual result. The equation could describe diffusion, for example. The covariant derivative could be synthesized separately, or it could be extracted from a second "neutral" area in the image. That area causes a nontrivial state of adaptation of the visual system. In this way our method would clone not pixels, but certain relations among pixels, their “structure and texture”.

Our numerical experiments showed that this theory gave beautiful results in practice. Areas were “healed” with correct texture, and not blurry as with earlier diffusion / inpainting methods. Jeff Chien did the challenging work of integrating these research ideas into the product. Some key suggestions were made by Mark Hamburg. With our joint effort the Healing Brush shipped as a major feature in Photoshop 7.0 in 2002. For the Healing Brush our covariant equation was approximated by the Poisson and bi-Poisson equations, and solved iteratively.

Today a special case of this method, based on Poisson’s equation, is widely used in image processing. It is often referred to as Poisson image editing, or gradient domain fusion; it has become a fundamental approach with numerous applications, such as: HDR compression, Poisson Editing, Photomontage, Artistic manipulations, and many others.

However, this Poisson-only approach lacks the covariant or perceptual interpretation -- and the applicaions that would come with it. From the viewpoint of the covariant theory it is only an approximation. The Poisson results are worse than the covariant results. My feeling is that we are missing half of the story here. It's even possible that we are only “scratching the surface” of what could be achieved based on deeper understanding of a perceptual, covariant derivative approach to image processing: Perceptual image editing...Theory of visual illusions...Hallucinating noisy, blurry, or HDR images...