Image Compression with Isotropic and Anisotropic Shepard Inpainting

Rahul Mohideen Kaja Mohideen, Tobias Alt, Pascal Peter, Joachim WeickertarXiv 2024 · DOI · arXiv

TL;DR

Researchers have developed a new family of image codecs that replace complex, computationally expensive differential equations with a localized version of Shepard interpolation. By adding directional awareness (anisotropy) and a novel "joint inpainting and prediction" encoding scheme, these simple algorithms can outperform JPEG and JPEG2000 at high compression ratios while running orders of magnitude faster than traditional inpainting methods.

What Problem Does This Paper Address?

Inpainting-based compression is an unconventional but powerful approach: instead of storing every pixel, you store a tiny, carefully chosen fraction of them (a "mask") and let an algorithm "fill in the blanks" during decoding.

Historically, the best results came from codecs using Partial Differential Equations (PDEs) to diffuse information across the image. While effective, PDEs are a headache for engineers: they require sophisticated numerical solvers, are computationally heavy, and are difficult to implement efficiently. The authors of this paper asked: Can we achieve state-of-the-art compression using a much simpler mathematical tool?

Methods

The authors turn to Shepard interpolation, a method based on normalized weighted averaging. To make it work for modern compression, they introduced several key innovations:

  1. Localized Isotropic Shepard: Instead of letting every known pixel influence every unknown pixel (which is $O(N^2)$), they truncate the Gaussian weighting functions to a local neighborhood, making the process incredibly fast.
  2. Anisotropic Extension: Standard Shepard interpolation is "isotropic"—it spreads information equally in all directions, which blurs edges. The authors introduced Anisotropic Shepard Inpainting, which uses elliptical kernels that align with the image's local gradients, allowing information to flow along edges rather than across them.
  3. Data Selection (Subdivision Masks): Rather than just using a regular grid of pixels, they use a B-tree-based subdivision. The algorithm splits the image into smaller blocks where the reconstruction error is high, placing more data points in detailed areas.
  4. Joint Inpainting and Prediction (RJIP): During encoding, the codec predicts the value of the next pixel based on the pixels already processed. It then only stores the "residual" (the difference between the prediction and reality), which significantly reduces the final file size.
  5. Tonal Optimization: They don't just store the original pixel values; they mathematically "tweak" the stored values to ensure the final reconstructed image has the lowest possible Mean Squared Error (MSE).

Datasets

The researchers evaluated their methods using several standard benchmarks:

  • The Kodak Dataset: 24 high-quality images used to test general compression performance.
  • The Berkeley Segmentation Dataset (BSDS500): 500 images used to test performance on textured and complex scenes.
  • Sintel: Used specifically for runtime scaling experiments to see how the algorithm handles increasing resolutions (up to 4K).
  • Individual test images: Such as trui (piecewise smooth) and disk (synthetic binary) for ablation studies.

Key Insights and Ideas

  • The Speed-Simplicity Paradox: We often assume better quality requires more complexity. This paper shows that a "simple" weighted average, when combined with smart data selection and directional kernels, can rival or beat sophisticated PDE solvers.
  • Anisotropy is Essential: The jump from isotropic to anisotropic Shepard inpainting is the "aha moment" for quality. It allows the codec to maintain sharp boundaries even when 98% of the image data has been discarded.
  • Closed-Form Efficiency: For isotropic Shepard, the authors derived a closed-form solution for tonal optimization. This allows them to find the "perfect" pixel values almost instantly, whereas PDE-based methods require slow, iterative "trial and error" or complex linear system solvers.

Key Results

  • Speed: The proposed RJIP codec is up to five orders of magnitude faster for tonal optimization than traditional PDE-based approaches. It can compress a 4K image in roughly 5 seconds on a single CPU core.
  • Quality at High Compression: At high compression ratios (e.g., 70:1 or 100:1), the Shepard-based codecs consistently outperform JPEG and JPEG2000, which suffer from "blocking" and "ringing" artifacts at those levels.
  • Visual Fidelity: The anisotropic version (RJIP-A) produced significantly sharper results on the trui test image, achieving an MSE of 71.50 compared to JPEG's 160.57 at the same compression ratio.

Limitations and Future Work

  • Texture Challenges: Like most inpainting-based methods, these codecs still struggle with highly textured areas (like grass or gravel) compared to transform-based methods like JPEG.
  • Grayscale Focus: This paper focuses primarily on grayscale images. While the logic extends to color, the authors note that dedicated strategies for human color perception will be needed for a production-ready color codec.
  • Subdivision Overhead: While subdivision masks help with detail, the "tree" structure required to store the mask adds its own storage overhead, which can sometimes negate the gains in highly complex images.

The authors suggest that the next frontier is applying these Shepard-based techniques to depth maps and flow fields, where piecewise smoothness is common and the speed of Shepard inpainting would be a massive advantage.

Summary updated

Abstract

Inpainting-based codecs store sparse selected pixel data and decode by reconstructing the discarded image parts by inpainting. Successful codecs (coders and decoders) traditionally use inpainting operators that solve partial differential equations. This requires some numerical expertise if efficient implementations are necessary. Our goal is to investigate variants of Shepard inpainting as simple alternatives for inpainting-based compression. They can be implemented efficiently when we localise their weighting function. To turn them into viable codecs, we have to introduce novel extensions of classical Shepard interpolation that adapt successful ideas from previous codecs: Anisotropy allows direction-dependent inpainting, which improves reconstruction quality. Additionally, we incorporate data selection by subdivision as an efficient way to tailor the stored information to the image structure. On the encoding side, we introduce the novel concept of joint inpainting and prediction for isotropic Shepard codecs, where storage cost can be reduced based on intermediate inpainting results. In an ablation study, we show the usefulness of these individual contributions and demonstrate that they offer synergies which elevate the performance of Shepard inpainting to surprising levels. Our resulting approaches offer a more favourable trade-off between simplicity and quality than traditional inpainting-based codecs. Experiments show that they can outperform JPEG and JPEG2000 at high compression ratios.
BibTeX
@misc{mohideen2024image,
  author = {Rahul Mohideen Kaja Mohideen and Tobias Alt and Pascal Peter and Joachim Weickert},
  title = {{Image Compression with Isotropic and Anisotropic Shepard Inpainting}},
  year = {2024},
  eprint = {2406.06247},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2406.06247},
}
Figure