Domain Decomposition Algorithms for Real-time Homogeneous Diffusion Inpainting in 4K

Niklas Kämper, Joachim Weickert

TL;DR

This paper achieves a major milestone in image processing: real-time 4K image inpainting. By adapting Domain Decomposition—specifically a multilevel Optimized Restricted Additive Schwarz (ORAS) method—the authors enable high-quality reconstruction of 4K images at over 30 frames per second on a single consumer GPU, outperforming previous state-of-the-art solvers by more than a factor of five.

What Problem Does This Paper Address?

Inpainting-based image compression is a clever alternative to standard methods like JPEG. Instead of saving every pixel, you only store a tiny fraction of "important" pixels (e.g., 5%) and use a mathematical process—diffusion—to "fill in the blanks" during decoding. While this produces high-quality results without the "blocky" artifacts of JPEG, it is computationally expensive.

The challenge is scale. A 4K image contains over 8 million pixels. Solving the differential equations required to inpaint these pixels typically takes seconds, not milliseconds. To be useful for video or interactive applications, the process needs to happen in under 33 milliseconds (30 FPS). Previous attempts using multicore CPUs or standard solvers fell short by at least an order of magnitude.

Methods

The authors bridge the gap by moving away from sequential solvers and embracing massive parallelism through Domain Decomposition.

  1. Homogeneous Diffusion: They model the inpainting as a steady-state heat equation (Laplace equation). This results in a massive linear system ($Au=b$) where every unknown pixel is a variable.
  2. ORAS (Optimized Restricted Additive Schwarz): Instead of solving the whole 8-million-pixel system at once, they subdivide the image into small, overlapping blocks (32x32 pixels). Each block is solved in parallel on the GPU. Crucially, ORAS allows these blocks to "communicate" at their boundaries, ensuring the final image is seamless and mathematically accurate to the global solution.
  3. Multilevel Strategy: To speed up convergence, they use a "coarse-to-fine" approach. They first solve a low-resolution version of the image to get the general structure right, then use that as a starting point for the full 4K resolution.
  4. Local Solver: Within each small block, they use a Conjugate Gradient (CG) algorithm, which is highly efficient for the GPU's architecture.

Datasets

The primary evaluation was performed on a high-resolution 4K test image titled "lofsdalen" (3840 × 2160 pixels).

  • Masking: They used an optimized inpainting mask created via Voronoi densification, retaining only 5% of the original pixel data.
  • Scaling Test: They also tested the algorithm across various resolutions ranging from 960 × 540 up to 4K to analyze how the runtime scales with image size.

Key Insights and Ideas

  • Seams are Optional: Unlike JPEG, which processes 8x8 blocks independently and creates visible "seams," domain decomposition iterates until the local solutions match the global one. You get the speed of block-based processing without the visual artifacts.
  • Parallelism is King: Most traditional solvers (like Multigrid) are difficult to implement efficiently on GPUs because they require complex data dependencies. Domain decomposition is "embarrassingly parallel" by design, making it a perfect fit for modern graphics hardware.
  • The PSNR "Sweet Spot": The authors observed that you don't need to solve the math to infinite precision. By monitoring the Peak Signal-to-Noise Ratio (PSNR), they found that a "relative residual" of $10^{-3}$ is enough to reach optimal visual quality, allowing them to stop the solver early and save time.

Key Results

  • Real-time Performance: The multilevel ORAS algorithm inpainted a 4K color image in just 25.2 milliseconds. This comfortably exceeds the 33.3 ms requirement for 30 FPS video.
  • Significant Speedup: Compared to a standard multilevel Conjugate Gradient solver (the previous standard for this task), the ORAS method was 5.61 times faster at reaching the optimal PSNR.
  • Linear Scaling: The computational time grows linearly with the number of pixels. This "ideal scaling" suggests the method will remain efficient even as resolutions move toward 8K and beyond.

Limitations and Future Work

The main limitation is that this paper focuses on homogeneous diffusion, which is a linear process. While great for certain image types (like depth maps or cartoon-like images), it can struggle with highly textured areas compared to more complex nonlinear diffusion models.

The authors note that their next step is extending this domain decomposition framework to more advanced, non-linear inpainting operators. If they can maintain real-time speeds with non-linear models, inpainting-based codecs could become a serious threat to traditional transform-based compression standards.

Summary updated

Abstract

Inpainting-based compression methods are qualitatively promising alternatives to transform-based codecs, but they suffer from the high computational cost of the inpainting step. This prevents them from being applicable to time-critical scenarios such as real-time inpainting of 4K images. As a remedy, we adapt state-of-the-art numerical algorithms of domain decomposition type to this problem. They decompose the image domain into multiple overlapping blocks that can be inpainted in parallel by means of modern GPUs. In contrast to classical block decompositions such as the ones in JPEG, the global inpainting problem is solved without creating block artefacts. We consider the popular homogeneous diffusion inpainting and supplement it with a multilevel version of an optimised restricted additive Schwarz (ORAS) method that solves the local problems with a conjugate gradient algorithm. This enables us to perform real-time inpainting of 4K colour images on contemporary GPUs, which is substantially more efficient than previous algorithms for diffusion-based inpainting.
BibTeX
@inproceedings{kamper2022domain,
  author = {Niklas Kämper and Joachim Weickert},
  title = {{Domain Decomposition Algorithms for Real-time Homogeneous Diffusion Inpainting in 4K}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2022},
  doi = {10.1109/icassp43922.2022.9746831},
}
Figure