Source-linked AI summary
Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration
Diana Mateus, Radu Horaud, David Knossow, Fabio Cuzzolin, Edmond Boyer
TL;DR
Articulated-shape matching is difficult because large or noisy graph embeddings make eigenvalue ordering unreliable, while real shapes may differ in topology, sampling, or voxel count. The paper selects and aligns Laplacian eigenfunctions using histogram signatures, then performs robust orthogonal point registration with EM and an outlier class. Experiments report successful dense matching of challenging articulated voxel-sets, including topology changes, with the procedure taking only a few seconds for large voxel-sets.
Problem
Large sparse graphs can have repeated or numerically unorderable Laplacian eigenvalues, while articulated shapes may contain discrepancies and outliers that complicate matching.
Method
The method combines Laplacian embedding, eigenfunction-histogram alignment, and unsupervised robust point registration under orthogonal transformations using EM and an outlier component.
Results
The experiments successfully recover dense or maximal-subset correspondences for challenging articulated voxel-sets, including topology changes and many unmatched points.
Takeaways & Limitations
Graph matching can be treated as orthogonal registration in a reduced spectral space, with histogram initialization and outlier rejection supporting large voxel-set matching.
Takeaways & Limitations
The paper identifies dimension selection for the embedding space as an open problem for future study.
Abstract
from arXiv · showhide
Matching articulated shapes represented by voxel-sets reduces to maximal sub-graph isomorphism when each set is described by a weighted graph. Spectral graph theory can be used to map these graphs onto lower dimensional spaces and match shapes by aligning their embeddings in virtue of their invariance to change of pose. Classical graph isomorphism schemes relying on the ordering of the eigenvalues to align the eigenspaces fail when handling large data-sets or noisy data. We derive a new formulation that finds the best alignment between two congruent $K$-dimensional sets of points by selecting the best subset of eigenfunctions of the Laplacian matrix. The selection is done by matching eigenfunction signatures built with histograms, and the retained set provides a smart initialization for the alignment problem with a considerable impact on the overall performance. Dense shape matching casted into graph matching reduces then, to point registration of embeddings under orthogonal transformations; the registration is solved using the framework of unsupervised clustering and the EM algorithm. Maximal subset matching of non identical shapes is handled by defining an appropriate outlier class. Experimental results on challenging examples show how the algorithm naturally treats changes of topology, shape variations and different sampling densities.
1. Introduction
Articulated 3-D shape matching remains difficult because the appropriate transformation group is unclear and real data contain noise, outliers, missing parts, and deformations. The paper combines Laplacian spectral embeddings with probabilistic point matching, using eigenfunction histograms instead of eigenvalue ordering.
- 3-D articulated shape matching remains difficult because the appropriate transformation group is not yet clear.
- Spectral embeddings represent locally connected shape graphs in a lower-dimensional space where dense matching becomes embedding alignment.
- The proposed method combines Laplacian embedding with probabilistic point matching for articulated-shape correspondence.
- Eigenfunction histograms replace eigenvalue ordering for selecting and aligning spectral components, especially for point-sets of roughly 10^4 elements and embedding dimension around 10.
- The paper frames graph matching as orthogonal point registration and uses unsupervised clustering to handle discrepancies and outliers through a uniform mixture component.
2. Problem statement
The paper constructs weighted voxel graphs and Laplacian embeddings, then reduces graph matching to orthogonal registration of lower-dimensional point sets. Reduced eigenspaces avoid unreliable full-spectrum eigenvalue ordering, while maximum sub-graph matching accommodates unequal and nonidentical shapes.
- 2.1. Graph Laplacian operator: Voxel connectivity and local shortest-path distances define a weighted adjacency matrix, whose normalized Laplacian captures graph structure.
- 2.2. Spectral graph matching: Graph matching seeks a permutation matrix minimizing an objective over correspondences between two graph representations.
- 2.2. Spectral graph matching: Umeyama’s alignment uses graph eigenspaces and a diagonal sign matrix, but requires distinct, reliably ordered eigenvalues.
- 2.3. Graph matching in a reduced eigenspace: For large or symmetric sparse graphs, eigenvalue multiplicities and numerical approximations make complete eigenbasis ordering impractical, potentially requiring search over N! orderings.
- 2.3. Graph matching in a reduced eigenspace: Selecting the K smallest Laplacian eigenvalues maps voxel sets into K-dimensional embeddings that preserve local geometry and produce congruent point-sets for locally isomorphic shapes.
- 2.3. Graph matching in a reduced eigenspace: Graph isomorphism in the reduced space is equivalent to estimating a K × K orthogonal transformation and recovering the point assignment.
- 2.3. Graph matching in a reduced eigenspace: Maximum sub-graph matching relaxes one-to-one assignment and equal-cardinality constraints for shapes with different voxel counts or local structure.
- 2.3. Graph matching in a reduced eigenspace: Eigenfunction-histogram initialization followed by robust latent-variable registration avoids exhaustive eigenvalue ordering and mitigates local-minimum risks.
3. Alignment using Laplacian eigenfunctions
The method aligns Laplacian eigenfunctions without relying on eigenvalue ordering by comparing histogram-based signatures, accounting for eigenvector sign ambiguity, and retaining only well-aligned pairs for registration.
- Motivation and signatures: Eigenvalue ordering is unreliable, so the alignment estimates permutation and sign matrices from eigenfunction signatures rather than node assignments.Each eigenfunction histogram is invariant to the ordering of graph-node components, making it a signature for matching.
- Signature matching: Histogram matching is formulated as a bipartite maximum-matching problem with O(K^3) complexity, while explicitly comparing both eigenfunction signs.The matrix entries measure histogram dissimilarity under both possible signs.
- Signature matching: The Hungarian algorithm produces an optimal eigenfunction assignment and resolves the sign ambiguity, providing initialization for point registration.Its output is a permutation matrix, with sign handling incorporated through the comparison procedure.
- Empirical behavior: Histogram signatures remain similar across extremely separated mannequin poses, even when hand self-contact changes the embedded topology.The figure compares the first five of 20 histograms and shows a sign flip for one aligned pair.
- Selection and initialization: Only eigenfunction pairs with the best alignment scores are retained from the leading 20–25 eigenfunctions, improving matching robustness.The retained pairs form an eigenspace in which assignment is easier.
4. Point registration and clustering
After Laplacian embedding, articulated-shape matching becomes registration of congruent point sets. The proposed unsupervised robust registration models transformed points as Gaussian clusters, adds a uniform outlier class, and estimates assignments with EM.
- Registration formulation: Articulated-shape matching is reduced to optimal alignment of congruent embedded point sets under an orthogonal transformation.The registration operates in a reduced K-dimensional space.
- Clustering model: The registration model treats one point set as observations and the other as Gaussian cluster centers, augmented by a uniform outlier component.The outlier likelihood is uniform over the volume containing the embedded shapes.
- Latent assignments: Latent variables assign each observation to a cluster, and point-to-point assignment is formulated through maximization of the mixture log-likelihood.The model assumes independently and identically distributed observations.
- EM optimization: EM estimates a global orthogonal transformation and a shared K × K covariance matrix rather than independent cluster means.The common covariance is constrained to avoid convergence problems when observations approach cluster centers.
- Robust registration: Posterior assignment probabilities and normalized weights classify observations as inliers or outliers while producing one-to-one point assignments.The resulting procedure is unsupervised robust point registration.
5. Experimental results
Experiments on articulated voxel-set shapes show that eigenfunction-based initialization combined with EM registration recovers correspondences despite topology changes, outliers, shape variation, and differing sampling. The method matches maximal common subsets and remains efficient on large voxel-sets.
- Experimental setup: The experiments evaluate wooden mannequins, people, and hands reconstructed from poses captured by six calibrated cameras.Most points are matched in few algorithm iterations.
- Wooden mannequin: For the wooden mannequin, eigenfunction signatures initialize a K = 5 embedding alignment despite topology changes caused by hand self-contact.Using only eigenvalue ordering makes point matching difficult and can lead EM to a local minimum.
- Wooden mannequin: Outlier rejection lets the algorithm recover the maximal matching subset despite many unmatchable voxels created by different graph topologies.Unmatched points are assigned to their own class so they do not influence the orthogonal alignment.
- Cross-shape matching: The method matches corresponding regions between a wooden mannequin and a person, demonstrating maximal sub-graph matching when the shapes share a common sub-structure.The experiment addresses shapes from different datasets.
- Hand matching: For hand poses with bending and self-contact, most matches are recovered, including the small finger, while the changed palm connectivity remains unmatched.The unmatched palm region reflects altered connectivity between the palm and finger.
- Discussion: Local graph connectivity supports self-contact and topology changes while producing sparse Laplacians, efficient eigendecomposition, and matching of large voxel-sets in a few seconds.Voxel representations provide stable embeddings and preserve volumetric information; the method uses no photometric information.
6. Conclusions
The paper establishes dense articulated-shape matching through spectral matching and unsupervised point registration. Its conclusions emphasize robust registration, large-graph equivalence, and possible extensions beyond voxel representations.
- The method establishes a simple equivalence between graph isomorphism and orthogonal point registration for low-dimensional embeddings.
- Eigenfunction histograms replace unreliable eigenvalue ordering and provide an effective initialization for subsequent EM-based registration.
- The EM formulation provides unsupervised robust point registration by modeling large discrepancies with a uniform mixture component.
- Future work will investigate whether the link between spectral matching and clustering can resolve embedding-dimension selection.
- The spectral-matching and probabilistic framework can also be applied to 3-D meshes, 2-D silhouettes, and bags of features.