Many-to-Many Feature Matching Using Spherical Coding of Directed Graphs

M. Fatih Demirci¹ - Ali Shokoufandeh¹ - Sven Dickinson² - Yakov Keselman³ - Lars Bretzner⁴

¹Department of Computer Science, Drexel University,
Philadelphia, PA 19104, USA
{mdemirci,ashokouf}@cs.drexel.edu
² Department of Computer Science, University of Toronto,
Toronto, Ontario, Canada
sven@cs.toronto.edu
³ School of Computer Science, Telecommunications and Information Systems,
DePaul University, Chicago, IL 60604, USA
ykeselman@cs.depaul.edu
⁴ Computational Vision and Active Perception Laboratory,
Department Of Numerical Analysis and Computer Science,
KTH, Stockholm, Sweden
bretzner@nada.kth.se

Abstract:

In recent work, we presented a framework for many-to-many matching of multi-scale feature hierarchies, in which features and their relations were captured in a vertex-labeled, edge-weighted directed graph. The algorithm was based on a metric-tree representation of labeled graphs and their metric embedding into normed vector spaces, using the embedding algorithm of Matousek [13]. However, the method was limited by the fact that two graphs to be matched were typically embedded into vector spaces with different dimensionality. Before the embeddings could be matched, a dimensionality reduction technique (PCA) was required, which was both costly and prone to error. In this paper, we introduce a more efficient embedding procedure based on a spherical coding of directed graphs. The advantage of this novel embedding technique is that it prescribes a single vector space into which both graphs are embedded. This reduces the problem of directed graph matching to the problem of geometric point matching, for which efficient many-to-many matching algorithms exist, such as the Earth Mover's Distance. We apply the approach to the problem of multi-scale, view-based object recognition, in which an image is decomposed into a set of blobs and ridges with automatic scale selection.