Point pattern matching via spectral geometry

In this paper, we describe the use of Riemannian geometry, and in particular the relationship between the Laplace-Beltrami operator and the graph Laplacian, for the purposes of embedding a graph onto a Riemannian manifold. Using the properties of Jacobi fields, we show how to compute an edge-weight matrix in which the elements reflect the sectional curvatures associated with the geodesic paths between nodes on the manifold. We use the resulting edge-weight matrix to embed the nodes of the graph onto a Riemannian manifold of constant sectional curvature. With the set of embedding coordinates at hand, the graph matching problem is cast as that of aligning pairs of manifolds subject to a geometric transformation. We illustrate the utility of the method on image matching using the COIL database.