比较两条路径的相似性

Question

我有A路径集和B路径集。我正在尝试找到一种算法来比较这两个路径集的相似性。

路径特征：

1. 路径集是一条或多条线，每条线上有两个或多个点。线条不一定要连接在一起。
2. 路径集可能会重叠（即X形路径）。
3. 路径集中可能包含不同数量的顶点（即一条路径看起来类似于另一条路径，但其中有更多的点）。
4. 两个路径集中的点的顺序未必相同。

应该考虑到比例尺，即小的X应该与大的X匹配。对于任何路径，不需要考虑翻译，因为任何路径的最底部的点的y值为0，最左边的点的x值为0。

是否有最佳实践或众所周知的算法（我在谷歌搜索中找到的很少）可以比较这些路径集的相似性？

- jjxtra

---

两条路径何时相似？您已经说明它们不应该旋转，但可以缩放。那么转置呢？顶点数量呢？如果路径在旋转后与之前相同，但点的顺序不同（即X轴旋转90或180度），会怎样呢？ - tobias_k

@tobias_k 更新了问题 - jjxtra

你应该明确两件事情：(1)“路径”甚至不需要是连通的（这与大多数人对“路径”的直觉相反--我认为你应该选择另一个词，比如“路径集”，因为已经有一个回答者感到困惑）；(2)仅仅寻找具有相似坐标的点对是不够的，因为需要处理缩放（和很可能更基本的平移）。 - j_random_hacker

@j_random_hacker 更新了问题。 - jjxtra

Answer 1

从算法上讲，我认为我会尝试这样做：

1. For each path, convert the consecutive pairs of points comprising the path into a list of vectors, where a vector is defined as a pairing of a magnitude (length) and a direction (an angle relative to the X-axis). You can compute these values like this (C#):

   double dx = endPoint.X - startPoint.X;
   double dy = endPoint.Y - startPoint.Y;
   double magnitude = Math.Sqrt((dx * dx) + (dy * dy));
   double direction = Math.Atan2(dy, dx) * (180 / Math.PI);
   

2. Next, "normalize" each vector sequence by combining consecutive vectors that have the same* direction. In other words, replace those with a new vector that has the same direction and the sum of their magnitudes. This will take care of the cases where you have more than two points on the same line anywhere on your paths. After this step you should have the same number of vectors in each sequence. (If not, the paths are not similar.)

3. Figure out the scaling factor. Take the magnitude of the first vector in the first sequence and divide it by the magnitude of the first vector in the second sequence.

4. Now you can compare the sequences for similarity by iterating over both sequences in tandem. For each corresponding vector in each sequence, check that their directions are equal* and the ratio of their magnitudes are equal* to the scaling factor. If not, the paths are not similar.

*在检查两个double值是否“相等”时，您必须记住，并非每个实数都可以由double精确表示，因此您不能直接比较两个double并期望得到准确的结果。相反，您应该确定适合您情况的误差容限，并确定要比较的值之间的差异是否在该容限范围内。有关该主题的详细处理，请参见float和double比较的最有效方法是什么？。

- Brian Rogers

---

哇，这是一个非常详细的答案。谢谢你。对于路径看起来相同但方向相反的情况，您会建议什么呢？考虑从左下到右上再到左上到右下画出的x与相反方向画出的x。 - jjxtra

首先，按照您描述的方式绘制“X”需要两条路径，而不是一条，对吗？当您抬起笔时，这不会开始一个新路径吗？其次，如果您可以以相反的顺序拥有点，那么这是否与原始路径的反射或（180°旋转）相同？最初，您曾说过您不需要处理旋转。所以，我想我需要更多地了解您真正想做什么（这是手写识别吗？），以及您认为什么是“相似”的，什么不是。图片会很好。我认为我的答案在目前的形式下无法为您工作。 - Brian Rogers

点可以以任何顺序出现在任何路径中，因此不能保证两个路径集合的点完全按照相同顺序排列。当我说旋转不重要时，这就类似于一个侧向箭头不必与上下箭头匹配。 - jjxtra

Answer 2

免责声明：我在图像处理方面是个外行。本回答中的所有内容都是基于我的猜测，未经过文献测试和支持。

我认为我们可以利用对象的“顶点”概念。这里涉及的对象是1D线条，因此顶点应该是线条的端点。

例如，对于图像“X”，假设有两条线，应该有四个顶点，每条线两个。

现在对于图像“X”，实际上可以由四条线组成，每条线都连接在中心。然后，朴素的顶点计数将给出八个顶点，这不是我们想要的。将线与邻域遍历合并以将此计数结果减少到四个的一种方法是。想象一下，如果它们在垂直、水平和对角跳跃范围内，则我们正在形成点之间的边缘。然后我们从一个随机顶点开始，在图上运行DFS，这将给出一组死胡同作为顶点。这将给出四个顶点而不是八个。

在您的问题中，要使两个图像相同，至少它们需要具有相同数量的顶点。当它们被最优地对齐时，顶点之间的距离应该很小，因此我们可以贪心地配对顶点以找到最佳对齐方式。查找图像之间最接近的一对，然后是下一个最接近的一对，直到所有顶点都被配对。然后，图像之间的相似性可以是欧几里得距离对的均方根。

或者，如果顶点数足够小，只需在O(N^3)（我认为是递减平方和...）可能的对中进行优化。这应该会给出更好的结果。

我不会尝试这个，因为我很懒......我的想象力像一只猪一样飞翔。干杯！

- Patrick the Cat