Many-to-many graph matching via metric embedding

Graph matching is an important component in many object recognition algorithms. 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...

Full description

Saved in:
Bibliographic Details
Main Authors: Keselman, Y., Shokoufandeh, A., Demirci, M.F., Dickinson, S.
Format: Conference Proceeding
Language:English
Subjects:
Clustering algorithms
Computer Society
Distributed computing
Earth
Embedded computing
Extraterrestrial measurements
Image segmentation
Motion measurement
Noise robustness
Object recognition
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph matching is an important component in many object recognition algorithms. 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. We present a 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.
ISSN:1063-6919
DOI:10.1109/CVPR.2003.1211441