SpiderMatch: 3D Shape Matching with Global Optimality and Geometric Consistency

Paul Roetzer, Florian BernardCVPR 2024 · DOI

Introduction

3D shape matching—the task of establishing dense correspondences between two 3D surfaces—is a fundamental problem in computer vision and graphics. Applications range from medical imaging and statistical shape analysis to character animation and texture transfer. Despite its importance, achieving a matching that is both globally optimal and geometrically consistent remains a significant challenge.

Currently, the field is divided between two primary approaches. Deep learning methods offer speed and high accuracy but often lack structural guarantees, potentially producing "noisy" matches where neighboring points on a source shape map to distant regions on the target. Conversely, optimization-based methods attempt to enforce geometric consistency (preserving local neighborhoods), but typically result in non-convex problems that are computationally expensive or prone to local minima.

SpiderMatch introduces a novel framework that bridges this gap. By representing the source shape as a "SpiderCurve"—a single, long, self-intersecting curve that covers the entire surface—the authors formulate the matching process as an Integer Linear Program (ILP). This approach achieves a solution that is guaranteed to be both globally optimal and geometrically consistent.

Overview of SpiderMatch: Matching a cyclic path from source to target, dense matching results, and scalability comparison.

The SpiderCurve Framework

The core innovation of SpiderMatch is the discretization of the source shape into a 1D structure called a SpiderCurve. Instead of matching a 2D surface directly to another 2D surface—a process that involves a massive 4D search space—the authors simplify the problem by treating the source as a single, self-intersecting cyclic curve that visits every vertex on the mesh.

A SpiderCurve covering the surface of a giraffe model.

This transformation turns the matching task into a shortest-path problem within a product graph (the combination of the SpiderCurve and the target 3D mesh). To ensure the resulting match is structurally sound, the authors employ an Integer Linear Program (ILP) with four critical constraints:

  1. Cyclic Path (CYC): Ensures the entire SpiderCurve is mapped to the target.
  2. Path Continuity (CON): Guarantees the matched path on the target shape is unbroken.
  3. Preservation of Existing Self-Intersections (PES): If the curve crosses itself on the source (e.g., at an armpit), it must maintain that crossing topology on the target.
  4. Avoidance of New Intersections (ANS): This constraint prevents the matching from folding or twisting incorrectly, enforcing strict geometric consistency.

Experimental Evaluation

The authors evaluated SpiderMatch on several standard benchmarks for non-rigid 3D shape matching, including FAUST (human shapes), SMAL (animal shapes), and DT4D-H (humanoid characters).

Key Results

  • Superior Accuracy: SpiderMatch achieved lower mean geodesic errors than state-of-the-art deep learning methods, such as Cao et al., on the FAUST and SMAL datasets.
  • Symmetry Resolution: A common failure in 3D matching is "left-right flips" (e.g., matching a left hand to a right hand). By enforcing global geometric consistency, SpiderMatch naturally avoids these errors, which often plague competing methods.
  • Computational Efficiency: Compared to previous methods that guarantee geometric consistency (e.g., Roetzer et al.), SpiderMatch is significantly faster. While ILP is generally NP-hard, the specific structure of the SpiderCurve problem allows off-the-shelf solvers like Gurobi to find global solutions for 1000-triangle meshes in approximately 100 seconds.

Discussion and Limitations

While SpiderMatch represents a major step forward, some limitations remain. The ILP approach currently scales to meshes with roughly 1,000 triangles; matching ultra-high-resolution scans directly remains a computational challenge. Additionally, the current method relies on a Traveling Salesperson Problem (TSP) approximation to generate the SpiderCurve. Future work may explore alternative space-filling curves to further optimize the matching process.

Despite these challenges, SpiderMatch demonstrates that global optimality and geometric consistency are achievable in practice, providing a robust foundation for future research in dense 3D shape correspondence.

Summary updated

BibTeX
@inproceedings{roetzer2024spidermatch,
  author = {Paul Roetzer and Florian Bernard},
  title = {{SpiderMatch: 3D Shape Matching with Global Optimality and Geometric Consistency}},
  booktitle = {IEEE/CVF Conference on Computer Vision and Pattern Recognition},
  year = {2024},
  doi = {10.1109/cvpr52733.2024.01378},
}
Figure