坐标轨迹计算_UMS——一种轨迹相似度的计算方法

在参与的项目中存在轨迹相似度计算的需求，在综合考虑后决定采用文章《Unveiling movement uncertainty for robust trajectory similarity analysis》中的UMS（Uncertain Movement Similarity）算法作为基准进行相似度计算。详细说明UMS的具体运算过程如下：

一、计算相似度Alikeness：

1. AUB距离（Approximate Upper Bound Distant）：

其中

是平面上的两个点，

是它们的平面坐标，可以证明：

代表两点之间的曼哈顿距离与欧几里得距离

2. 构造Narrowed Movement Ellipse:

给定点

，将它们视作椭圆 e 的焦点，

也记为

，

连线的中点记为

，

这3点被称为椭圆 e 的参考点。椭圆 e 的焦距

，长轴

，短轴

。

3. Point Matching：

我们通过观测所得的轨迹是由一系列采样点组成的，在每条轨迹中相邻两个采样点之间会形成一个具有特定参数的Narrowed Movement Ellipse（下文中简称‘椭圆’）。其中一条轨迹R中共有r个采样点，则能够形成r-1个这样的椭圆；这些椭圆所组成的整体即被称为E(R)，且每个椭圆及其对应的时间序列编号是严格一致的。

给定一个轨迹点

和 一个椭圆轨迹 E(S)，如果 r 在任意一个椭圆

中，则称 r 和 E(S) 匹配，m匹配方程如下：

4. 计算相似度Alikeness：

其中

表示轨迹 R 中采样点的e个数。

二、计算共享度Shareness：

1. 参考点归一化距离（Reference Point Normalized Distance）：

给定一个轨迹点

和 一个椭圆轨迹 E(S)，参考点归一化距离

：

其中

如果 r 不在 e' 中，则

2. Reference Point-Ellipse Sharing Score：

给定一个轨迹点

用于 椭圆轨迹的一种标记方法中的一种椭圆轨迹E(S)，r 用于其参考点-椭圆共享评分（Reference Point-Ellipse Sharing Score）的计算公式如下

其中，在轨迹 S 上确定与 r 匹配的所有那些点之后，在这些点中找到与 r 欧氏几何距离最小的那个点，则该点对应的 e' 即为所求的距离值。

。

3.计算共享度（Shareness）：

两条轨迹 R 和 S 的共享度计算公式如下：

三、计算连续度Continuity：

1. 匹配队列：

给定一个轨迹点

和 一个椭圆轨迹 E(S)，定义一个函数

该函数生成一个匹配序列（命名为匹配队列），其元素对应于与r匹配的所有e’编号，并按E(S)中e’出现的顺序排列。

2. 第一匹配位置（First Matching Position）：

给定一个轨迹点

和 一个椭圆轨迹 E(S)，

的第一匹配位置

根据以下条件计算：

比如

，

；

，

。

3. 计算连续度（Continuity）：

给定长度为 n 的轨迹 R 和长度为 m 的轨迹 S ，记 ：

连续度的计算公式如下：

其中

四、UMS 相似度：

给定两条轨迹 R 和 S ，它们之间的相似度由 UMS(R,S) 计算：

UMS 非负、对称、自反。