Vision & Cognition Laboratory

Department of Computer Science, Drexel University

Many-to-Many Matching

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. For more information, please see the references below.

Primary Reference

M. F. Demirci, A. Shokoufandeh, Y. Keselman, L. Bretzner, and S. Dickinson. Object Recognition as Many-to-Many Feature Matching. International Journal of Computer Vision, 2006, Volume 69, Number 2, pp. 203-222.

Related References

M. Fatih Demirci, A.  Shokoufandeh, Y.  Keselman, S.  Dickinson and L.  Bretzner. Many-to-Many Feature Matching Using Spherical Coding of Directed Graphs. The 8th European Conference on Computer Vision. ECCV (1) 2004: 322-335. Prague, May 11-14, 2004.

M. Fatih Demirci, A. Shokoufandeh, Y. Keselman, S. Dickinson and L. Bretzner. Many-to-Many Matching of Scale-Space Feature Hierarchies using Metric Embedding. 4^th International Conference on Scale-Space. Scale-Space 2003: 17-32. Isle of Skye, Scotland, UK. June 10-12, 2003.

Y. Keselman, A. Shokoufandeh, M. Fatih Demirci and S. Dickinson. Many-to-Many Matching using Metric Embedding IEEE Conference on Computer Vision and Pattern Recognition. CVPR (1) 2003: 850-857. Madison, Wisconsin. June 16-22, 2003.