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

吳 青 華

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

0　引　言

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

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

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

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

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

1　相關(guān)概念

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

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

圖1　近似軌跡

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

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

圖2　SED和垂直歐氏距離

(1)

(2)

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

(3)

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

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

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

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

RSF算法以用戶期望達(dá)到的壓縮率為依據(jù)對在線GPS軌跡數(shù)據(jù)進(jìn)行壓縮，算法步驟可以簡單描述為：

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

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

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

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

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

算法1RFS算法

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

輸出：壓縮軌跡數(shù)據(jù)T′。其中，T′={P1,Pi1,Pi2,…Pn},P1,Pi1,Pi2,…,Pn∈T，P1,Pi1,Pi2,…,Pn是經(jīng)壓縮之后保留的軌跡點，稱為原始軌跡數(shù)據(jù)中的關(guān)鍵軌跡點。

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)，計算當(dāng)前允許的存儲隊列最大長度,其中i為當(dāng)前采集到的軌跡點總數(shù)(步驟4)。若當(dāng)前存儲隊列長度大于當(dāng)前壓縮率所允許的存儲隊列最大長度，則通過LIPS算法，得到當(dāng)前存儲隊列中包含軌跡信息量最少的軌跡點標(biāo)記序列(步驟6)。對標(biāo)記序列中的每個點計算其相對于存儲隊列中前后相鄰軌跡點的SED(步驟7-9)，從中選擇最小SED值對應(yīng)的軌跡點，將其從存儲隊列中移除(步驟10)，保證壓縮結(jié)果達(dá)到給定的壓縮率的同時盡可能地減小因刪除軌跡點而引起的誤差。

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

算法2LIPS算法

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

輸出：標(biāo)記序列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算法在存儲的軌跡點個數(shù)超過當(dāng)前情況下壓縮率所允許的最大個數(shù)時，從當(dāng)前存儲隊列中軌跡全局的角度，衡量每個軌跡點所攜帶的軌跡時空信息量，將包含軌跡信息量較大的軌跡點保留在存儲隊列中，盡可能減小壓縮軌跡與原始軌跡之間的差異。下面從理論分析和實驗驗證兩個方面驗證RSF算法的有效性。

3　算法分析及其性能度量指標(biāo)

3.1　算法分析

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

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

3.2　算法性能度量指標(biāo)

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

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

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

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

(4)

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

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

(5)

4　實驗與分析

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

4.1　實驗環(huán)境和數(shù)據(jù)

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

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

表1　軌跡點信息

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

40.010 6,116.322 961,39 925.110 405 092 6

4.2　實驗結(jié)果分析

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

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

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

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

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

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

5　結(jié)　語

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

[1] 許佳捷，鄭凱，池明旻,等.軌跡大數(shù)據(jù):數(shù)據(jù)、應(yīng)用與技術(shù)現(xiàn)狀[J]. 通信學(xué)報,2015,36(12):97-105.

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

[3] 江俊文，王曉玲. 軌跡數(shù)據(jù)壓縮綜述[J]. 華東師范大學(xué)學(xué)報(自然科學(xué)版),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軌跡數(shù)據(jù)壓縮[J].計算機(jī)工程與應(yīng)用,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]. 計算機(jī)應(yīng)用, 2015, 35(5):1209-1212.

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

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

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

[17] 吳佩莉.移動對象軌跡數(shù)據(jù)管理關(guān)鍵技術(shù)研究[D].北京：北京理工大學(xué),2015.

[18] 馮神柱.路網(wǎng)軌跡數(shù)據(jù)的壓縮存儲技術(shù)研究[D].杭州：杭州電子科技大學(xué)，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.