06-11-2012, 02:12 PM
Applying Modern PDE Techniques to Digital Image Restoration
Applying Modern PDE Techniques.pdf (Size: 86.52 KB / Downloads: 21)
Inpainting, or image interpolation, is a process used to reconstruct missing parts of images. Artists have
long used manual inpainting to restore damaged paintings. Today, mathematicians apply partial
differential equations (PDEs) to automate image interpolation. The PDEs operate in much the same way
that trained restorers do: They propagate information from the structure around a hole into the hole to fill it
in [1,2,3].
While artists can work directly on a painting, a PDE requires a mathematical representation of the subject
matter, such as a digital image. A digital image is essentially a 2D matrix of integers, with each integer
representing the color or grayscale value of an individual pixel. Holes in the image are represented by
unknown values in the matrix. PDE-inpainting fills in these missing values based on the values of nearby
pixels.
One of my first explorations of the use of PDEs for inpainting focused on the restoration of 14th-century
frescoes. I have found that high-order, nonlinear PDEs enable a wide range of other applications for
inpainting, in fields as diverse as medicine, astronomy, and cartography.
For me, MATLAB® is a natural choice for inpainting with PDEs. MATLAB enables me to rapidly develop
and test preliminary algorithms. The MATLAB operations in my scripts have a virtually one-to-one
relationship with the steps in the algorithms I develop. This level of correspondence is all but impossible to
achieve using a lower-level programming language. I can easily visualize the results in many different
formats using graphs and plots, a type of graphical analysis that, with a lower-level language, often
requires a second tool.
Simple Inpainting: Fourier's Heat Equation
Fourier's heat equation describes how temperature in a material changes. Given this PDE, knowledge of
the thermal conductivity of the material, and knowledge of the initial temperature conditions u(t=0), it is
possible to calculate the temperature at any point in the material for any given time by The heat equation is also known as the diffusion equation because it describes how a value (in this case,
temperature) diffuses across an area over a time interval.
With grayscale values replacing temperature, a slightly modified version of this equation can be used for
basic inpainting. I implemented a simple MATLAB program that uses this technique. This program can
restore an image with holes cut in it by propagating (or diffusing) the grayscale values surrounding each
hole toward the hole's center (Figure 1).
Handling Nonlinearity: The Perona-Malik Equation
Because the heat equation possesses only smooth solutions, it cannot preserve discontinuous image
features such as edges. In particular, it cannot propagate edges across large holes because it relies on
linear interpolation. In Figure 2, these edges (the dark parallel lines on either side of the hole) are not
propagated into the hole by the inpainting process.
To address this shortcoming, I created a second MATLAB program that uses nonlinear diffusion. This
program uses total variation flow [2], a technique in which the diffusivity constant depends upon the size
of the image gradient, reducing the amount of diffusion that occurs near edges
Factoring in Gradients: Fourth-Order Total Variation Equation
Higher-order PDEs address the deficiencies of the total variation flow approach. With a MATLAB program
that uses fourth-order PDEs, we can take two boundary conditions into account instead of just one.
Specifically, instead of factoring in only the grayscale value of the pixels near a hole, the program also
factors in the gradient, which enables it to model the direction in which edges should be propagated into
the hole.
Material science researchers often use the Cahn-Hilliard equation to model phase separation, a process
in which the constituents of a fluid mixture spontaneously separate, coarsening the phases. The Cahn-
Hilliard equation has been very successfully applied to the inpainting of binary structures with large gaps
[5].