Exemplar-Based Inpainting - Technique

Computational Vision Topics - Anna Regina Corbo - corbo@impa.br

This project reproduces the algorithm proposed by [Criminisi, Perez & Toyama, 2003] for removing large objects from digital images, in a way that the result looks quite reasonable for our eyes.

Here, the inpainting process is done by an algorithm that fill the target area with linear structures sampled in the source region. This propagation by exemplar-based texture synthesis is done choosing the best-match sample from the source region, i.e., which one is most similar to those parts that are already filled in the patch to be filled. For example, if the patch P lies on the continuation of an image edge, the most likely best matches will lie along the same (or a similarly coloured) edge. Figure 1 illustrates this point.

Figure 1. The region to be filled, i.e., the target region is indicated by W, and its contour, the fill front, is denoted dW. The source region F, which remains fixed throughout the algorithm, provides samples used in the filling process.

The algorithm is divided in 3 steps:

  • Compute patch priorities
  • Propagate texture and structure information
  • Update confidence values

    • STEP 1: Compute patch priorities

    Used for crate a filling order, using the onion peel method where the propagation of structures and textures dependes entirely on the priority values of each patch on the fill front. The priority P(p) of a pixel p is computed by

    This priority is computed for every border patch in the boundary of target region, where C(p) is the confidence term and D(p) is the data term, defined as

    Figure 2. Notation diagram. Given the patch p, Ip is the isophote (direction and intensity) at point p, |p| is the area of p, alfa is a normalization factor and np is a unit vector orthogonal to the front dW in the point p. The entire image is denoted with I.

    STEP 2: Propagate texture and structure information

    Here, the patch with highest priority is filled with data extracted from the source region. We search in the source region for that patch q which is most similar to p. Having found the source exemplar q, the value of each pixel-to-be-filled is copied from its corresponding position inside q.

    STEP 3: Update confidence values

    After the patch P has been filled with new pixel values, the confidence C(p) is updated in the area delimited by P as follows:

    This simple update rule allows us to measure the relative confidence of patches on the fill front, without image specific parameters. As filling proceeds, confidence values decay, indicating that we are less sure of the colour values of pixels near the centre of the target region.

    Technique Results References and Downloads

    main page