基于相對同步歐氏距離篩選的在線GPS軌跡數據壓縮算法

吳 青 華

(廣西大學計算機與電子信息學院　廣西 南寧 530004)

0　引　言

隨著衛星定位技術、物聯網定位技術和全球定位系統(GPS)的發展，以及各種移動終端的普及，大量的歷史移動軌跡被記錄下來，形成了時空軌跡數據。許多基于位置的服務LBS(Location Based Services)利用這些軌跡數據為用戶提供服務。但是隨著GPS軌跡數據規模的指數級增長[1]，使得在對其進行存儲、傳輸、行為模式挖掘等方面的處理時均面臨巨大挑戰，加之移動設備存儲設備、計算能力等限制，通常需要對采集到的軌跡數據采用壓縮的方法來處理[2-3]。

GPS軌跡數據壓縮旨在從各種移動設備中采集到的、具有較大冗余的原始軌跡中消除包含信息量較小的冗余點，在滿足壓縮后的軌跡與原始軌跡之間的相似度條件下，盡可能地減小軌跡數據量。同樣的軌跡數據，經過消除冗余的壓縮后，其潛在的數據挖掘速度得到極大的提高[4-5]。對于 GPS軌跡數據而言，有損壓縮比無損壓縮可以更大程度地減少數據量的存儲[5-6], 現有的GPS軌跡數據壓縮方法也以有損壓縮為主[7]。通常，GPS軌跡數據的有損壓縮分為離線壓縮和在線壓縮兩種，前者需要事先明確軌跡中包含的所有軌跡點，處理的是靜態的軌跡數據；后者無需事先明確軌跡中的所有軌跡點，軌跡的終點可以動態地變化，處理的是動態的軌跡數據。離線壓縮方法可以把握軌跡的整體信息，獲得一個全局較優的解，但不適合實時壓縮的場景。在線GPS軌跡數據壓縮算法可以滿足實時壓縮的場景，尤其對那些存儲容量有限的移動設備而言，在線GPS軌跡數據壓縮算法具有更好的適用性。由于存儲設備和傳輸條件等多方面的限制，在實際應用中在線軌跡壓縮算法更能夠滿足用戶邊采集邊壓縮的需求。

常見的GPS軌跡數據壓縮方法主要是對原始軌跡進行線性擬合，把線段簡化的思想運用到軌跡數據壓縮中，用另一條包含更少軌跡點的軌跡曲線近似表示原始軌跡曲線，同時保證兩條軌跡曲線之間的差異在一個可接受的范圍內。通過此種方式在減少軌跡數據量的同時保留原始軌跡的時空特征[6-16]，達到GPS軌跡數據壓縮的目的，這種方法又被稱為線段簡化壓縮方法[3]。Douglas等[8]提出的道格拉斯-普克算法DP(Douglas-Peucker)就是一種基于線性擬合思想的經典離線GPS軌跡數據壓縮算法。該算法首先以軌跡起點和軌跡終點的連線作為原始軌跡的近似軌跡，依次計算原始軌跡中各個軌跡點到該近似軌跡的垂直歐氏距離。并以垂直歐氏距離大于給定距離閾值的軌跡點作為分割點將當前軌跡段分為兩部分。重復以上過程，直到所有原始軌跡點到其對應的近似軌跡段的距離均小于給定距離閾值，各分割點的序列即為壓縮后的軌跡點序列。Keogh等[9]提出的開放窗口 (Open Window, OPW) 算法是在線GPS軌跡數據壓縮算法的經典算法之一。該算法提供了一種窗口機制，在包含原始軌跡中部分軌跡點的窗口中進行迭代，每次迭代只關注窗口內部軌跡點的處理，通過窗口的不斷迭代來實現實時軌跡數據的壓縮。對于OPW算法而言，窗口的迭代條件并不唯一，可以選擇窗口內的誤差總和大于用戶給定的最大誤差閾值時進行窗口迭代；也可以選擇窗口內各軌跡點對應的最大誤差大于用戶給定的閾值時進行窗口迭代[3,10]。DP算法和OPW算法均是以垂直歐氏距離作為壓縮時距離誤差的度量方式。其中，垂直歐氏距離是指軌跡點到其對應近似軌跡線段的垂線段長度。以垂直歐氏距離作為軌跡點的距離誤差度量方式可以較為完整地保留軌跡點的空間特性，但軌跡數據不僅包含空間信息還包含軌跡的時間信息，垂直歐氏距離度量方式忽略了軌跡的時間信息。因此，Meratnia等[10]提出了一種新的距離誤差度量方式——同步歐氏距離SED(Synchronous Euclidean Distance)代替垂直歐氏距離，將軌跡的時間信息也考慮在內，并基于SED對DP算法和OPW算法進行改進，提出了按時間比例的自頂向下壓縮算法TD-TR(Top-Down Time Ratio)和按時間比例的開放窗口算法OPW-TR(Opening Window Time Ratio)。

