IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 13, NO. 9, SEP 2004 1Region Filling and Object Removal byExemplar-Based Image InpaintingA. Criminisi*, P. P´erez and K. ToyamaMicrosoft Research, Cambridge (UK) and Redmond (US)[email protected]—A new algorithm is proposed for removing large objects fromdigital images. The challenge is to fill in the hole that is left behind in avisually plausible way.In the past, this problem has been addressed by two classes of algo-rithms: (i) “texture synthesis” algorithms for generating large image re-gions from sample textures, and (ii) “inpainting” techniques for filling insmall image gaps. The former has been demonstrated for “textures” – re-peating two-dimensional patterns with some stochasticity; the latter focuson linear “structures” which can be thought of as one-dimensional patterns,such as lines and object contours.This paper presents a novel and efficient algorithm that combines theadvantages of these two approaches. We first note that exemplar-based tex-ture synthesis contains the essential process required to replicate both tex-ture and structure; the success of structure propagation, however, is highlydependent on the order in which the filling proceeds. We propose a best-firstalgorithm in which the confidence in the synthesized pixel values is propa-gated in a manner similar to the propagation of information in inpainting.The actual colour values are computed using exemplar-based synthesis.In this paper the simultaneous propagation of texture and structure in-formation is achieved by a single, efficient algorithm. Computational effi-ciency is achieved by a block-based sampling process.A number of examples on real and synthetic images demonstrate theeffectiveness of our algorithm in removing large occluding objects as wellas thin scratches. Robustness with respect to the shape of the manuallyselected target region is also demonstrated. Our results compare favorablyto those obtained by existing techniques.Keywords— Object Removal, Image Inpainting, Texture Synthesis, Si-multaneous Texture and Structure Propagation.I. INTRODUCTIONThis paper presents a novel algorithm for removing large ob-jects from digital photographs and replacing them with visuallyplausible backgrounds. Figure 1 shows an example of this task,where the foreground person (manually selected as the targetregion) is automatically replaced by data sampled from the re-mainder of the image. The algorithm effectively hallucinatesnew colour values for the target region in a way that looks “rea-sonable” to the human eye. This paper builds upon and extendsthe work in [8], with a more detailed description of the algorithmand extensive comparisons with the state of the art.In previous work, several researchers have considered texturesynthesis as a way to fill large image regions with “pure” tex-tures – repetitive two-dimensional textural patterns with mod-erate stochasticity. This is based on a large body of texture-synthesis research, which seeks to replicate texture ad infinitum ,given a small source sample of pure texture [1], [9], [11], [12],[13], [14], [16], [17], [18], [22], [25]. Of particular interest areexemplar-based techniques which cheaply and effectively gen-erate new texture by sampling and copying colour values fromthe source [1], [11], [12], [13], [17].As effective as these techniques are in replicating consistenttexture, they have difficulty filling holes in photographs of real-world scenes, which often consist of linear structures and com-abFig. 1. Removing large objects from images. (a) Original photograph. (b) Theregion corresponding to the foreground person (covering about 19% of theimage) has been manually selected and then automatically removed. Noticethat the horizontal structures of the fountain have been synthesized in theoccluded area together with the water, grass and rock textures.posite textures – multiple textures interacting spatially [26]. Themain problem is that boundaries between image regions are acomplex product of mutual influences between different tex-tures. In constrast to the two-dimensional nature of pure tex-tures, these boundaries form what might be considered moreone-dimensional, or linear, image structures.A number of algorithms specifically address the image fill-ing issue for the task of image restoration, where speckles,scratches, and overlaid text are removed [2], [3], [4], [7], [23].These image inpainting techniques fill holes in images by prop-agating linear structures (called isophotes in the inpainting lit-erature) into the target region via diffusion. They are inspiredby the partial differential equations of physical heat flow, andwork convincingly as restoration algorithms. Their drawback isthat the diffusion process introduces some blur, which becomesnoticeable when filling larger regions.The technique presented here combines the strengths of bothapproaches into a single, efficient algorithm. As with inpainting,we pay special attention to linear structures. But, linear struc-tures abutting the target region only influence the fill order ofwhat is at core an exemplar-based texture synthesis algorithm.The result is an algorithm that has the efficiency and qualita-tive performance of exemplar-based texture synthesis, but whichalso respects the image constraints imposed by surrounding lin-ear structures.The algorithm we propose in this paper builds on very recentresearch along similar lines. The work in [5] decomposes theoriginal image into two components; one of which is processed2 IEEE TRANSACTIONS ON IMAGE PROCESSING, VOL. 13, NO. 9, SEP 2004by inpainting and the other by texture synthesis. The output im-age is the sum of the two processed components. This approachstill remains limited to the removal of small image gaps, how-ever, as the diffusion process continues to blur the filled region(cf. [5], fig.5 top right). The automatic switching between “puretexture-” and “pure structure-mode” of [24] is also avoided.Similar to [5] is the work in [10], where the authors de-scribe an algorithm that interleaves a smooth approximationwith example-based detail synthesis for image completion. Likethe work in [5] also the algorithm in [10] is extremely slow (asreported processing may take between 83 and 158 minutes on a384 × 256 image) and it may introduce blur artefacts (cf. fig.8b,last row of fig.13 and fig. 16c in [10]). In this paper we present asimpler and faster region