Page 210 -

Section 6.3 Synthesizing Textures and Filling Holes in Images 178

FIGURE 6.11: Efros and Leung (1999) synthesize textures by matching neighborhoods of
the image being synthesized to the example image, and then choosing at random amongst
the possible values reported by matching neighborhoods (Algorithm 6.4). This means
that the algorithm can reproduce complex spatial structures, as these examples indicate.
The small block on the left is the example texture; the algorithm synthesizes the block
on the right. Note that the synthesized text looks like text: it appears to be constructed
of words of varying lengths that are spaced like text, and each word looks as though it
is composed of letters (though this illusion fails as one looks closely). This figure was
originally published as Figure 3 of “Texture Synthesis by Non-parametric Sampling,” A.
Efros and T.K. Leung, Proc. IEEE ICCV, 1999 c IEEE, 1999.

neighborhoods by just setting a threshold on the similarity function, because we
might not have any matches. A better strategy to find matching neighborhoods
is to select all whose similarity value is less than (1 + )s min ,where s min is the
similarity function of the closest neighborhood and is a parameter.
Generally, we need to synthesize more than just one pixel. Usually, the values
of some pixels in the neighborhood of the pixel to be synthesized are not known;
these pixels need to be synthesized too. One way to obtain a collection of examples
for the pixel of interest is to count only the known values in computing the sum
of squared differences, and scale the similarity to take into account the number of
known pixels. Write K for the set of pixels around a point whose values are known,
and K for the size of this set. We now have, for the similarity function,

2 2
1 2 −(i + j )
(A ij −B ij ) exp .
K 2σ 2
(i,j)∈K
The synthesis process can be started by choosing a block of pixels at random from
the example image, yielding Algorithm 6.4.

Filling in Patches