基于上述研究背景和成果，近年來，有關GPS軌跡數據壓縮的成果較多，且以在線軌跡數據壓縮算法為主。Muckell等[11]提出了具有緩沖的啟發式空間質量簡化算法SQUISH(Spatial Quality Simplification Heuristic)算法。SQUISH算法首先初始化了一個固定長度k的優先級隊列，把軌跡點依次加入到該隊列中，當隊列滿時，刪除隊列中引起誤差最小的軌跡點，并重新計算隊列中每個軌跡點的優先級。之后，針對SQUISH算法的壓縮誤差沒有上界、壓縮軌跡與原始軌跡之間距離誤差較大等問題，Muckell等[12]又對SQUISH算法進行改進，將壓縮率和距離誤差閾值引入到SQUISH算法中，并改進了優先級隊列中軌跡點優先級的計算方式，進而提出SQUISH-E算法。SQUISH-E算法可以設定用戶需要的壓縮率也可以設定壓縮過程中允許的最大誤差距離閾值，但其在計算軌跡點優先級時，僅考慮了軌跡點所在的局部軌跡段的時空信息，不能較為準確地衡量軌跡點在當前軌跡中所攜帶的信息量大小。吳家皋等[13]充分考慮軌跡數據的時空信息，利用GPS數據的位置信息、時間信息、方向角和速度信息進行軌跡特征點的綜合判斷，從原始軌跡數據中選出包含較大信息量的軌跡點進行壓縮。但此方法的壓縮效果依賴于用戶輸入速度閾值、方向角度閾值等參數，而實際應用中用戶并沒有足夠的經驗給定合適的閾值以達到期望的壓縮效果。同年，吳家皋等[14]在OPW算法的基礎上進行改進，將最大偏移距離參考軌跡點作為當前待壓縮的軌跡點能否被壓縮的判據,降低了軌跡的壓縮時間。劉磊軍等[15]通過軌跡點的轉向角度大小和速度變化大小來評估軌跡點信息量的大小，同時用SED限制點的偏移量,進而提出限定SED的閾值結合算法(SLTA)，以達到減小壓縮軌跡與原始軌跡之間差異的目的。龍浩等[16]針對現有軌跡數據壓縮算法難以確定壓縮閾值的問題，對DP算法進行改進，提出了自適應參數的軌跡壓縮算法。

