如何比较两条曲线(点数组)

Question

我有2个点(x,y)阵列,我可以绘制2条曲线.

任何人都有想法如何计算这些曲线是如何相似的？

Answer 1

您始终可以计算这两条曲线之间的区域.(如果端点匹配,这会更容易一些.)如果面积很小,曲线是相似的,如果面积不小,则曲线不相似.

请注意,我没有定义'小'.那是故意的.然后,你没有定义'相似'.

编辑
有时区域不是最佳指标.例如,考虑函数f(x)= 0和f(x)= 1e6*sin(x).如果x的范围是2*pi的某个整数倍,则这些曲线之间的面积为零.在正负一百万之间振荡的函数不是f(x)= 0的良好近似值.

需要更好的指标.这是一对夫妇.注意:我在这里假设两组中的x值相同; 唯一不同的是y值.

1. 平方和.对于每个x值,计算delta_y _i = y _1,i -y _2,i并累积delta_y _i ².该度量是最小二乘优化的基础,其目标是最小化误差平方和.这是一种广泛使用的方法,因为它通常很容易实现.

2. 最大偏差.找到abs_delta_y _i = | y _1,i - y _2,i | 最大化| y _1,i - y _2,i | 对于所有x值.该度量标准是数学库中许多函数实现的基础,其目标是最小化最大错误.这些数学库实现是真实函数的近似值.作为这种近似的消费者,我通常更关心近似对我的应用程序要做的最糟糕的事情,而不是关心该近似将如何平均表现.

Answer 2

您可能需要考虑使用动态时间扭曲(DTW) 或Frechet distance。

动态时间扭曲

动态时间扭曲总结了整个曲线的差异。它可以处理两个不同大小的数组。这是维基百科关于代码外观的片段。此解决方案使用二维数组。成本将是两点之间的距离。数组 DTW[n, m] 的最终值包含累积距离。

int DTWDistance(s: array [1..n], t: array [1..m]) {
    DTW := array [0..n, 0..m]

    for i := 1 to n
        DTW[i, 0] := infinity
    for i := 1 to m
        DTW[0, i] := infinity
    DTW[0, 0] := 0

    for i := 1 to n
        for j := 1 to m
            cost:= d(s[i], t[j])
            DTW[i, j] := cost + minimum(DTW[i-1, j  ],    // insertion
                                        DTW[i  , j-1],    // deletion
                                        DTW[i-1, j-1])    // match

    return DTW[n, m]
}

DTW 类似于 Jacopson 的回答。

Frechet距离

Frechet 距离计算曲线分离的最远距离。这意味着曲线上的所有其他点都比这个距离更近。这种方法通常用狗和主人表示，如下所示： Frechet 距离示例。

根据您的数组，您可以比较点的距离并使用最大值。