GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation
- URL: http://arxiv.org/abs/2205.15217v1
- Date: Mon, 30 May 2022 16:22:53 GMT
- Title: GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation
- Authors: Rolandos Alexandros Potamias and Alexandros Neofytou and
Kyriaki-Margarita Bintsi and Stefanos Zafeiriou
- Abstract summary: We propose a learnable network to approximate geodesic paths on 3D surfaces.
The proposed method provides efficient approximations of the shortest paths and geodesic distances estimations.
- Score: 93.60478281489243
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Geodesic paths and distances are among the most popular intrinsic properties
of 3D surfaces. Traditionally, geodesic paths on discrete polygon surfaces were
computed using shortest path algorithms, such as Dijkstra. However, such
algorithms have two major limitations. They are non-differentiable which limits
their direct usage in learnable pipelines and they are considerably time
demanding. To address such limitations and alleviate the computational burden,
we propose a learnable network to approximate geodesic paths. The proposed
method is comprised by three major components: a graph neural network that
encodes node positions in a high dimensional space, a path embedding that
describes previously visited nodes and a point classifier that selects the next
point in the path. The proposed method provides efficient approximations of the
shortest paths and geodesic distances estimations. Given that all of the
components of our method are fully differentiable, it can be directly plugged
into any learnable pipeline as well as customized under any differentiable
constraint. We extensively evaluate the proposed method with several
qualitative and quantitative experiments.
Related papers
- DataSP: A Differential All-to-All Shortest Path Algorithm for Learning Costs and Predicting Paths with Context [4.202961704179733]
This paper introduces DataSP, a differentiable all-to-all shortest path algorithm to facilitate learning latent costs from trajectories.
Complex latent cost functions from contextual features can be represented in the algorithm through a neural network approximation.
We show that DataSP outperforms state-of-the-art machine learning approaches in predicting paths on graphs.
arXiv Detail & Related papers (2024-05-08T09:45:54Z) - Learning the Geodesic Embedding with Graph Neural Networks [22.49236293942187]
We present GeGnn, a learning-based method for computing the approximate geodesic distance between two arbitrary points on discrete polyhedra surfaces.
Our key idea is to train a graph neural network to embed an input mesh into a high-dimensional embedding space.
We verify the efficiency and effectiveness of our method on ShapeNet and demonstrate that our method is faster than existing methods by orders of magnitude.
arXiv Detail & Related papers (2023-09-11T16:54:34Z) - NeuroGF: A Neural Representation for Fast Geodesic Distance and Path
Queries [77.04220651098723]
This paper presents the first attempt to represent geodesics on 3D mesh models using neural implicit functions.
Specifically, we introduce neural geodesic fields (NeuroGFs), which are learned to represent the all-pairs geodesics of a given mesh.
NeuroGFs exhibit exceptional performance in solving the single-source all-destination (SSAD) and point-to-point geodesics.
arXiv Detail & Related papers (2023-06-01T13:32:21Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space.
We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size.
We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
arXiv Detail & Related papers (2023-02-14T22:12:16Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics.
We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
arXiv Detail & Related papers (2021-12-08T08:23:37Z) - Fast and Scalable Optimal Transport for Brain Tractograms [4.610968512889579]
We present a new multiscale algorithm for solving regularized Optimal Transport problems on a linear memory footprint.
We show the effectiveness of this approach on brain tractograms modeled either as bundles of fibers or as track density maps.
arXiv Detail & Related papers (2021-07-05T13:28:41Z) - PointFlow: Flowing Semantics Through Points for Aerial Image
Segmentation [96.76882806139251]
We propose a point-wise affinity propagation module based on the Feature Pyramid Network (FPN) framework, named PointFlow.
Rather than dense affinity learning, a sparse affinity map is generated upon selected points between the adjacent features.
Experimental results on three different aerial segmentation datasets suggest that the proposed method is more effective and efficient than state-of-the-art general semantic segmentation methods.
arXiv Detail & Related papers (2021-03-11T09:42:32Z) - Learning High Dimensional Wasserstein Geodesics [55.086626708837635]
We propose a new formulation and learning strategy for computing the Wasserstein geodesic between two probability distributions in high dimensions.
By applying the method of Lagrange multipliers to the dynamic formulation of the optimal transport (OT) problem, we derive a minimax problem whose saddle point is the Wasserstein geodesic.
We then parametrize the functions by deep neural networks and design a sample based bidirectional learning algorithm for training.
arXiv Detail & Related papers (2021-02-05T04:25:28Z) - Shortest path distance approximation using deep learning techniques [0.43461794560295636]
We show that a feedforward neural network fed with embeddings can approximate distances with relatively low distortion error.
The suggested method is evaluated on the Facebook, BlogCatalog, Youtube and Flickr social networks.
arXiv Detail & Related papers (2020-02-12T21:59:25Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.