Texture Design Using a Simplicial Complex of Morphable Textures

Wojciech Matusik Matthias Zwicker Frédo Durand

Mitsubishi Electric Research Laboratories Massachusetts Institute of Technology
(MERL) Computer Science and Artificial Intelligence Laboratory

Figure 1: Continuous interpolation along a path connecting four samples in the space spanned by our database. Morphable textures with
sharpness preservation lead to an artifact free interpolation.

Abstract tedious image retouching. The user might be able to find a num-
ber of textures that are similar to the wanted result but do not quite
We present a system for designing novel textures in the space of tex- match. It is then appropriate to combine these textures to produce
tures induced by an input database. We capture the structure of the the desired output. In addition, textures often vary spatially due to
induced space by a simplicial complex where vertices of the sim- natural processes [Walter et al. 2001; Zhang et al. 2003] such as
plices represent input textures. A user can generate new textures weathering [Dorsey et al. 1996; Dorsey et al. 1999]. These effects
by interpolating within individual simplices. We propose a mor- are hard to achieve with photo editing software and are not trivial
phable interpolation for textures, which also defines a metric used to implement as procedural textures.
to build the simplicial complex. To guarantee sharpness in inter- We propose an alternative technique for modeling and design-
polated textures, we enforce histograms of high-frequency content ing a wide variety of natural textures. Our approach is data-driven,
using a novel method for histogram interpolation. We allow users building upon a collection of photographic textures. We allow the
to continuously navigate in the simplicial complex and design new user to combine these textures and continuously explore the space
textures using a simple and efficient user interface. We demonstrate of textures induced by the dataset.
the usefulness of our system by integrating it with a 3D texture The structure of the space of all textures, however, is extremely
painting application, where the user interactively designs desired complex as shown by research in human vision, e.g., [Richards and
textures. Koenderink 1995; Heaps and Handel 1999]. Quoting Heaps and
Handel [1999], “there is no fixed set of dimensions that character-
Keywords: Texture Synthesis, Data-driven Models, Image Warp- ize natural textures.” Traditional linear analysis and manifold em-
ing, Morphable Models bedding cannot be used to achieve our goal. The space of textures
induced by our database is likely to be non-manifold; that is, vari-
ous neighborhoods have different dimensionality. Hence, we apply
1 Introduction a learning technique based on adaptive distance graphs [Giesen and
Wagner 2003] to construct a simplicial complex [Ngo et al. 2000]
Textures play a fundamental role in enhancing the complexity and of textures.
realism of 3D models. They are usually defined using procedural Our technique involves two main components. The first com-
modeling or input photographs. Procedural textures, e.g., [Perlin ponent is a morphable model that facilitates the interpolation of
1985; Ebert et al. 1994], provide great flexibility and allow for fine textures using a warp deformation. Our interpolation scheme also
tuning of parameters to control the visual pattern. Unfortunately, includes a technique to preserve high frequency content, or sharp-
they require programming skills that are out of the reach of most ness, in interpolated textures. The second component consists of
users. Furthermore, it is challenging to reproduce a realistic nat- a simplicial complex that represents the space spanned by the tex-
ural pattern. The use of photographs ensures realism but requires tures in our database. For this, we define a texture distance metric
finding exactly the desired texture in the real world or performing and construct the simplicial complex using a neighborhood graph
based on texture distances. We describe a simple and efficient user
interface to navigate in this space and produce new, natural textures
as illustrated in Figure 1. We have also integrated our system with a
3D texture painting application, allowing the user to design desired
textures interactively.
In summary, this paper makes the following contributions:
Data-driven texture model. We present a model for the space of
textures induced by an input database. New textures are generated
by the combination of input textures.
Simplicial complex. The structure of the induced space is captured
by a simplicial complex where vertices represent input textures. We
allow interpolating input textures inside each simplex. Two main strategies have been proposed to introduce non-linearities
in the analysis.
Morphable textures and distance metric. We propose a mor- Morphable models were developed for face analysis and synthe-
phable interpolation for textures, which also defines a metric used sis [Jones and Poggio 1998; Blanz and Vetter 1999]. A non-linear
to build the simplicial complex. warp registers face images or 3D models to a reference face. Lin-
Sharpness preservation. We present a general method that guaran- ear analysis is then performed on the shape described by the warp
tees sharpness in image morphing by enforcing histograms of high- vector field and the registered images. Interpolation is carried out
frequency content. Appropriate histogram interpolation is achieved both on the shape and texture components.
by interpolating the inverse cumulative histograms rather than the In contrast to linear techniques, non-linear dimensionality reduc-
histograms themselves. tion [Tenenbaum et al. 2000; Roweis and Saul 2000] permits the
capture of spaces that are curved. However, it is usually assumed
Navigation. We allow users to continuously navigate in the simpli- that the local dimensionality is constant (manifold assumption) and
cial complex. Navigation relies on barycentric coordinates inside the topology is equivalent to a disk. Gomes and Mojsilovic [2002]
simplices. The user can move from simplex to simplex by remov- alleviate these restrictions, but their variational approach is lim-
ing and adding textures from a set of neighbors. ited to low-dimensional data by high computational costs. Ngo et
al. [2000] define non-manifold configuration spaces for animation
1.1 Previous Work using simplicial complexes. However, the topology of the space
needs to be defined by the user. We use a similar representation but
Our work draws from two research areas: texture synthesis and propose an automatic construction technique for arbitrary datasets.
data-driven models. Similarly to our work, some methods combine morphable and
non-linear approaches. In Schödl et al.’s video textures [2000], op-
Texture synthesis Texture synthesis seeks to generate textures tical flow permits a morph between pairs of data-samples (video
of arbitrary size given a small texture sample. Several algorithms frames). The graph connecting the frames can be seen as a sim-
characterize textures according to distributions of multi-scale image plicial complex with simplices of dimension one. Peters [2003]
properties [Heeger and Bergen 1995; Bonet 1997; Zhu et al. 1997; constructs morphable models for specific image domains (e.g., fish,
Zhu et al. 1998; Bar-Joseph et al. 2001; Portilla and Simoncelli dogs) using non-linear dimensionality reduction. His image corre-
2000]. In non-parametric texture synthesis [Efros and Leung 1999; spondences are, however, defined manually. In our work, we build
Hertzmann et al. 2001; Efros and Freeman 2001; Wei and Levoy on these techniques to deal with non-manifold data sets and arbi-
2000; Zelinka and Garland 2002], texture is synthesized one pixel trary dimensionality.
(or one patch) at a time by finding pixels in the source sample sim-
ilar to the already synthesized pixels. Brooks and Dodgson [2002] 1.2 Paper Overview
presented a related technique that uses similarity between texture
pixels to facilitate editing. Wu and Yu [2004] improved patch-based In Section 2, we discuss the structure of texture space and point out
texture synthesis using feature matching and patch deformation to the difficulties involved in building a data-driven model. In Sec-
reduce artifacts at patch boundaries. Their feature matching and tion 3, we explain how textures can be interpolated using morph-
texture deformation approach is similar to our warp computation. ing and present our method for sharpness preservation. We also
Epitomic representations [Jojic et al. 2003] encode images using a introduce a new distance metric which is used to define similarity
set of representative patches and mappings of those patches to the between pairs of textures. In Section 4, we present our simplicial
original image. Hence, patch based texture synthesis can be seen as complex based on the pairwise texture distances and describe our
the inverse process of constructing an epitome. navigation method. Section 5 presents results obtained using our
A number of authors have tackled the challenge of combining model. Finally, we summarize the paper and describe possible di-
and mixing textures. Heeger and Bergen [1995] and Bar-Joseph et rections for future work in Section 6.
al. [2001] create novel textures that combine the multi-scale proper-
ties of different input textures. Wei [2001], Hertzman et al. [2001],
Efros and Freeman [2001], and Kwatra et al. [2003] synthesize a
2 Data-Driven Texture Model
non-uniform texture composed of homogeneous patches. Similar To make textures amenable to mathematical analysis, we interpret
to our algorithm, the texture metamorphosis approach by Liu et discrete texture images as high-dimensional vectors. We unroll the
al. [2002] is based on warp functions, but it requires the user to pixels of each texture and concatenate red, green, and blue color
specify feature correspondences manually. Zhang et al. [2003] gen- channels to form a vector. However, vectors corresponding to nat-
erate spatially-varying textures from two input textures. However, ural textures occupy only a small portion of this high-dimensional
these approaches rely on a user to choose suitable textures that can space. It is our goal to model the subspace of natural textures such
be combined in a meaningful way. In contrast, we automatically that a user can easily explore it and generate novel, valid textures.
construct a texture space that spans the range of textures induced Unfortunately, the space of natural textures does not form a lin-
by a database of natural images. ear subspace of the original high-dimensional space: Linear blend-
Liu et al. [2004] describe a system to analyze and manipulate ing between two textures might result in an image that is blurry,
photographic textures that allows a user to design novel textures. which prevents the use of standard linear analysis such as PCA. In
However, they focus on near-regular textures, whereas we strive to addition, the topology of the neighborhood of a texture varies from
build a comprehensive texture model. Although they enable the texture to texture. Some textures can be naturally blended with a
user to modify structure and color of individual textures, they do large number of textures, while others have only a small number of
not provide ways to compute sets of similar textures and interpolate natural neighbors. We must emphasize that the notion of perceptual
their properties as we do. texture similarity and the structure of texture space is challenging at
best [Richards and Koenderink 1995; Heaps and Handel 1999]; it
Data-Driven Models Data-driven approaches offer powerful is highly dependent on the task or context. Perceptual studies have
means to generalize the information present in input datasets. Lin- shown mixed results when it comes to parameterizing this space,
ear approaches such as Principal Component Analysis are most and Heaps and Handel [1999] argue that “a dimensional model is
popular, but they cannot account for more complex phenomena. inappropriate” for natural textures.
 We propose to model the space of natural textures as a union
