[發明專利]軌跡相似度確定方法和裝置

有效

• 申請號: 201910851151.0
• 申請日: 2019-09-06
• 公開（公告）號: CN110555061B
• 公開（公告）日: 2022-04-05
• 發明（設計）人: 楊雙全;劉暢;謝奕
• 申請（專利權）人: 北京百度網訊科技有限公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06F16/29
• 代理公司: 北京市鑄成律師事務所 11313
• 代理人: 王一;武晨燕

1.一種軌跡相似度確定方法，其特征在于，包括：

根據目標對象行為數據中的位置信息和時間信息，在時空坐標系中構建第一行為軌跡和第二行為軌跡；

對于所述第一行為軌跡上任意第一軌跡點以及所述第二行為軌跡上的任意第二軌跡點，在所述第一軌跡點與所述第二軌跡點的時間距離小于等于時間閾值的情況下，確定所述第一軌跡點與所述第二軌跡點之間的編輯距離；

基于各編輯距離，計算所述第二行為軌跡轉換到所述第一行為軌跡的最小編輯距離；

根據最小編輯距離，確定所述第一行為軌跡與所述第二行為軌跡的相似度。

2.根據權利要求1所述的方法，其特征在于，基于第一行為軌跡的各軌跡點，計算第二行為軌跡轉換到第一行為軌跡的最小編輯距離，包括：

在所述第一行為軌跡上確定第一目標軌跡點；

在所述第二行為軌跡上生成第二目標軌跡點，所述第二目標軌跡點與所述第一目標軌跡點的坐標相同；

根據預設編輯距離算法，計算生成所述第二目標軌跡點的第一編輯距離；

利用遞歸求解算法，計算所述第二目標軌跡點之前的第二行為軌跡轉換到所述第一目標軌跡點之前的第一行為軌跡的第二編輯距離；

根據所述第一編輯距離和所述第二編輯距離，計算所述第二行為軌跡轉換到所述第一行為軌跡的最小編輯距離。

3.根據權利要求1所述的方法，其特征在于，基于第一行為軌跡的各軌跡點，計算第二行為軌跡轉換到第一行為軌跡的最小編輯距離，包括：

在所述第一行為軌跡上確定第三目標軌跡點和第四目標軌跡點；

去除所述第二行為軌跡上的冗余軌跡點，所述冗余軌跡點為時間坐標處于所述第三目標軌跡點與所述第四目標軌跡點的時間坐標之間的軌跡點；

根據預設編輯距離算法，計算去除所述冗余軌跡點的第三編輯距離；

利用遞歸求解算法，計算所述冗余軌跡點之前的第二行為軌跡轉換到所述第三目標軌跡點之前的第一行為軌跡的第四編輯距離；

根據所述第三編輯距離和所述第四編輯距離，計算所述第二行為軌跡轉換到所述第一行為軌跡的最小編輯距離。

4.根據權利要求2所述的方法，其特征在于，在所述第二行為軌跡上生成第二目標軌跡點，包括：

將所述第二行為軌跡上的一個軌跡點變更為所述第二目標軌跡點；或，

在所述第二行為軌跡上增加一個所述第二目標軌跡點。

5.根據權利要求4所述的方法，其特征在于，將所述第二行為軌跡上的一個軌跡點變更為所述第二目標軌跡點的預設編輯距離算法為：

其中，L(P₁，P₂)表示變更軌跡點的預設編輯距離，P₁表示所述第二行為軌跡上的一個軌跡點，P₂表示所述第二目標軌跡點，x₁為P₁在X軸的坐標，y₁為P₁在Y軸的坐標，x₂為P₂在X軸的坐標，y₂為P₂在Y軸的坐標。

6.根據權利要求4所述的方法，其特征在于，在所述第二行為軌跡上增加一個所述第二目標軌跡點的預設編輯距離算法為：

其中，AL(P_k)表示增加軌跡點的預設編輯距離，P_k表示增加的所述第二目標軌跡點，P_i表示所述第二行為軌跡上位于所述第二目標軌跡點之前的一個軌跡點，P_j表示所述第二行為軌跡上位于所述第二目標軌跡點之后的一個軌跡點，L(P_i，P_k)表示軌跡點P_i與軌跡點P_k之間的編輯距離，L(P_k，P_j)表示軌跡點P_k與軌跡點P_j之間的編輯距離。