SQUISH-E算法和OPW-TR算法是目前壓縮效果較好的在線壓縮算法，代表了線段簡化軌跡壓縮方法中在線GPS軌跡數據壓縮的兩個研究方向[3,5]。現有在線GPS軌跡數據壓縮算法(如：SQUISH-E算法、OPW-TR算法、SLTA算法)中，除SQUISH_E算法外，大部分算法(如：OPW-TR算法、SLTA算法)都需要用戶給定一個或多個特定的閾值，如：可接受的最大誤差距離閾值、最大角度閾值、最大速度閾值等。而實際應用中，用戶并沒有足夠的經驗可以設置合適的閾值來達到期望的壓縮率。此外，大多現有在線GPS軌跡數據壓縮的算法，如SQUISH-E[12]、OPW-TR算法[9]等均是通過軌跡點所處的局部軌跡段的時空信息來衡量軌跡點在軌跡全局中所占的信息量大小[3]，不能夠較為準確地衡量軌跡點在當前存儲軌跡全局中的信息量，可能存在因軌跡點信息量衡量不當，導致壓縮軌跡與還原軌跡之間產生較大差異的問題。針對上述問題，本文提出一種以壓縮率為壓縮依據，且考慮當前存儲隊列中所有軌跡點時空信息的在線GPS軌跡數據壓縮算法-基于相對SED篩選RSF(Relative SED Filtering)的軌跡數據壓縮算法。該算法首先初始化一個存儲隊列，每次將新到來的軌跡點添加到存儲隊列中。當存儲隊列長度超過當前情況下壓縮率所允許的最大長度時，結合當前存儲隊列中軌跡數據對應的軌跡整體走勢，借鑒TD_TR算法的思想從當前存儲隊列中篩選出引起SED誤差相對較小的軌跡點，并將其從存儲隊列中移除，保證在給定壓縮率下，壓縮軌跡與原始軌跡之間具有較小的差異。

1　相關概念

定義1近似軌跡、近似軌跡段。線段簡化壓縮算法是通過使用一條包含較少軌跡點的軌跡點序列來近似表示原始軌跡點序列，而這條包含較少軌跡點的軌跡就稱為原始軌跡的近似軌跡。近似軌跡中兩個相鄰軌跡點連接所形成的軌跡段稱為其對應原始軌跡的近似軌跡段。

如圖1所示，S、P1、P2、P3、P4、E表示原始軌跡中6個相鄰的軌跡點。而近似軌跡中只存儲了S、E兩個軌跡點。即用軌跡段SE近似表示原始軌跡中軌跡點S到軌跡點E的這段軌跡，SE就稱為原始軌跡中S到E這段軌跡的近似軌跡。

圖1　近似軌跡

定義2同步歐氏距離SED(Synchronous Euclidean Distance)[10]。同步歐氏距離是指原始軌跡數據中的軌跡點與其在近似軌跡段上按其時間比例所求得的對應位置之間的歐氏距離。

如圖2所示，P′是軌跡點P2在其相應的近似軌跡段上按時間比例的對應位置，P2P′即為軌跡點P2對應的同步歐氏距離。P″是軌跡點P2在近似軌跡段SE上的垂足，P2P″即為軌跡點P2到其對應的近似軌跡段SE的垂直歐氏距離。

圖2　SED和垂直歐氏距離

(1)

(2)

由軌跡點P2和P′的位置信息可以計算出P2的同步歐氏距離:

(3)

通過式(1)、式(2)可以看出SED的度量方式考慮了軌跡數據的空間信息和時間信息。

2　基于相對SED篩選的在線GPS軌跡數據壓縮算法

壓縮率一定時，如何在有限的存儲空間內選擇包含更多軌跡時空信息的軌跡點進行存儲是在線GPS軌跡數據壓縮算法的關鍵。換而言之，在一定壓縮率要求下，在線GPS軌跡壓縮算法的關鍵就是隨著新軌跡點的不斷加入，如何從當前存儲隊列中選出引起SED誤差最小的軌跡點進行移除。由于在線GPS軌跡壓縮算法所壓縮的軌跡的終點是不確定的，當新的軌跡點到來時，存儲隊列中的其他軌跡點所攜帶的軌跡信息量會隨著新軌跡點的時空信息發生變化。因此，從當前存儲隊列中軌跡整體走勢的角度來衡量存儲隊列中各個軌跡點的信息量相比于僅從軌跡點所處局部軌跡段的角度考慮軌跡點信息量更加準確。

TD-TR算法作為離線軌跡數據壓縮領域的經典算法，其壓縮過程把握了軌跡的全局走勢，每次將包含軌跡信息量較大的軌跡點作為軌跡的分割點，進行存儲，較在線GPS軌跡數據壓縮算法只考慮軌跡點所在局部軌跡段的方式能夠更準確地衡量軌跡點所攜帶的軌跡信息量。RSF算法借鑒TD-TR算法的思想，當存儲隊列長度超過一定限制時，對存儲隊列中的軌跡點信息量進行衡量，以篩選出存儲隊列中包含軌跡信息量較小的軌跡點。