of low dimensional convex sets (linear spaces) of different dimen-
sions. This construction allows us to capture the topological and
non-linear complexity of texture space and accurately represent the
range of valid textures. Our work should be taken in the context of
computer graphics: It is designed for the task of texture generation.
The navigation and texture adjacencies we define allow a user to
interpolate smoothly between textures and create the texture they
need. While our data-driven model captures important aspects of Feature map F0 Warp W01 Feature map F1
the structure of texture space and texture similarity, we realize that
perception and machine vision might involve additional concerns. Figure 2: Visualization of the dense warp field W01 between two
Our data-driven texture model is built from a database of about feature maps F0 and F1 .
1500 natural textures acquired from photographs. The textures in
our database include a wide variety of phenomena such as building 3.2 Warp Computation
materials (e.g., bricks, stone), organic materials (e.g., wood, grass),
and others. Furthermore, the textures were manually rotated and Based on the per-pixel feature maps obtained with the compass op-
scaled to have approximately the same orientation and feature size. erator, we determine warp functions that minimize the feature mis-
In our prototype, we represent each texture by a texture sample de- alignment error between pairs of textures. Our approach to compute
fined as a 128 × 128 texture patch. We make the patches tileable the warp functions is based on a coarse-to-fine search, with a regu-
by using dynamic programming to find two pairs of optimal, non- larization to ensure smoothness.
straight patch boundaries in a vertical and horizontal overlap area Let us denote the feature maps of a pair of textures (i, j) by Fi , F j .
around the patch [Efros and Freeman 2001]. Then we solve a Pois- For each point (x, y) in Fi , the warp function Wi j defines a corre-
son equation with periodic boundary conditions to eliminate color sponding point (x, y) + Wi j (x, y) in F j . To find Wi j , we perform a
seams [Pérez et al. 2003]. coarse to fine search as follows:
Starting at the coarsest scale, we overlay both feature maps Fi
and F j with a regular triangulation based on a square grid of vertices
3 Morphable Textures (each vertex has six neighbors). At the coarsest scale, the feature
maps are subsampled to a resolution of 16 × 16 pixels and we use
Our morphable texture model is designed to facilitate seamless in- a triangulation of 8 × 8 vertices. Now, we exhaustively search for
terpolation of similar textures. In particular, we want to avoid the optimal position of each vertex in the triangulation of F j while
ghosting artifacts that occur when strong features of the interpolated keeping the vertices in Fi fixed. The cost of a vertex position is
textures are misaligned. To address this, we use a warp function that determined by warping each triangle of its one-ring neighborhood
optimizes feature alignment. The residual feature misalignment er- from F j to Fi and computing the L2 -error of the per-pixel scalar
ror after warping indicates the amount of artifacts during interpo- feature strength. To ensure smoothness of the warp field, we also
lation. We use this error as a texture similarity metric, which is compute the 2 × 2 Jacobian of the affine mapping that relates a tri-
central to the construction of our simplicial complex of textures. angle in F j to its corresponding triangle in Fi . As a measure of
In the following, we explain this approach in more detail: We the induced space deformation, we compute the L2 difference be-
describe feature extraction in Section 3.1 and computation of the tween the elements of this Jacobian and the identity matrix (i.e., the
warp function in Section 3.2. We show how to perform morphable Frobenius norm). The deformation penalty for a vertex is given by
interpolation between multiple textures in Section 3.3. Then, we the sum of these values for all triangles in its one-ring neighbor-
explain how we use the warp functions and the morphing procedure hood. Finally, we use a weighted average of the L2 feature error
to compute a pairwise symmetric similarity metric in Section 3.4. and the deformation measure as the cost for the vertex position. We
Finally, we introduce our technique for sharpness preservation in have determined heuristically a suitable weighting factor that was
Section 3.5. used for all textures in the database.
At each scale, we iterate once over all vertices of feature map F j
3.1 Feature Extraction and apply the above procedure to find their optimal positions. Then,
we increase the resolution of the feature maps by a factor of two and
From a wealth of feature detectors, we chose the compass operator subdivide the mesh by splitting each triangle into four. We repeat
introduced by Ruzon and Tomasi [2001] to extract oriented edge the search procedure and continue until the original resolution is
features from the texture samples. The compass operator extends reached.
the notion of edges from discontinuities in color value to disconti- Note that, because we work with tileable patches, we construct
nuities in color distribution (texture edges). It is based on a circular tileable warp fields by using modulo arithmetic at the patch bound-
filter window split into two half-windows along a line. This window aries. A visualization of the dense warp field between two brick
is rotated, and for each orientation, the filter response is the differ- textures is shown in Figure 2. Furthermore, it is straightforward to
ence in color distribution between the half-windows. The compass obtain the inverse mapping W ji = Wi−1 j , which we will need in the
operator reports the orientation and strength of the maximum re- next section.
sponse at each pixel.
The compass operator has three parameters: the standard devi-
ation σ of a Gaussian that is used to weight pixels in the circular 3.3 Morphable Interpolation
window, the number of discrete orientations k at which the operator
is evaluated at each pixel, and the maximum number of clusters c Our morphable texture interpolation is based on a barycentric for-
that are used to represent color distributions. For optimal results, mulation of the morphing algorithm described by Jones and Pog-
the value of σ should be adapted to the noise level of the input im- gio [1998]. In contrast to their approach, we do not work with a
age. Hence, we manually choose a value of either 1, 1.5, or 2 for single reference texture. Warps are defined between pairs of im-
each texture. The other parameters are fixed at k = 30 and c = 10 for ages rather than with respect to a global reference image.
all textures. In our approach, we use the strength of the maximum Each texture in the morphable model is represented by a color
response for each pixel as a scalar feature map. and a shape component. Color is given by the map I : R2 → R3
 30 1. 4
