[發明專利]基于歐式距離和相對方向的不確定移動對象軌跡分組方法

在審

• 申請號: 202011590233.3
• 申請日: 2020-12-29
• 公開（公告）號: CN112579923A
• 公開（公告）日: 2021-03-30
• 發明（設計）人: 李博涵;張夢茜;戴天倫;王高旭;秦小麟
• 申請（專利權）人: 南京航空航天大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06K9/62
• 代理公司: 南京業騰知識產權代理事務所(特殊普通合伙) 32321
• 代理人: 繆友益

1.一種基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，包括如下步驟：

(1)通過移動對象軌跡相似度算法將歷史一段時間內具有相似運動軌跡的移動對象劃分為一個群組；

(2)將同一個分組的移動對象放入索引結構中；

(3)當移動對象的空間位置發生變化時，索引結構借助哈希表實現自底向上的查詢；

(4)當移動對象發出位置更新請求時，將新的記錄信息插入到索引結構中，并將過時的位置信息刪除；

(5)對索引結構的數據進行周期性更新。

2.根據權利要求1所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(1)中將具有相似運動軌跡的移動對象劃分為一個群組的具體方法為：

(1-1)初始化頂點數組V和鄰接矩陣E，并在移動對象數組M中，計算任意兩個移動對象之間的空間軌跡相似度關系，將結果記錄在V和E中構成一個無向圖；

(1-2)找到劃分群組的移動對象，給移動對象初始化一個分組g，通過廣度優先遍歷移動對象中所有相依可達或直接可達的對象，將這些對象加入g中，最后返回分組集合G。

3.根據權利要求2所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(1-1)中，兩個移動對象之間的空間軌跡相似度關系采用歐式距離公式，相對方向公式和速率比公式。

4.根據權利要求2所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(1-2)中，直接可達為最小空間軌跡相似度是節點直接可達的判斷閾值，為常數；當兩個移動對象的空間軌跡相似度大于最小空間軌跡相似度時，認為在t時刻兩個移動對象直接可達；反之則兩個移動對象非直接可達。

5.根據權利要求4所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(1-2)中，相依可達是對于任意兩個移動對象，存在另外一個移動對象，使得兩個移動對象分別與這個移動對象直接可達，則稱這兩個節點相依可達，反之則兩個移動對象非相依可達。

6.根據權利要求2所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(1-2)中，分組g為將具有相似運動軌跡的移動對象劃分為一個群組。

7.根據權利要求1所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(4)中移動對象分組更新的具體方法為：

(4-1)根據移動對象的群組編號代入哈希函數得到哈希表中存放該群組的地址；

(4-2)判斷更新后的位置是否超過所在葉節點的最小外包矩陣范圍之內，若未超出范圍，則直接更新葉節點，否則更新過程等價于在索引結構中刪除和插入新記錄；

(4-3)在空間層數據更新后同步將移動對象所在群組的地址寫回哈希表中。

8.根據權利要求1所述的基于歐式距離和相對方向的不確定移動對象軌跡分組方法，其特征在于，步驟(5)中對索引結構的數據進行周期性更新的具體方法為：

(5-1)首先獲取系統當前的時間t_now，將索引結構中每一個分組中記錄的下一次更新時間與t_now進行比較；

(5-2)如果檢測到某分組需要更新，則將該組中所有對象存放進集合M，調用移動對象軌跡相似度算法重新對移動對象進行分組；

(5-3)比較新的分組G’和原先的分組G，如果發生改變則將新的分組G’添加到索引結構中，最后更新下一次更新的時間。