一種保持移動特徵的車輛軌跡線數據壓縮方法與流程
2023-10-09 00:06:34 1
本發明屬於地理信息技術領域，涉及一種車輛軌跡線數據的壓縮方法，尤其涉及一種保持移動特徵的車輛軌跡線數據壓縮方法。
背景技術：
車輛軌跡線通常由一系列按時間序列組織的位置坐標組成，用以描述車輛在一定地理空間範圍及時間周期內的時空運動狀態。隨著以全球衛星定位系統(GPS)、我國的北鬥導航系統等為代表的定位導航技術的不斷發展完善，以及車載/人載位置感知設備的普及，各種類型的車輛軌跡監測數據成為當前眾源大數據的重要組成部分。這些軌跡監測數據對於城市群體\個體行為模式分析、交通信息實時監測表達、以及地理資料庫更新等具有重要意義。然而，具備空間/時間高解析度特點的車輛軌跡數據通常規模十分巨大。例如，車載GPS接收設備每10秒記錄一次車輛當前的位置信息，一個中等規模城市的計程車單個工作日產生的軌跡線數據量將達到GB級別。一方面，這對存儲設備空間、網絡傳輸帶寬以及後期分析的計算資源造成巨大壓力；另一方面，軌跡數據本身包含大量冗餘信息，浪費存儲計算資源的同時也對分析處理及可視化表達造成負面幹擾。解決上述問題的途徑之一是研究高效的車輛軌跡線數據壓縮方法，即在滿足一定幾何精度條件下刪除冗餘甚至信息量較小的軌跡點，從而壓縮軌跡線數據規模。
目前，實施軌跡線壓縮主要採用來自傳統面向快照式靜態地理數據的線目標壓縮方法。它們的基本思想是從壓縮精度控制出發，依據幾何上的距離、角度、面積等指標參量評估線目標上每個點的重要性，保留重要特徵點(如端點、局部極值點、拐點等)的同時刪除其它次要的點。以應用中使用頻率最高的Douglas-Peucker算法為例，通過相對當前基準線(首尾點連線)的最大偏移距離對原始線目標進行遞歸分段，當某一分段部分對應的最大偏移距離小於設定的幾何化簡精度ε，則將該分段部分擬合為對應的基準線。這類方法能夠較好地保持原始線目標的空間形態結構，但是缺乏對時間維信息的考慮，應用到車輛時空軌跡線壓縮中容易丟失速度、加速度、方向變化等移動特徵。
技術實現要素：
針對上述存在的應用問題，本發明設計了一種新的保持移動特徵的車輛軌跡線數據壓縮方法。本發明的核心思想是依據速度、方向等移動特徵相似性原則對原始軌跡線進行層次化剖分，使得幾何精度控制下的軌跡點取捨決策儘量發生在移動模式均一的軌跡線片段內，從而緩解單純考慮幾何特徵的壓縮方法對原始軌跡線蘊含的移動特徵的破壞。
本發明所採用的技術方案是：一種保持移動特徵的車輛軌跡線數據壓縮方法，其特徵在於，包括以下步驟：
步驟1：按軌跡點產生的時間次序將原始軌跡線T組織為T＝{p1,p2,…,pn}，每個軌跡點pi表示為三元組信息，xi和yi為軌跡點pi的空間位置坐標，ti表示pi產生的時間信息，n是包含的軌跡點數量，1≤i≤n；
步驟2：依次提取相鄰兩個軌跡點構成的軌跡直線段，組織為軌跡直線段集合E＝{e1,e2,…,en-1}，計算每一條軌跡直線段ej對應區域內車輛的移動速度vj和移動方向θj，1≤j≤n-1；
步驟3：在拓撲連接關係約束下，基於速度、方向特徵相似性原則對集合E中的軌跡直線段進行層次化聚類，並將聚類結果組織為層次二叉樹結構；
步驟4：在壓縮的幾何精度閾值ε控制下，通過由上到下遍歷層次二叉樹結構的方式對原始軌跡線T實施分區處理，使得同一區域內軌跡線段的中間點距首尾基準線最大偏移距離小於ε；
步驟5：提取各分區內軌跡線片段的首尾點，按時間次序連接組織為壓縮後的軌跡線T』。
本發明通過針對軌跡直線段的層次化聚類手段，將軌跡線隱含的速度、方向變化信息納入到對局部軌跡點取捨決策中，使得移動特徵變化上具有重要意義的軌跡點由於處在分區臨界點而得以保留，從而使壓縮結果達到更好地保持原始軌跡線移動特徵這一目的。
附圖說明
圖1是本發明實施例的流程圖；
圖2是本發明實施例的車輛軌跡線初始化組織示意圖；
圖3是本發明實施例的車輛軌跡線直線段組織示意圖；
圖4是本發明實施例的軌跡直線段範圍內車輛移動方向定義示意圖；
圖5是本發明實施例的軌跡線直線段層次化聚類方法示意圖；
圖6是本發明實施例的利用二叉樹表達軌跡直線段層次化聚類結果的示意圖；
圖7是本發明實施例的軌跡線分區結果示意圖；
圖8是本發明實施例的軌跡線壓縮結果生成示意圖；
具體實施方式
為了便於本領域普通技術人員理解和實施本發明，下面結合附圖及實施例對本發明作進一步的詳細描述，應當理解，此處所描述的實施示例僅用於說明和解釋本發明，並不用於限定本發明。
請見圖1，本發明提供的一種保持移動特徵的車輛軌跡線數據壓縮方法，包括以下步驟：
步驟1：按照車輛GPS軌跡線數據具體的文件格式讀取數據後，進行數據的初始化組織。
如圖2所示的一條原始軌跡線T，該軌跡線按軌跡點產生的時間次序組織為T＝{p1,p2,…,p11}，一共包含11個軌跡點，每個軌跡點pi表示為三元組信息,xi和yi為軌跡點pi的空間位置坐標，ti表示pi產生的時間信息，1≤i≤11；
步驟2：依次提取相鄰兩個軌跡點構成的軌跡直線段，組織為軌跡直線段集合E＝{e1,e2,…,en-1}，計算每一條軌跡直線段ej對應區域內車輛的移動速度vj和移動方向θj，1≤j≤n-1；
圖3是在圖2所示的軌跡線基礎上進一步提取軌跡直線段，共得到10條軌跡直線段，組織為集合E＝{e1,e2,…,e10}。
車輛運動是一種連續的狀態，而軌跡線是對車輛運動位置狀態的離散化描述模型，相鄰軌跡點的中間狀態無法獲得精確的描述。因此，本發明忽略同一軌跡直線段內車輛的運動狀態的變化，即認為同一軌跡直線段內車輛的運行速度及方向相同。基於這一前提條件，分別定義由相鄰軌跡點pi，pi+1組成直線段ei範圍內車輛的運動速度vi和移動方向θi如下：
(1)移動速度vi：定義為相鄰軌跡點pi，pi+1間的歐式距離與兩個軌跡點定位時間差的商。其中，d(pi,pi+1)表示軌跡點pi和pi+1間的歐式距離，ti和ti+1則分別是軌跡點pi和pi+1的定位時間。
(2)移動方向θi：定義為由正向X軸沿逆時針方向至有向線段形成的夾角(如圖4所示)，其中0≤θi＜2π。
步驟3：提取軌跡直線段並計算相關速度、方向信息後，下一步在在拓撲連接關係約束下依據速度、方向相似性原則對集合E中的軌跡直線段進行層次化聚類，並將聚類結果組織為層次二叉樹結構。
結合圖5，實施例具體的實施過程說明如下：
(1)首先，將每條軌跡直線段映射為一個聚類單元。如圖5a所示實例，該軌跡線共包含10條軌跡直線段，每條直線段獨立構成一個聚類單元，表示為G1＝{e1}、G2＝{e2}、…、G10＝{e10}。
(2)在相鄰聚類單元間定義連接邊，並計算所有連接邊的長度。連接邊長度表示相鄰兩個聚類單元間移動特徵(包括速度、方向)的差異性，如對於相鄰的兩個聚類單元Gi和Gj，連接邊長度L(Gi,Gj)定義為：
其中，和分別表示Gi包含的軌跡直線段的平均速度值和平均方向值，和分別表示Gj包含的軌跡直線段的平均速度值和平均方向值，vmax和vmin則分別表示集合E包含的軌跡直線段的最大速度值和最小速度值，m1和m2分別表示速度差異和方向差異在連接邊長度計算中的權值。m1和m2的具體取值需要考慮軌跡線自身特點和應用需求。例如對於沿城區道路行駛的車輛軌跡數據，車速特徵相對方向特徵變化更為頻繁，m1取值應適當高於m2取值，如m1和m2分別取0.6和0.4。對於圖5a所示實例，按上述方法首先計算相鄰聚類單元間的連接邊長度，包括L(G1,G2)、L(G2,G3)、L(G3,G4)、L(G4,G5)、L(G5,G6)、L(G6,G7)、L(G7,G8)、L(G8,G9)、L(G9,G10)。
(3)取當前長度值最小的連接邊，將相連接的兩個聚類單元合併為一個新的聚類單元，同時按式2計算新的聚類單元兩側的連接邊長度。如圖5b中，連接邊長度L(G9,G10)最小，因此將聚類單元G9＝{e9}和G10＝{e10}組成更大的聚類單元G11＝{e9,e10}；同時將原來G8和G9之間的連接邊更新為G8和G11間的連接邊，按照式2重新計算連接邊長度L(G8,G11)，更新後的連接邊長度依次是L(G1,G2)、L(G2,G3)、L(G3,G4)、L(G4,G5)、L(G5,G6)、L(G6,G7)、L(G7,G8)、L(G8,G11)。
(4)重複步驟3.3直至集合E中所有的軌跡直線段單元聚合為一個聚類單元Gf，即Gf＝{e1,e2,…,en-1}。例如圖5c是在圖5b表示的結果基礎上進一步將連接邊長度最小的兩個聚類單元G4＝{e54}和G5＝{e5}組成更大的聚類單元G12＝{e4,e5}，重新計算G12兩側的連接邊長度，更新後的連接邊長度依次是L(G1,G2)、L(G2,G3)、L(G3,G12)、L(G12,G6)、L(G6,G7)、L(G7,G8)、L(G8,G11)；重複上述過程，直至得到最高級別的聚類單元G19＝{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}。圖5d通過不同灰度的緩衝區記錄了整個層次化聚類的過程及中間結果。
(5)將整個層次化聚類結果組織為層次二叉樹結構，樹的根結點對應最大的聚類單元(包含所有的軌跡直線段)，葉子節點對應單條軌跡直線段構成的聚類單元，中間節點則對應由多條軌跡直線段構成的不同層次的聚類單元。圖6表示了圖5中層次化聚類結果的二叉樹結構，二叉樹的根結點對應於包含所有軌跡直線段的最高級別聚類單元G19＝{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}，二叉樹的葉子節點則分別是條軌跡直線段構成的聚類單元如G1＝{e1}、G2＝{e2}、…、G10＝{e10}，中間結點由多條軌跡直線段構成的不同層次的聚類單元，不同結點間的分支關係則描述了層次化聚類的過程信息。由二叉樹根結點到葉子結點，樹節點對應的軌跡直線段間的移動特徵(速度、方向)差異越來越小，為後面基於移動特徵差異性的分區處理提供了結構化信息支撐。
步驟4：在壓縮的幾何精度閾值ε控制下，通過由上到下遍歷層次二叉樹結構的方式對原始軌跡線T實施分區處理，使得同一區域內軌跡線段的中間點距首尾基準線最大偏移距離小於ε；
實施例具體的實施過程說明如下：
以圖6所示的層次化聚類結果二叉樹結構為例，由根結點向葉子結點遍歷構建的層次二叉樹，每遍歷一個樹結點：
(1)提取該結點對應聚類單元包含的所有軌跡線直線段，按相鄰關係組織為軌跡線片段。如圖6中編號為2的二叉樹結點對應的聚類單元為G16＝{e1,e2,e3}，將G16包含的軌跡直線段按相鄰關係連接後得到由軌跡點p1,p2,p3,p4構成的軌跡片段。
(2)以該軌跡線片段的首尾點構成的直線段為基準線，計算每一個中間點到基準線的偏移距離，記錄其中的最大偏移距離dmax。例如圖6中聚類單元G16對應的由軌跡點p1,p2,p3,p4構成的軌跡片段，分別計算中間軌跡點p2和p3到由首尾點p1,p4構成的基準線的偏移距離(即點p2(或p3)到直線段的最短距離)，將其中的最大偏移距離記錄為dmax。
(3)如果dmax≤ε，將該部分軌跡線片段劃分為同一個區域，同時跳過該樹結點的孩子結點；反之，則按照上述方法進一步考察該結點包含的孩子結點。以圖6中編號為2的二叉樹結點對應的聚類單元G16為例，如果dmax≤ε，則將由G16包含的軌跡直線段e1,e2,e3組成的軌跡線片段劃分為同一個區域，，並且跳過對該樹結點的孩子結點的考察；反之，如果dmax＞ε，則進一步考察編號為7和12的孩子結點。
(4)按上述步驟完成對對二叉樹結構的遍歷後，原始軌跡線被分解為若干不同的區域(或若干不同的軌跡線片段)。圖7是在圖6所示的層次化聚類結果二叉樹結構基礎上，在壓縮的幾何精度閾值ε控制下基於上述步驟得到的分區結果，各分區的軌跡線片段分別表示為Seg1＝{e1,e2}，Seg2＝{e3}，Seg3＝{e4,e5,e6}，Seg4＝{e7}，Seg5＝{e8,e9,e10}。
步驟5：依次連接各分區內軌跡線段的首尾點並保存為最終的壓縮結果T』。如圖8所示，依次連接各分區內軌跡線片段的首尾點，然後組織為新的軌跡線T』＝{p1,p3,p4,p7,p8,p11}}導出作為壓縮結果。
應當理解的是，本說明書未詳細闡述的部分均屬於現有技術。
應當理解的是，上述針對較佳實施例的描述較為詳細，並不能因此而認為是對本發明專利保護範圍的限制，本領域的普通技術人員在本發明的啟示下，在不脫離本發明權利要求所保護的範圍情況下，還可以做出替換或變形，均落入本發明的保護範圍之內，本發明的請求保護範圍應以所附權利要求為準。