Conformal Wasserstein distance: II. computational aspects and extensions

Yaron Lipman, Jesús Puente, Ingrid DaubechiesMath. Comput 2013 · DOI

TL;DR

This paper introduces a novel computational framework for measuring the geometric similarity between surfaces, extending previous work on disk-type surfaces to sphere-type surfaces. The core contribution is an efficient algorithm for computing this "conformal Wasserstein distance," which is shown to be robust and effective for tasks like shape comparison and classification, even for non-rigid deformations.

What Problem Does This Paper Address?

Comparing and aligning surfaces is a fundamental problem in many scientific disciplines, from computer graphics to biology. Traditional methods often rely on identifying specific landmarks or require surfaces to be nearly isometric. This paper addresses the challenge of quantifying the geometric similarity between surfaces that can undergo significant non-rigid deformations, such as brain cortices or molar teeth. The authors extend their previous work on "conformal Wasserstein distance" to handle more general surface types (like spheres) and provide a practical, computationally efficient algorithm for its calculation. This distance metric is designed to capture intrinsic geometric properties and is invariant to conformal transformations, making it suitable for comparing surfaces with varying topologies and deformations.

Methods

The paper builds upon the concept of optimal mass transportation, specifically the Wasserstein distance, but adapts it to the geometric context of surfaces. The key innovation is the use of conformal uniformization to map surfaces to a canonical space (the hyperbolic disk for disk-type surfaces, and the extended complex plane for sphere-type surfaces). This allows the problem to be framed as finding an optimal transportation plan between the resulting "metric densities" on these canonical spaces.

The authors introduce a conformal Wasserstein distance that uses a specialized cost function designed to measure the dissimilarity between local geometric neighborhoods. This cost function is made robust to noise and is invariant under conformal mappings.

For computational tractability, the paper presents an algorithm that:

  1. Approximates uniformization: Surfaces are mapped to their canonical representations.
  2. Discretizes measures: Continuous densities on the canonical spaces are approximated using sample points.
  3. Approximates the cost function: The local geometric dissimilarity is computed between pairs of sample points.
  4. Solves a linear program: The discrete optimal mass transportation problem is solved to approximate the conformal Wasserstein distance.

The paper also discusses extensions to sphere-type surfaces, requiring new definitions for neighborhoods and adapting the cost function.

Datasets

The authors evaluate their algorithms on several datasets:

  • Non-rigid World data-set: Contains meshes of articulated objects (cats, dogs, humans, etc.) in different poses, specifically designed for evaluating non-rigid shape comparison.
  • SHREC 2007 Watertight Benchmark: A challenging dataset with significant in-class variations across categories like chairs, animals, and humans.
  • Synthetic data-set: Used to test the influence of the "size" parameter (R) on the distance behavior.
  • Primate molar teeth: A real-world biological application dataset used for classification of lemur species based on tooth surface geometry.

Key Insights and Ideas

  • Conformal Invariance is Key: By leveraging conformal mappings, the distance metric becomes invariant to local stretching and shrinking, focusing instead on intrinsic geometric structure. This is crucial for comparing surfaces that undergo significant non-rigid deformations.
  • Mass Transportation as a Geometric Tool: The paper elegantly reframes surface comparison as an optimal mass transportation problem, where "mass" represents geometric density and "cost" reflects local geometric dissimilarity.
  • Generalization to Spheres: Extending the framework from disk-type surfaces to sphere-type surfaces is a significant theoretical and practical advancement, broadening the applicability of the method.
  • Local Neighborhoods Matter: The definition of local neighborhoods, based on area and circumference, is critical for capturing local geometric similarity and is designed to be invariant under conformal transformations.
  • Linear Programming for Efficiency: Recasting the problem as a linear program allows for efficient computation of the distance and optimal transportation plan, making the method practical for real-world applications.

Key Results

  • Algorithm for Conformal Wasserstein Distance: The paper provides a concrete algorithm for computing the conformal Wasserstein distance for both disk-type and sphere-type surfaces.
  • Convergence Guarantees: Theoretical analysis demonstrates that the discrete approximation of the distance converges to the true distance as the sampling density increases. Error bounds are provided, showing dependence on fill distance and approximation parameters.
  • Experimental Validation: The algorithm is tested on various datasets, showing competitive or superior performance compared to state-of-the-art methods like the Gromov-Hausdorff distance, particularly for non-rigid shape comparison and classification.
  • On the Non-rigid World dataset, the conformal Wasserstein distance achieved a classification rate of 94% for the first nearest neighbor, outperforming speGH at 78%.
  • On the SHREC 2007 dataset, a combined distance metric achieved a 95% classification rate.
  • Connection to Local Isometry: A theoretical result shows that a small conformal Wasserstein distance implies that the surfaces are locally near-isometric, providing a geometric interpretation of the metric.

Limitations and Future Work

  • Computational Bottleneck: The computation of the local distance function (d_R) is identified as the bottleneck in the algorithm's runtime, especially for sphere-type surfaces.
  • Discrete Uniformization as a "Black Box": The paper relies on existing methods for discrete uniformization and does not analyze their convergence or error contribution in detail, treating it as a "black box."
  • Higher Regularity of Cost Function: The authors hypothesize that the cost function might be Lipschitz rather than just uniformly continuous, which would imply linear convergence rates for the algorithm. Verifying this is left as future work.
  • Generalization to Higher Genus Surfaces: The current framework is primarily for genus-zero surfaces (disks and spheres). Extending it to surfaces with higher genus is a natural next step.
  • Robustness to Noise: While the method is designed to be robust to noise, further investigation into its performance with highly noisy data could be beneficial.

Summary updated

BibTeX
@article{lipman2013conformal,
  author = {Yaron Lipman and Jesús Puente and Ingrid Daubechies},
  title = {{Conformal Wasserstein distance: II. computational aspects and extensions}},
  journal = {Math. Comput.},
  year = {2013},
  doi = {10.1090/s0025-5718-2012-02569-5},
}
Figure