# Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
## 5 Computational Experiments
### Shape Correspondence: Synthetic Data from SHREC19  
The second test case we consider is shape correspondence: identifying corresponding points between two (or more) 3D shapes. Note that this is different from shape registration, namely finding a transformation that brings one shape \"close\" to another. Indeed, correspondence can be derived from registration, while the reverse may not be true. The Gromov-Wassertein framework allows for finding correspondence, as the latter is embedded in the optimal transport plan it computes. To assess how well GW can recover correspondence, we considered the SHREC19 benchmark [39]. This benchmark includes 3D shapes represented with a triangular mesh of their surfaces. These shapes are derived from 3D scans of real-world objects, with each object being present in multiple poses associated with one or more types of deformation. The deformations are classified into four different groups, referred to as test-sets. Those four groups correspond to articulated deformations (group 0), isometric deformations (group 1), non-isometric deformations (group 2), and topologic/geometric deformations (group 3). Example of shapes for each test-set are provided in Figure 3.  
The SHREC19 benchmark includes 76 shape pairs that are selected from the four different groups, and regrouped in four test sets (Table 1). Test-set 0 includes 14 pairs of articulating wooden hands from group 0. Test-set 1 includes 26 pairs of models corresponding to clothed humans as well as hands from group 1. Test-set 2 includes 19 pairs of models from the group 2. Each of those pairs includes a thin clothed mannequin and a larger mannequin, ensuring the the transformation is non-isometric. Finally test-set 3 includes 17 pairs of shapes from group 3 that contain challenging geometric and topological changes. We chose the low resolution version of this benchmark. In this version, each shape is represented by approximately 10,000 vertices and 20,000 triangles. For each pair of shapes, the ground-truth correspondence is known. Figure 2: **Quality of 3D shape recognition based of the temperature-dependent GW distances as a function of temperature. ** The probability of classifying correctly a shape into its own class within the TOSCA dataset using the distance measure \(DM_{\beta}\equiv U_{\beta}^{\text{MF}}\) (see text for details) is plotted against \(\beta\), the inverse of the temperature. The curve is generated from the arithmetic means over 10,000 experiments (see text for details). Shaded areas represent standard deviations over those experiments. The quality of shape correspondence is evaluated by measuring normalized geodesics between the ground-truth (available as part of the SHREC19 dataset) and the predicted correspondence that is derived from the GW optimal coupling. Specifically, let \(x_{i}\) be a point on shape \(X\), \(y_{i}\) its predicted correspondence on shape \(Y\) and \(g_{i}\) the ground truth position of \(x_{i}\) on \(Y\). Note that \(y_{i}\) and \(g_{i}\) are both on the surface of \(Y\). The normalized geodesic error \(\epsilon(x_{i})\) between the \(y_{i}\) and \(g_{i}\) is computed as:  
\[\epsilon(x_{i})=\frac{d_{Y}(y_{i},g_{i})}{area(Y)^{1/2}},\]  
where \(d_{Y}(y_{i},g_{i})\) is the geodesic distance between \(y_{i}\) and \(g_{i}\) on the surface of \(Y\). The geodesic distance is computed with the algorithm from [PERSON] et al. [38], as described in the previous subsection. We compared two different implementations of the GW framework, based on two different algorithms, named the fixed point method described in Algorithm 1 and the physics-based algorithm described in Algorithm 2, both implemented in FreeGW. Algorithm 1 uses a fixed regularization parameter, \(\epsilon\). To make sure that the corresponding transport plan is close to the actual GW transport plan, we chose \(\epsilon=10^{-12}\). Traditional regularized OT solver do not work well for such a small \(\epsilon\). We chose therefore our own OT solver [23; 24] to solve step 2 in Algorithm 1.