Deformable Templates

Introduction to Pattern Theory

Have you ever wondered about the patterns in the world around you? Like the patterns in the arrangements of molecules that make up our genes, or the patterns of behavior of people in crowds? Pattern theory proposes the idea that the world can be understood in terms of patterns. The goal of pattern theory is to build a mathematical framework to describe these patterns.

This chapter may seem like a deviation from our path to understanding the basics of metric matching, but it will actually be introducing the ideas that are central to our final goal. Imagine the set of all the possible images of a stomach. By assuming that it is possible to define how "close" or "far" every stomach shape is to/from every other stomach, we are assuming that they possess a common pattern. The template image might be chosen to be the stomach shape which is most common. If that is the case, then the group of all stomach shapes would be the orbit of the most common stomach, under a (very large) group of diffeomorphisms. The chapter on group orbits and actions explains this concept towards the end.

But what is a template anyway? It is one thing to say that it is a "shape", and another thing entirely to try to define it mathematically. One way to define a template more exactly would be to say that it is any set of generators. The term "generator", however, is still very vague. A set of generators would have to be defined much more explicitly for a given pattern. Two examples that will be addressed in this chapter and templates for 2-dimensional shapes and templates for the language in fairytales.

Example 1: A good way to define a 2-d shape template would be to make the generators the set of points that define the border of that shape. If the template were a circle with radius 1, centered at the origin, then the set of generators might contain the points (1,0), (0,1), (-1,0), (0,-1), as well as many other points to better define the circle boundary.

Example 2: It is much harder to pick an appropriate set of generators for a piece of language, like a sentence. One approach might be to choose a set of words as the generators. Such a template might severely restrict the number of possible sentences. For example, the set of generators {the, cat, is, fat} might only be able to construct the sentences "the cat is fat", "the cat fat is", "the fat is cat", etc... Another way would be to define the set of generators as parts of speech. If the second generator was a noun, then maybe the second word of each sentence would always be a noun. A third, more abstract set of generators is a set of "stations" in a sentence, with many options as to how to get from one "station" to the next using different words. This last possibility for a language template will be explored because it allows for much more flexibility than the first types of sets of generators.