Non-Local Patch-Based Image Inpainting
Alasdair Newson, Andrés Almansa, Yann Gousseau, Patrick Pérez
Alasdair Newson, Andrés Almansa, Yann Gousseau, and Patrick Pérez, Non-Local Patch-Based Image Inpainting, Image Processing On Line, 7 (2017), pp. 373–385.

Communicated by Pablo Arias
Demo edited by Pablo Arias


Image inpainting is the process of filling in missing regions in an image in a plausible way. In this contribution, we propose and describe an implementation of a patch-based image inpainting algorithm. The method is actually a two-dimensional version of our video inpainting algorithm proposed in [A. Newson et al., Video inpainting of complex scenes, SIAM Journal of Imaging Sciences, 7 (2014)]. The algorithm attempts to minimize a highly non-convex functional, first introducted by Wexler et al. in [Wexler et al., Space-time video completion, CCVPR (2004)]. The functional specifies that a good solution to the inpainting problem should be an image where each patch is very similar to its nearest neighbor in the unoccluded area. Iterations are performed in a multi-scale framework which yields globally coherent results. In this manner two of the major goals of image inpainting, the correct reconstruction of textures and structures, are addressed. We address a series of important practical issues which arise when using such an approach. In particular, we reduce execution times by using the PatchMatch [C. Barnes, PatchMatch: a randomized correspondence algorithm for structural image editing, ACM Transactions on Graphics, (2009)] algorithm for nearest neighbor searches, and we propose a modified patch distance which improves the comparison of textured patches. We address the crucial issue of initialization and the choice of the number of pyramid levels, two points which are rarely discussed in such approaches. We provide several examples which illustrate the advantages of our algorithm, and compare our results with those of state-of-the-art methods.