  We address the problem of 3D shape registration and we propose a novel
technique based on spectral graph theory and probabilistic matching. The task
of 3D shape analysis involves tracking, recognition, registration, etc.
Analyzing 3D data in a single framework is still a challenging task considering
the large variability of the data gathered with different acquisition devices.
3D shape registration is one such challenging shape analysis task. The main
contribution of this chapter is to extend the spectral graph matching methods
to very large graphs by combining spectral graph matching with Laplacian
embedding. Since the embedded representation of a graph is obtained by
dimensionality reduction we claim that the existing spectral-based methods are
not easily applicable. We discuss solutions for the exact and inexact graph
isomorphism problems and recall the main spectral properties of the
combinatorial graph Laplacian; We provide a novel analysis of the commute-time
embedding that allows us to interpret the latter in terms of the PCA of a
graph, and to select the appropriate dimension of the associated embedded
metric space; We derive a unit hyper-sphere normalization for the commute-time
embedding that allows us to register two shapes with different samplings; We
propose a novel method to find the eigenvalue-eigenvector ordering and the
eigenvector signs using the eigensignature (histogram) which is invariant to
the isometric shape deformations and fits well in the spectral graph matching
framework, and we present a probabilistic shape matching formulation using an
expectation maximization point registration algorithm which alternates between
aligning the eigenbases and finding a vertex-to-vertex assignment.
