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.