A low-dimensional representation for robust partial isometric correspondences computation

Alan Brunton, Michael Wand, Stefanie Wuhrer, Hans-Peter Seidel, Tino Weinkauf

This paper, published in 2014, presents a robust method for finding correspondences between 3D shapes that are deforming (like a person moving) and may be incomplete or "noisy" (containing holes or parts touching each other).

TL;DR

The authors propose a "local-to-global" approach for matching deformable 3D shapes by observing that a single point and a tangent direction are enough to define an entire isometric (distance-preserving) map. By growing these maps locally and clustering them, the algorithm achieves high robustness against "topological noise" like holes and self-contacts that typically break global matching methods.

What Problem Does This Paper Address?

In computer graphics and vision, "shape matching" is the task of identifying which point on Shape A corresponds to which point on Shape B. This is easy for rigid objects but very hard for deformable ones (like a dancer in different poses).

Most state-of-the-art methods rely on global isometry, assuming that the "intrinsic" distance (the distance measured along the surface) between any two points remains constant. However, real-world 3D scans are messy. They often have:

  1. Holes/Missing Data: Occlusions during scanning.
  2. Topological Noise: When two parts of a shape touch (e.g., a hand on a hip), a "bridge" is created in the data.

These artifacts distort global distances, causing standard algorithms to fail. This paper tackles partial matching, where we only expect parts of the surfaces to match isometrically, ignoring the areas corrupted by noise or missing data.

Methods

The core of the paper is a shift from global invariants to local propagation.

  • The 3-DOF Representation: The authors leverage a principle from differential geometry: an isometry between surfaces is uniquely determined by the mapping of a single point and its tangent space (direction). This means the search space for a match has only 3 degrees of freedom (2 for the point's position on the surface, 1 for the rotation).
  • Isometric Region Growing: Instead of solving for the whole shape at once, the algorithm starts at a "seed" (a likely point-to-point match). It then "flood-fills" the correspondence to neighboring points using parallel transport.
  • Stretch Constraint: As the match grows, the algorithm monitors the "stretch" (metric distortion). If the local geometry starts to differ too much—which happens at the edge of a hole or a contact point—the growth stops.
  • Agglomerative Clustering: Because many different "seeds" might actually represent the same overall partial match, the authors use a manifold-based clustering technique to group these individual partial maps into a single, consistent, and robust correspondence.

Datasets

The authors evaluated their method on several challenging 3D datasets:

  • Samba Sequence: Scans of a woman dancing in a dress. This is notoriously difficult because the dress frequently touches the legs, changing the surface topology.
  • SCAPE Dataset: A standard benchmark containing 71 scans of a male in various poses.
  • BU-3DFE: A database of 3D facial expressions, used here to test robustness against small holes and outliers.
  • Flashkick Dataset: High-speed motion data involving significant topological changes (e.g., pants merging during a kick).

Key Insights and Ideas

  • Locality is Robustness: By using a local propagation model, the algorithm naturally "flows" around holes and stops at "bridges" (contacts). Global methods, by contrast, let the error from one bad area "pollute" the entire calculation.
  • Redundancy as a Filter: The representation is intentionally redundant. By starting many "growths" from different feature points and clustering them, the algorithm can distinguish between a "true" isometric match (which many seeds will agree on) and a "false" match caused by noise (which will be isolated or inconsistent).
  • Minimal Degrees of Freedom: Realizing that you only need 3 parameters to define a match significantly reduces the complexity compared to "elastic" matching methods that try to solve for thousands of variables at once.

Key Results

  • Superiority over Global Methods: The method significantly outperformed Heat Kernel Maps (HKM) and Blended Intrinsic Maps (BIM) on data with topological noise. In the Samba sequence, while BIM produced visual artifacts and misalignments near contacts, this method maintained a clean, semantically correct mapping.
  • Quantitative Accuracy: On the SCAPE dataset, the method achieved lower geodesic error than BIM in regions where the isometry was well-preserved.
  • Handling "Bridges": The paper demonstrates that while other methods might map a hand to a hip because they are physically touching in the scan, this algorithm correctly identifies them as separate parts of the surface.

Limitations and Future Work

  • Computational Cost: The process is slow. Depending on the complexity, it can take anywhere from 30 minutes to 8 hours to compute a full correspondence on a standard laptop.
  • Initialization Dependency: The algorithm relies on finding at least a few good "seeds" (initial feature matches). If the noise is so extreme that no initial features can be matched, the region growing cannot start.
  • Symmetry Ambiguity: Like most intrinsic methods, it can struggle with "bilateral symmetry" (e.g., accidentally mapping a left hand to a right hand) if the clustering doesn't have enough information to distinguish them.
  • Future Direction: The authors suggest combining this with methods that detect continuous intrinsic symmetries to further prune the search space and improve speed.

Summary updated

Abstract

Intrinsic isometric shape matching has become the standard approach for pose invariant correspondence estimation among deformable shapes. Most existing approaches assume global consistency, i.e., the metric structure of the whole manifold must not change significantly. While global isometric matching is well understood, only a few heuristic solutions are known for partial matching. Partial matching is particularly important for robustness to topological noise (incomplete data and contacts), which is a common problem in real-world 3D scanner data. In this paper, we introduce a new approach to partial, intrinsic isometric matching. Our method is based on the observation that isometries are fully determined by purely local information: a map of a single point and its tangent space fixes an isometry for both global and the partial maps. From this idea, we develop a new representation for partial isometric maps based on equivalence classes of correspondences between pairs of points and their tangent spaces. From this, we derive a local propagation algorithm that find such mappings efficiently. In contrast to previous heuristics based on RANSAC or expectation maximization, our method is based on a simple and sound theoretical model and fully deterministic. We apply our approach to register partial point clouds and compare it to the state-of-the-art methods, where we obtain significant improvements over global methods for real-world data and stronger guarantees than previous heuristic partial matching algorithms.
BibTeX
@inproceedings{brunton2014low,
  author = {Alan Brunton and Michael Wand and Stefanie Wuhrer and Hans-Peter Seidel and Tino Weinkauf},
  title = {{A low-dimensional representation for robust partial isometric correspondences computation}},
  booktitle = {Graph. Model},
  year = {2014},
  url = {https://openreview.net/forum?id=BzuHry5jT8_},
}

Loading related content...

Figure