RSF算法以用戶期望達到的壓縮率為依據對在線GPS軌跡數據進行壓縮，算法步驟可以簡單描述為：

(1) 首先初始化一個存儲隊列，將每一個新到來的軌跡點加入到存儲隊列中。

(2) 當存儲隊列長度超過當前情況下壓縮率所允許的最大長度時，利用TD-TR算法的思想，從當前存儲隊列中標記出包含軌跡信息量較小的軌跡點。

(3) 從這些信息量較小的軌跡點中選擇引起SED誤差相對較小的軌跡點進行移除，而非像TD-TR算法那樣，根據一個用戶輸入的固定距離閾值來判定軌跡點的去留。

隨著軌跡點的不斷到來，重復以上過程，即可實現GPS軌跡數據的在線壓縮。存儲隊列中的軌跡點序列即為壓縮后的軌跡點序列。

RSF算法的具體過程如算法1的偽代碼所示，其中，SaveQueue表示存儲隊列，存儲的是需要被存儲的軌跡點信息，信息格式與壓縮前的軌跡點信息格式一致，包含經緯度信息和時間信息；|SaveQueue|表示SaveQueue隊列的長度；LIPS(Little Information Point Select)算法是一個軌跡點選擇算法，目的是從當前存儲隊列中標記出包含軌跡信息量較小的軌跡點，返回值為標記序列signSeq[]；CalcSED()是一個SED距離計算算法，計算方法如式(3)所示。

算法1RFS算法

輸入：原始軌跡數據T、壓縮率ratio。其中，T={P1,P2,…,Pn}={(x1,y1,t1),(x2,y2,t2),…,(xn,yn,tn)};

輸出：壓縮軌跡數據T′。其中，T′={P1,Pi1,Pi2,…Pn},P1,Pi1,Pi2,…,Pn∈T，P1,Pi1,Pi2,…,Pn是經壓縮之后保留的軌跡點，稱為原始軌跡數據中的關鍵軌跡點。

Begin

1) |SaveQueue|←2//將軌跡點存儲隊列的大小初始化為2

2) foreachnewPointPi

3)SaveQueue←Pi;

4)maxLen←(i*ratio);

5)If |SaveQueue|>maxLen

6)signSeq[]←LIPS(SaveQueue);

7)foreachpointPinsignSeq[]

//j為軌跡點P在SaveQueue中的編號

8)CalcSED(Pj-1,Pj,Pj+1);

9)Endfor

10)SelectminSEDPointremovefromSaveQueue

11)end If

12) Endfor

End

如算法1所示，首先初始化一個大小為2的存儲隊列(步驟1)，對于每一個新采集到的軌跡點Pi，將Pi存入存儲隊列中去(步驟2-3)，計算當前允許的存儲隊列最大長度,其中i為當前采集到的軌跡點總數(步驟4)。若當前存儲隊列長度大于當前壓縮率所允許的存儲隊列最大長度，則通過LIPS算法，得到當前存儲隊列中包含軌跡信息量最少的軌跡點標記序列(步驟6)。對標記序列中的每個點計算其相對于存儲隊列中前后相鄰軌跡點的SED(步驟7-9)，從中選擇最小SED值對應的軌跡點，將其從存儲隊列中移除(步驟10)，保證壓縮結果達到給定的壓縮率的同時盡可能地減小因刪除軌跡點而引起的誤差。

如算法2所示，LIPS算法首先以存儲隊列中的第一個軌跡點和最后一個軌跡點作為存儲隊列中所有軌跡點所表示的原始軌跡的近似軌跡。然后依次計算軌跡中各點到該近似軌跡的SED距離，并以最大SED距離對應的軌跡點作為原始軌跡的分割點，將原始軌跡分割成兩條子軌跡(步驟7-8)。遞歸進行此操作(步驟9-10)，直到子軌跡中包含的軌跡點數不超過3為止。將包含3個軌跡點的子軌跡段對應的中間軌跡點Pj進行標記，加入到標記序列中。因為，按照TD-TR算法的規則，當子軌跡中只包含3個軌跡點時，其對應的中間軌跡點所包含的軌跡信息量相對于其他2個軌跡點而言是比較小的，也就是說若將子軌跡段的中間軌跡點從存儲隊列中移除，其引起的誤差是較小的。LIPS算法的返回結果為軌跡點標記序列。

