java - 在已知缺失时间间隔之间插入 3D 坐标

Question

数据是空间中的路径。我有 3D 位置数据 (x,y,z) 以及记录位置点的时间。

x、y 和 z 坐标是物体在 3D 空间中移动的点位置。时间值是记录每个点的时间(从 0 开始)。

x     y    z    time(s)
0.1   2.2  3.3  0
2.4   2.4  4.2  0.3
4.5   2.5  1.8  0.6

我最终会错过一些录制 Activity 。 (这是已知的并被接受为正确的)并且数据流将以不同的时间间隔继续:

x     y    z    time(s)
0.1   2.2  3.3  0
2.4   2.4  4.2  0.3
//missing x,y,z data point at time 0.6
//missing x,y,z data point at time 0.9
4.5   2.5  1.8  1.2
...
...

请注意数据已简化。我的目标是在已知的缺失时间插入缺失的 3D 点。我研究了各种插值技术，但我不完全确定哪种插值方法适合我的问题。

1)有人可以简洁地解释一下这是什么问题吗？我的数学非常生疏，我不知道如何正确描述它，这导致我研究可能不合适的插值技术。

2) 更新 1 三三次插值不应适用于此，因为我没有在 3D 空间中使用网格。我正在研究轨迹。我找到了Tricubic Interpolation implementation在 Apache math3 commons 中，但是我不确定这是否是我所需要的。如果你看一下它所采用的参数，它需要一个我不确定的 double[][][] fval 矩阵。

3) 如果不是最适合 Java，那么插入此数据的最佳工具是什么？

更新 2 - 有关 Spectre 解决方案的问题

在您的编辑中，您提供了以下有关“匹配关节点的一阶导数”的提示:

让我们定义我们的t=<-2,+2>并像这样对控制点进行采样(实际上并不重要，它只会影响系数大小，并且包括 -1,0,1 将大大简化方程):

p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3

现在假设我们要对区间 t=<0,1> 上的所有点进行插值所以 p2 之间的所有点和p3 。我们想要连续的分段曲线，因此关节点的一阶导数应该匹配。我们在左侧多了一个控制点，因此二阶导数也可以在那里匹配:

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

希望我在第二次推导中没有犯任何愚蠢的错误。现在只需替换​​ p(t)已知控制点并形成方程组并计算 a0,a1,a2,a3,a4从代数上看 p0,p1,p2,p3,p4 .

1) joint points 是什么意思？ ？

2)去哪里

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)

从哪里来？它们与 p(0) = p2 有任何关系吗？和p(1) = p3 ？它们可以是您选择的任何东西吗？

可以重写为 p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1))正确的？我不清楚为什么要这样做。甚至为什么可以做到

2b)类似的问题

p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

但我假设澄清问题 2) 会减轻我对 2b) 的歧义，因为我也不知道方程来自哪里。

接下来的内容非常简单，那就是方程组

Answer 1

由于您的数据很可能只是一些平滑曲线采样点，我将使用如下三次插值多项式:

• Piecewise linear integer curve interpolation in C#/Unity3D

曲线属性使其穿过所有控制点 ( t={-1,0,+1,+2} )，并且内部控制点处的方向(一阶导数)是展位侧面的平均值以平滑连接(类似于 贝塞尔曲线 三次方) )。

算法是这样的:

1. 在缺失点之前得到 2 点，在缺失点之后得到 2 点

   我们称它们为p0,p1,p2,p3理想情况下，它们应该是时间等距的......并按时间排序。

2. 计算每个轴的 4 个系数

   d1=0.5*(p2.x-p0.x);
   d2=0.5*(p3.x-p1.x);
   ax0=p1.x;
   ax1=d1;
   ax2=(3.0*(p2.x-p1.x))-(2.0*d1)-d2;
   ax3=d1+d2+(2.0*(-p2.x+p1.x));
   
   d1=0.5*(p2.y-p0.y);
   d2=0.5*(p3.y-p1.y);
   ay0=p1.y;
   ay1=d1;
   ay2=(3.0*(p2.y-p1.y))-(2.0*d1)-d2;
   ay3=d1+d2+(2.0*(-p2.y+p1.y));
   
   d1=0.5*(p2.z-p0.z);
   d2=0.5*(p3.z-p1.z);
   az0=p1.z;
   az1=d1;
   az2=(3.0*(p2.z-p1.z))-(2.0*d1)-d2;
   az3=d1+d2+(2.0*(-p2.z+p1.z));
   

