A Factorisation Framework for Structural Pattern Matching

Edwin Hancock

Department of Computer Science,

University of York,

York, Y01 5DD, UK

erh@cs.york.ac.uk

Relational representations are of critical importance in high-level vision. They can be used to represent the arrangement of image primitives in a manner which captures the structure of both objects and scenes. Moreover, they can convey important semantic information which is not captured by using object attributes alone. In this talk we describe some important steps in the direction of learning relational descriptions for high-level vision.

The talk commences by showing how the EM algorithm can be used to compute a measure of relational similarity between pairs of graphs. Next, we show how the statistical measure of relational similarity, which results from this analysis, can be cast into a matrix setting. This opens the possibility for performing a number of important operations on relational graphs using matrix factorisation methods, such as singular value decomposition and eigendecomposition. First, we show how to find correspondence matches between graphs of different size, i.e. subgraph isomorphisms, using singular value decomposition. Next, we suggest how to use the new matrix representation to learn structural representations. Finally, we show how the framework can be used to edit the structure of graphs so as to remove relational errors using an eigenclustering method.

We demonstrate the new framework on a number of problems from high-level vision, including model alignment, content-based image retrieval and perceptual grouping. This work can be viewed as combining ideas from statistical and structural pattern recognition, and from spectral graph theory.