如何计算两个点序列之间的"差异"？

Question

我有两个长度为n和m的序列.每个都是形式(x,y)的一系列点,并表示图像中的曲线.我需要找到不同(或类似)这些序列给出的事实

1. 一个序列可能比另一个序列长(即,一个序列可以是另一个序列的一半或四分之一,但如果它们跟踪大致相同的曲线,则它们是相同的)

2. 这些序列可能是相反的方向(即序列1从左到右,而序列2从右到左)

   我研究了Levenshtein之类的一些差异估计以及蛋白质折叠的结构相似性匹配中的编辑距离,但它们似乎都没有.我可以编写自己的暴力方法,但我想知道是否有更好的方法.

谢谢.

Answer 1

沿着这些思路的方法可能有效：

对于两个序列：

通过序列拟合一条曲线。确保从 [0,1] 到该曲线上的点具有连续的一对一函数。也就是说，对于 0 到 1 之间的每个（实数）数字，此函数返回属于它的曲线上的一个点。通过追踪从 0 到 1 的所有数字的函数，您可以得到整条曲线。

拟合曲线的一种方法是在每对连续点之间画一条直线（这不是一条很好的曲线，因为它有急弯，但它可能适合您的目的）。在这种情况下，可以通过计算所有线段的总长度（毕达哥拉斯）来获得该函数。曲线上对应于数字 Y（介于 0 和 1 之间）的点对应于曲线上距序列上第一个点距离为 Y *（所有线段的总长度）的点，通过在线段（！！）。

现在，在我们获得第一个序列的函数 F(double) 和第二个序列的函数 G(double) 后，我们可以计算相似度如下：

double epsilon = 0.01;
double curveDistanceSquared = 0.0;
for(double d=0.0;d<1.0;d=d+epsilon)
{
   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(d); 
   //alternatively, use G(1.0-d) to check whether the second sequence is reversed       
   double distanceOfPoints = pointOnCurve1.EuclideanDistance(pointOnCurve2);
   curveDistanceSquared = curveDistanceSquared + distanceOfPoints * distanceOfPoints;
}
similarity = 1.0/ curveDistanceSquared;

可能的改进：

-找到一种改进的方法来拟合曲线。请注意，您仍然需要跟踪曲线的函数才能使上述方法发挥作用。

-计算距离时，考虑重新参数化函数 G 以使距离最小化。（这意味着您有一个递增函数 R，使得 R(0) = 0 且 R(1)=1，但这在其他方面是通用的。在计算您使用的距离时

   Point pointOnCurve1 = F(d);    
   Point pointOnCurve2 = G(R(d)); 

随后，您尝试以最小化距离的方式选择 R。（要看看会发生什么，请注意 G(R(d)) 也跟踪曲线））。