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.