Efficiently compare 3D shapes using advanced geodesic distances
Unlocking Geodesic Gromov-Wasserstein Distances for 3D Modeling
Computer Vision and Pattern RecognitionData Structures and Algorithms
Summary
Comparing complex shapes or 3D objects is often slow and difficult because it involves heavy calculations. The authors developed faster methods to measure differences between shapes by using distances along surfaces or graphs rather than straight lines. Their new approach works better in 3D pose estimation and finding object parts in scenes. It is both more accurate and computationally lighter than previous methods that used simple Euclidean distances.
What this means in practice
- •For 3d graphics developers: Enhance 3D pose estimation in complex scenes by efficiently measuring shape similarity using geodesic distances.
- •For computer vision engineers: Enable partial template matching in 3D scene analysis with scalable and accurate shape comparison techniques.
Authors
Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar, Dwaipayan Saha
Abstract
\textit{Gromov-Wasserstein Distances} (GWDs) provide quantitative ways of comparing probabilistic distributions defined on different metric spaces by applying techniques from the optimal transport theory. As such, GWD can be potentially useful in a large variety of applications ranging from graph matching problems to 3D object detection. However its practical use at scale is significantly limited by cubic time complexity computations involving dense intra-space distance matrices. Even though in the Euclidean metric spaces several techniques (e.g. involving scalable kernel methods) were proposed to address it, to the best of our knowledge, analogous techniques for general geodesic distances on manifolds, or shortest-path distance on graphs in their discretized variants, were not developed. In this paper, we present \textbf{E}fficient \textbf{G}eodesic \textbf{Gro}mov-\textbf{W}asserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced \textit{GenusSink} methods \citep{genussink} and the theory of random features. We provide important downstream applications, namely: 3D pose estimation and 3D template detection. In the latter setting, we formulate a partial 3D template recovery as a staged problem: capacity-constrained scene selection is followed by semi-relaxed recovery of template visibility and correspondence. Our empirical findings show that EGGroW provides accurate solutions when standard Euclidean-based techniques fail and is characterized by light computational footprint, as our theoretical analysis predicts.