p0(x) CDF0(x)
1. 2 CDF1(x)
25 P1(x)
c0=0.75, c1=0.25 1.0
20
ci = 0 c0=0.5, c1=0.5
0. 8
15 c0=0.25, c1=0.75
0. 6
10
0. 4
5 0. 2

0 0
0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1

ci = 0.5 Figure 4: (Left) Interpolation of density functions p0 (x) and p1 (x)

for different weights c0 and c1 . (Right) We interpolate the inverse
CDFs (i.e., we interpolate CDF values horizontally as indicated
by the horizontal arrow); the interpolated density is obtained by
differentiation.

3.5 Sharpness Preservation by Histogram Inter-

ci = 1 polation and Matching
The above warp succeeds in aligning major features, but blending
still has an averaging effect that leads to a small amount of blurri-
ness. In order to match the sharpness level of the input textures, we
wi = 1 wi = 0.5 wi = 0
extract their high frequency statistics and enforce these statistics on
Figure 3: Interpolating between two textures Ii (bottom left) and I j the interpolated textures.
(top right) with independent weights for shape and texture. We capture high-frequency content using histograms of steer-
able pyramid coefficients [Simoncelli and Freeman 1995], and we
that assigns a color value to each point. Shape is represented by the achieve proper histogram interpolation using a novel technique
warp vector fields W : R2 → R2 establishing dense correspondences based on interpolating inverse cumulative histograms. We pre-
between the pixels of pairs of textures. Barycentric morphing be- serve high frequency content in interpolated textures by enforc-
tween n textures Ii , 0 ≤ i < n, involves two steps: First, we linearly ing interpolated histograms following the approach of Heeger and
interpolate the warp vectors to produce intermediate warped ver- Bergen [1995]. Below, we focus on our novel technique for his-
sions of the input textures. Then, we linearly blend between these togram interpolation. Please refer to the original work by Simon-
intermediate textures to get the output texture I.ˆ This can be com- celli and Freeman [1995] and Heeger and Bergen [1995] for more
bined into a single expression details on steerable pyramids and histogram matching,.
Histogram matching is based on the cumulative distribution

 functions (CDF) of the histograms. A desired histogram can be
