Page 209 -

Section 6.3 Synthesizing Textures and Filling Holes in Images 177

compare it to neighborhoods in the example image, and select some of these to form
a set of example values. The size and shape of this neighborhood is significant,
because it codes the range over which pixels can affect one another’s values directly
(see Figure 6.12). Efros et al. use a square neighborhood, centered at the pixel of
interest.

Choose a small square of pixels at random from the example image
Insert this square of values into the image to be synthesized
Until each location in the image to be synthesized has a value
For each unsynthesized location on
the boundary of the block of synthesized values
Match the neighborhood of this location to the
example image, ignoring unsynthesized
locations in computing the matching score
Choose a value for this location uniformly and at random
from the set of values of the corresponding locations in the
matching neighborhoods
end
end

Algorithm 6.4: Non-parametric Texture Synthesis.

The neighborhoods we select will be similar to the image example in some
sense. A good measure of similarity between two image neighborhoods can be
measured by forming the sum of squared differences (or ssd) of corresponding pixel
values. We assume that the missing pixel is at the center of the patch to be
synthesized, which we write S. We assume the patch is square, and adjust the
indexes of the patch to run from −n to n in each direction. The sum of squared
differences between this patch and an image patch P of the same size is given by
2
(A ij −B ij ) .
(i,j)∈patch,(i,j) =(0,0)
The notation implies that because we don’t know the value of the pixel to be
synthesized (which is at (0, 0)), we don’t count it in the sum of squared differences.
This similarity value is small when the neighborhoods are similar, and large when
they are different (it is essentially the length of the difference vector). However,
this measure places the same weight on pixels close to the unknown value as it does
on distant pixels. Better results are usually obtained by weighting up nearby pixels
and weighting down distant pixels. We can do so using Gaussian weights, yielding
2 2
2 −(i + j )
(A ij −B ij ) exp .
2σ 2
(i,j)∈patch,(i,j) =(0,0)
Now we know how to obtain the value of a single missing pixel: choose uniformly
and at random amongst the values of pixels in the example image whose neigh-
borhoods match the neighborhood of our pixel. We cannot choose those matching