算法2LIPS算法

輸入：存儲隊列SaveQueue,其中，SaveQueue={Pj1,Pj2,…,Pjm}={(xj1,yj1,tj1),(xj2,yj2,tj2),…,(xjm,yjm,tjm)}

輸出：標記序列signSeq[]

Begin

1) If |SaveQueue|=3

2)FlagthemiddlepointinsignSeq[]

3) Else if |SaveQueue|>3

4)foreachPointPjxinSaveQueue,(1

5)CalcSED(Pj1,Pjx,Pjm);

6)Endfor

7)SelectPointPjwhichPjhasmaxSED

8)createtwosub-Trajectory

9)LIPS(sub-Tra1);

10)LIPS(sub-Tra2);

11) end If

12) returnsignSeq[];

End

RSF算法在存儲的軌跡點個數超過當前情況下壓縮率所允許的最大個數時，從當前存儲隊列中軌跡全局的角度，衡量每個軌跡點所攜帶的軌跡時空信息量，將包含軌跡信息量較大的軌跡點保留在存儲隊列中，盡可能減小壓縮軌跡與原始軌跡之間的差異。下面從理論分析和實驗驗證兩個方面驗證RSF算法的有效性。

3　算法分析及其性能度量指標

3.1　算法分析

目前GPS軌跡數據在線壓縮方法中的主流算法有SQUISH-E算法和OPW算法的改進算法OPW-TR算法等。其中，OPW-TR算法需要設置最大誤差距離閾值進行軌跡數據的壓縮，SQUISH-E算法可以設置所需要的壓縮率(ratio)也可以設置最大誤差距離閾值。由于以最大誤差距離閾值為參數的壓縮算法需要用戶具有足夠的經驗給定閾值才可能達到預期的壓縮效果，所以以壓縮率為依據的軌跡數據壓縮算法適用性更強。RSF算法是以用戶需要的壓縮率(ratio)為參數進行軌跡數據壓縮的，所以下面主要將RSF算法與可設置壓縮率的SQUISH-E算法進行對比。為了方便表述，本文將以ratio作為輸入參數的SQUISH-E算法記為SQUISH-E(ratio)算法。

RSF算法和 SQUISH-E(ratio)算法均是從原始軌跡數據中選擇部分關鍵軌跡點進行存儲。SQUISH-E(ratio)算法在篩選關鍵軌跡點時，通過軌跡點自身的優先級進行篩選，軌跡點的優先級包含當前軌跡點自身到前后關鍵點所形成近似軌跡段的SED距離，以及曾經的鄰居軌跡點被刪除時累加到自身的優先級兩個方面。只考慮了局部軌跡點信息，沒有考慮當前存儲隊列中全部的軌跡信息，且由于軌跡點被刪除之后，其鄰居軌跡點相對于其前后軌跡點的SED距離已經發生了變化，此時再將刪除點的優先級直接累加到鄰居軌跡點的優先級上來衡量鄰居軌跡點的信息量可能存在一定偏差。RSF算法結合TD-TR算法的思想，將每個子軌跡段中最后作為分割點的軌跡點標記出來，從當前存儲隊列對應軌跡全局的角度考慮了存儲隊列中每個軌跡點的信息量。最后，統一用存儲隊列中該軌跡點相對于其前后相鄰軌跡點的SED距離選出引起誤差最小的軌跡點進行刪除。在保證達到一定壓縮率要求的前提下，盡可能地保留了包含軌跡時空信息量較大的軌跡點，進而達到減小壓縮后的軌跡與原始軌跡之間差異的目的。

3.2　算法性能度量指標

