[發明專利]一種移動軌跡數據壓縮方法及裝置

有效

• 申請號: 201611185891.8
• 申請日: 2016-12-20
• 公開（公告）號: CN106788448B
• 公開（公告）日: 2020-04-10
• 發明（設計）人: 鄧澤;王力哲;韓偉;褚軍德;陳小島;陳云亮
• 申請（專利權）人: 中國地質大學（武漢）
• 主分類號: H03M7/30
• 分類號: H03M7/30
• 代理公司: 北京華沛德權律師事務所 11302
• 代理人: 房德權

技術領域

本發明涉及計算機處理領域，尤其涉及一種移動軌跡數據壓縮方法及裝置。

背景技術

20世紀90年代以來，隨著計算機硬件及信息系統和網絡技術的不斷發展和日益成熟，位置服務和車聯網應用的不斷普及,由地理數據、車輛軌跡和應用記錄等所構成的軌跡數據已成為當前用來感知人類社群活動規律、分析地理國情和構建智慧城市的重要戰略性資源。采集的原始軌跡數據的不僅體量大，更新速度快而且信息碎片化，價值密度低。由此已經造成了三個主要的問題是：首先，傳輸大量原始位置數據是昂貴和費時的，其次分析利用這些位置數據需要耗費昂貴的計算資源才能提取有用的信息，第三，原始軌跡數據中包含大量的冗余的數據耗費大量的存儲資源和磁盤存取時間。

因此，需要對原始軌跡數據進行壓縮處理，但是現有軌跡壓縮方法若要獲得滿意的壓縮率就包含巨大的計算量，導致傳統軌跡數據壓縮方法對軌跡數據的壓縮效率不高。

發明內容

鑒于上述問題，本發明實施例通過提供一種移動軌跡數據壓縮方法及裝置，以克服上述問題或者至少部分地解決上述問題。

第一方面，本發明實施例提供了一種移動軌跡數據壓縮方法，包括：

獲得移動軌跡數據流，其中，所述移動軌跡數據流包括M個原始軌跡段，所述M個原始軌跡段分別由連續軌跡點構成，M為正整數；

通過對應的BQS數據結構分別過濾掉所述M個原始軌跡段中不超過設定角度誤差的軌跡點，以獲得M個初壓縮后軌跡段；

將所述M個初壓縮后軌跡段分別在所述GPU平臺上經過構圖后的BFS廣度優先搜索，以獲得所述M個初壓縮后軌跡段分別的最優路徑，其中，所述構圖不超過所述設定角度誤差；

返回由所述M個初壓縮后軌跡段分別的最優路徑合成的壓縮后軌跡數據流。

優選的，所述通過對應的BQS數據結構分別過濾掉所述M個原始軌跡段中不超過設定角度誤差的軌跡點，包括：

將所述M個原始軌跡段的第i個原始軌跡段通過對應的BQS數據結構過濾掉所述第i個原始軌跡段中不超過所述設定角度誤差的軌跡點，以輸出第i個初壓縮后軌跡段，i依次為1至M；

所述將所述M個初壓縮后軌跡段分別在所述GPU平臺上經過構圖后的BFS廣度優先搜索，以獲得所述M個初壓縮后軌跡段分別的最優路徑，包括：

將所述第i個初壓縮后軌跡段傳遞至所述GPU平臺，在所述GPU平臺上經過所述構圖后的BFS獲得所述第i個初壓縮后軌跡段的最優路徑，i依次為1至M。

優選的，所述通過對應的BQS數據結構分別過濾掉所述M個原始軌跡段中不超過設定角度誤差的軌跡點，以獲得M個初壓縮后軌跡段，包括：

讀入所述第i個原始軌跡段；

針對所述第i個原始軌跡段依次構建多個BQS數據結構，其中，各個所述BQS數據結構分別包括上下界<d^lb,d^ub>；

將各個所述BQS數據結構的距離誤差∈_t轉換為方向誤差∈_d：

所述第i個原始軌跡段中滿足各個所述BQS數據結構的d^lb≥∈_d或d^lb≤∈_d≤d^ub的軌跡點確定為不可初壓縮的軌跡點；

各個所述不可初壓縮的軌跡點構成為所述第i個初壓縮后軌跡段。

優選的，所述在所述GPU平臺上經過所述構圖后的BFS獲得所述第i個初壓縮后軌跡段的最優路徑，包括：

針對所述第i個初壓縮后軌跡段構建不超過所述設定角度誤差的圖；

通過所述BFS在所述不超過所述設定角度誤差的圖上進行正序遍歷各個最短路徑；

通過所述BFS逆序處理遍歷到的最短路徑，以獲得所述第i個初壓縮后軌跡段的最優路徑。

優選的，所述針對所述第i個初壓縮后軌跡段構建不超過所述設定角度誤差的圖，包括：

計算得到所述第i個初壓縮后軌跡段上任意子軌跡段分別的可用角度范圍，i依次為1至M：

判斷各個所述可用角度范圍是否為空；

將所述可用角度范圍不為空對應的子軌跡段建立在圖上以形成所述不超過所述設定角度誤差的圖。

第二方面，本發明實施例提供了一種移動軌跡數據壓縮裝置，包括：

采集模塊，用于獲得移動軌跡數據流，其中，所述移動軌跡數據流包括M個原始軌跡段，所述M個原始軌跡段分別由連續軌跡點構成，M為正整數；