Exemplar-based inpainting from a variational point of view

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 [Ann. Statist., 34 (2006), pp. 1751-1773] 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: (1) to propose well-posed variational models in the continuous domain that can be naturally associated to exemplar-based algorithms; (2) to investigate their ability to reconstruct either local or long-range geometric features like edges. In particular, we propose several optimization models in ℝ^N, we discuss their relation with the original algorithms, and we show the existence of minimizers in a suitable weak framework. Focusing on a simple two-dimensional situation, we provide experimental evidence that basic exemplar-based algorithms are able to reconstruct a local geometric information, whereas the minimization of the proposed variational models allows a 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 toward new inpainting algorithms with an improved quality of geometry reconstruction and no loss of quality for texture reconstruction.