Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching

Thomas Windheuser, Ulrich Schlickewei, Frank R. Schmidt, Daniel CremersComputer Graphics Forum 2011 · DOI

TL;DR

This paper presents a novel framework for matching 3D shapes that preserves their orientation and geometric consistency. They achieve this by formulating the problem as an Integer Linear Program (ILP), which can be efficiently solved using linear programming relaxation and a multiresolution approach, enabling large-scale applications.

What Problem Does This Paper Address?

Matching 3D shapes, especially non-rigid ones, is a fundamental challenge in computer graphics and related fields. This is crucial for tasks like comparing anatomical structures, analyzing deformations, or fusing data from different scans. Traditional methods often rely on local optimization, making them sensitive to initialization and prone to producing incorrect or inconsistent correspondences, particularly regarding orientation. The paper tackles the problem of finding globally optimal, orientation-preserving, and geometrically consistent matchings for large-scale 3D shapes, which is computationally demanding.

Methods

The core of the paper is an Integer Linear Programming (ILP) formulation for shape matching. Instead of matching points to points, they match small surface patches. This allows them to enforce geometric consistency and orientation preservation.

Key methodological contributions include:

  • ILP Formulation: They represent the matching as a binary decision problem (activate or deactivate a correspondence between two patches). The objective is to minimize an energy function that penalizes stretching and bending.
  • LP Relaxation: Since ILPs are NP-hard, they relax the binary constraints to continuous values ([0,1]) to obtain a solvable Linear Program (LP).
  • Iterative Binary Solution: To recover a binary solution from the LP relaxation, they use an iterative scheme: solve the relaxed LP, fix variables above a threshold (e.g., 0.5) to 1, and re-solve. This process is shown to converge quickly.
  • Multiresolution Framework: To handle high-resolution meshes (which lead to a massive number of variables in the ILP), they introduce a hierarchical approach. They first compute a matching on a coarse version of the shapes and then use this solution to guide and reduce the search space for finer resolutions.
  • Performance Analysis of LP Solvers: They evaluate various LP algorithms (simplex, interior-point, and a parallelizable primal-dual algorithm) on their problem, highlighting the benefits of GPU acceleration for larger instances.
  • Feature Descriptors: They demonstrate how incorporating feature descriptors (like Wave Kernel Signatures) into the energy function can significantly speed up the computation by making the LP relaxation solution more likely to be binary.

Datasets

The paper evaluates their method on pairs of models from the dataset of Vlasic et al. [VBMP08] (specifically "crane", "samba", and "bouncing" sets). They also mention using data from the SHREC 2011 benchmark and Sumner and Popović [SP04] for visualizations.

Key Insights and Ideas

  • Patch-based matching is key for consistency: Matching small surface patches, rather than individual points, is crucial for enforcing geometric continuity and orientation preservation across the entire shape.
  • ILP offers global optimality guarantees: By formulating the problem as an ILP, the method can, in principle, find the globally optimal matching, avoiding the local minima issues of many traditional methods.
  • LP relaxation is a practical path to approximate solutions: While the ILP is hard, its LP relaxation provides a computationally tractable way to get good approximate solutions, with a small gap to the true optimum.
  • Multiresolution is essential for scale: The quadratic growth of variables with mesh resolution makes direct ILP solving infeasible for detailed models. The multiresolution strategy is a critical enabler for handling large, high-resolution shapes.
  • Feature descriptors can dramatically speed up convergence: Adding a data term based on feature descriptors can make the LP relaxation solution binary more often, significantly reducing the number of iterative fixing steps required.

Key Results

  • The proposed method successfully computes orientation-preserving and geometrically consistent matchings for 3D shapes.
  • The iterative scheme for obtaining binary solutions from LP relaxation typically converges in less than 10 iterations, with a gap to the integer optimum usually between 0 and 3 percent.
  • A GPU-based implementation of the Eckstein-Bertsekas algorithm for LP solving shows significant speedups for larger problems compared to interior-point methods.
  • The multiresolution framework allows matching shapes with over 2000 triangles, which is impractical for direct ILP solvers.
  • Quantitative evaluation shows a mean geodesic error of 0.03 on test datasets, outperforming the GMDS method (0.079) and consistently preserving orientation, unlike GMDS which inverted orientation in 12 out of 30 pairs and had partially intertwined orientations in 8 others.
  • Incorporating feature descriptors reduced the average number of fixing steps from 8 to 2.3, with binary solutions occurring in 56% of experiments compared to 13% without.

Limitations and Future Work

  • Computational Cost: While the multiresolution approach and LP solver evaluations address efficiency, solving the ILP for very large or complex shapes can still be computationally intensive.
  • Memory Consumption: The interior-point method in CPLEX was observed to run out of memory for very large problems, whereas the GPU-based primal-dual algorithm had linear memory consumption.
  • Future Work: The paper suggests exploring other energy terms and feature descriptors, as well as investigating more advanced LP solvers or approximation techniques. The flexibility of the framework allows for integration of various energy models.

Summary updated

BibTeX
@article{windheuser2011large,
  author = {Thomas Windheuser and Ulrich Schlickewei and Frank R. Schmidt and Daniel Cremers},
  title = {{Large-Scale Integer Linear Programming for Orientation Preserving 3D Shape Matching}},
  journal = {Computer Graphics Forum},
  year = {2011},
  doi = {10.1111/j.1467-8659.2011.02021.x},
}
Figure