Representing, matching, and generalising
structural descriptions of complex
physical objects.
by David Brian Andreae
A thesis submitted to the Victoria University of Wellington in fulfillment of
the requirements for the degree of Doctor of Philosophy Victoria University of
Wellington
1994
Abstract
This thesis addresses the problem of representing, matching, and generalising
descriptions of complex structured physical objects, in the absence of
functional and domain-specific knowledge. A system called GRAM is described,
which includes a representation scheme, an instance-constructor, a matcher, and
a generaliser. These components incorporate and extend ideas from a number of
other structured-object learning systems, as well as introducing several new
ideas.
A central contribution of this thesis is to show that descriptions of complex
physical objects can be matched and generalised effectively and efficiently by
exploiting their structure. GRAM does this by a number of means, such as by
representing objects at multiple levels of detail; using `neighbour
relationships' to allow a more flexible traversal of object graphs during
matching; explicitly distinguishing between substructure and context to allow
partial matching and a simple form of disjunction; and using an explicit
representation of groups to describe several similar objects as a single
descriptive entity.
A second contribution is to show that complex objects can
be matched without having to enforce consistency between object
correspondences. This is possible partly because of the richness of physical
objects, and partly because GRAM represents concepts as simple entities defined
by relationships with other concepts, rather than as a complete set of
subcomponents defined locally within the concept description itself. This scheme
leads to greater simplicity, efficiency, and robustness.