ANALYSIS OF A VARIATIONAL FRAMEWORK FOR EXEMPLAR-BASED IMAGE INPAINTING

In this paper we study some variational models for exemplar-based image inpainting, namely the patch nonlocal means and the patch nonlocal Poisson methods, previously studied by the authors from the experimental point of view. In both cases, the unknowns are the image u to be reconstructed and a weight function w expressing the similarity of patches. As a limit case of the studied framework, the weight function reduces to a correspondence map from the inpainting domain to the known part of the image. We prove the existence and regularity of minima for both functionals. In particular, we prove the existence of optimal correspondence maps which are uniform limits of maps of bounded variation with finitely many values. Then we prove the convergence of an alternating optimization scheme for the variables (u, w). We also prove the convergence in probability of the PatchMatch method, a recently introduced and efficient algorithm for computing optimal correspondence maps. Finally, we display some numerical experiments illustrating the performance and properties of the methods.