Exemplar-based image inpainting: Fast priority and coherent nearest neighbor search

Raúl Martínez-Noriega, Aline Roumy, Gilles Blanchard

TL;DR

This paper introduces a novel exemplar-based image inpainting algorithm that significantly improves the preservation of linear edges and reduces error propagation. It achieves this through a refined filling order that prioritizes structures and a new similarity metric for selecting candidate patches, leading to more coherent and visually pleasing results with lower computational cost.

What Problem Does This Paper Address?

Image inpainting, the task of filling in missing or damaged parts of an image, becomes particularly challenging when dealing with large missing regions. While diffusion-based methods work well for small gaps, they struggle with larger areas that require both structure and texture reconstruction. Exemplar-based methods, inspired by texture synthesis, address this by copying information from known image regions (exemplars) to fill the missing parts. However, these methods face two key challenges: deciding which missing patches to fill first (filling order) and how to select the best exemplars to copy from. Poor choices in either can lead to artifacts, error propagation, and a loss of image coherence, especially along linear structures. This paper aims to tackle these issues to produce more robust and visually accurate inpainting results.

Methods

The proposed algorithm builds upon the greedy exemplar-based approach and introduces two main innovations:

  • Improved Filling Order: The authors refine the priority calculation for deciding which patch to fill next. They leverage Criminisi's original priority terms (confidence and data terms) but propose an exponential amplification of the data term. This amplification strategically boosts the priority of patches with strong linear structures (high data term values) while maintaining a more concentric filling order for smooth regions, thus better preserving edges.
  • Coherent Nearest Neighbor Search: To select the best exemplars, the paper introduces a new similarity metric that combines the Sum of Squared Differences (SSD) with the Hellinger distance.
  • SSD measures pixel-wise similarity within the known regions of patches.
  • Hellinger distance quantifies the similarity between the probability density functions (PDFs) of two patches, allowing for a comparison of the entire patch's information, not just the known parts.
  • Crucially, the authors propose different ways to compute the PDF based on whether a patch is classified as a "structure" or "texture" patch. For structure patches, they infer the PDF on the entire patch by considering linear edges. For texture patches, they focus on the known regions. This dual approach aims to reduce error propagation by better detecting outliers and ensuring spatial coherence.

Datasets

The paper evaluates its algorithm on natural images. Specific datasets are not explicitly named or introduced as new benchmarks. The examples shown in the figures include images like "Bungee jumping," "Soldier," "Bench," and "Jaguar."

Key Insights and Ideas

  • Exponential Amplification for Edge Preservation: The core idea behind the improved filling order is that a simple amplification of the data term in the priority calculation can dramatically improve the preservation of linear structures without significantly increasing computational complexity. This is a clever way to balance structure propagation with texture synthesis.
  • PDFs for Coherent Patch Selection: Using the Hellinger distance to compare patch PDFs is a powerful way to ensure that selected exemplars are not just similar in their known parts but also in their overall statistical properties. This leads to more visually coherent results.
  • Structure vs. Texture Patch Classification: Differentiating between structure and texture patches and computing their PDFs accordingly is a key insight. It allows the algorithm to tailor its similarity comparison to the specific characteristics of the image content, leading to more accurate and robust inpainting.
  • Reduced Error Propagation: The combination of the improved filling order and the new similarity metric effectively combats the common problem of error propagation in exemplar-based methods, resulting in cleaner and more artifact-free reconstructions.

Key Results

  • Improved Edge Preservation: The proposed algorithm demonstrates superior preservation of linear edges compared to existing methods, as visually evident in the provided figures.
  • Reduced Error Propagation: The algorithm significantly reduces error propagation, leading to a noticeable improvement in image quality, especially in block erasure scenarios where it outperforms other methods by at least 12 dB in PSNR.
  • Lower Computational Load: The paper claims that their approach has a significantly lower computational load compared to most algorithms used for comparison, while achieving better or similar performance.
  • Qualitative Improvements: The inpainted images are described as having a more natural look and better completeness of linear edges. The new metric is shown to select more visually pleasant patches, avoiding artifacts introduced by simpler metrics like SSD.

Limitations and Future Work

  • Parameter Tuning: The authors acknowledge that an open problem is finding an easy way to tune parameters, such as the threshold T for patch classification and the variance σ² for data term amplification, or even to avoid manual tuning altogether.
  • Patch Classification Improvement: While the current patch classification is effective, the authors suggest that further work could involve improving this classification and adapting the inpainting process more specifically to each class for potentially even better results.
  • Parametric Technique: The paper mentions the goal of developing a "less parametric technique," implying that current parameter tuning might still be a limitation.

Summary updated

Abstract

Greedy exemplar-based algorithms for inpainting face two main problems, decision of filling-in order and selection of good exemplars from which the missing region is synthesized. We propose an algorithm that tackle these problems with improvements in the preservation of linear edges, and reduction of error propagation compared to well-known algorithms from the literature. Our improvement in the filling-in order is based on a combination of priority terms, previously defined by Criminisi, that better encourages the early synthesis of linear structures. The second contribution helps reducing the error propagation thanks to a better detection of outliers from the candidate patches carried. This is obtained with a new metric that incorporates the whole information of the candidate patches. Moreover, our proposal has significant lower computational load than most of the algorithms used for comparison in this paper. Index Terms — exemplar, inpainting, coherence, priority 1.
BibTeX
@inproceedings{martineznoriega2012exemplar,
  author = {Raúl Martínez-Noriega and Aline Roumy and Gilles Blanchard},
  title = {{Exemplar-based image inpainting: Fast priority and coherent nearest neighbor search}},
  booktitle = {MLSP},
  year = {2012},
  doi = {10.1109/mlsp.2012.6349810},
}

Loading related content...

Figure