在已知缺失时间间隔之间插入 3D 坐标 [英] Interpolating 3D Coordinates between known missing time intervals
问题描述
数据是空间中的路径.我有 3D 位置数据 (x,y,z) 和记录位置点的时间.
The data is a Path in space. I have 3D location data (x,y,z) and the time the location point was recorded.
x、y 和 z 坐标是穿过 3D 空间的物体的点位置.时间值是记录每个点的时间(从 0 开始).
The x ,y, and z coordinates are the point locations of something traveling through 3D Space. The time values is the time (beginning at 0) that each point was recorded.
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
我最终会错过一些录制活动.(这是已知的并被接受为真的)并且数据流将以不同的时间间隔继续:
I will eventually miss some recording events. (this is known and accepted as true) And the data stream will continue at a different time interval:
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 点.我研究了各种插值技术，但我不完全确定哪种插值方法适合我的问题.
Please note the data was simplified. My goal is to interpolate the missing 3D points at the known missing times. I have looked into various interpolating techniques but I am not entirely sure which interpolation method is suited for my problem.
1) 有人能简洁地解释一下这是什么问题吗?我的数学非常生疏，我不知道如何正确描述它，这导致我研究可能不合适的插值技术.
1) Can someone succinctly explain the kind of problem this is? My math is extremely rusty and I am not sure how to properly describe it, which leads me to investigating interpolation techniques that may not be properly suited.
2) 更新 1 三次插值不应该在这里应用，因为我没有在 3D 空间中使用网格.我正在使用轨迹.我找到了一个 Apache math3 commons 中的三次插值实现，但是我不确定这是否是我需要的.如果你看看它需要的参数，它需要一个 double[][][] fval 矩阵，我不确定.
2) Update 1 Tricubic Interpolation should not apply here since I am not working with a grid in 3D space. I am working with a trajectory. I have found a Tricubic Interpolation implementation in the Apache math3 commons, however I am not sure if this is what I need. If you look at the arguments it takes, it takes a double[][][] fval matrix that I am not sure about.
3) 如果不是最适合 Java，那么插入这些数据的最佳工具是什么?
3) If not best suited for Java, what is the best tool to interpolate this data?
更新 2 - 关于 Spectre 解决方案的问题
在您的编辑中，您提供了以下有关匹配关节点的一阶导数"的提示:
In your edit you provide the following tip regarding "matching first derivations of joint points":
让我们定义我们的 t=<-2,+2> 并像这样对控制点进行采样(它如何影响系数幅度并包括 -1 并不重要,0,1 将简化等式很多):
let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):
p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
现在假设我们想对区间 t=<0,1> 上的所有点进行插值，因此 p2 和 p3 之间的所有点代码>.我们想要连续的分段曲线，所以关节点的一阶导数应该匹配.我们在左侧多了一个控制点，所以第二个推导也可以在那里匹配:
now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:
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) 替换为已知的控制点并形成方程组并从 p0,p1 代数计算 .a0,a1,a2,a3,a4，p2,p3,p4
Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4.
1) 关节点是什么意思?
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 有任何关系吗?它们可以是您选择的任何东西吗?
come from? Do they in any way relate to p(0) = p2 and p(1) = p3 ? Can they be anything you chose ?
可以改写为 p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) 正确? 我不清楚为什么要这样做.甚至为什么它可以做到
It can be re written as p'(0) = 0.5*((p(3)-p(0)) + (p(0)-p(-1)) correct? It is not clear to me why this is being done. Or even why it can be done
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) 的歧义，因为我也不知道等式从何而来.
but I am assuming that clarifying question 2) will alleviate my ambiguity for 2b) because I have no idea where the equation came from either.
接下来的内容很简单，那就是方程组
What follows is pretty straight forward,then it's just systems of equations
推荐答案
由于您的数据很可能只是一些平滑的曲线采样点，我会像这样使用三次插值多项式:
As your data are most likely just some smooth curve sampled points I would use cubic interpolation polynomial like this:
曲线属性使得它通过所有控制点(t={-1,0,+1,+2})并且内部控制点的方向(一阶导数)是平均的展位边的平滑连接(类似于贝塞尔立方).
Curve properties are such that it goes through all control points (t={-1,0,+1,+2}) and the direction (1st derivation) at inner control points is average of booth sides to join smoothly (similar to Bezier cubics).
算法是这样的:
在缺失点之前取2分，在缺失点之后取2分
让我们称它们为 p0,p1,p2,p3 理想情况下，它们应该是时间等距的......并按时间排序.
lets call them p0,p1,p2,p3 they should be ideally time equidistant ones ... and ordered by time.
为每个轴计算 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));
设置参数t=<0,1>为缺失时间对应的值
set parameter t=<0,1> to value corresponding to missing time
所以如果你选择点 p0,p1,p2,p3 和时间 t0,t1,t2,t3 那么缺少的时间 tm对应参数:
so if you chose points p0,p1,p2,p3 with times t0,t1,t2,t3 then the missing time tm corresponds to parameter:
t = (tm-t1)/(t2-t1);
计算缺失点.
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
如果通过推导类似的方程或拟合还不够，您可以使用更高阶的多项式.也看看这个:
You can use polynomials of higher order if this is not enough by deriving similar equations or fitting. Also take a look at this:
[Edit1] 构造自己的多项式
您的评论的答案在 三次和 catmull 样条对图像的影响的[edit2]中 这也在上面的前一个链接中链接.要以类似的方式制作四次插值多项式，您将有 5 个点 (p0,p1,p2,p3,p4) 和方程:
The answer to your comment is in [edit2] of Impact of cubic and catmull splines on image which is also linked in previous link above. To make 4th degree interpolation polynomial in similar manner you will have 5 points (p0,p1,p2,p3,p4) and equations:
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 将简化等式很多):
let define our t=<-2,+2> and sample the control point like this (does not really matter how it will just affect the coefficients magnitude and including -1,0,1 will ease up the equations a lot):
p(-2) = p0
p(-1) = p1
p( 0) = p2
p( 1) = p3
p( 2) = p4
现在假设我们想对区间 t=<0,1> 上的所有点进行插值，因此 p2 和 p3 之间的所有点代码>.我们想要连续的分段曲线，所以关节点的一阶导数应该匹配.我们在左侧多了一个控制点，所以第二个推导也可以在那里匹配:
now let assume we want to interpolate all the points on the interval t=<0,1> so all points between p2 and p3. And we want continuous piecewise curve so first derivations on joint points should match. We got one more control point on the left side so the second derivation can match there too:
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) 替换为已知的控制点并形成方程组并从 p0,p1 代数计算 .提示使用 a0,a1,a2,a3,a4，p2,p3,p4t=0,t=+1 和 t=-1 这样你就会得到它们的线性方程.例如:
Hope I did not make any silly mistake in the second derivation. Now just substitute p(t) with known control points and form system of equations and compute a0,a1,a2,a3,a4 algebraically from p0,p1,p2,p3,p4. Hint use t=0,t=+1 and t=-1 so you will get linear equations for those. For example:
p( 0) = p2 = a0 + a1*0 + a2*0*0 + a3*0*0*0 + a4*0*0*0*0
p2 = a0
正如你所看到的，a0 的计算非常简单，同样可以用于推导:
As you can see a0 is computed really simply the same can be used for derivations:
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.您可以设置关节点导数来满足您的特定需求(不仅仅是左右导数的平均值)，但形成像您这样的连续曲线是最好的(根据我的经验).
Now use t=+1 and t=-1 and compute the a3,a4. You can set the joint point derivations to meet your specific needs (not just average of derivation from left and right) but to form continuous curve like yours is this the best (from my experience).
这篇关于在已知缺失时间间隔之间插入 3D 坐标的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