就壓縮算法而言，數據經過壓縮之后所帶來的存儲空間的節省和能夠達到的還原精度是壓縮算法重要的性能指標。GPS軌跡數據壓縮算法的性能可以從壓縮率、恢復效果和壓縮速度三個方面來衡量[17-18]。本文用軌跡數據壓縮后所節省的存儲空間和原始GPS軌跡數據大小的比值來表示壓縮率信息；用壓縮軌跡產生的平均SED誤差來衡量壓縮后軌跡的還原軌跡與原始軌跡之間的誤差[18]，此誤差越小，表示壓縮后的軌跡數據所能達到的還原精度越高；用GPS軌跡數據壓縮算法的壓縮時間來衡量其壓縮速度。

壓縮率和平均SED誤差的定義如下：

定義3壓縮率[18]。壓縮率指壓縮后數據較原始數據所節省的存儲空間大小與原始數據所占存儲空間大小的比值。

式(4)給出了壓縮率的計算方式。其中，CR為壓縮率(Compression Ratio)，S1和S2分別表示壓縮后和壓縮前的軌跡數據大小。僅考慮壓縮率的情況下，壓縮率越高,壓縮算法的壓縮效果越好。

(4)

定義4平均SED誤差[12]。平均SED誤差是指原始軌跡中被舍棄的軌跡點與還原軌跡中對應位置的平均誤差，反映了還原軌跡和原始軌跡之間的差距。

式(5)給出了平均SED誤差的計算方式。其中SED(pi)指原始軌跡中的第i個軌跡點與其在壓縮軌跡中對應的軌跡點之間的歐氏距離，n為原始軌跡中軌跡點的個數。

(5)

4　實驗與分析

為了進一步驗證RSF算法的有效性，在理論分析的基礎上通過實驗進行對比分析。這里仍將在線GPS軌跡數據主流壓縮算法中以壓縮率為輸入參數的SQUISH-E(ratio)算法作為RSF算法的對比算法，根據實驗結果，從壓縮率、平均SED誤差和壓縮時間三個方面進行對比分析，并給出相應結論。

4.1　實驗環境和數據

本次實驗中的算法程序通過Java語言編寫，使用eclipse開發工具,實驗環境為：Intel(R) Corei7處理器,主頻2.6 GHz,Win7操作系統,物理內存4 GB。

實驗數據采用的是微軟亞洲研究院發布的公開軌跡數據集Geolife[19]，數據包括了182名志愿者5年的軌跡，共17 621條軌跡，總距離達到129 295公里，總時長達到50 176小時，采集設備各不相同，采樣率也有差異，但91%以上的是高密度的采樣，如：1～5秒或5～10米。Geolife數據集包含的信息巨大，本次實驗的目的是為了驗證RFS算法的有效性，對軌跡數據量的大小并沒有過多要求，固不需要軌跡數據集合中的全部信息，本文從編號為“000”的Geolife軌跡數據中選取了一條包含軌跡點數目較多的軌跡進行實驗。該軌跡由1 103個軌跡點組成，軌跡點信息由經緯度信息、時間戳信息、海拔高度等7個字段的信息組成。表1給出了某軌跡點的描述信息。

表1　軌跡點信息

其中，字段“天數”指的是距離1899年12月30日的天數(包括小數部分)。根據“天數”字段的值可以計算出相應的“日期”和“時間”字段信息。根據常用的軌跡數據查詢類型可知，軌跡的經緯度信息和時間信息是人們較為關心的[16]，因此，在進行實驗時，本文僅從原始軌跡中選取經緯度信息和天數信息三個字段的數據作為實驗的輸入數據。以下為實驗輸入數據中1個軌跡點的描述信息，以逗號分隔的三個字段分別代表軌跡點的緯度信息、經度信息和時間信息：

40.010 6,116.322 961,39 925.110 405 092 6

4.2　實驗結果分析

