Many-to-many feature matching using spherical coding of directed graphs

Fatili Demirci M. F., Shokoufandeh A., Dickinson S., Keselman Y., Bretzner L.

8th European Conference on Computer Vision, ECCV 2004, Prague, Czech Republic, 11 - 14 May 2004, vol.3021, pp.325-332 identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 3021
  • City: Prague
  • Country: Czech Republic
  • Page Numbers: pp.325-332
  • Ankara Yıldırım Beyazıt University Affiliated: No


© Springer-Verlag Berlin Heidelberg 2004.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.