Möbius voting for surface correspondence

Yaron Lipman, Thomas A. FunkhouserACM Trans. Graphics 2009 · DOI

TL;DR

This paper introduces "Möbius Voting," a novel algorithm for automatically finding point correspondences between surfaces that are approximately or partially isometric. It leverages the low-dimensionality of the Möbius group to efficiently discover these correspondences, even for shapes with significant deformations or different object types.

What Problem Does This Paper Address?

Finding correspondences between 3D shapes is a fundamental problem in computer graphics and related fields, with applications ranging from shape interpolation and analysis to medical imaging. A major challenge arises when the input shapes are not perfectly aligned or are significantly deformed (e.g., a cat in different poses, or a dog and a wolf). Traditional methods often struggle with these "extreme deformations," requiring manual landmark input, relying on local shape descriptors that fail with significant geometric differences, or being computationally prohibitive. The goal is to find a dense set of point correspondences that minimize deformation error, ideally reflecting intrinsic shape similarity rather than just rigid alignment.

Methods

The core of the proposed method, "Möbius Voting," is built upon three key observations:

  1. Möbius Group Invariance: Isometries (shape-preserving transformations) are a subset of the Möbius group, which has a low dimensionality (6 degrees of freedom for spheres, 3 for discs). This means a few point correspondences can define the entire transformation.
  2. Closed-Form Möbius Transformations: Using a "mid-edge flattening" technique (based on Pinkall and Polthier's work), surfaces are mapped to a canonical 2D complex plane. In this flattened space, the Möbius transformation interpolating any three point pairs can be computed efficiently in closed-form.
  3. Deformation as Transportation: Deviations from isometry are modeled using a "transportation-type" distance between corresponding points in the flattened space.

The algorithm proceeds as follows:

  • Point Sampling: Key points are sampled from both input meshes, prioritizing points with high Gaussian curvature and then using a farthest point algorithm for uniform distribution.
  • Mid-Edge Uniformization: Each mesh is flattened to the complex plane using a robust mid-edge conformal flattening technique. This preserves conformal structure and allows for efficient Möbius transformation computation.
  • Möbius Voting: The algorithm iteratively samples random triplets of points from each flattened mesh. For each triplet, it computes the Möbius transformation that aligns them in a canonical domain. This transformation is then applied to all other points. A "fuzzy correspondence matrix" is populated by "voting" for potential correspondences between mutually closest points, with vote magnitude inversely proportional to the computed deformation error.
  • Matrix Processing: The fuzzy correspondence matrix is processed using a greedy "max-row-column" algorithm to extract a discrete set of correspondences with confidence scores.

Datasets

The paper evaluates its method on several datasets:

  • Non-Rigid World Benchmark: Contains meshes of the same object in different poses, allowing for quantitative comparison against ground truth.
  • SCAPE Data Set: Meshes of a single person in various poses, reconstructed from range scans, offering a slightly harder challenge due to reconstruction noise but still providing ground truth.
  • SHREC 2007 Watertight Benchmark: A diverse dataset of 3D models across different object classes, used to test performance on objects with significantly different global and local shapes, and even those with higher genus (handles).

Key Insights and Ideas

  • Leveraging Low-Dimensionality: The core insight is that the low-dimensionality of the Möbius group is a powerful invariant for finding correspondences, especially when dealing with near-isometries. This allows for a more efficient and robust search than methods relying solely on local features or brute-force combinatorial approaches.
  • Canonical Domain for Robustness: Mapping both surfaces to a shared canonical domain before computing transformations makes the process invariant to the specific flattening choices and more robust to variations in the input surfaces.
  • Voting for Correspondences, Not Transformations: Instead of voting for transformations (a common approach in Hough transforms), the algorithm votes directly for correspondences. This avoids issues with non-uniform sampling of the transformation space and naturally discovers partial correspondences.
  • Deformation Error as Transportation Cost: Modeling deformation error as a "transportation-type" cost provides a more intuitive and effective measure of how well a mapping preserves intrinsic geometry, especially when dealing with near-isometries.

Key Results

  • The algorithm successfully finds dozens of point correspondences automatically, even between different object types (e.g., dog and wolf) and in cases of extreme deformation.
  • On the Non-Rigid World Benchmark, the algorithm finds the top 45 good correspondences in most examples with less than 3% error, and often more than 50.
  • For the SCAPE dataset, the top 15 correspondences have less than 3% error in most cases, with many achieving over 30 such correspondences.
  • The method demonstrates success in matching semantic features between very different objects (e.g., man and gorilla) and in partial matching scenarios (e.g., horse centaur).
  • The computational complexity is polynomial in the number of sampled points (O(N³ log N) expected), making it feasible for practical use.

Limitations and Future Work

  • Flattening Artifacts: The current implementation uses a linear flattening technique that can produce artifacts for meshes with "bad" triangles. Future work could explore more advanced flattening methods.
  • Cutting Face Computation: The method for finding the cutting face for mid-edge uniformization is currently slow (O(n log n)). Faster alternatives could improve overall performance.
  • Genus Limitation: The algorithm is primarily designed for topological spheres with holes. While it shows some promise for higher genus objects, extending the theory to guarantee performance for such cases is a direction for future research.
  • Adaptive Hierarchical Approach: The current algorithm tends to find more correspondences in larger surface regions. An adaptive, hierarchical approach could improve the distribution and quality of correspondences, especially for complex shapes.
  • Application-Specific Tuning: The paper suggests exploring how the algorithm's capabilities can be tailored to specific applications (e.g., morphing, symmetry analysis) by considering their unique requirements for correspondence accuracy and outlier rejection.

Summary updated

BibTeX
@article{lipman2009mobius,
  author = {Yaron Lipman and Thomas A. Funkhouser},
  title = {{Möbius voting for surface correspondence}},
  journal = {ACM Trans. Graphics},
  year = {2009},
  doi = {10.1145/1531326.1531378},
}
Figure