Efficient Data Optimisation for Harmonic Inpainting with Finite Elements

Vassillen Chizhov, Joachim WeickertCAIP 2021 · DOI

Abstract

Inpainting-based image compression offers a compelling alternative to transform-based standards like JPEG by storing a sparse set of mask pixels and reconstructing the image via partial differential equations (PDEs). However, the computational cost of optimizing mask pixel locations and tonal values has historically limited this approach to low-resolution images. This paper introduces a Finite Element Method (FEM) framework for harmonic inpainting that utilizes adaptive triangulation and linear-scaling optimization. The proposed method achieves reconstruction speeds up to 10,000 times faster than previous state-of-the-art techniques while improving visual quality and reducing memory overhead, enabling the processing of high-resolution, 16-megapixel images on standard hardware.

Introduction

Harmonic inpainting-based compression relies on solving the Laplace equation to fill in missing data from a sparse mask. The primary challenge lies in the "encoding" phase, which requires two distinct optimizations: spatial optimization (finding optimal pixel locations) and tonal optimization (fine-tuning color values). Traditional approaches using Finite Difference Methods (FDM) on regular grids suffer from quadratic scaling ($O(N^2)$) and visual artifacts known as "logarithmic singularities"—spiky distortions around stored pixels. These limitations have long relegated PDE-based compression to a theoretical curiosity rather than a practical tool.

Methodology

The core innovation of this work is the transition from FDM to a Finite Element Method (FEM) based on adaptive triangle meshes.

Adaptive Triangulation and Spatial Optimization

Instead of a rigid grid, the authors employ Delaunay triangulation where each mask pixel serves as a vertex. This allows the mesh density to adapt naturally to image features—dense in high-detail areas and sparse in flat regions. To optimize these locations efficiently, a "coarse-to-fine" densification strategy is used. Starting with a minimal set of points, the algorithm iteratively adds pixels in regions with the highest reconstruction error. This approach is significantly more efficient than traditional "pruning" methods.

Figure 1: High-quality reconstruction of the peppers benchmark using the proposed FEM approach.

Linear-Scaling Tonal Optimization

To address the memory bottleneck of tonal optimization, the researchers implemented a nested conjugate gradient (CG) solver. By exploiting the inherent sparsity of the Laplace operator, the memory requirements scale linearly ($O(N)$) with the number of pixels. Furthermore, because a Delaunay triangulation can be reconstructed solely from vertex coordinates, the mesh connectivity does not need to be stored, maximizing compression efficiency.

Key Results and Discussion

The FEM-based approach demonstrates substantial improvements in both speed and quality over FDM baselines. Quantitatively, for the trui benchmark at 4% pixel density, the Mean Squared Error (MSE) dropped from 36.04 (FDM) to 26.62 (FEM). Visually, the FEM approach eliminates the spiky singularities common in FDM reconstructions, producing smoother transitions and more natural textures.

Figure 6: Visual comparison of standard benchmarks (trui, walter, peppers). The top row shows the superior, smooth reconstructions from the proposed FEM method, while the bottom row displays the artifact-prone FDM results.

Computationally, the speedups are transformative. Spatial optimization for a 512x512 image was reduced from 4 hours using previous probabilistic methods to just 1.3 seconds. This efficiency allowed the authors to successfully compress and reconstruct a 16-megapixel image (saomiguel), a task previously considered computationally infeasible for optimized harmonic inpainting.

Conclusion

By replacing traditional grid-based discretizations with adaptive finite elements and linear-scaling solvers, this research removes the primary barriers to practical PDE-based image compression. Future work will explore extending this framework to anisotropic PDEs for better edge handling and applying these principles to data on non-Euclidean manifolds.

Summary updated

BibTeX
@inproceedings{chizhov2021efficient,
  author = {Vassillen Chizhov and Joachim Weickert},
  title = {{Efficient Data Optimisation for Harmonic Inpainting with Finite Elements}},
  booktitle = {CAIP},
  year = {2021},
  doi = {10.1007/978-3-030-89131-2\_40},
}
Figure