One Point Isometric Matching with the Heat Kernel

Maks Ovsjanikov, Quentin Mérigot, Facundo Mémoli, Leonidas J. GuibasComputer Graphics Forum 2010 · DOI · OpenReview

TL;DR

This paper introduces a novel method for finding precise isometric maps between 3D shapes using the heat kernel. By leveraging the heat kernel's ability to uniquely characterize points on a shape, they demonstrate that a single point correspondence is sufficient to recover a full isometric map, significantly simplifying shape matching and enabling applications like intrinsic symmetry detection and matching incomplete models.

What Problem Does This Paper Address?

Matching shapes, especially those undergoing non-rigid deformations, is a fundamental problem in computer graphics and geometry processing. A particularly desirable type of correspondence is an isometry, which preserves geodesic distances between points on a shape. While many algorithms exist for finding approximate isometries, understanding the underlying structure of the space of isometries and how to efficiently recover them has been a challenge. Specifically, it's been unclear how many initial correspondences are truly needed to define a full isometric map, and how to robustly establish these maps in practice, especially for shapes that aren't perfectly isometric or are incomplete.

Methods

The core of this paper lies in the Heat Kernel Map. For a given shape (represented as a manifold) and a chosen "source" point, the Heat Kernel Map associates every other point on the shape with a function. This function, derived from the heat kernel, essentially encodes how "heat" diffuses from the source point to that specific point over time. The authors prove that under mild "genericity" conditions (meaning the shape doesn't have certain symmetries in its spectral properties), this Heat Kernel Map is injective, meaning each point on the shape gets a unique "signature."

This injectivity is key: if we know one point p on shape M corresponds to point q on shape N, then any other point x on M must correspond to a point y on N such that their Heat Kernel Maps (with respect to p and q respectively) are identical. This allows for the propagation of a single correspondence to a full, dense isometric map.

For practical implementation on triangle meshes, they discretize the heat kernel and use efficient numerical methods for its computation. They also introduce two heuristics to improve robustness:

  1. Feature Detection: Identifying salient points on shapes (e.g., local maxima of the Heat Kernel Signature) to establish initial landmark correspondences.
  2. Correspondence Augmentation: Incorporating local descriptors (like the Heat Kernel Signature itself) and additional landmark correspondences to improve the accuracy and stability of the resulting dense map, especially when shapes are not perfectly isometric or generic.

Datasets

The paper evaluates its method on various shape datasets, including:

  • The Nonrigid World 3D Database.
  • The SCAPE dataset.
  • Datasets by Vlasic et al.

They do not introduce a new dataset but rather demonstrate their algorithm's performance on existing benchmarks for shape matching and symmetry detection.

Key Insights and Ideas

  • A single point correspondence is sufficient for a full isometry: This is the most striking result. The heat kernel's unique signature allows us to "name" each point on a shape, and if this naming is preserved between two shapes, the mapping must be an isometry.
  • The Heat Kernel Map as a "Shape Fingerprint": The heat kernel provides a robust, intrinsic descriptor for each point on a shape, invariant to isometric deformations.
  • Genericity is key: The theoretical guarantees rely on certain "generic" properties of the shape's spectral decomposition. While this might seem restrictive, the authors note that such properties hold for most shapes and can be achieved with slight perturbations.
  • Practical robustness through augmentation: While theory suggests one point is enough, in practice, adding local descriptors (HKS) and more landmark correspondences significantly improves results for real-world, imperfect shapes.

Key Results

  • The algorithm successfully recovers dense isometric maps for shapes with moderate geodesic distortion (e.g., 5.3% and 13.2% distortion shown in Figure 6).
  • It can accurately detect intrinsic symmetries in shapes.
  • The method demonstrates effectiveness in matching partial and incomplete models (Figure 9).
  • The use of Heat Kernel Signatures (HKS) significantly improves the quality of matches, preventing erroneous correspondences (e.g., matching the tail to the leg in Figure 4).
  • The computational cost of the Heat Kernel Map stabilizes after a relatively small number of time samples (around 10-15), making the approach efficient.

Limitations and Future Work

  • Genericity Assumptions: The theoretical guarantees of injectivity and isometry preservation rely on the shape being "generic." While the authors suggest this is common and can be achieved with minor perturbations, it's a theoretical limitation for highly symmetric or degenerate shapes.
  • Near-Isometries: The paper focuses on exact isometries. Future work is suggested to provide quantitative statements about the behavior of the Heat Kernel Map under near-isometries and to explore approximate versions of their theorems.
  • Topological Changes: While the method shows promise for shapes with different topologies (Figure 10), exploring its stability and robustness under significant topological changes is an open problem.
  • Parametrizing Near-Isometries: The authors pose the question of whether the space of near-isometries can also be parametrized by a small set of correspondences.

Summary updated

Abstract

A common operation in many geometry processing algorithms consists of finding correspondences between pairs of shapes by finding structure‐preserving maps between them. A particularly useful case of ...
BibTeX
@article{ovsjanikov2010one,
  author = {Maks Ovsjanikov and Quentin Mérigot and Facundo Mémoli and Leonidas J. Guibas},
  title = {{One Point Isometric Matching with the Heat Kernel}},
  journal = {Computer Graphics Forum},
  year = {2010},
  doi = {10.1111/j.1467-8659.2010.01764.x},
}
Figure