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 64 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 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 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 towards new inpainting algorithms with an improved quality of geometry reconstruction and no loss of quality for texture reconstruction. 1