Graphcut Textures: Image and Video Synthesis Using Graph Cuts
Vivek Kwatra Arno Sch
¨
odl Irfan Essa Greg Turk Aaron Bobick
GVU Center / College of Computing
Georgia Institute of Technology
http://www.cc.gatech.edu/cpl/projects/graphcuttextures
This banner was generated by merging the source images in Figure 6 using our interactive texture merging technique.
Abstract
In this paper we introduce a new algorithm for image and video
texture synthesis. In our approach, patch regions from a sample
image or video are transformed and copied to the output and then
stitched together along optimal seams to generate a new (and typi-
cally larger) output. In contrast to other techniques, the size of the
patch is not chosen a-priori, but instead a graph cut technique is
used to determine the optimal patch region for any given offset
between the input and output texture. Unlike dynamic program-
ming, our graph cut technique for seam optimization is applicable
in any dimension. We specifically explore it in 2D and 3D to per-
form video texture synthesis in addition to regular image synthe-
sis. We present approximative offset search techniques that work
well in conjunction with the presented patch size optimization. We
show results for synthesizing regular, random, and natural images
and videos. We also demonstrate how this method can be used to
interactively merge different images to generate new scenes.
Keywords: Texture Synthesis, Image-based Rendering, Image and
Video Processing, Machine Learning, Natural Phenomenon.
1 Introduction
Generating a newer form of output from a smaller example is
widely recognized to be important for computer graphics applica-
tions. For example, sample-based image texture synthesis methods
are needed to generate large realistic textures for rendering of com-
plex graphics scenes. The primary reason for such example-based
synthesis underlies the concept of texture, usually defined as an in-
finite pattern that can be modeled by a stationary stochastic process.
In this paper, we present a new method to generate such an infinite
pattern from a small amount of training data; using a small exam-
ple patch of the texture, we generate a larger pattern with similar
stochastic properties. Specifically, our approach for texture synthe-
sis generates textures by copying input texture patches. Our algo-
rithm first searches for an appropriate location to place the patch;
it then uses a graph cut technique to find the optimal region of
the patch to transfer to the output. In our approach, textures are
not limited to spatial (image) textures, and include spatio-temporal
(video) textures. In addition, our algorithm supports iterative refine-
ment of the output by allowing for successive improvement of the
patch seams.
When synthesizing a texture, we want the generated texture to
be perceptually similar to the example texture. This concept of per-
ceptual similarity has been formalized as a Markov Random Field
(MRF). The output texture is represented as a grid of nodes, where
each node refers to a pixel or a neighborhood of pixels in the input
texture. The marginal probability of a pair of nodes depends on the
similarity of their pixel neighborhoods, so that pixels from similar-
looking neighborhoods in the input texture end up as neighbors in
the generated texture, preserving the perceptual quality o f the input.
The goal of texture synthesis can then be restated as the solution for
the nodes of the network, that maximizes the total likelihood. This
formulation is well-known in machine-learning as the problem of
probabilistic inference in graphical models and is proven to be NP-
hard in case of cyclic networks. Hence, all techniques that model
the texture as a MRF [DeBonet 1997; Efros and Leung 1999; Efros
and Freeman 2001; Wei and Levoy 2000] compute some approxi-
mation to the optimal solution.
In particular, texture synthesis algorithms that generate their out-
put by copying patches (or their generalizations to higher dimen-
sions) must make two decisions for each patch: (1) where to posi-
tion the input texture relative to the output texture (the offset of the
patch), and (2) which parts of the input texture to transfer into the
output space (the patch seam) (Figure 1). The primary contribution
of this paper is an algorithm for texture synthesis, which after find-
ing a good patch offset, computes the best patch seam (the seam
yielding the highest possible MRF likelihood among all possible
seams for that offset). The algorithm works by reformulating the
