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.
翻译：在图形中找到最短路径对于计算机视觉和图形中的许多问题都很重要,包括图像分割、形状匹配或计算离散表面的大地距离等。传统上,对于带有卡路里边重量的图形,可以考虑最短路径的概念,这样就可以通过将个别边缘重量加在一起来计算路径长度。然而,具有卡路里边重量的图形在表达性方面受到严重限制,因为往往使用边缘来编码更复杂的相互关系。在这项工作中,我们弥补了这种建模限制,并在一个带有矩阵值边缘的图表中引入了一条最短路径的新颖的图形理论概念。为此,我们定义了一种有意义的方法来量化矩阵值边缘的路径长度,我们提出了一种简单而有效的算法来计算各自的最短路径。虽然我们的形式主义是普遍的,因此适用于视觉、图形及以后的多种环境,但我们侧重于在3D多层分析中展示其优点。
相关内容
微信扫码咨询专知VIP会员