由于RSF算法和SQUISH-E(ratio)算法均以用戶期望達到的壓縮率ratio作為壓縮時的依據。圖3為RSF算法和SQUISH-E(ratio)算法在不同壓縮率下產生的平均SED誤差對比圖。圖4為RSF算法和SQUISH-E(ratio)算法在不同壓縮率下所消耗的壓縮時間對比圖，該運行時間取的是各算法運行10次時間的平均值。其中，用于輸入的期望壓縮率ratio∈[0,1)，壓縮率等于0時，壓縮后的軌跡數據與壓縮前的軌跡數據相同。隨著壓縮率的增大，壓縮后的軌跡數據越來越小，包含的軌跡點也越來越少。極端情況下，一條軌跡壓縮后僅包含軌跡的起點和終點兩個軌跡點，但達不到壓縮率等于1的情況。

圖3　不同壓縮率下的平均SED誤差對比

圖4　相同壓縮率下的壓縮時間對比

由圖3可以看出平均SED誤差隨著壓縮率的增高而不斷增大。在相同壓縮率下，RSF算法對應的平均SED誤差始終小于SQUISH_E(ratio)。此外，隨著壓縮率的增加，兩算法平均SED誤差的差距呈增大趨勢。當ratio<0.5時，SQUISH_E(ratio)算法與RSF算法在相同壓縮率下，平均SED誤差平均相差約0.53 m。當ratio>0.5時，SQUISH_E(ratio)算法與RSF算法在相同壓縮率下，對應的平均SED誤差平均相差約1.54 m，相對于壓縮率小于0.5時，平均SED誤差的差距增加了近2倍。這主要是由于隨著壓縮率的增加，相同原始軌跡點數下，能夠保存的軌跡點個數越來越少，刪除的軌跡點引起的誤差也越來越大，這時關鍵軌跡點的選擇也就尤為重要，RSF算法的優勢也就越來越明顯。

由圖4為相同壓縮率下兩算法所需壓縮時間的對比圖，從圖中可以看出RSF算法所需的壓縮時間較SQUISH_E(ratio)算法所需的壓縮時間更長，且RSF算法在壓縮率取0.3～0.7時所需的壓縮時間較長，在壓縮率為0.4時達到峰值478 ms。這主要是由于當軌跡存儲隊列長度大于ratio下所允許的最大長度時，RSF算法需對隊列中的所有軌跡點進行一次LIPS算法操作，從當前存儲隊列對應軌跡全局的角度考慮之后篩選出引起誤差最小的軌跡點進行刪除。而SQUISH_E(ratio)算法則只需比較軌跡隊列中每個軌跡點在局部軌跡段的優先級，即可選出將要被刪除的軌跡點。所以RSF算法在壓縮過程中所需的計算量更大，相應的運行時間也就越長。此外，對于RSF算法而言，當壓縮率較高時(如0.9)，由于其可允許的存儲隊列長度較小，每次在選擇要刪除的軌跡點時，其計算量也大大降低，相應的壓縮時間也就越短；當壓縮率較低時(如0.1)，由于其可允許的存儲隊列長度較大，需要刪除的軌跡點較少，其計算次數較壓縮率較低時明顯減少，相應的壓縮時間也就越短；當壓縮率適中時(如0.4)，其所需的計算次數和計算量都相對較多，所需的壓縮時間也較長，因此如圖4所示，壓縮率適中時，RSF算法所需的壓縮時間較長。

綜合以上理論分析和實驗結果，在相同壓縮率下，RSF算法對應的平均SED誤差較SQUISH_E(ratio)算法對應的平均SED誤差更小，相應的，RSF算法對應的還原軌跡比SQUISH_E(ratio)算法對應的還原軌跡具有更高的還原精度。此外，RSF算法較SQUISH_E(ratio)算法所需的壓縮時間相對較長，對于在線GPS軌跡數據壓縮算法而言，一定壓縮率前提下，在可接受的壓縮時間內獲得更高的軌跡還原精度是值得的。

5　結　語

