Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis

• URL: http://arxiv.org/abs/2112.04165v1
• Date: Wed, 8 Dec 2021 08:23:37 GMT
• Title: Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis
• Authors: Viktoria Ehm, Daniel Cremers, Florian Bernard
• Abstract summary: 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.
• Score: 69.08838724594584
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics, including image segmentation, shape matching, or the computation of geodesic distances on discrete surfaces. Traditionally, the concept of a shortest path is considered for graphs with scalar edge weights, which makes it possible to compute the length of a path by adding up the individual edge weights. Yet, graphs with scalar edge weights are severely limited in their expressivity, since oftentimes edges are used to encode significantly more complex interrelations. In this work we compensate for this modelling limitation and introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges. To this end, we define a meaningful way for quantifying the path length for matrix-valued edges, and we propose a simple yet effective algorithm to compute the respective shortest path. While our formalism is universal and thus applicable to a wide range of settings in vision, graphics and beyond, we focus on demonstrating its merits in the context of 3D multi-shape analysis.

Related papers

• 3D Neural Edge Reconstruction [61.10201396044153]
  We introduce EMAP, a new method for learning 3D edge representations with a focus on both lines and curves. Our method implicitly encodes 3D edge distance and direction in Unsigned Distance Functions (UDF) from multi-view edge maps. On top of this neural representation, we propose an edge extraction algorithm that robustly abstracts 3D edges from the inferred edge points and their directions.
  arXiv  Detail & Related papers  (2024-05-29T17:23:51Z)
• Efficiently Visualizing Large Graphs [18.764862799181053]
  We propose a novel dimension reduction method for graph visualization, called t-Distributed Graph Neighbor Embedding (t-SGNE) t-SGNE is specifically designed to visualize cluster structures in the graph. To suit t-SGNE, we combined Laplacian Eigenmaps with the shortest path algorithm in graphs to form the graph embedding algorithm ShortestPath Laplacian Eigenmaps Embedding (SPLEE)
  arXiv  Detail & Related papers  (2023-10-17T12:07:14Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• A Generalization of the Shortest Path Problem to Graphs with Multiple Edge-Cost Estimates [13.046825574678579]
  The shortest path problem in graphs is a cornerstone of AI theory and applications. We present a framework for weighted directed graphs, where edge weight can be computed (estimated) multiple times. We then present two complete algorithms for the generalized problem, and empirically demonstrate their efficacy.
  arXiv  Detail & Related papers  (2022-08-22T22:07:27Z)
• E-Graph: Minimal Solution for Rigid Rotation with Extensibility Graphs [61.552125054227595]
  A new minimal solution is proposed to solve relative rotation estimation between two images without overlapping areas. Based on E-Graph, the rotation estimation problem becomes simpler and more elegant. We embed our rotation estimation strategy into a complete camera tracking and mapping system which obtains 6-DoF camera poses and a dense 3D mesh model.
  arXiv  Detail & Related papers  (2022-07-20T16:11:48Z)
• GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
  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.
  arXiv  Detail & Related papers  (2022-05-30T16:22:53Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  We propose a graph kernel to compute more comprehensive similarity between paths and walks. We also combine it with optimal transport theory to extract more in-depth features of graphs. Our proposed method outperforms many state-of-the-art graph kernel methods.
  arXiv  Detail & Related papers  (2020-12-07T11:59:14Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)

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.