量化线段路径差的算法

Question

假设我有两个线段路径，例如以下示例的一个子集。我如何量化它们之间的区别？

1. |__
2. \_
3. __
4. /\
5. \/
6. |
7. _

这两个路径可能具有不同数量的段，每个段的长度以及它们之间的角度是可变的。

我认为建立坐标系并将细分定义为节点和边缘是一件好事。差异也许可以通过将一个转换为另一个的操作进行量化，类似于 Levenshtein距离 算法。不幸的是，操作空间很大。有任何想法吗？谢谢！

Answer 1

我会比@awoodland指出的要走得更远：您如何量化它取决于 完全 关于为什么要量化差异。

您是否想提出一个唯一的（至少，可能是唯一的）数字，例如线段路径的哈希代码？还是您试图量化线段路径，以说：“此路径比该路径更复杂（或更长，或更长的急性角度）？

如果要创建哈希代码，我建议创建两个32位CRC（或类似的内容）：一个用于段长度，一个用于角度。一旦您计算出这些CRC，就将它们放在64位值中，在高32位和低32位的长度中，其角度将其放在一起。根据片段的数量，也许单个CRC值可以：对于每个段，添加长度，然后在其和下一个段之间添加角度。

请注意，以上可能为您提供每个路径的唯一数字，但不能保证。

如果您想量化线段路径的复杂性...我没有很多想法。

Answer 2

您可以将它们绘制成固定尺寸的图像，然后使用欧几里得距离比较图像。

或者，您可以测量总长度并将角度的绝对值（以及签名的角度）作为一个度量。基于此的东西将具有与形状方向不变（如果需要的话！）的不变属性。

您如何量化它有所取决于 为什么 您想量化它们之间的区别。

Answer 3

您可以查看本文：

http://www.vision.ee.ethz.ch/~calvin/publications/ferrari07pami.pdf

在本文中，我们使用的是KAS（段对的概括：您可以有多个片段相互连接）进行对象检测。我们介绍了这些片段的描述符，您可以用来描述您的对。

我们的描述符并非旋转不变，因此可能不适合您。

Answer 4

如果您使用操作：

• 添加角和细分市场
• 删除角和细分
• 拉伸段（差异的重量）
• 弯曲角（差异的重量）

在仍处于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.