n−1  −1
ˆ y) =
I(x, ∑ ci Ii (x, y) + ∑ w jWi j (x, y) , (1) enforced by substituting all pyramid coefficients with value v with
new coefficients v given by
i=0 j=i

where ci and w j are separate weights for color and shape interpo- v = CDF −1
new (CDF old (v)), (2)
lation, respectively. We need to obey the constraint ∑ j w j = 1 to
guarantee that all the textures are aligned. Morphable interpolation where CDFnew is the CDF of the desired histogram, and CDFold is
between two textures is illustrated in Figure 3. The textures in the the original CDF, which is obtained from the interpolated texture.
bottom left and top right corners are samples from the database, To preserve sharpness in the interpolated texture, we generalize
while the others are generated using different weights to interpolate this approach by setting the desired histogram to be an interpolation
shape and color. Results of interpolation between multiple textures of the histograms of the input textures. This is achieved by linearly
are given in Section 5. interpolating the inverse input CDFs:
−1
CDFnew = ∑ w jCDF j−1 , (3)
j
3.4 Warp-Based Texture Similarity Metric
where w j are the shape interpolation weights and CDF j are the
Our texture similarity metric is based on the dense correspondences CDFs of the input textures. This procedure is illustrated for a syn-
given by the warp field; it measures the residual error in the feature thetic example in Figure 4. It leads to a more natural interpolation
registration achieved by the warp. This metric is a good indicator than directly averaging the histograms, smoothly morphing one his-
for the amount of artifacts due to feature misalignment occurring in togram into the other.
morphable interpolation (Section 3.3). Because we are interested in enhancing high frequencies in the
To define a symmetric distance, we warp the feature maps of a interpolated texture, we only match the residual high-pass and the
pair of textures (i, j) half-way. That is, we compute a pair of warped highest-frequency pass-band histograms of the pyramid decompo-
feature maps F̂i and F̂ j by using the feature maps Fi , F j instead of sition. The enhanced interpolated texture is then reconstructed by
the corresponding texture images Ii , I j in Equation 1. We choose collapsing the pyramid with the modified high-frequency bands.
interpolation coefficients ci = 1, c j = 0, wi = w j = 0.5, and ci = 0, This is in contrast to Heeger and Bergen’s texture synthesis algo-
c j = 1, wi = w j = 0.5, respectively. We then compute the similarity rithm, where histogram matching and image reconstruction is per-
between textures i and j as the sum of squared differences between formed iteratively over all pyramid subbands and, in addition, the
the warped feature maps F̂i and F̂ j . As in Section 3.2, we only pixel color histograms.
take into account the difference between scalar feature strength and Figure 5 illustrates our technique with a result obtained by en-
ignore feature orientation. hancing the interpolation of two textures. In Figure 6, we point
 (a) (b) (c) (d)
Figure 5: Morphable interpolation with sharpness preservation:
(a), (b) input textures I0 , I1 , (c) morphable interpolation without
sharpness preservation, (d) with sharpness preservation.
(a) Linear model (b) Non-linear (c) Piecewise
model linear model
Figure 7: Comparison between data-driven models. In this exam-
ple linear models fit a line or the whole 2D to the 2D data points
(left). Non-linear manifold learning methods approximate these
data points with locally linear spaces of a fixed dimension (center).
(a) (b) (c) (d) Our method constructs a piece-wise linear model with variable di-
Figure 6: Comparison of our technique to linear blending: (a), (b) mensionality (right).
input textures I0 , I1 , (c) linear blending, (d) our technique. Interpo-
lation weights are wi = 0.5, ci = 0.5, i ∈ {0, 1}. be specified using barycentric coordinates of the n vertices. A sub-
set of m nodes that are shared by two cliques can be interpreted as
out the improvements achieved over linear blending without morph- an m-dimensional boundary face between the two simplices.
ing and sharpness preservation. Note that the procedure described More formally, our simplicial complex model can be described
above is general and can be used with any image morphing appli- as follows: In the case of textures represented by our morphable
cation. model from Section 3, a data point is defined by a shape weight
vector w and a color weight vector c. Both these vectors are in RN ,
where N is the number of samples in the dataset. The necessary
4 Simplicial Complex Modeling condition for a data point to be in the simplicial complex model is
therefore
The goal of our technique is to facilitate the exploration of the space N N
induced by the input database and the design of novel textures. ∑ wi = 1, wi ≥ 0 , ∑ ci = 1, ci ≥ 0, (4)
Since only similar textures can be combined in a compelling way, i=1 i=1
we use the distance metric described above to capture the topolog- and the set of indices {i | wi > 0 or ci > 0} must form a clique.
ical structure of this space and guide morphable interpolation. As
discussed in Section 1.1, we expect natural textures to have a com-
plex structure in a high dimensional space as illustrated in Figure 7. 4.1 Navigation
However, standard linear and non-linear dimensionality reduction Given the above construction, we now describe how a user navi-
algorithms are not flexible enough to describe such datasets with gates in this space to design novel textures. To make our interface
non-manifold structure (Figures 7a and 7b). Therefore, we apply intuitive, we abstract from the underlying topological representa-
an alternative method for constructing a non-linear representation, tion and facilitate smooth navigation in the space spanned by the
which handles closed manifolds, manifolds with holes, and non- model.
manifolds (see Figure 7c). The method we propose is general and Our interface is centered around a set of active textures and a
can be applied to a wide range of data. set of neighbor textures that are presented to the user visually. The
We model the space spanned by our dataset using an adaptive active set always corresponds to a clique in the neighborhood graph.
neighborhood graph, where each texture corresponds to a vertex A texture belongs to the set of neighbor textures if it can be added
in the graph. Two vertices are linked by an edge only if the dis- to the active set without breaking the clique constraint.
tance between them obeys an adaptive distance criterion [Giesen To design new textures, the user interactively changes the shape
and Wagner 2003]. Finally, we define the space that represents valid and color weights of the active textures. The weights are normal-
textures as the space inside all cliques of the graph. Our representa- ized to obey the barycentric constraints of Equation (4) at any time.
tion is a union of convex sets, or a simplicial complex of the graph. To move towards one specific sample in the active set, the user grad-
To construct the graph, we start by computing a pairwise distance ually increases both its color and shape weight. When the weights
matrix between all texture samples. For each texture i, we introduce reach one, the sample is reproduced exactly.
undirected edges to other nodes j if the distance di, j obeys the local The user can modify the active set to include desired source tex-
threshold di, j ≤ c · di,min , where c > 1 is a global constant and di,min tures by adding and removing individual textures. To add a texture,
is the distance from node i to its closest neighbor. The advantage of one selects any texture from the neighbors of the active set. Tex-
this graph construction over other neighborhood graphs is that the tures are added one at a time, as the set of neighbor textures is
connectivity parameter c is independent of the local dimensionality affected by this operation and needs to be updated before the next
of the data points and adapts to variations in sample density [Giesen texture can be selected. The user can continuously move from the
and Wagner 2003]. currently interpolated texture towards the newly added texture by
Our model for generating new textures is based on two assump- increasing its weights. On the other hand, one can remove active
tions: First, if there is an edge between two nodes in the graph, then textures with zero shape and color weights, as these do not con-
morphable interpolation leads to a valid texture. Second, if n nodes tribute to the currently interpolated texture. This will enlarge the
in the graph form a clique (each of these nodes has an edge to all set of neighbor textures and offer new textures to be added to the
other nodes), then all convex combinations of these nodes produce active set (Figure 8, left).
valid model points. That is, we interpret an n-clique as an (n − 1)- In the process of adding and removing textures from the active
dimensional simplex. Each point in the interior of the simplex can set, the user effectively hops from one clique in the neighborhood
 8000
6000
4000
2000
0
2 3 4 5 6 7 8 9 10 11 12 13 14 15
c=1.08, k=0 c=1.08, k=10 c=1.09, k=0 c=1.08, k=10
Figure 9: Histograms of clique sizes illustrating the connectivity
of the simplicial complex.

current point neighbor set start and end point

clique A active set interpolation path
samples along
clique B interpolation path
other samples
Figure 8: Given a current interpolation point, the user can move
into a neighboring clique A or B by adding a texture from the neigh-
bor set to the active set (left). Piecewise linear interpolation along Figure 10: Examples of maximal cliques in the simplicial complex
the shortest path between two points (right). model with c = 1.08 and k = 10.

graph to the next. If the active set is a subset with m nodes of a proximate similarity). We then updated the similarities based on
maximal clique with n nodes, then the user has moved to a (m − 1)- the high resolution warps and constructed a sparse distance matrix
dimensional boundary of the (n − 1)-dimensional simplex spanned with 200 entries for each texture. This stage took several days to
by the maximal clique. Transparently to the user, adding another compute on a single PC.
node moves the active set into any of the neighboring maximal Figure 9 illustrates the connectivity of the simplicial complex
cliques. model through histograms of the size of maximal cliques. We doc-
We can also generate new textures by continuously interpolating ument results with an adaptive distance threshold of c = 1.08 and
along a path between two arbitrary points in the model. In this sce- c = 1.09. In both cases, the model consists of a single connected
nario, the user picks a start and an end point, specified by their color component, and the maximum number of neighbors for any texture
and shape weights. We first determine the closest sample in the is below 200. We can also add edges to the k nearest neighbors
cliques containing each of the points and then compute the short- of each texture to ensure that the user has a minimum number of
est path in the neighborhood graph that connects these samples, as neighbors to choose from. The disadvantage of increasing the graph
shown in Figure 8 on the right. Textures along the path are then connectivity is that the navigation interface becomes cluttered with
generated using Equation 1. textures that lead to artifacts when combined with morphable inter-
polation. We found that values c = 1.08 and k = 10 work best with
our database. A number of representative maximal cliques for these
5 Results parameters is shown in Figure 10.
Although our database consists of texture patches with 128×128
We constructed a simplicial complex of morphable textures from resolution, this does not limit the size and quality of images that we
roughly 1500 images. We first extracted texture samples (i.e., 128× can produce with our system. We apply the following two tech-
128 pixel patches) from these images and added them one-by-one niques to alleviate this seeming limitation. First, we use tileable
to the database. We manually picked one representative subwindow patches for the texture samples. Second, if the original input tex-
in each original photograph such that the orientation, scale, and ture was of higher resolution than the database patch size, we retain
translation matched with perceptually similar input samples already the original image. During texture interpolation, we can use the
processed. This manual process took about one man-day for the original data and simply upsample the warp fields to the original
whole database. resolution to obtain high quality results. Alternatively, any of the
We then processed the samples as described in the previous sec- texture synthesis algorithms discussed in Section 1.1 could be ap-
tions, computing pairwise warps and the corresponding distance plied to the interpolated sample.
matrix. For each pair of textures, the warp computation (Sec- We have implemented an interactive 3D texture painting proto-
tion 3.2) and the evaluation of the similarity metric (Section 3.4) type and integrated it with our user interface. Figure 11 shows a
together take about five seconds. Computing the full 15002 dis- screen-shot of a painting session. We can create realistic effects
tance matrix is not practical. Therefore, we adopted a two-stage such as wear and tear of cloth using the wide variety of textures in
procedure. In the first stage, we computed an approximation of the the database.
similarity metric for all 15002 pairs of textures, which is obtained Figure 1 shows an example of a continuous interpolation along
by finding only the coarsest scale warps (Section 3.2) and evaluat- a path in texture space. Four samples are pairwise connected and
ing the distance metric based on these. This took about eight hours piecewise linear interpolation is performed in each pair. A similar
on a single PC. In a neighborhood graph with reasonable connec- example with a set of 26 different textures connected to a path is
tivity, it is safe to assume that the number of neighbors for each given in Figure 12. This example highlights how a wide variety of
texture is limited. We found that with our database it is not useful textures can be connected and smoothly interpolated using simpli-
to connect each texture to more than 200 neighbors (see below). In cial complex modeling (Section 4). For all the results presented in
the second stage, for each texture we calculated the high resolution this paper, we used tileable texture patches that were constructed as
warps only for the 200 most similar textures (according to the ap- described in Section 2. We achieve spatially varying interpolation
 B ROOKS , S., AND D ODGSON , N. 2002. Self-similarity based
texture editing. In Proceedings of SIGGRAPH 2002,, Annual
Conference Series, 653–656.
DANA , K. J., VAN G INNEKEN , B., NAYAR , S. K., AND KOEN -
DERINK , J. J. 1999. Reflectance and texture of real world sur-
faces. ACM Transactions on Graphics 1, 18, 1–34.
D ORSEY, J., P EDERSEN , H. K., AND H ANRAHAN , P. M. 1996.
Flow and changes in appearance. In Proceedings of SIGGRAPH
Figure 11: Interactive texture design using a prototype 3D painting 96, Annual Conference Series, 411–420.
application.
D ORSEY, J., E DELMAN , A., L EGAKIS , J., J ENSEN , H. W., AND
P EDERSEN , H. K. 1999. Modeling and rendering of weathered
using manually specified weight maps as illustrated in Figure 13. stone. In Proceedings of SIGGRAPH 99, Annual Conference
Here, we set the color weights to be equal to the warp weights. The Series, 225–234.
source texture samples are shown at the bottom.
E BERT, D., M USGRAVE , K., P EACHEY, D., P ERLIN , K., AND
W ORLEY. 1994. Texturing and Modeling: A Procedural Ap-
6 Conclusions and Future Work proach. Academic Press, Oct. ISBN 0-12-228760-6.

We have presented a novel approach for designing realistic textures E FROS , A. A., AND F REEMAN , W. T. 2001. Image quilting
for texture synthesis and transfer. In Proceedings of ACM SIG-
based on a database of input textures. The main advantage of our GRAPH 2001, Annual Conference Series, 341–346.
model is a high degree of realism since the synthesized textures
are combinations of natural textures acquired from photographs. E FROS , A. A., AND L EUNG , T. K. 1999. Texture synthesis by
Our system allows for both easy navigation in the space of tex- non-parametric sampling. In International Conference on Com-
tures spanned by the database and continuous interpolation between puter Vision, 1033–1038.
multiple textures. This is achieved by combining simplicial com-
plex modeling, morphable models, and sharpness enhancement for G IESEN , J., AND WAGNER , U. 2003. Shape dimension and intrin-
interpolated textures. We also believe that our sharpness preserva- sic metric from samples of manifolds with high co-dimension.
In Symposium on Computational Geometry, 329–337.
tion technique and simplicial complex modeling could be used for
generating models in other domains. G OMES , J., AND M OJSILOVIC , A. 2002. A variational approach
Our morphable texture interpolation is based on a single one- to recovering a manifold from sample points. Lecture Notes in
to-one warp deformation between pairs of texture samples, which Computer Science 2351, 3–17.
might be too restrictive for textures with highly irregular structures.
In the future, we will investigate epitomic image representations, H EAPS , C., AND H ANDEL , S. 1999. Similarity and features of
which are based on collections of small patches and discontinuous natural textures. Journal of Experimental Psychology: Human
mappings of these patches to the original image. However, to deal Perception and Performance 25, 1–24.
with these discontinuous mappings in the context of image interpo- H EEGER , D. J., AND B ERGEN , J. R. 1995. Pyramid-based texture
lation seems challenging. Finally, it would be desirable to extend analysis/synthesis. In Proceedings of SIGGRAPH 95, Annual
the texture model to incorporate reflectance as well (e.g., using bidi- Conference Series, 229–238.
rectional texture functions [Dana et al. 1999; Tong et al. 2002]).
H ERTZMANN , A., JACOBS , C. E., O LIVER , N., C URLESS , B.,
AND S ALESIN , D. H. 2001. Image analogies. In Proceedings
Acknowledgments of SIGGRAPH 2001, Annual Conference Series, 327–340.

We wish to thank Gabriel Lopez-Betanzos and Yang Ruan for their J OJIC , N., F REY, B., AND K ANNAN , A. 2003. Epitomic analysis
help with data collection and processing. Special thanks go to of appearance and shape. In ICCV, 34–41.
Kevin Der for implementing the painting application. We would
J ONES , M. J., AND P OGGIO , T. 1998. Multidimensional mor-
also like to thank the internal reviewers at MIT and the anonymous phable models. In ICCV, 683–688.
referees for their valuable comments. This work was supported by
an NSF CAREER award 0447561 “Transient Signal Processing for K WATRA , V., S CH ÖDL , A., E SSA , I., T URK , G., AND B OBICK ,
Realistic Imagery”, an NSF CISE Research Infrastructure Award A. 2003. Graphcut textures: image and video synthesis using
(EIA9802220), a grant from the Shell, and a stipend by the Swiss graph cuts. ACM Trans. Graph. 22, 3, 277–286.
National Science Foundation.
L IU , Z., L IU , C., S HUM , H.-Y., AND Y U , Y. 2002. Pattern-based
texture metamorphosis. In PG ’02: Proceedings of the 10th Pa-
References cific Conference on Computer Graphics and Applications, 184–
191.
BAR -J OSEPH , Z., E L -YANIV, R., L ISCHINSKI , D., AND W ER -
MAN , M. 2001. Texture mixing and texture movie synthesis L IU , Y., L IN , W.-C., AND H AYS , J. H. 2004. Near regular tex-
using statistical learning. IEEE Transactions on Visualization ture analysis and manipulation. ACM Transactions on Graphics
and Computer Graphics 7, 2, 120–135. (SIGGRAPH 2004) 23, 3 (August), 368 – 376.

B LANZ , V., AND V ETTER , T. 1999. A morphable model for the N GO , T., C UTRELL , D., DANA , J., D ONALD , B., L OEB , L., AND
synthesis of 3d faces. In Proceedings of SIGGRAPH 99, Annual Z HU , S. 2000. Accessible animation and customizable graphics
Conference Series, 187–194. via simplicial configuration modeling. In Proceedings of ACM
SIGGRAPH 2000, Annual Conference Series, 403–410.
B ONET, J. S. D. 1997. Multiresolution sampling procedure for
analysis and synthesis of texture images. In Proceedings of SIG- P ÉREZ , P., G ANGNET, M., AND B LAKE , A. 2003. Poisson image
GRAPH 97, Annual Conference Series, 361–368. editing. ACM Trans. Graph. 22, 3, 313–318.
 Figure 12: A path connecting 26 samples in the simplicial complex model.

Figure 13: Examples of spatially varying texture interpolation using manually painted weight maps.

P ERLIN , K. 1985. An image synthesizer. In Proceedings of SIG- T ONG , X., Z HANG , J., L IU , L., WANG , X., G UO , B., AND
GRAPH 85, Annual Conference Series, 287–296. S HUM , H.-Y. 2002. Synthesis of bidirectional texture func-
tions on arbitrary surfaces. ACM Transactions on Graphics 21,
P ETERS , M. R. 2003. Multidimensional image morphs: construc- 3 (July), 665–672.
tion and user interface. Master’s thesis, Massachusetts Institute
of Technology. WALTER , M., F OURNIER , A., AND M ENEVAUX , D. 2001. Inte-
grating shape and pattern in mammalian models. In Proceedings
P ORTILLA , J., AND S IMONCELLI , E. P. 2000. A parametric tex- of ACM SIGGRAPH 2001, Annual Conference Series, 317–326.
ture model based on joint statistics of complex wavelet coeffi-
cients. Int. Journal of Computer Vision 40, 1 (Oct.), 49–70. W EI , L.-Y., AND L EVOY, M. 2000. Fast texture synthesis us-
ing tree-structured vector quantization. In Proceedings of SIG-
R ICHARDS , W., AND KOENDERINK , J. J. 1995. Trajectory map- GRAPH 2000, Annual Conference Series, 479–488.
ping (”TM”): A new non-metric scaling technique. Perception W EI , L.-Y. 2001. Texture Synthesis by Fixed Neighborhood
24, 1315–1331. Searching. PhD thesis, Stanford University.
ROWEIS , S., AND S AUL , L. 2000. Nonlinear dimensionality re- W U , Q., AND Y U , Y. 2004. Feature matching and deformation for
duction by locally linear embedding. Science 290, 5500 (De- texture synthesis. ACM Transactions on Graphics (SIGGRAPH
cember), 2323–2326. 2004) 23, 3 (August), 362–365.
RUZON , M., AND T OMASI , C. 2001. Edge, junction, and corner Z ELINKA , S., AND G ARLAND , M. 2002. Towards real-time tex-
detection using color distributions. IEEE Trans. on Pattern Anal- ture synthesis with the jump map. In Rendering Techniques
ysis and Machine Intelligence 23, 11 (November), 1281–1295. 2002: 13th Eurographics Workshop on Rendering, 99–104.

S CH ÖDL , A., S ZELISKI , R., S ALESIN , D. H., AND E SSA , I. Z HANG , J., Z HOU , K., V ELHO , L., G UO , B., AND S HUM , H.-
2000. Video textures. In Proceedings of SIGGRAPH 2000, An- Y. 2003. Synthesis of progressively variant textures on arbitrary
nual Conference Series, 489–498. surfaces. ACM Transactions on Graphics 22, 3 (July), 295–302.
Z HU , C. S., W U , Y., AND M UMFORD , D. 1997. Minimax en-
S IMONCELLI , E. P., AND F REEMAN , W. T. 1995. The steerable tropy principle and its application to texture modeling. Neural
pyramid: a flexible architecture for multi-scale derivative com- Computation 9, 8.
putation. In Proceedings of the 1995 IEEE International Con-
ference on Image Processing, 3444. Z HU , C. S., W U , Y., AND M UMFORD , D. 1998. Filters, random
fields and maximum entropy (frame): Towards a unified theory
T ENENBAUM , J., DE S ILVA , V., AND L ANGFORD , J. 2000. A for texture modeling. International Journal of Computer Vision
global geometric framework for nonlinear dimensionality reduc- 27, 2.
tion. Science 290, 5500 (December), 2319–2323.