A common approach to compute distances on continuous surfaces is by considering a discretized polygonal mesh approximating the surface and estimating distances on the polygon. We show that exact geodesic distances restricted to the polygon are at most second-order accurate with respect to the distances on the corresponding continuous surface. By order of accuracy we refer to the convergence rate as a function of the average distance between sampled points. Next, a higher-order accurate deep learning method for computing geodesic distances on surfaces is introduced. Traditionally, one considers two main components when computing distances on surfaces: a numerical solver that locally approximates the distance function, and an efficient causal ordering scheme by which surface points are updated. Classical minimal path methods often exploit a dynamic programming principle with quasi-linear computational complexity in the number of sampled points. The quality of the distance approximation is determined by the local solver that is revisited in this paper. To improve state of the art accuracy, we consider a neural network-based local solver which implicitly approximates the structure of the continuous surface. We supply numerical evidence that the proposed learned update scheme provides better accuracy compared to the best possible polyhedral approximations and previous learning-based methods. The result is a third-order accurate solver with a bootstrapping-recipe for further improvement.
Figures & tables
Figure 1. Geodesic distances from a single point on each surface are presented as colors (white to red) and level sets painted on the surface. The proposed method produces substantially more accurate than state of the art distance maps while operating in quasi-linear time. The evaluation was done on shapes from the TOSCA dataset ( Bronstein et al., 2008 ) , whereas our solver was trained with a small number of 2nd order polynomial surfaces. Figure 1. Geodesic distance computed by our method is shown on shapes from the Tosca dataset as distance maps and iso-contours. Our method computes highly accurate distances.
Figure 2. The proposed local solver pipeline described in Section 4.1 . For each point in the Wavefront , the Visited points from from its local neighbourhood are chosen, and their coordinates and distance function are transformed into their canonical representation with respect to the target point. The processed input is fed into the neural network and the output is further processed to revert the centering and scaling transformations. Figure 2. illustration of the pipeline of our local solver. Fully described in the text.
Figure 3. The proposed network architecture described in Section 4.1 . The input coordinates and distance function are in their canonical form, after translation rotation and scale. Figure 3. Illustration of the architecture of our local solver. Fully described in the text.
Figure 4. Bootstrapping by training. Distance values computed for a high h2 -resolution sampled mesh of a continuous surface with an r accurate scheme yields O(h2r) accurate distances given at the mesh points. The mesh can then be sampled into a lower h -resolution mesh of the same continuous surface, while keeping the corresponding O(h2r) accurate distances at the vertices. See text for an elaborated discussion regarding data augmentation at high resolution and training more accurate update procedures at the low resolution. Figure 4. Present the proposed bootstrapping method used to create our training examples. Fully described in the text.
Figure 5. Order of accuracy: Right: Plots showing how the edge size effects the error. The accuracy of each scheme is defined by the corresponding slope. We used mesh approximations of a unit sphere with different edge size. Left: Errors presented on high resolution spheres for 2nd order methods and our presented method (when brighter colour indicates higher error). Figure 5. Numerical evaluation of the order of accuracy presented on spheres. The order of accuracy for the fast marching method is 0.68, for the MMP method 1.95, for the method presented by Lichtenstein et al. 2.1, and for our method 3.02. For high-resolution meshes with an average edge of less than 0.1, our method shows errors that are more than an order of magnitude smaller compared to all other methods
Figure 6. Polynomial surfaces: Errors presented for the polyhedral scheme and the proposed method. Local errors, represented as colors on the surface, were computed relative to exact polyhedral distances computed at a high-resolution sampled mesh of the continuous surface, as described in Subsection 4.3 . Figure 6. Visualized errors on hyperbolic parabolic surfaces comparing MMP methods and our method. Our method has significantly lower errors compared to MMP.
Surface
L1(×10−2)
L∞(×10−2)
FMM
LPK
MMP
Ours
FMM
LPK
MMP
Ours
x2−y2
2.86
0.21
0.09
0.04
7.95
1.17
0.24
0.16
x2+y2
2.05
0.34
0.28
0.09
6.80
1.44
0.67
0.26
x2−y2+xy
2.91
0.33
0.18
0.09
6.40
2.60
0.63
0.28
Table 1. Polynomial surfaces: Quantitative evaluation conducted on 2nd order paraboloids. The errors were computed relative to the polyhedral distance projected from high-resolution sampled meshes, as described in Subsection 4.3 .
Figure 7. Order of accuracy on parametric surfaces: Plots showing the effect of the edge size on the errors. The accuracy of each scheme is associated with its corresponding slope. Ground truth distances were evaluated using our bootstrapping method 4.3 . Left: Evaluation on hyperbolic paraboloid x2−y2 . Right: Evaluation on regular paraboloid x2+y2 . Figure 7. Numerical evaluation of the order of accuracy for a regular paraboloid and a hyperbolic paraboloid. For a regular paraboloid, the order of accuracy is 1.93 and 3.02 for the MMP method and our method, respectively. For a hyperbolic paraboloid, the accuracy is 1.74 for the MMP method and 3.01 for our method.
Shape
L1(×10−1)
L∞(×10−1)
Heat
FMM
LPK
Ours
Ours - Point clouds
Heat
FMM
LPK
Ours
Ours - Point clouds
Dog
0.728
0.110
0.123
0.037
0.072
8.688
1.514
1.318
0.465
2.968
Cat
1.260
0.101
0.278
0.043
0.045
5.379
0.735
3.949
0.474
0.863
Wolf
0.440
0.162
0.169
0.072
0.092
2.244
1.009
1.343
0.422
0.598
Horse
0.796
0.129
0.256
0.043
0.089
3.331
1.687
2.761
0.602
3.502
Michael
3.142
0.089
1.170
0.067
0.081
8.525
0.506
3.800
0.418
0.563
Table 2. Generalization to arbitrary surfaces: Quantitative evaluation tested on TOSCA. The errors are relative to the MMP scheme. Our solver and the one proposed in ( Lichtenstein et al., 2019 ) were trained using our bootstrapping method 4.3 with a limited number of 2nd order polynomial surfaces, the three paraboloids presented in Table 5 . In addition to shapes represented as triangulated meshes, we present results for applying the proposed method to point clouds, see Section 5.3 .
Figure 8. Generalization to arbitrary surfaces. Errors presented for the heat kernel method, fast marching, Lichtenstein et al. and the proposed method. Local errors presented as colors on the surface (brighter color indicates higher error), were computed relative to the polyhedral MMP distances. The evaluation was done on the TOSCA data base, whereas our solver and the solver proposed by Lichtenstein et al. were trained with a small number of 2nd order polynomial surfaces, the three paraboloid surfaces presented in Table 5 Figure 8. Present errors of the Heat method, FMM, Lichtenstein et al. and our method. Fully described in the text
Figure 9. Generalization to arbitrary shapes: Iso-contours shown for (left to right) the heat method, fast marching, Lichtenstein et al., our method and the exact polyhedral scehme, calculated by the MMP algorithm. The evaluation was conducted on shapes from TOSCA whereas our solver and the solver proposed by Lichtenstein et al. were trained with only limited number of 2nd order polynomial surfaces (the 3 surfaces presented in Table 5 ). Figure 9. Present iso-contours on shapes from the Tosca dataset for the Heat method, FMM, Lichtenstein et al., our method and the exact polyhedral distances. Our method shows more accurate iso-contours on sharp edges, even though it was trained on smooth surfaces. Fully described in the text.
Figure 10. Point clouds: Distance maps computed by the proposed method. The evaluation was done on shapes from the TOSCA dataset, given as point clouds. Our solver was trained using the suggested bootstrapping framework 4.3 with a limited number of 2nd order polynomial surfaces, represented by polygonal meshes. Figure 10. Point clouds. Geodesic distance computed by our method is plotted on shapes from the Tosca dataset represented as point clouds. Fully described in the text.
Figure 11. Order of accuracy for point clouds: Plots showing the effect of the edge size of the corresponding mesh or distances between nearby points in the point cloud case, on the errors. When applied to point clouds, the local neighborhood is given by KNN 3,6 as defined in Subsection 5.3 . Figure 11. Numerical evaluation of the order of accuracy shown on spheres. The variation of our method for point clouds shows a similar order of accuracy and errors as the variation of our method for triangulated meshes.
Figure 12. Point clouds and nearest neighbors: Local inaccuracies presented as colors on the surface (brighter color indicates higher error), were computed relative to distances computed on the polyhedral mesh representation of the surfaces. In the point cloud representation, the local neighborhood is defined using the KNN framework, which is based on the Euclidean distance between points in the extrinsic embedding space R3 . This is in contrast to the intrinsic neighborhood defined by edge connectivity in the mesh representation. In the green regions, points from far away parts of the surface are wrongly identified as neighbors by the solver. It leads to loss of accuracy in distance approximation in such regions. Figure 12. Point clouds and nearest neighbors. Illustration of errors that occur when defining the local neighborhood using the extrinsic embedding space R3. Fully described in the text.
Figure 13. Left: Local neighborhood: Evaluation of the proposed method on spheres with different local neighborhoods support. Ring i corresponds to a neighborhood containing all vertices with at most i edges from the evaluated target. Right: Precision floating point representation: Evaluation of our method on spheres with different floating point precision representation of the neural network weights. Figure 13. Left: Local neighbourhood: numerical evaluation of the order of accuracy of our method for different local neighbourhoods. The order of accuracy for Ring1, Ring2, Ring3, and Ring4 are 0.98, 2.63, 3.02, and 2.97, respectively. Right: Precision floating point representation: numerical evaluation of the order of accuracy of our method with different floating point representations of the neural network weight. The order of accuracy for float16, float32, and float64 are 2.83, 3.00, and 3.02, respectively.
Error
FMM
Heat method
LPK
MMP
Ours
L1
0.01804
0.01964
0.00510
0.00128
0.00099
L2
0.01865
0.02048
0.00672
0.00142
0.00127
L∞
0.0270
0.0361
0.02278
0.0027
0.0041
Table 3. Robustness to triangulation: Quantitative evaluation of the ability of the proposed method to handle triangulations other than those for which it was trained for. The evaluation was conducted on randomly uniformly non-regularly sampled spheres whereas our solver and the solver proposed by Lichtenstein et al. were trained only on regularly sampled spheres.
Figure 14. Robustness to Triangulation: Errors presented for the “exact” MMP scheme and the proposed method. Local errors, represented as colors on the surface, were computed relative to the analytical geodesic distances. The proposed method was trained on regularly sampled spheres as can be seen in Figure 16 . Figure 14. Robustness to Triangulation. Visualization of errors on spheres containing ill condition triangulation. The methods presented are the MMP method and our method when trained on regularly sampled spheres. Fully described in the text.
Neural architecture
Residual connections
Activation
negative slope
Pooling
Model 1
✓
LeakyReLu
0.2
max
Model 2
✓
LeakyReLu
0.2
avg
Model 3
✓
LeakyReLu
0.001(default)
max
Model 4
✓
ReLu
✗
max
Model 5
✗
ReLu
✗
max
LPK
✗
ReLu
✗
max
Table 4. Neural Architectures: Various architectural modifications to the presented neural network 3 . The residual connections and the different activation functions are defined only for the shared weight MLP, while the fully connected network applied after the pooling operation has LeakyRelu activation with a negative slope of 0.001 in all variants of our neural network.
Figure 15. Neural architectures: Evaluation of the effects of different modifications to our neural network, presented in 6.3 . All different models use the same local neighborhood support, which includes all vertices with at most three edges from the evaluated target. Figure 15. Neural architectures: numerical evaluation of the order of accuracy on spheres for different architectures presented in Table \ref{table: Neural Architectures}. The order of accuracy for Model1, Model2, Model3, Model4, and Model5 are 3.02, 2.59, 2.73, 2.38, and 2.22, respectively.
Figure 16. Attention map showing the importance of each neighboring point in the network approximation. The source point is colored pink, the point whose distance is currently evaluated is colored red, and all other plotted points form the current local neighborhood. The Visited neighboring points that are fed into the neural network are colored according to the percentage of the corresponding features in the latent vector obtained from the max-pooling operation. It can be seen that the neural network pays more attention to the neighboring points that are closer to the geodesic path. Figure 16. Attention map showing the importance of each neighboring point in the network approximation. Fully described in the text.
Neural PDE solvers use trainable models to approximate solutions or solution operators for partial differential equations, often with physical constraints.
The concept of geodesic-like curves was introduced by Chen in 2010 as a method for estimating shortest paths (geodesics) on parametric surfaces, with its convergence established theoretically. However, an efficient numerical computational framework has not yet been developed. In this paper, we propose an elegant and efficient approach for computing geodesic-like curves by leveraging deep learning and Physics-Informed Neural Networks (PINNs). Under the proposed framework, not only can single parametric surfaces be handled efficiently, but a broad class of complex parametric surfaces including multi-surface systems with C0 or higher continuity and surfaces of revolution can also be robustly addressed.
Sheng-Gwo Chen, Chen-Chang Peng
Department of Applied Mathematics, National Chiayi University, Chia-Yi 600, Taiwan
Machine learning has been progressively generalised to operate within non-Euclidean domains, but geometrically accurate methods for learning on surfaces are still falling behind. The lack of closed-form Riemannian operators, the non-differentiability of their discrete counterparts, and poor parallelisation capabilities have been the main obstacles to the development of the field on meshes. A principled framework to compute the exponential map on Riemannian surfaces discretised as meshes is straightest geodesics, which also allows to trace geodesics and parallel-transport vectors as a by-product. We provide a parallel GPU implementation and derive two different methods for differentiating through the straightest geodesics, one leveraging an extrinsic proxy function and one based upon a geodesic finite differences scheme. After proving our parallelisation performance and accuracy, we demonstrate how our differentiable exponential map can improve learning and optimisation pipelines on general geometries. In particular, to showcase the versatility of our method, we propose a new geodesic convolutional layer, a new flow matching method for learning on meshes, and a second-order optimiser that we apply to centroidal Voronoi tessellation. Our code, models, and pip-installable library (digeo) are available at: circle-group.github.io/research/DSG.
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 Efficient Geodesic Gromov-Wasserstein methods (EGGroW), a new class of efficient algorithms designed to calculate geodesic Gromov-Wasserstein distances with entropic Sinkhorn-like approaches, leveraging recently introduced 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.
Krzysztof Marcin Choromanski, Derek Long, Ananya Parashar +1