Synthesizing patterns using factor graphs

Placeholder Show Content


In computer graphics, we are interested in recreating the richness and beauty of the world we see around us. We are also interested in helping artists create novel work. Even though the arrangement of design elements can vary greatly in patterns, we may still often characterize the relationships between design elements in the same kind of patterns. Previous pattern synthesis methods consist mainly of procedural and optimization techniques. Procedural techniques are good for generating a collection of models using a set of predefined rules and parameters. However, they are difficult to control. Optimization methods generate the best model given a cost function defined by a set of constraints. How do we combine the strength of the two methods such that we can generate a collection of models that satisfy both hard and soft constraints? That is, we want a system where preferred models are more likely to be generated. In this dissertation, we propose to use factor graphs, a type of graphical model, to encode the constraints present in patterns for computer graphics. We then model the design space for possible patterns as a generative probabilistic distribution. We also demonstrate how we can use factor graphs to set up the probabilistic distributions and develop synthesis algorithms for two classes of pattern synthesis problems: example- based tiled patterns and scene synthesis. In example-based tiled patterns, the patterns are grid-based and the size of a tiled pattern is fixed (i.e., a closed world). We learn the factor functions from the examples. Because of the hard constraints that the adjacent pairs of tiles must adjoin seamlessly, the distribution has high probability states that are isolated into disconnected regions. To address this challenge, we propose a search algorithm for tilings that is an extension of MC-SAT. Next, we consider the problem of scene synthesis. In scene synthesis, we relax the grid restriction and allow the number of objects to vary in the scene (i.e., an open world). The resulting distribution is transdimensional. Such a setting is useful when the number of objects is not known a priori. We propose a reversible jump Markov chain Monte Carlo method (LARJ-MCMC) that uses localized annealing. We also show through experimentation that the proposed MCMC sampler better adapts to the change in energy landscape when the dimensionality changes. Both algorithms exploit the factor graph formulation to synthesize layouts more efficiently.


Type of resource text
Form electronic; electronic resource; remote
Extent 1 online resource.
Publication date 2013
Issuance monographic
Language English


Associated with Yeh, Yi-Ting
Associated with Stanford University, Department of Electrical Engineering.
Primary advisor Hanrahan, P. M. (Patrick Matthew)
Thesis advisor Hanrahan, P. M. (Patrick Matthew)
Thesis advisor Goodman, Noah
Thesis advisor Guibas, Leonidas J
Advisor Goodman, Noah
Advisor Guibas, Leonidas J


Genre Theses

Bibliographic information

Statement of responsibility Yi-Ting Yeh.
Note Submitted to the Department of Electrical Engineering.
Thesis Thesis (Ph.D.)--Stanford University, 2013.
Location electronic resource

Access conditions

© 2013 by Yi-Ting Yeh
This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).

Also listed in

Loading usage metrics...