Page 208 -

Section 6.3 Synthesizing Textures and Filling Holes in Images 176

Algorithm 6.3). It is possible to search for an appropriate number of clusters by
applying k-means for different values of k and comparing the results; we defer a
discussion of this issue until Section 10.7.

Choose k data points to act as cluster centers
Until the cluster centers change very little
Allocate each data point to cluster whose center is nearest.
Now ensure that every cluster has at least
one data point; one way to do this is by
supplying empty clusters with a point chosen at random from
points far from their cluster center.
Replace the cluster centers with the mean of the elements
in their clusters.
end

Algorithm 6.3: Clustering by K-Means.

6.3 SYNTHESIZING TEXTURES AND FILLING HOLES IN IMAGES
Many different kinds of user want to remove things from images or from video. Art
directors might like to remove unattractive telephone wires; restorers might want to
remove scratches or marks; there’s a long history of government officials removing
people with embarrassing politics from publicity pictures (see the fascinating pic-
tures in King (1997)); and home users might wish to remove a relative they dislike
from a family picture. All these users must then find something to put in place of
the pixels that were removed. Ideally, a program would create regions of texture
that fit in and look convincing, using either other parts of the original image, or
other images.
There are other important applications for such a program. One is to produce
large quantities of texture for digital artists to apply to object models. We know
that good textures make models look more realistic (it’s worth thinking about why
this should be true). Tiling small texture images tends to work poorly, because it
can be hard to obtain images that tile well. The borders have to line up properly,
and even when they do, the resulting periodic structure can be annoying.

6.3.1 Synthesis by Sampling Local Models
As Efros and Leung (1999) point out, an example texture can serve as a probability
model for texture synthesis (Figure 6.11). Assume for the moment that we know
every pixel in the synthesized image, except one. To obtain a probability model for
the value of that pixel, we could match a neighborhood of the pixel to the example
image. Every matching neighborhood in the example image has a possible value for
the pixel of interest. This collection of values is a conditional histogram for the pixel
of interest. By drawing a sample uniformly and at random from this collection, we
obtain the value that is consistent with the example image.
We must now take some form of neighborhood around the pixel of interest,