University of York, Department of Computer Science

 

Richard Wilson's Research
Contents

Current Research Topics

Previous work

Spectral Methods for Graphs

 In recent work, we have shown how to extract features from the eigenvalues and eigenvectors of graph Laplacians. These features can be used to represent the structure of a graph and are very quick to compute. They also allow matching, clustering and modelling to be performed in vector space rather than graph space. We have also shown how to extend these constructions to attributed graphs. Considerable challenges remain however, because the feature space is high-dimensional and does not always respond in a straightforward way with changes in graph structure. The feature space is also rich enough to allow the original graph to be reconstructed from the features.

Papers

  • B. Luo, R. C. Wilson and E. R. Hancock, "Spectral Embedding of Graphs", Pattern Recognition 36(10) pp 2213-2223, 2003
  • R. C. Wilson and E. R. Hancock, "Pattern Spaces from Graph Polynomials", 12th International Conference on Image Analysis and Processing, pp. 480-485, 2003
  • R. C. Wilson, E. R. Hancock and B. Luo, "Pattern Vectors from Algebraic Graph Theory", IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7) pp1112-1124, 2005

Code

Possible PhD topics

Investigating the relationship between changes in graph structure and the spectral decomposition of the Laplacian, and constructing stable variants of the Laplacian matrix. Using methods such as PCA or ICA to construct useful low dimensional feature spaces. Applying these techniques to large structural databases.

Graphs can potentially be reconstructed from a feature vector. Can this be done efficiently? Is it possible to mix graphs by mixing their features and then creating a graph from the mixed feature vector? Can this feature space be used to create generative models of graphs or extract important components?

Chemical structure databases

  

Databases of chemical structures are an important tool for the pharmaceutical industry because they allow virtual screening of molecules for particular biological effects. The molecules in these databases are typically represented by atom-bond graphs. The aim of this work is to apply graph matching methods to retrieval, activity  prediction and generation of new molecules. Both classic graph matching techniques and spectral methods can be applied to this problem.

Possible PhD topics

Clustering is an important application in large databases, and allows similar molecules to be grouped together. Previous work has looked at the clustering of graph structures based on distance measures, techniques which could be applied to chemical structure databases.

Activity prediction of compounds in a database allows for virtual screening which can give an indication of which molecules may have potential for a particular application. There exist many powerful methods for achieving this on vectorial data. These methods could be extended to molecular graphs either using graph embedding methods or spectral features.

Stereo and Shape from Shading Algorithms

 Stereo algorithms can be used to extract 3D structure from a pair (or more) of images. Stereo is very effective where good correspondences can be found, i.e. where there is clear surface texture, but fails on smooth surfaces. Shape from shading can also be used to extract 3D information from a single image, but only for textureless surface. The aim of this work is to combine these two methods to produce a more effective and complete reconstruction.

Possible PhD topics

Optimisation methods for solving the hybrid stereo/SFS problem.

Quantum Algorithms

 Graph isomorphism appears to be a hard problem, but we do not currently known which complexity class it belongs to. Subgraph isomorphism and inexact graph matching on the other hand are know to be NP-complete. This work is investigating the possible of an efficient algorithm for isomorphism and methods for representing and improving the speed of inexact graph matching on a quantum computer. Two possible approaches are either to find a variant of Shor's algorithm which can solve graph isomorphism, or to examine whether quantum walks can yield any computational advantage for graph algorithms.

 
Relational Graph Matching 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.

This work is aimed at providing principled Bayesian methods for rectifying initialisation errors, in the presence of significant structural error. The second phase of this research provides techniques for identifying and removing structural errors from relational graphs. Finally it provides an experimental comparison with more traditional methods.

Possible PhD topics

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 attributed graphs.

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.

sar    sar graph    map graph

Papers

Code

Other areas

 I am also interested in supervising students in the following areas

Multiple classifier systems. The theory of multiple classifiers and the application of information theory to the design of multiple classifier systems.
 

Previous Research
3D Surface reconstruction Variance-Bias

In this work, I derive a method of surface differential estimation based on that of Stoddart et al. I show how two sources of error in the calculation of surface differentials (noise and bias) can be expressed in terms of the area on the surface over which the quantities are estimated. The effect of noise decreases as the area increases. Conversely, the bias increases with increasing area and there is an area of minimum error in the surface estimates.

I present a method of estimating the optimal area using the statistics of the data-points which form the surface. This method consists of measuring the deviation of the surface from a local model of the surface. These deviations are then used to determine coefficients of an error equation. This error equation is minimised to find the optimal area of estimation. The optimal area for estimation is determined adaptively across the surface and can be used to to accurately estimate the differential quantities on the surface.

The area of estimation can also be used to seed a mesh with important properties. The triangular faces of the mesh are such that the surface area they cover is accurately represented by the face within the accuracy constraints of the surface point noise.

Code

Adaptive mesh

This work presents an active mesh representation for surface reconstruction. The mesh is active in the sense that it is capable of adapting to surfaces of varying curvature and noise. The surface representation has a dual structure. The control points which sparsely sample the surface are represented by a triangulated mesh. Raw data-points associate to the triangular faces of the mesh. By collecting groups of faces we construct support neighbourhoods whose geometry is dependent on the local mesh configuration. The points encompassed by these neighbourhoods are used to compute the maximum likelihood parameters for local quadric patches. The region over which each quadric patch has influence is therefore closely coupled to the local mesh topology. In fact under certain conditions, the mesh density is proportional to the surface curvature.

Surface labelling

The main contributions in this work are twofold. In the first instance, we demonstrate how H-K surface labelling can be realised using a constrained dictionary of feasible surface-label configurations. These configurations observe certain constraints on the adjacency of surface-curvature types and on the smoothness and continuity of curvature regions. The second contribution is to develop a statistical model which allows the surface-labels to be assigned with the probabilities of the different H-K classes. These probabilities model the assignment of curvature classes using surface normal information. They also capture uncertainties in the computation of surface curvature through the propagation of variance in the surface normal measurements.

Sorry, no code available for the surface work as yet.

Applications

  • Mesh decimation - forming optimally accurate low-triangle count 3D models from their high-resolution counterparts
  • Automatic reconstruction of 3D models from medical images or range scans
  • Matching 3D models based on their surface curvature

Head mesh

Mesh decimation of a 3D model obtained from an MRI scan

Range head mesh

Mesh decimation of a 3D model from a range image

Range       Mesh

Forming a mesh from a digital elevation map

 Curvature labelling

Curvature labelling applied to the MRI head
Energy Minimisation Techniques This research has been aimed at exploring new optimisation techniques such as genetic optimisation, tabu search and comparing a variety of energy minimisation techniques in terms of their performance in pattern matching and recognition tasks. This work has led to some new insights into the connection between energy minimisation and physical quantities such as entropy and Gibb’s energy.

This work is highly theoretical and is intended to provide insights and alternative optimisation techniques for dealing with relational graph structures.
 

Hits: Counter since 21/2/02