本文針對現有在線GPS軌跡數據壓縮算法中存在的壓縮率一定時，壓縮軌跡與原始軌跡之間差異較大的問題提出了一種基于相對SED篩選的在線GPS軌跡數據壓縮算法。該算法以用戶期望達到的壓縮率為依據，進行軌跡數據的壓縮。當存儲的軌跡點個數超過壓縮率要求時，利用TD-TR算法的思想考慮當前存儲隊列中所有軌跡點的時空信息，從當前存儲隊列中刪除引起SED誤差最小的軌跡點，盡可能地保證包含軌跡時空信息量較大的軌跡點被保留在存儲隊列中，以達到減小壓縮后的軌跡與原始軌跡之間時空信息差異的目的。理論分析和實驗結果表明，較現有以壓縮率為壓縮依據的主流在線GPS軌跡數據主流壓縮算法而言，RSF算法可以在給定壓縮率的限制下，以一定的壓縮時間為代價，獲得更小的平均SED誤差距離，進而得到與原始軌跡更接近的壓縮軌跡。在將來的研究中，將針對RSF算法的壓縮時間進行進一步優化，以期設計出更有效的GPS軌跡數據壓縮算法。

[1] 許佳捷，鄭凱，池明旻,等.軌跡大數據:數據、應用與技術現狀[J]. 通信學報,2015,36(12):97-105.

[2] Zheng Y, Zhou X. Computing with Spatial Trajectories[M]. Springer New York, 2011.

[3] 江俊文，王曉玲. 軌跡數據壓縮綜述[J]. 華東師范大學學報(自然科學版),2015(5):61-76.

[4] Jeung H, Man L Y, Jensen C S. Trajectory Pattern Mining[M]// Computing with Spatial Trajectories. Springer New York, 2011:330-339.

[5] 樊慶富，張磊，劉磊軍,等.基于偏移量計算的在線GPS軌跡數據壓縮[J].計算機工程與應用,2016,52(3):1-7.

[6] Chen M, Xu M, Franti P. Compression of GPS Trajectories[C]//Data Compression Conference. IEEE, 2012:62-71.

[7] Chen M, Xu M, Franti P. Compression of GPS trajectories using optimized approximation. [C]//Proceeding of the 2012 21st International Conference on Pattern Recognition. Piscataway, NJ: IEEE, 2012, 3180-3183.

[8] Douglas D H, Peucker T K. Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or Its Caricature[J]. Cartographica the International Journal for Geographic Information & Geovisualization, 2001, 10(2):112-122.

[9] Keogh E J, Chu S, Pazzani M J. An Online Algorithm for Segmenting Time Series[C]// IEEE International Conference on Data Mining. IEEE Computer Society, 2001:289-296.

[10] Meratnia N, By R A D. Spatiotemporal Compression Techniques for Moving Point Objects[M]// Advances in Database Technology-EDBT 2004. Springer Berlin Heidelberg, 2004:765-782.

[11] Muckell J, Hwang J H, Patil V, et al. SQUISH: an online approach for GPS trajectory compression[C]//Proceedings of the 2nd International Congference on Computing for Geospatial Research & Applications. New York:ACM,2011:13.

[12] Muckell J, Olsen P W, Hwang J H, et al. Compression of trajectory data: a comprehensive evaluation and new approach[J]. GeoInformatica, 2014, 18(3):435-460.

[13] 吳家皋,錢科宇,劉敏,等.基于綜合時空特性的混合式軌跡壓縮算法[J]. 計算機應用, 2015, 35(5):1209-1212.

[14] 吳家皋, 劉敏, 韋光,等. 一種改進的滑動窗口軌跡數據壓縮算法[J]. 計算機技術與發展, 2015, 25(12):47-51.

[15] 劉磊軍，房晨，張磊,等. 基于運動狀態改變的在線全球定位系統軌跡數據壓縮[J].計算機應用，2016，36(1):122-127.

[16] 龍浩,張書奎,孫鵬輝. 自適應參數的軌跡壓縮算法[J/OL]. 計算機應用研究,優先出版,2018，35(3). http://www.arocmag.com/article/02-2018-03-026.html.

[17] 吳佩莉.移動對象軌跡數據管理關鍵技術研究[D].北京：北京理工大學,2015.

[18] 馮神柱.路網軌跡數據的壓縮存儲技術研究[D].杭州：杭州電子科技大學，2013.

[19] Zheng Y, Xie X, Ma W Y. GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory[J]. Bulletin of the Technical Committee on Data Engineering, 2011, 33(2):32-39.