F.Demirci; "Many-to-Many Feature Matching", 28.09.2005, 14:40, G035

Many-to-Many Feature Matching
 

M. Fatih Demirci

Abstract:

The problem of object recognition is often formulated as that of matching configurations of image features to configurations of model features. Such configurations are often represented as vertex-labeled graphs, whose nodes represent image features (or their abstractions), and whose edges represent relations (or constraints) between the features. When graphs are used to represent objects, the object recognition problem can be defined as that of graph matching.

Although most graph matching algorithms seek a one-to-one correspondence between nodes, it is often the case that a more meaningful correspondence exists between a cluster of nodes in one graph and a cluster of nodes in the other. I will present a graph matching algorithm that establishes many-to-many correspondences between nodes of noisy, vertex-labeled weighted graphs. The algorithm is based on recent developments in efficient low-distortion metric embedding of graphs into normed vector spaces. By embedding weighted graphs into normed vector spaces, we reduce the problem of many-to-many graph matching to that of computing a distribution-based distance measure between graph embeddings. We use a specific measure, the Earth Mover's Distance, to compute distances between sets of weighted vectors. Empirical evaluation of the algorithm on an extensive set of recognition trials demonstrates both the robustness and efficiency of the overall approach.

Bio:
Fatih Demirci is a Ph.D. candidate in the Department of Computer Science, Drexel University, United States. He works at the Applied Algorithms Lab. under the advise of Dr. Shokoufandeh. Mr. Demirci is the recipient of the Drexel University, College of Engineering Outstanding Graduate Research Award. His research interests include structural pattern matching, feature tracking, and graph theory.

September 28, 2005, 14:40-15:30, FENS G035