Relational evidence theory and spatial interpretation procedures.

Abstract

Spatial interpretation involves the intelligent processing of images for learning, planning and visualisation. This involves building systems which learn to recognise patterns from the content of unconstrained data such as handwritten schematic symbols, photographic, and video images.The efficiency of spatial interpretation systems is measured not only in terms of their ability to learn to classify patterns, but their computational complexity and capacity to accommodate different patterns. This is reflected in the ease of human factors involved in the interactive process of inputting and manipulating training patterns, particularly if large numbers of patterns are used.This thesis focuses on the theoretical and procedural issues involved in applying machine learning to computer vision for efficient spatial interpretation. Two different approaches to evidential learning are consolidated in how they apply to generalising relational data structures. Relational Evidence Theory integrates information theoretic methods from, decision trees with graph matching methods from constraint interpretation. It offers an evidence-based framework for evaluating and updating relational representations suitable for spatial applications.A new algorithm is developed, Rulegraphs, which combines graph matching with rule-based approaches from machine learning. This algorithm reduces of the cardinality of the graph matching problem by replacing pattern parts by rules. Rulegraphs not only reduce the search space but, also improve the uniqueness of the matching process. The system is demonstrated for difficult two-dimensional pattern recognition and three-dimensional object recognition problems. An empirical comparison with an evidence-based neural network system is conducted.A consolidated learning algorithm based on relational evidence theory (CLARET) is presented which integrates Rulegraph matching with rule generation techniques from inductive logic programming. The approach utilises the relational constraints in spatial data to optimise the representational hierarchies and search strategies used during learning.An on-line schematic and symbol recognition application is demonstrated for learning to recognise symbols and patterns invariant to rotation, scale, and shift. The classification performance, computational efficiency, and the human factors involved in incrementally training the system are empirically compared with other inductive logic programming techniques.The significance of this work is twofold. Firstly, it extends the applicability of machine learning theories and algorithms into new domains. The techniques complement the image query and retrieval tools currently available in computer vision by offering additional ways of recognising and manipulating spatial information. Secondly, the development of a working schematic system allows for the evaluation of the efficiency of spatial interpretation techniques, and places emphasis on the dialogue between the user and the technology.