# Exemplar-based inpainting from a variational point of view

created by masnou on 06 Jan 2009

[BibTeX]

Submitted Paper

Inserted: 6 jan 2009

Year: 2008

Abstract:

Among all methods for reconstructing missing regions in a digital image, the so-called exemplar-based algorithms are very efficient and often produce striking results. They are based on the simple idea -- initially used for texture synthesis -- that the unknown part of an image can be reconstructed by simply pasting samples extracted from the known part. Beyond heuristic considerations, there have been very few contributions in the literature to explain from a mathematical point of view the performances of these purely algorithmic and discrete methods. More precisely, a recent paper by Levina and Bickel provides a theoretical explanation of their ability to recover very well the texture, but nothing equivalent has been done so far for the recovery of geometry. Our purpose in this paper is twofold: \begin{enumerate} \item To propose well-posed variational models in the continuous domain that can be naturally associated to exemplar-based algorithms; \item To investigate their ability to reconstruct either local or long-range geometric features like edges. \end{enumerate} In particular, we propose several optimization models in ${\mathbf R}^N$, we discuss their relation with the original algorithms, and show the existence of minimizers in the framework of functions of bounded variation. Focusing on a simple 2D situation, we provide experimental evidences that basic exemplar-based algorithms are able to reconstruct a {\it local} geometric information whereas the minimization of the proposed variational models allows a {\it global} reconstruction of geometry and in particular of smooth edges. The derivation of globally minimizing algorithms associated to these models is still an open problem. Yet the results presented in this paper are a first step towards new inpainting algorithms with an improved quality of geometry reconstruction and no loss of quality for texture reconstruction.