Queen Mary Vision Laboratory seminar
------------------------------------


Speaker:
Dr Antonio Robles-Kelly of the Department of Computer Science, The University of York

Date:
8th December 2003

Title:
Graph-spectal Methods for Computer Vision

Abstract:
Although well established in several areas of mathematics, the application of graph-spectral
techniques in computer vision and pattern recognition is a recent development. Spectral-graph 
theory allows graphs to be described in a compact form due to the fact that the set of leading 
eigenvalues and eigenvectors provide an embedding of the nodes in the graph into a k-dimensional 
subspace. In the computer vision community, graph-spectral methods have found application in the 
areas of segmentation and grouping, surface reconstruction, shape representation, edit distance and 
graph matching. Despite being elegant by virtue, existing methods are not statistical in nature. 
The reasons for using statistical methods in conjunction with graph-spectral theory are twofold. 
Firstly, despite proving effective, graph-spectral algorithms can benefit of the robustness to 
noise and structural corruption inherent to statistical approaches. Secondly, performance bounds 
can be set when the problem is posed in a statistical setting.

In this talk, I will commence by introducing graph-spectral methods. I will also review the 
literature on graph-spectral methods relevant to the talk. Having reviewed existing methods, I will 
illustrate how graph-spectral theory and the apparatus of statistical inference can be used to 
develop algorithms for performing segmentation and grouping and graph matching. To this end, I will 
present two methods developed recently at York. The first of these is a maximum likelihood 
framework for segmentation and grouping. Here, I will introduce the concept of "modal sharpening", 
where the leading eigenvector is used for refining the structure of the link-weight matrix. Making 
use of the modal analysis of the log-likelihood function, I will also establish the convergence 
properties of the algorithm.

Turning our attention to the graph-matching problem, I will present a graph-spectral edit distance 
computation algorithm. Here, I will show how the properties of the leading eigenvector of the 
adjacency matrix can be used for converting the graph into a string. As a result, the graph edit 
distance can be computed finding the sequence of string edit operations, which minimise the cost of 
a path traversing the edit lattice. I will also show how the edit costs can be computed using the a 
posteriori probability of visiting a site.


Finally, I will illustrate the utility of the methods presented in the talk for purposes of 
database indexing and retrieval.

Bio:
ANTONIO A. ROBLES-KELLY received his B.Eng. degree in Electronics and Communications from the Inst. 
Tecnologico y de Estudios Superiores de Monterrey with honours in 1998. In 2001, he visited the 
University of South Florida as part of the William Gibbs/Plessey Award to the best research 
proposal to visit an overseas research lab. The award was considered in consultation with GEC-
Marconi Underwater Systems Ltd. He received his PhD in Computer Science from the University of York 
in 2003. Currently, he is a Research Associate under the MathFit-EPSRC framework at York.

His research interests are in the areas of computer vision, pattern recognition and computer 
graphics. Along these lines, he has done work on segmentation and grouping, graph-matching, shape-
from-X and reflectance models. He is also interested in the differential structure of surfaces. His 
research has found applications in areas such as database organisation, 3D surface recovery and 
reflectance model approximation.