Page 211 -

Section 6.3 Synthesizing Textures and Filling Holes in Images 179

FIGURE 6.12: The size of the image neighborhood to be matched makes a significant
difference in Algorithm 6.4. In the figure, the textures at the right are synthesized from
the small blocks on the left, using neighborhoods that are increasingly large as one moves
to the right. If very small neighborhoods are matched, then the algorithm cannot capture
large-scale effects easily. For example, in the case of the spotty texture, if the neighborhood
is too small to capture the spot structure (and so sees only pieces of curve), the algorithm
synthesizes a texture consisting of curve segments. As the neighborhood gets larger, the
algorithm can capture the spot structure, but not the even spacing. With very large
neighborhoods, the spacing is captured as well. This figure was originally published as
Figure 2 of “Texture Synthesis by Non-parametric Sampling,” A. Efros and T.K. Leung,
Proc. IEEE ICCV, 1999 c IEEE, 1999.

Synthesizing a large texture in terms of individual pixels will be unnecessarily
slow. Because textures repeat, we expect that whole blocks of pixels also should
repeat. This suggests synthesizing a texture in terms of image patches, rather than
just pixels. Most of the mechanics of the procedure follow those for pixels: to
synthesize a texture patch at a location, we find patches likely to fit (because they
have pixels that match the boundary at that location), then choose uniformly and
at random from among them. However, when we place down the new patch, we
must deal with the fact that some (ideally, many) of its pixels overlap with pixels
that have already been synthesized. This problem is typically solved by image
segmentation methods, and we defer that discussion to Chapter 9.

6.3.2 Filling in Holes in Images
There are four approaches we can use to fill a hole in an image. Matching meth-
ods find another image patch that looks a lot like the boundary of the hole, place
that patch over the hole, and blend the patch and the image together. The patch
might well be found in the image (for example, Figure 6.13). If we have a very large
set of images, we could find a patch by looking for another image that matches the
image with a hole in it. Hays and Efros (2007) show this strategy can be extremely