比较两条路径的相似性

Question

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

路径特征：

路径集是一条或多条线，每条线有两个或多个点。线路不必连接。
路径集可能会重叠（即 X）。
路径集可能包含不同数量的顶点（即一条路径可能看起来与另一条路径相似，但其中包含更多点）。
不能保证两个路径集的点都是有序的。

应考虑比例，即小 X 应与大 X 匹配。对于任何路径都不需要考虑平移，因为任何路径的最底部点的 y 值为 0，最左侧任何路径的点都将具有 0 的 x。

是否有最佳实践或众所周知的算法（我在 Google 搜索中发现的很少）来比较这些类型的路径集的相似性？

Answer 1

从算法上讲，我想我会尝试这样的事情：

对于每条路径，将包含路径的连续点对转换为向量列表，其中向量定义为大小（长度）和方向（相对角度）的对到 X 轴）。您可以像这样计算这些值 (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);
```
接下来，"normalize" 每个矢量序列通过组合具有相同*方向的连续个矢量。换句话说，用具有相同方向和它们的大小之和的新向量替换它们。这将处理路径上任何地方在同一条线上有两个以上点的情况。在这一步之后，每个序列中应该有相同数量的向量。（如果不是，则路径不相似。）
找出比例因子。取第一个序列中第一个向量的大小除以第二个序列中第一个向量的大小。
现在您可以通过串联迭代两个序列来比较序列的相似性。对于每个序列中的每个对应向量，检查它们的方向是否相等*并且它们的大小之比是否等于*比例因子。如果不是，则路径不相似。

*检查两个double值是否为"equal"时，必须记住不是每个实数都可以用double准确表示，因此不能直接比较两个double并期望得到准确的结果。相反，您应该决定适合您的情况的误差容限，并确定您正在比较的值之间的差异是否在该容差范围内。有关主题的广泛处理，请参阅 What is the most effective way for float and double comparison?。

Answer 2

免责声明：我是图像处理的门外汉。本回答所有内容均为本人猜想，未经文献检验和支持。

我想我们可以利用对象的概念vertices。这里关注的对象是一维直线，所以顶点应该是直线的端点。

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

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

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

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

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

比较两条路径的相似性

Compare Two Paths for Similarity

algorithm

vector-graphics