Graphics Reference
In-Depth Information
for the algorithm is a texture image (e.g., a photograph of a brick wall) that's
called the
source,
and a size,
n
×
k
, of an image to be created. The output is an
×
×
n
k
is much larger than the size of the
input image. The idea is that the target should look like it comes from “the same
stuff as the source”; for example, like a photograph of a larger region of a brick
wall. Figure 20.21 shows the idea. We fill in the target image row by row, moving
left to right. At a typical point in the filling-in procedure, the blue-colored pixels
have had their values determined and the yellow area is still to be processed. We
select a small rectangle (2
k
image we'll call the
target;
typically
n
3 in the figure) containing mostly known pixels, and
one unknown (pink) pixel at the bottom right. (We'll call this set of six pixels a
template.
) The goal is to determine a value for this last pixel, and then advance
the template one step to the right.
×
We take the five known pixels in the rectangle, and look in the source image
for similarly shaped clusters that match these five known pixels. We then pick one
with a good fit, and copy its
sixth
pixel into the appropriate spot in the target. We
then move the template one step to the right, and proceed.
This description glosses over several important points, such as “How do we
get started?” and “How do we move to a new row?” and “How do we find in
the source image good-matching patches for the known template pixels without
taking forever to do it?” One way to start is with random pixels from the source
image filling the target. As we start at the upper left, finding a “match” for the first
5-pixel patch will be very difficult—we'll have to be happy with a not-very-good
result. But as we move forward, things gradually start to work better. To improve
matters, we may want to run the algorithm several times, working top to bottom,
bottom to top, left to right, right to left, etc., to clean up the edges.
As for finding good candidates as matching patches, one useful observation
is that if you move the template one step to the right, a good candidate for filling
in the next pixel is exactly one step to the right of the source pixel you just used
(i.e., the algorithm's very likely to favor copying whole rows of pixels). This can
be generalized. For instance, right above the missing pixel is one that you filled in
one row earlier. If we look at the corresponding source pixel, the one immediately
below it is a good candidate for the missing pixel, too. In fact, the source loca-
tions of all five known template pixels similarly provide (with slight offsets) good
candidate locations in which to find a source for the missing sixth pixel. The algo-
rithm proceeds by picking a pixel from this candidate set. Occasionally (e.g., when
a source pixel is near the edge of the image) this may not work, in which case we
have to replace this candidate with another; there are many possible choices, and
the details are not important.
The results are quite impressive. Figure 20.22 shows an example in which a
few berries are used to synthesize many berries. The algorithm has another advan-
tage: It's possible to start with the target image partly filled in! We can declare in
advance that we want certain pixels to have certain colors, and when the algorithm
reaches these pixels, it finds them already “filled in” and leaves them unchanged.
But their presence affects how well the subsequent patches fit with one another,
and hence the synthesis of subsequent pixels. Figure 20.23 shows an example.
The end result of the synthesis process is that long diagonal strips from the
source tend to be copied whole, in such a way that they match up with neighboring
strips. Figure 20.24 shows this structure.
In this situation, a small square of the target image around some pixel
(
i
,
j
)
tends to match a small square in the source image around some pixel
(
i
,
j
)
,
although along the edges between strips this isn't an exact match. If we compute
Figure 20.20: Reaction-diffusion
textures. Top: Textures synthe-
sized by Kass and Witkin. (Cour-
tesy of Michael Kass, Pixar
and Andrew Witkin, © 1991
ACM, Inc. Reprinted by permis-
sion). Bottom: Texture synthe-
sized by Greg Turk. (Courtesy of
Greg Turk, © 1991 ACM, Inc.
Reprinted by permission.)
Source
Target
Figure 20.21: A partly synthe-
sized image, and a highlighted
region with one unknown pixel.
