Image Inpainting Based on Exemplar and Sparse Representation

Lei Zhang, Baosheng Kang, Benting Liu, Fei ZhangInternational Journal of Signal Processing Image Processing and Pattern Recognition 2016 · DOI

TL;DR

This paper introduces a novel image inpainting technique that cleverly combines exemplar-based and sparse representation methods. By using sparse representation to refine patches that might otherwise cause visual discontinuities, the approach aims to produce more natural and error-free restored images, outperforming traditional exemplar-based methods.

What Problem Does This Paper Address?

Image inpainting is the process of filling in missing or damaged regions of an image in a way that is imperceptible to the viewer. This is crucial for restoring old photographs, removing unwanted objects, or reconstructing corrupted image data. Existing methods often fall into categories like Partial Differential Equation (PDE)-based, texture synthesis, or exemplar-based approaches. While exemplar-based methods are good at filling large, textured regions by copying similar patches from known areas, they can sometimes introduce visual discontinuities if the best-matching patch isn't a perfect fit. This can lead to accumulated errors and unnatural results. The paper addresses this by proposing a hybrid approach that leverages the strengths of both exemplar-based methods and sparse representations to mitigate these issues.

Methods

The proposed method combines two key techniques:

  • Exemplar-Based Patch Selection: Similar to established methods, the algorithm first identifies candidate patches from the known (source) region that are most similar to the missing (target) patch. Similarity is typically measured by the Sum of Squared Differences (SSD) of the existing pixels within the patches. A priority mechanism is used to determine the order in which patches are filled, favoring those on strong edges and surrounded by high-confidence pixels.
  • Sparse Representation for Refinement: This is the core novelty. When an exemplar patch is selected, the algorithm doesn't immediately use it. Instead, it calculates two metrics:
  • DBP (Distance Between Patches): Measures the SSD between the target patch and the exemplar patch using only the existing pixels.
  • DIP (Distance in Patches): Measures the difference between the existing pixels in the target patch and the corresponding pixels in the exemplar patch. If either DBP or DIP exceeds predefined thresholds (β and γ), it indicates a potential for visual discontinuity or error. In such cases, instead of directly copying the exemplar patch, the algorithm employs sparse representation. It uses a learned redundant dictionary (trained via K-SVD) to find a sparse representation of the target patch. This sparse representation is then used to reconstruct the target patch, effectively "correcting" the potential mismatch from the exemplar.

The paper also details:

  • Patch Priority Computation: Based on confidence (number of existing pixels) and data terms (isophote strength at the boundary).
  • Dictionary Learning: K-SVD is used to train an over-complete dictionary for sparse representation.
  • Threshold Determination: Thresholds β and γ are determined empirically by analyzing the distribution of DBP and DIP values on sample data.

Datasets

The paper evaluates its approach on:

  • Synthetic Images: Two test images are synthesized to demonstrate the method's ability to handle specific geometric shapes and regions.
  • Natural Images: Several natural images are used to showcase the algorithm's practicality and effectiveness in real-world scenarios.

The paper does not introduce new datasets but uses standard image inpainting scenarios for evaluation.

Key Insights and Ideas

  • The "Best" Exemplar Isn't Always Best: The paper highlights a critical limitation of purely exemplar-based methods: the patch with the lowest SSD might still introduce visual artifacts due to subtle differences or structural mismatches.
  • Sparse Representation as a "Correction" Mechanism: The core idea is to use sparse representation not as the primary inpainting method, but as a sophisticated fallback mechanism to refine or replace potentially problematic exemplar patches. This prevents error accumulation.
  • Synergy of Two Approaches: By combining exemplar-based search (efficient for finding good candidates) with sparse representation (robust for detailed reconstruction), the algorithm aims to achieve the best of both worlds.
  • Thresholding is Key: The effectiveness of the hybrid approach hinges on correctly identifying when to switch from direct exemplar replacement to sparse representation-based reconstruction using appropriate thresholds.

Key Results

The experimental results, shown in Figures 6-9, demonstrate that the proposed approach generally produces more visually pleasing and natural results compared to the reference exemplar-based method [15]. Specifically:

  • Synthetic Images: The proposed method successfully restores regions without introducing undesired objects or artifacts, unlike the reference method which sometimes shows such issues.
  • Natural Images: The recovered images using the proposed method are described as more natural and better meeting human visual requirements, avoiding the introduction of unsuitable exemplar patches and subsequent undesired objects.

Quantitative results (e.g., specific PSNR or SSIM values) are not explicitly detailed in the provided text, but the qualitative results are presented as superior.

Limitations and Future Work

  • Threshold Determination: While a method for determining thresholds is presented, it's based on empirical analysis of sample data. The paper doesn't elaborate on how these thresholds might generalize across vastly different image types or missing region characteristics.
  • Computational Cost: Sparse representation, especially with dictionary learning, can be computationally intensive. While not explicitly stated as a limitation, it's an inherent trade-off.
  • Future Work: The paper suggests that the proposed algorithm can be viewed as a generalization of both exemplar-based and sparse-representation-based methods. This implies potential for further exploration of how to optimally tune the balance between these two components for various inpainting tasks. The authors also mention that their approach is efficient for restoring damaged images and removing unwanted objects.

Summary updated

Abstract

We propose a novel image inpainting approach in which the exemplar and the sparse representation are combined together skillfully. In the process of image inpainting, often there will be such a situation: although the sum of squared differences (SSD) of exemplar patch is the smallest among all the candidate patches, there may be a noticeable visual discontinuity in the recovered image when using the exemplar patch to replace the target patch. In this case, we cleverly use the sparse representation of image over a redundant dictionary to recover the target patch, instead of using the exemplar patch to replace it, so that we can promptly prevent the occurrence and accumulation of errors, and obtain satisfied results. Experiments on a number of real and synthetic images demonstrate the effectiveness of proposed algorithm, and the recovered images can better meet the requirements of human vision.
BibTeX
@article{zhang2016image,
  author = {Lei Zhang and Baosheng Kang and Benting Liu and Fei Zhang},
  title = {{Image Inpainting Based on Exemplar and Sparse Representation}},
  journal = {International Journal of Signal Processing Image Processing and Pattern Recognition},
  year = {2016},
  doi = {10.14257/ijsip.2016.9.9.17},
}
Figure