3. 设置参数t=<0,1>与缺失时间对应的值

   所以如果你选择点 p0,p1,p2,p3与时俱进t0,t1,t2,t3那么缺失的时间tm对应参数:

   t = (tm-t1)/(t2-t1);
   

4. 计算缺失点。

   x=ax0+ax1*t+ax2*t*t+ax3*t*t*t
   y=ay0+ay1*t+ay2*t*t+ay3*t*t*t
   z=az0+az1*t+az2*t*t+az3*t*t*t
   

如果通过推导类似的方程或拟合还不够，您可以使用更高阶的多项式。另请看一下这个:

• How can i produce multi point linear interpolation?

[Edit1]构造自己的多项式

您评论的答案在Impact of cubic and catmull splines on image的[edit2]中这也在上面的先前链接中链接。要以类似的方式制作 4 次插值多项式，您将有 5 个点 (p0,p1,p2,p3,p4)和方程:

p(t)= a0 + a1*t + a2*t*t + a3*t*t*t + a4*t*t*t*t
p'(t) =    a1 + 2*a2*t + 3*a3*t*t + 4*a4*t*t*t
p''(t) =        2*a2   + 6*a3*t   +12*a4*t*t

让我们定义我们的t=<-2,+2>并像这样对控制点进行采样(实际上并不重要，它只会影响系数大小，并且包括 -1,0,1 将大大简化方程):

p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
p( 2) = p4

现在假设我们要对区间 t=<0,1> 上的所有点进行插值所以 p2 之间的所有点和p3 。我们想要连续的分段曲线，因此关节点的一阶导数应该匹配。我们在左侧多了一个控制点，因此二阶导数也可以在那里匹配:

p'(0) = 0.5*((p3-p2)+(p2-p1)) = 0.5*(p3-p1)
p'(1) = 0.5*((p4-p3)+(p3-p2)) = 0.5*(p4-p2)
p''(0)= 0.5*(((p2-p1)-(p1-p0))+((p4-p3)-(p3-p2)))
      = 0.5*((p2-2*p1+p0)+(p4-2*p3+p2))
      = 0.5*(p0+p4)-p1+p2-p3

希望我在第二次推导中没有犯任何愚蠢的错误。现在只需替换​​ p(t)已知控制点并形成方程组并计算 a0,a1,a2,a3,a4从代数上看 p0,p1,p2,p3,p4 。提示使用t=0,t=+1和t=-1所以你会得到这些的线性方程。例如:

p( 0) = p2 = a0 + a1*0 + a2*0*0 + a3*0*0*0 + a4*0*0*0*0
        p2 = a0

如您所见 a0计算起来非常简单，可以用于推导:

p'(0) = 0.5*(p3-p1)          = a1 + 2*a2*0 + 3*a3*0*0 + 4*a4*0*0*0
p''(0)= 0.5*(p0+p4)-p1+p2-p3 =      2*a2   + 6*a3*0   +12*a4*0*0
-------------------------------------------------------------------
        0.5*(p3-p1)          = a1  
        0.5*(p0+p4)-p1+p2-p3 =      2*a2
-------------------------------------------------------------------
        0.5*(p3-p1)                 = a1  
        0.25*(p0+p4)-0.5*(p1+p2-p3) = a2
-------------------------------------------------------------------

现在使用t=+1和t=-1并计算a3,a4 。您可以设置关节点导数以满足您的特定需求(不仅仅是左右导数的平均值)，但形成像您这样的连续曲线是最好的(根据我的经验)。