algorithm - 如何实时检测曲线中的 "knee/elbow"(最大曲率)

Question

在下面的曲线(蓝线)中，我试图检测应该位于 x = 2.5 附近的“膝盖/肘部”

这是我正在使用的一组值:

x = {-10, -9, -8, -7, -6, -5, -4, -3, -2 , -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

y = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 107, 122, 145, 176, 215, 262, 317, 380, 451, 530, 617}

我试过 Kneedle algorithm和 formal definition of the curvature of a graph (有符号曲率)。我在 Kneedle 算法中遇到的问题是，在实时应用程序(嵌入式系统)中，我不知道哪个是 y 轴的最大值，所以我无法正确归一化这些点，也无法找到一个斜率值适用于所有情况。当使用图形曲率的正式定义时，我尝试用 5 阶多项式(绿线)拟合曲线，然后获取导数的值来计算曲率。然而，由于多项式的存在，该点周围存在曲率，因此该方法找到了 x = -2 周围的曲率。

有人可以建议我一种检测膝盖/肘部的方法吗？

Answer 1

这不是连续曲线，也不是连续曲线的近似值，因此我们不必在这里浪费时间:您有一个简单的多边形。相当于“曲率半径”的多边形是入射角和折射角的差值:差值越小，“曲率”半径就越大。

如果您正确地对数据进行采样，我们可以计算每个数据点的角度差异:

for (i=1, i<p.length -1):
  vector1 = p[i] - p[i-1] // assuming your language of choice has points as primitives
  vector2 = p[1+1] - p[i] // if not, you'll have to extract x/y separately.
  p[i].angle = findAngle(vector1,vector2)

findAngle 函数应该很容易实现，有一百万个教程教你如何用你最喜欢的语言实现它(它是许多语言的基本算法，甚至是某些语言的内置) ).就是这样，我们已将 2D 数据转换为具有 (x,y,z) 坐标的 3D 数据，其中 z 表示穿过该点的局部角度。

为了找到任何“膝盖”，我们可以查看所有三个数据点集 (x-1)、(x) 和 (x+1)，并考虑那些 x局部角度差大于其邻居的角度差。差异最大的 x 是“赢家”:您找到了膝盖。 (或者实际上， 膝盖，因为点数据做出零 promise 不会上下多次，导致多边形有很多拐点)

knee = undefined
max_diff = 0;
for (i=1, i<p.length -1):
  a = p[i].angle

  a1 = p[i-1].angle
  d1 = a1-a

  a3 = p[i+1].angle
  d2 = a3-a

  diff = ... // there's a few ways to compute this
  p[i].diff = diff // always useful if we need to do more work later

  if (diff > max_diff):
    max_diff = diff
    knee = p[i]

我已将 diff 计算留给您，因为您可能只想要 d1+d2 或 (d1+d2)/2，或者您可能想根据 d1 或 d2(但不是两者)是0等

当然，这里要注意的重要一点是，当我们收集数据点时，我们可以“一次性”完成所有这些事情，因为新点不会影响旧点的位置，所以在某些时候n，我们已经知道了 n-1 的角度，并且我们已经知道了 n-2 的膝盖，所以我们可以计算所有这些值在一个单一的线性传递。漂亮而高效。

这种方法类似于寻找数据拟合曲线的导数的根，但是当我们只有数值数据时，有时最正确的方法是使用该数据，而不是“你从中导出数据的原始事物的假定重建”。在这种情况下，您不知道您的数据源在样本点之间做了什么。也许它表现得很好，也许不是，但是你不知道，所以不要把周期浪​​费在使问题复杂化上，而是直接使用你知道是真的属性(当然， 它们的真实用途:这些是传感器读数，您的传感器绝对可能有噪音甚至有故障)。