比较原始轨迹和两条压缩轨迹的最佳方法是什么 [英] What's the best method to compare original trajectory with two compressed trajectory

问题描述

假设具有GPS轨迹-即:一系列时空坐标，每个坐标是(x，y，t)信息，其中x是经度，y是纬度，t是时间戳.假设每个轨迹由1000(x，y)点标识，则压缩轨迹的轨迹比原始轨迹要少，例如300个点.压缩算法(Douglas-Peucker，Bellman等)决定压缩轨迹中的哪些点以及哪些点将被丢弃.

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.

每种算法都有自己的选择.更好的算法不仅通过空间特征(x，y)来选择点，而且还使用时空特征(x，y，t)来选择点.

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.

我想到了DTW算法来检查轨迹的相似性，但这可能不在乎时间分量.我可以使用哪种算法进行控制?

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?

推荐答案

我已经找到了计算时空误差所需的条件.如论文"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:

同步欧几里得距离(sed)测量之间的距离在相同的时间戳记两点.在图1中，五个时间步长(t1至t5).简化线(可以认为是轨迹的压缩表示)仅由两个组成点(P't1和P't5)；因此，它不包括点P't2，P't3和P't4.为了量化这些遗漏点带来的误差，在相同的时间步长测量距离.由于三点在P't1和P't5之间被删除，该行分为四个相等大小的线段，使用三个点P't2，P't3和P't4为了测量误差.测量总误差作为同步时间所有点之间的距离之和瞬间，如下图所示.(在下面的表达式中，n表示考虑的总点数.)

Synchronized Euclidean distance (sed) measures the distance between two points at identical time stamps. In Figure 1, five time steps (t1 through t5) are shown. The simplified line (which can be thought of as the compressed representation of the trace) is comprised of only two points (P't1 and P't5); thereby, it does not include points P't2, P't3 and P't4. To quantify the error introduced by these missing points, distance is measured at the identical time steps. Since three points were removed between P't1 and P't5, the line is divided into four equal sized line segments using the three points P't2, P't3 and P't4 for the purposes of measuring the error. The total error is measured as the sum of the distance between all points at the synchronized time instants, as shown below. (In the following expression, n represents the total number of points considered.)

这篇关于比较原始轨迹和两条压缩轨迹的最佳方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！