Related Work

The problem of many-to-many graph matching has been studied most often in the context of edit-distance (see, e.g., [14,12,15,18]). In such a setting, one seeks a minimal set of re-labelings, additions, deletions, merges, and splits of nodes and edges that transform one graph into another. However, the edit-distance approach has its drawbacks: 1) it is computationally expensive (p-time algorithms are available only for trees); 2) the method, in its current form, does not accommodate edge weights; 3) the method does not deal well with occlusion and scene clutter, resulting in much effort spent in ``editing out'' extraneous graph structure; and 4) the cost of an editing operation often fails to reflect the underlying visual information (for example, the visual similarity of a contour and its corresponding broken fragments should not be penalized by the high cost of merging the many fragments). In the context of line and segment matching, Beveridge and Riseman [3] addressed this problem via exhaustive local search. Although their method found good matches reliably and efficiently (due to their choice of the objective function and a small neighborhood size), it is unclear how the approach can be generalized to other types of feature graphs and objective functions. In a novel generalization of Scott and Longuet-Higgins [17], Kosinov and Caelli [11] showed how inexact graph matching could be solved using the re-normalization of projections of vertices into the eigenspaces of graphs combined with a form of relational clustering. Our framework differs from their approach in that: (1) it can handle information encoded in a graph's nodes, which is desirable in many vision applications; (2) it does not require an explicit clustering step; (3) it provides a well-bounded, low-distortion metric representation of graph structure; (4) it encodes both local and global structure, allowing it to deal with noise and occlusion; and 5) it can accommodate multi-scale representations. Low-distortion embedding techniques haven proven to be useful in a number of graph algorithms, including clustering and, most recently, on-line algorithms. Indyk [9] provides a comprehensive survey of recent advances and applications of low-distortion graph embedding. Gupta [8] proposes a randomized procedure for embedding metric trees into a vector space of prescribed dimensions. Our spherical coding is a deterministic variation of this procedure. For recent results related to the properties of low-distortion tree embedding, see [1,13].