如何实时检测曲线中的"膝盖/肘部"(最大曲率)

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算法和图形曲率的正式定义(带符号曲率).我对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是“胜利者”：你找到了你的膝盖。（或者实际上是膝盖，因为点数据使得零承诺不会多次上下移动，从而产生具有大量拐点的多边形）

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，因此我们可以在一次线性传递中计算所有这些值。又好又高效。

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