吳 青 華

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

0　引　言

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

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

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

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

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

1　相關(guān)概念

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

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

圖1　近似軌跡

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

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

圖2　SED和垂直歐氏距離

(1)

(2)

由軌跡點(diǎn)P2和P′的位置信息可以計(jì)算出P2的同步歐氏距離:

(3)

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

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

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

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

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

(1) 首先初始化一個(gè)存儲(chǔ)隊(duì)列，將每一個(gè)新到來(lái)的軌跡點(diǎn)加入到存儲(chǔ)隊(duì)列中。

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

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

隨著軌跡點(diǎn)的不斷到來(lái)，重復(fù)以上過(guò)程，即可實(shí)現(xiàn)GPS軌跡數(shù)據(jù)的在線壓縮。存儲(chǔ)隊(duì)列中的軌跡點(diǎn)序列即為壓縮后的軌跡點(diǎn)序列。

RSF算法的具體過(guò)程如算法1的偽代碼所示，其中，SaveQueue表示存儲(chǔ)隊(duì)列，存儲(chǔ)的是需要被存儲(chǔ)的軌跡點(diǎn)信息，信息格式與壓縮前的軌跡點(diǎn)信息格式一致，包含經(jīng)緯度信息和時(shí)間信息；|SaveQueue|表示SaveQueue隊(duì)列的長(zhǎng)度；LIPS(Little Information Point Select)算法是一個(gè)軌跡點(diǎn)選擇算法，目的是從當(dāng)前存儲(chǔ)隊(duì)列中標(biāo)記出包含軌跡信息量較小的軌跡點(diǎn)，返回值為標(biāo)記序列signSeq[]；CalcSED()是一個(gè)SED距離計(jì)算算法，計(jì)算方法如式(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)壓縮之后保留的軌跡點(diǎn)，稱為原始軌跡數(shù)據(jù)中的關(guān)鍵軌跡點(diǎn)。

Begin

1) |SaveQueue|←2//將軌跡點(diǎn)存儲(chǔ)隊(duì)列的大小初始化為2

2) foreachnewPointPi

3)SaveQueue←Pi;

4)maxLen←(i*ratio);

5)If |SaveQueue|>maxLen

6)signSeq[]←LIPS(SaveQueue);

7)foreachpointPinsignSeq[]

//j為軌跡點(diǎn)P在SaveQueue中的編號(hào)

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

9)Endfor

10)SelectminSEDPointremovefromSaveQueue

11)end If

12) Endfor

End

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

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

算法2LIPS算法

輸入：存儲(chǔ)隊(duì)列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算法在存儲(chǔ)的軌跡點(diǎn)個(gè)數(shù)超過(guò)當(dāng)前情況下壓縮率所允許的最大個(gè)數(shù)時(shí)，從當(dāng)前存儲(chǔ)隊(duì)列中軌跡全局的角度，衡量每個(gè)軌跡點(diǎn)所攜帶的軌跡時(shí)空信息量，將包含軌跡信息量較大的軌跡點(diǎn)保留在存儲(chǔ)隊(duì)列中，盡可能減小壓縮軌跡與原始軌跡之間的差異。下面從理論分析和實(shí)驗(yàn)驗(yàn)證兩個(gè)方面驗(yàn)證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)驗(yàn)給定閾值才可能達(dá)到預(yù)期的壓縮效果，所以以壓縮率為依據(jù)的軌跡數(shù)據(jù)壓縮算法適用性更強(qiáng)。RSF算法是以用戶需要的壓縮率(ratio)為參數(shù)進(jìn)行軌跡數(shù)據(jù)壓縮的，所以下面主要將RSF算法與可設(shè)置壓縮率的SQUISH-E算法進(jìn)行對(duì)比。為了方便表述，本文將以ratio作為輸入?yún)?shù)的SQUISH-E算法記為SQUISH-E(ratio)算法。

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

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

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

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

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

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

(4)

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

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

(5)

4　實(shí)驗(yàn)與分析

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

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

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

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

表1　軌跡點(diǎn)信息

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

40.010 6,116.322 961,39 925.110 405 092 6

4.2　實(shí)驗(yàn)結(jié)果分析

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

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

圖4　相同壓縮率下的壓縮時(shí)間對(duì)比

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

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

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

5　結(jié)　語(yǔ)

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

[1] 許佳捷，鄭凱，池明旻,等.軌跡大數(shù)據(jù):數(shù)據(jù)、應(yīng)用與技術(shù)現(xiàn)狀[J]. 通信學(xué)報(bào),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é)報(bào)(自然科學(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] 樊慶富，張磊，劉磊軍,等.基于偏移量計(jì)算的在線GPS軌跡數(shù)據(jù)壓縮[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] 吳家皋,錢科宇,劉敏,等.基于綜合時(shí)空特性的混合式軌跡壓縮算法[J]. 計(jì)算機(jī)應(yīng)用, 2015, 35(5):1209-1212.

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

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

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

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

[18] 馮神柱.路網(wǎng)軌跡數(shù)據(jù)的壓縮存儲(chǔ)技術(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.