Non-Local Patch-Based Image Inpainting
Alasdair Newson, Andrés Almansa, Yann Gousseau, Patrick Pérez
⚠ This is a preprint. It may change before it is accepted for publication.


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 [Alasdair Newson, Andrés Almansa, Matthieu Fradet, Yann Gousseau, and Patrick Pérez, Video inpainting of complex scenes, SIAM Journal of Imaging Sciences, 7 (2014)]. The algorithm attempts to minimise a highly non-convex functional, first introducted by Wexler et al. The functional specifies that a good solution to the inpainting problem should be an image where each patch is very similar to its nearest neighbour 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 algorithm for nearest neighbour searches, and we propose a modified patch distance which improves the comparison of textured patches. We address the crucial issue of initialisation 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.