algorithm - 量化线段路径差异的算法

Question

假设我有两条线段路径，例如下面示例的子集。如何量化它们之间的差异？

两条路径可能有不同数量的段，并且每段的长度和它们之间的角度是可变的。

我认为建立一个坐标系并将段定义为节点和边会很好。这种差异也许可以通过将一个转换为另一个所需的操作来量化，类似于Levenshtein 距离算法。可惜操作空间很大。有任何想法吗？谢谢！

score 2 · Accepted Answer

您可以将它们绘制成固定大小的图像，然后使用欧几里德距离来比较图像。

或者您可以测量总长度并将角度的绝对值（可能还有带符号的角度）相加作为度量。基于此的东西将具有不变的形状方向的好特性（如果你想要的话！）。

你如何量化它在某种程度上取决于你为什么要量化它们之间的差异。

score 1 · Accepted Answer

如果您使用操作：

您仍然可以在 n^2 时间内使用 Levenshtein 距离。

将段编码为以下 [segment,corner]*。所以它会是：

[length, rotation] [length, rotation]...

其中旋转与线段指向方向有关。

计算拉伸和弯曲非常明显。Value[i-1, j-1] + stretch + bend.

计算添加/删除。添加Value[i,j-1] + Cost of adding，删除Value[i-1, j] + cost of removal。

score 1 · Accepted Answer

我会比@awoodland 指出的更进一步：你如何量化它完全取决于你为什么要量化差异。

您是否正在寻找一个唯一（至少，可能是唯一的）数字，例如线段路径的哈希码？或者您是否试图量化线段路径以说“这条路径比那条路径更复杂（或更长，或具有更多锐角）”？

如果你想创建一个哈希码，我建议创建两个 32 位 CRC（或类似的东西）：一个用于段长度，一个用于角度。计算完这些 CRC 后，将它们放在一个 64 位值中，高 32 位中的角度和低 32 位中的长度。根据段的数量，也许单个 CRC 值可以：对于每个段，添加长度，然后添加它与下一段之间的角度。

请注意，上面可能会为您提供每个路径的唯一编号，但不能保证。

如果要量化线段路径的复杂度……我的想法不多。

score 1 · Accepted Answer

你可以看看这篇论文：

在本文中，我们使用 kAS（分段对的泛化：您可以将多个分段相互连接）进行对象检测。我们为这些段集引入了一个描述符，您可以使用它来描述您的配对。

我们的描述符不是旋转不变的，所以它可能不适合你。

4 回答 4