Optimising Different Feature Types for Inpainting-based Image Representations

Ferdinand Jost, Vassillen Chizhov, Joachim Weickert

TL;DR

This paper introduces a unified mathematical framework that allows image inpainting to use a diverse mix of features—such as gradients and local averages—rather than just raw pixel colors. By treating these features as linear constraints and using an automated "Voronoi densification" strategy to place them, the authors achieve significantly higher reconstruction quality from sparse data than traditional methods.

What Problem Does This Paper Address?

Inpainting-based image compression is a clever alternative to standards like JPEG. Instead of storing every pixel, it saves a tiny, carefully chosen subset of data (the "mask") and uses a diffusion process (like heat spreading) to fill in the gaps during decoding.

While most methods only store color values, some researchers have found that storing derivatives (gradients) can help capture edges better. However, these were usually "one-off" heuristic approaches. Before this paper, there wasn't a general way to mix different types of features—color, first-order derivatives, second-order derivatives, or even local averages—and optimize their locations and values simultaneously. The challenge is: how do you decide which feature is best for a specific part of an image, and how do you solve the resulting math problem efficiently?

Methods

The authors propose a Generalized Discrete Formulation. They frame inpainting as a constrained optimization problem where the goal is to find a smooth reconstruction that satisfies a set of linear equality constraints.

  1. Linear Constraints: Any feature that can be expressed as a convolution with a stencil (like a derivative or a box filter) fits into their model. This allows the framework to handle color values, $x$ and $y$ derivatives, and multiscale local averages in one go.
  2. Numerical Solver: Because the resulting system of equations is symmetric but "indefinite" (a tricky property for many solvers), they employ the SYMMLQ algorithm, which is robust enough to handle these specific mathematical hurdles.
  3. Spatial Optimization: To find the best locations for these features, they use an iterative "Voronoi densification" strategy. The algorithm looks at where the current reconstruction error is highest, partitions the image into Voronoi cells, and adds the most helpful feature type to the cells with the largest errors.
  4. Tonal Optimization: Once the locations are fixed, they perform a second pass to fine-tune the values of the stored features (e.g., slightly adjusting a gradient value) to minimize the global Mean Squared Error (MSE).

Datasets

The researchers evaluated their framework on several standard test images:

  • Color images: elpaso and windmill.
  • Grayscale images: trui, cameraman, and house.
  • Depth maps: ballet.

These images represent a range of challenges, from smooth gradients to sharp edges and complex textures.

Key Insights and Ideas

  • The Power of Generality: By realizing that most useful image features can be written as linear constraints ($Au = b$), the authors moved away from specialized "hacks" toward a robust, "plug-and-play" framework for inpainting.
  • Averages Matter: One of the most surprising findings is that local averages (e.g., the average color of a 16x16 patch) are highly effective features. They provide a "global" hint that complements the "local" detail provided by derivatives.
  • Automatic Budgeting: The algorithm automatically "spends" its data budget. In flat areas, it might choose a local average; near an edge, it might choose a derivative. This happens without manual tuning.
  • Monotone Improvement: The experiments show that as you increase the variety of feature types (while keeping the total number of data points the same), the reconstruction error consistently drops.

Key Results

The authors tested their method using a total mask density of 5% (meaning only 1 out of every 20 pixels' worth of data was stored).

  • Quantitative Gains: For the elpaso image, using five feature types instead of just color reduced the MSE from 32.46 to 23.25.
  • Tonal Optimization Impact: Adjusting the feature values (tonal optimization) improved the reconstruction quality by about one-third across the board.
  • Visual Quality: The qualitative results show that the multi-feature approach preserves sharp edges and structural details much better than color-only inpainting, which often looks "blurry" at high compression ratios.

Limitations and Future Work

While the paper provides a powerful representation framework, it does not yet address coding aspects. To turn this into a full image codec (like a .jpg file), the authors need to figure out how to efficiently compress the locations and values of these diverse features into a bitstream.

Additionally, the current framework is limited to linear inpainting operators (homogeneous diffusion). The authors suggest that extending this to nonlinear operators—which can handle edges even more sharply—is a promising next step. They also plan to explore an even wider range of feature types to see if further gains are possible.

Summary updated

Abstract

Inpainting-based image compression is a promising alternative to classical transform-based lossy codecs. Typically it stores a carefully selected subset of all pixel locations and their colour values. In the decoding phase the missing information is reconstructed by an inpainting process such as homogeneous diffusion inpainting. Optimising the stored data is the key for achieving good performance. A few heuristic approaches also advocate alternative feature types such as derivative data and construct dedicated inpainting concepts. However, one still lacks a general approach that allows to optimise and inpaint the data simultaneously w.r.t. a collection of different feature types, their locations, and their values. Our paper closes this gap. We introduce a generalised inpainting process that can handle arbitrary features which can be expressed as linear equality constraints. This includes e.g. colour values and derivatives of any order. We propose a fully automatic algorithm that aims at finding the optimal features from a given collection as well as their locations and their function values within a specified total feature density. Its performance is demonstrated with a novel set of features that also includes local averages. Our experiments show that it clearly outperforms the popular inpainting with optimised colour data with the same density.
BibTeX
@inproceedings{jost2023optimising,
  author = {Ferdinand Jost and Vassillen Chizhov and Joachim Weickert},
  title = {{Optimising Different Feature Types for Inpainting-based Image Representations}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10097051},
}
Figure