Diffusion-Shock Inpainting

Kristina Schaefer, Joachim Weickert

This paper, presented at the 2023 Scale Space and Variational Methods in Computer Vision (SSVM) conference, introduces a surprisingly simple yet powerful approach to image inpainting. By blending two "classic" image processing techniques, the authors have created a method that can bridge massive gaps in images while keeping edges razor-sharp.

TL;DR

Diffusion–Shock (DS) inpainting is a new second-order integrodifferential equation that combines the smooth filling power of homogeneous diffusion with the edge-sharpening capabilities of shock filters. It outperforms many complex higher-order methods by providing perfectly sharp edges and guaranteed numerical stability (the maximum–minimum principle) in a computationally efficient framework.

What Problem Does This Paper Address?

Image inpainting is the art of filling in missing or damaged parts of an image. The challenge lies in "hallucinating" structures that look natural.

Existing methods generally fall into two camps:

  1. Simple Second-Order PDEs: Like homogeneous diffusion. These are stable and fast but tend to blur edges over long distances.
  2. Higher-Order PDEs: Like Euler’s elastica or Cahn–Hilliard models. These can connect lines over gaps, but they are mathematically complex, computationally expensive, and often suffer from "dissipative artifacts"—essentially, they still get a bit blurry.

Furthermore, many advanced methods lack a discrete maximum–minimum principle. Without this, the algorithm might produce "overshoots" or "undershoots," creating pixels that are brighter or darker than anything in the original data (ringing artifacts).

Methods

The authors propose Diffusion–Shock (DS) inpainting, which uses a convex combination of two processes:

  1. Homogeneous Diffusion: This acts as the "filler," efficiently smoothing out flat areas.
  2. Coherence-Enhancing Shock Filtering: This acts as the "sharpener." It uses a structure tensor to sense the direction of image features and applies morphological operations (dilation and erosion) to create perfectly sharp "shocks" or edges.

The "magic" happens via a weight function (the Charbonnier diffusivity) that detects gradients. In flat areas, diffusion takes over; near edges, the shock filter dominates.

Key Innovation: The authors developed a specific discrete scheme using a weighted combination of axial and diagonal differences. They proved (Theorem 1) that this scheme satisfies the discrete maximum–minimum principle, ensuring the algorithm never produces out-of-bounds pixel values.

Datasets

The paper evaluates the method on several challenging synthetic and real-world scenarios:

  • Binary Shape Completion: Reconstructing crosses and bars (inspired by Cahn–Hilliard experiments).
  • Sparse Dipoles: Reconstructing a full disk from just four tiny dots (dipoles) or two half-planes from a single dipole.
  • The Kanizsa Triangle: A classic computer vision benchmark for connecting interrupted edges.
  • Sparse Greyscale Images: Reconstructing the well-known "Peppers" and "House" images from only 10% randomly sampled pixels.

The method was compared against a "who's who" of inpainting: TV inpainting, biharmonic interpolation, EED (Edge-Enhancing Anisotropic Diffusion), and Euler’s elastica.

Key Insights and Ideas

  • Synergy of Opposites: Diffusion is isotropic (spreads in all directions), while shock filters are highly anisotropic (follow a specific direction). Combining them allows the model to fill large holes while maintaining directional "flow."
  • Second-Order is Enough: A major "aha" moment is that you don't necessarily need complex fourth-order equations to get high-quality results. By using a second-order integrodifferential equation, the authors achieve results comparable to or better than much more complex models.
  • The Power of the Structure Tensor: By guiding the shock filter with a structure tensor, the method becomes robust to noise and can "see" through gaps to connect interrupted lines.
  • Stability by Design: Proving the stability of the discrete algorithm is a significant contribution, as it makes the method reliable for practical engineering applications where artifacts are unacceptable.

Key Results

  • Razor-Sharp Edges: Qualitatively, DS inpainting produces significantly sharper edges than Euler’s elastica or EED, especially in binary image reconstruction.
  • Long-Distance Connectivity: The method successfully reconstructed a disk from just four dipoles, demonstrating an incredible ability to bridge gaps.
  • Efficiency: On a standard consumer CPU (Intel i9), the method reconstructed 256x256 images in roughly 3.3 to 3.7 seconds.
  • Stability: Unlike EED, DS inpainting is guaranteed to stay within the original grey-value range, preventing unwanted artifacts.

Limitations and Future Work

  • Parameter Sensitivity: The method relies on several parameters (scales for Gaussian smoothing $\sigma, \rho, \nu$ and a contrast parameter $\lambda$). While the authors used "optimised parameters" for their tests, they don't provide an automated way to choose these for a new, unknown image.
  • Integrodifferential Complexity: While simpler than fourth-order PDEs, the integrodifferential nature (using convolutions inside the PDE) still requires careful implementation.
  • Future Directions: The authors suggest exploring other applications for this class of equations beyond just inpainting, hinting at a broader potential for "diffusion-shock" logic in image processing.

Summary updated

Abstract

We propose diffusion-shock (DS) inpainting as a hitherto unexplored integrodifferential equation for filling in missing structures in images. It combines two carefully chosen components that have proven their usefulness in different applications: homogeneous diffusion inpainting and coherence-enhancing shock filtering. DS inpainting enjoys the complementary synergy of its building blocks: It offers a high degree of anisotropy along an eigendirection of the structure tensor. This enables it to connect interrupted structures over large distances. Moreover, it benefits from the sharp edge structure generated by the shock filter, and it exploits the efficient filling-in effect of homogeneous diffusion. The second order equation that underlies DS inpainting inherits a continuous maximum-minimum principle from its constituents. In contrast to other attractive second order inpainting equations such as edge-enhancing anisotropic diffusion, we can guarantee this property also for the proposed discrete algorithm. Our experiments show a performance that is comparable to or better than many linear or nonlinear, isotropic or anisotropic processes of second or fourth order. They include homogeneous diffusion, biharmonic interpolation, TV inpainting, edge-enhancing anisotropic diffusion, the methods of Tschumperlé and of Bornemann and März, Cahn-Hilliard inpainting, and Euler's elastica.
BibTeX
@inproceedings{schaefer2023diffusion,
  author = {Kristina Schaefer and Joachim Weickert},
  title = {{Diffusion-Shock Inpainting}},
  booktitle = {SSVM},
  year = {2023},
  doi = {10.1007/978-3-031-31975-4\_45},
}

Loading related content...

Figure