using Nonparametric Partially Ordered Markov Models

With Jennifer Davidson

A shorter version appeared in:

Proceedings of the 1999 Congress on Evolutionary Computation

In this paper we describe a solution to the problem of synthesizing
textures. We use a pair of genetic algorithms to create fast one-pass
generating algorithms for five black-and-white textures. This is done
using only examples of those textures as input. The key to success is
the use of a pair of genetic algorithms and a special structure called a
*foot pattern*. The first genetic algorithm locates a foot
pattern, a set of pixel locations containing important structural
information about the texture, in essence a point of view from which the
example texture looks relatively non-random. The foot pattern is a kind
of *basic texture element* or *texel*. The second genetic
algorithm then uses this texel as the core of a fitness function that
compares two textures so as to tell when one ``looks like'' the other.
With this ``looks like'' fitness function available, the second genetic
algorithms synthesizes a non-parametric partially ordered Markov model
for the example texture. The genetic algorithms used are themselves are
quite standard, but their pairing and the fitness functions used yield a
breakthrough in black-and-white texture synthesis. Extending these
techniques to gray scale and colored textures is possible, but suffers
from combinatorial explosion. Suggestions on overcoming the
difficulties of such extension appear in the discussion of future work.