如何实时检测曲线中的"knee/elbow"（最大曲率）

Question

在下面的曲线（蓝线）中，我试图检测应该位于 x = 2.5

附近的“knee/elbow”

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

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

有人可以建议我一种检测 knee/elbow 的方法吗？

Answer 1

这是一个算法：

1) 将范围分为三等分。 A,B,C

2) 对于每个范围 (A,B,C) 计算任意点的最大斜率减去任意点的最小斜率，并将其称为 SlopeDiversity。

3) 无论哪一个第三个（A、B 或 C）具有最大的斜率多样性，取它并从步骤 #1 开始重复整个过程。这就像二等分，但是是三等分。

可能还有一些可行的二分算法，但分成 3 份是有意义的，因为你想扔掉坏的部分并保留最好的部分，这需要每次分成 3 个范围。

另一种 'state that' 或做到这一点的方法是，当您将其中的所有点与简单线性回归模型（该模型的线公式）进行比较时，只选择具有 "largest total error" 的第 3 个仅第三名）。

Answer 2

答案取决于您如何获得这些值。下面的答案假设您在输入时得到了一组这些 XY 数字（就像在您的示例中一样）。

还有你是如何定义曲率的。

对于曲率的几何意义（与轴方向无关），您可以将 B 点的曲率估计为 abs( crossproduct(B-A, C-B) ) / length(C-A)，其中 A 和 C 是两个相邻点。因为平方根（长度需要）可能会非常昂贵，尤其是。在嵌入式上，您可以改用该值的平方。

关于曲率的代数定义（二阶导数，在很大程度上取决于轴的方向），参见这个公式：https://mathformeremortals.wordpress.com/2013/01/12/a-numerical-second-derivative-from-three-points/

更新：对于曲率的几何意义，上面的公式只有在点分布均匀的情况下才可以。对于不同的点密度，最好使用 a precise formula 作为曲率半径。 4*K = 2*abs( crossproduct(B-A, C-B) )。不幸的是，您需要一个平方根（您可以先将所有 3 边的平方相乘，然后从乘积中取一个根）。

Answer 3

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

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

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 表示穿过该点的局部角度。

然后找到任何 "knee"，我们可以查看三个数据点 (x-1)、(x) 和 (x+1) 的所有集合，并考虑那些 x，其中本地 angular 差异大于其邻居的 angular 差异。 x 最大的区别是 "winner"：你找到了你的膝盖。（或者实际上，a 膝盖，因为点数据做出零承诺不会多次上下移动，导致多边形有很多拐点）

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]

我已将差异计算留给您，因为您可能只想要 d1+d2 或 (d1+d2)/2，或者您可能想根据 d1 或 d2（但不是两者）进行切换) 为 0，等等

当然，这里要注意的重要一点是，当我们收集数据点时，我们可以做所有这些事情 "in one go"，因为新点不会影响旧点的位置，所以在某个点 n，我们已经知道到 n-1 的角度，并且我们已经知道到 n-2 的膝盖，所以我们可以在一个线性通道中计算所有这些值。漂亮又高效。

这种方法类似于求数据拟合曲线的导数的根，但是当我们只有数值数据时，有时最正确的方法是使用数据，而不是 "a presumed reconstruction of the original thing you derived the data from"。在这种情况下，您没有知道您的数据源在样本点之间做了什么。也许它表现得很好，也许不是，但是你不知道，所以不要浪费时间使问题复杂化，而是直接使用你知道的属性是非常值得的（并且当然，它们的真实情况：这些是传感器读数，您的传感器绝对可能有噪音甚至有故障）。

Answer 4

我从事 Knee/Elbow 点检测已有一段时间了。绝不，我是专家。尽管如此，我还是在目前已实现的代码上测试了您的示例。

Kneedle -> 3.0
L-method -> 4.0
S-method -> 2.0
Menger Curvature -> 1.0
DFDT -> 3.0
DSDT -> 3.0
R-Method -> NA (R2 = NAN)
DK-method -> 1.0

K-needle 似乎给出了一个很好的近似值，如 DFDT/DSDT 和 S-method。正如您提到的 kneedle 与您的用例无关。

DFDT 代表动态一阶导数阈值。它计算一阶导数并使用阈值算法来检测 knee/elbow 点。 DSDT类似，但使用二阶导数，我的评估表明它们具有相似的性能。

S-method 是 L-method 的扩展。 L-method 将两条直线拟合到您的曲线，两条线之间的截距是 knee/elbow 点。通过循环所有点、拟合线和评估 MSE（均方误差）找到最佳拟合。 S-method 拟合 3 条直线，这提高了准确性，但也需要更多的计算。

我的所有代码都可以在 github 上公开获得。此外，此 article 可以帮助您找到有关该主题的更多信息。它只有四页长，所以应该很容易阅读。您可以使用代码，如果您想讨论任何方法，请随时讨论。

如何实时检测曲线中的"knee/elbow"（最大曲率）

How to detect in real time a "knee/elbow" (maximal curvature) in a curve

algorithm

curve

polynomials