比较原始轨迹与两个压缩轨迹的最佳方法是什么
假设有一个GPS轨迹——即：一系列时空坐标，每个坐标都是一个(x,y,t)信息，其中x是经度，y是纬度，t是时间戳。 假设每条轨迹由 1000 个 (x,y) 点标识，则压缩轨迹是比原始点更少的轨迹，例如 300 个点。压缩算法（Douglas-Peucker、Bellman 等）决定哪些点将出现在压缩轨迹中以及哪些点将被丢弃。
每个算法都会做出自己的选择。更好的算法不仅通过空间特征（x，y）而且使用时空特征（x，y，t）来选择点。
现在我需要一种方法来将两个压缩轨迹与原始轨迹进行比较，以了解哪种压缩算法可以更好地减少时空（时间分量非常重要）轨迹。
我想过使用 DTW 算法来检查轨迹相似性，但这可能不关心时间分量。我可以使用什么算法来进行此控制？
Suppose to have a GPS trajectory - i.e.: a series of spatio-temporal coords, every coord is a (x,y,t) information, where x is longitude, y is latitude and t is the time stamp.
Suppose each trajectory identified by 1000 (x,y) points, a compressed trajectory is trajectory with fewer points than the original, for instance 300 points. A compression algorithm (Douglas-Peucker, Bellman, etc) decide what points will be in compressed trajectory and what point will be discarded.
Each algorithm make his own choice. Better algorithms choice the points not only by spatial characteristics (x, y) but using spatio-temporal characteristics (x,y,t).
Now I need a way to compare two compressed trajectories against the original to understand what compression algorithm better reduce a spatio-temporal (temporal component is really important) trajectory.
I've thinked of DTW algorithm to check trajectory similarity, but this probably don't care about temporal component. What algorithm can I use to make this control?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
什么是最好的压缩算法在很大程度上取决于您想要用它实现的目标，并且取决于其他外部变量。通常，我们将识别并删除峰值，然后删除冗余数据。例如;
已知的最小和最大速度、加速度和调整能力将让您消除尖峰。如果我们查看一对点之间的连接距离除以时间，其中
速度 = sqrt((xb - xa)^2 + (yb - ya))/(tb-ta)
我们可以消除距离不能的点t 在给定速度限制的情况下在经过的时间内行驶。我们可以对加速度约束做同样的事情，并改变给定速度的方向约束。这些约束会改变 GPS 接收器是否是静态的、手持式的、在汽车中、在飞机中等...
我们可以使用查看三个点的移动窗口来删除冗余点，其中如果插值 (x,y,t)中间点可以与观测点进行比较，如果观测点位于插值点的指定距离+时间容差范围内，则删除观测点。我们还可以对数据进行曲线拟合并考虑到曲线的距离，而不是使用移动的 3 点窗口。
基于给定的约束，压缩还可以具有不同的目标，例如通过去除冗余观测值和尖峰来简单地减小数据大小，或者也平滑数据。
对于前者，在根据定义的约束检查尖峰后，我们只需检查每个点到连接压缩点的折线的 3d 距离。这是通过找到已删除的点之前和之后的一对点、根据观测时间在连接这些点的线上插值位置、并将插值位置与观测位置进行比较来实现的。当我们允许距离容差增加时，移除的点数将会增加。
对于后者，我们还必须考虑平滑结果对数据建模的效果、约束施加的权重以及设计形状/曲线参数。
希望这有一定道理。
What is the best compression algorithm depends to a large extent on what you are trying to achieve with it, and is dependent on other external variables. Typically, were going to identify and remove spikes, and then remove redundant data. For example;
Known minimum and maximum velocity, acceleration, and ability to tuen will let you remove spikes. If we look at the join distance between a pair of points divided by the time where
velocity = sqrt((xb - xa)^2 + (yb - ya))/(tb-ta)
we can eliminate points where the distance couldn't be travelled in the elapsed time given the speed constraint. We can do the same with acceleration constraints, and change in direction constraints for a given velocity. These constraints change whether the GPS receiver is static, hand held, in a car, in an aeroplane etc...
We can remove redundant points using a moving window looking at three points, where if the an interpolated (x,y,t) for middle point can be compared with an observed point, and the observed point removed if it lies within a specified distance + time tolerance of the interpolated point. We can also curve fit the data and consider the distance to the curve rather than using a moving 3 point window.
The compression may also have differing goals based on the constraints given, e.g. to simply reduce the data size by removing redundant observations and spikes, or to smooth the data as well.
For the former, after checking for spikes based on defined constraints, we simply check the 3d distance of each point to the polyline connecting the compressed points. This is achieved by finding the pair of points before and after the point that has been removed, interpolating a position on the line connecting those points based on the observed time, and comparing the interpolated position with the observed position. The amount of points removed will increase as we allow this distance tolerance to increase.
For the latter we also have to consider how well the smoothed result models the data, the weights imposed by the constraints, and the design shape / curve parameters.
Hope this makes some sense.
也许您可以使用一段时间内轨迹之间的均方距离。
也许，简单地查看时间 1s,2s,... 的距离就足够了，但您也可以在时间戳积分之间做得更精确， (x1(t)-x2(t))^2 + (y1(t )-y2(t))^2。请注意，在 2 个时间戳之间，两条轨迹都是直线。
Maybe you could use mean square distance between trajectories over time.
Probably, simply looking at distance at time 1s,2s,... will be enough, but you can also do it more precise between time stamps integrating, (x1(t)-x2(t))^2 + (y1(t)-y2(t))^2. Note that between 2 time stamps both trajectories will be straight line.
我找到了计算时空误差所需的内容。
正如论文《GPS 轨迹数据的压缩与挖掘》中所写：
新技术和应用”，作者：Lawson、Ravi 和 Hwang：
I've found what I need to compute spatio-temporal error.
As written in paper "Compression and Mining of GPS Trace Data:
New Techniques and Applications" by Lawson, Ravi & Hwang: