The relational structure of objects or symbols is a very powerful tool in
computer vision and pattern recognition. In the relational paradigm,
patterns are formed not only by the nature of the objects which make the
pattern, but also by their relationships to each other. These relationships
provide a very flexible representation which can be used in many tasks such
as object recognition, scene matching and registration and tracking. For
example, the work of Barrow and Popplestone first established the relational
graph as a practical representation for scene matching.
Effective relational matching must be capable of accommodating two classes of
error. The first of these are initial matching errors which result from
ambiguities in object appearance created by the acquisition process. The second
source of error is structural disturbance of the relational descriptions under
match. These structural errors result from either poor initial image
segmentation or the presence of noise and clutter.
Much recent work has looked at the edit distance approach to graph matching.
The edit distance between two graphs is the cost of a set of elementary edit
operations (such as edge or vertex deletion) which transform one graph into
another. These costs are usually specified manually, but it should be possible
to learn the costs from a sample set. These ideas could also be extended to
A generative model is one which allows new examples to be generated from the
model. This would be a valuable thing to do for graphs since it would allow new
graphs to be generated for particular classes of data. These models could be
formed as a probabilistic graph which combines samples, or by projection into
a feature space, which could be coupled with a standard generative model.