李升宏，耿生玲,2，田立勤,3，李路加，陳 娜，林連海

(1.青海師范大學 計算機學院，青海 西寧 810008；2.高原科學與可持續(xù)發(fā)展研究院，青海 西寧 810008； 3.華北科技學院 計算機學院，河北 廊坊 065201)

隨著通信信息技術(shù)快速發(fā)展和廣泛應(yīng)用，產(chǎn)生了與人們工作和生活息息相關(guān)的海量數(shù)據(jù)。此類海量數(shù)據(jù)，應(yīng)用于大到對航天、航空和衛(wèi)星的軌跡實時跟蹤中，小到無人駕駛、公交站臺顯示和到站提醒、網(wǎng)約平臺的實時定位以及用戶每時每刻所形成的位置變化中等，而這些數(shù)據(jù)都離不開矢量數(shù)據(jù)的獲取與處理。一方面，矢量數(shù)據(jù)會源源不斷地生產(chǎn)與輸出，另一方面，用于存儲數(shù)據(jù)的設(shè)備介質(zhì)和計算機的處理能力始終有限。因此，矢量數(shù)據(jù)的有損壓縮問題研究是大數(shù)據(jù)存儲與傳播的關(guān)鍵問題之一。

矢量數(shù)據(jù)指既有大小又有方向的一類數(shù)據(jù)集，通常用于表示地圖圖形或地理實體位置或形狀的數(shù)據(jù)。軌跡壓縮處理也叫曲線的特征點處理，或曲線的抽稀處理。壓縮方法通常分為有損壓縮[1]和無損壓縮[2]，按其技術(shù)特點又可分為批處理算法、在線算法[3]和單遍掃描算法。前者是從待壓縮的數(shù)據(jù)中精確地重建原始數(shù)據(jù)，不會造成信息損失。而后者是在一定誤差范圍內(nèi)，從原始曲線Γ數(shù)據(jù)集中壓縮重復(fù)冗余或連續(xù)變化形態(tài)不明顯的數(shù)據(jù)元素，將剩余的元素按原序連接形成新的曲線?！洹Ｆ渲?，?！?Γ，Γ′是Γ的子集。

當前，已出現(xiàn)眾多成熟的有損壓縮理論，如垂距限值法[3-7]、角度限制法、面積偏差控制法以及經(jīng)典的道格拉斯(Douglas-Peucker,D-P)算法等[8-13]。王笑天等[14]針對D-P算法存在大量迭代計算問題，提出第一特征點提取法，把時間復(fù)雜度降到O(n)。但是，該算法每次操作的均是局部第一特征點，沒有對全局特征點進行權(quán)衡，壓縮后曲線部分出現(xiàn)形變。楊得志等[8]對D-P算法改進，利用徑向距離作為補充約束條件控制壓縮面積的誤差，雖然使得壓縮后的曲線較為光滑，但算法仍然存在大量的迭代操作。米學軍等[5]利用直線逐漸逼近曲線空間，提出了面積偏差限值法，很大程度上解決了由于線段空間偏移過大以及面積偏差不可控的問題，效果明顯。但是，需要進行大量的直線空間相交點方程求解和多邊形面積的計算，導致時間復(fù)雜度劇增。

陳飛翔等[15]提出基于動態(tài)規(guī)劃的矢量壓縮算法。該算法通過一條參考路徑構(gòu)造一條可自適應(yīng)調(diào)整寬度窄帶區(qū)域，可限定最小誤差搜索范圍，算法雖然能有效縮短計算時間，減少壓縮誤差，但沒有考慮多實體間的整體優(yōu)化關(guān)系，會導致局部失真明顯。汪林林等[16]在動態(tài)規(guī)劃的基礎(chǔ)上進一步改進，設(shè)定閾值最大位移防止局部失真，有效地解決了曲線部分失真的問題，但由于時間復(fù)雜度依然過高，不適用大數(shù)據(jù)下的矢量軌跡壓縮。WEI等[17]設(shè)計了一種考慮軌跡空間和運動特征的算法。該算法能夠根據(jù)船舶行為特征對自動識別系統(tǒng)(Automatic Identification System,AIS)軌跡進行有效的壓縮，但算法中閾值參數(shù)不能自適應(yīng)確定，且計算復(fù)雜度過高。張?zhí)鸬萚18]利用分段處理的思想，在速度保留算法的基礎(chǔ)上提出基于速度分段的移動對象軌跡簡化處理算法。該算法將原曲線分割成不同的速度保留段，通過計算各段的同步歐氏距離閾值進一步處理曲線節(jié)點，實驗證明其效果好于速度保留算法。但是，該算法也是采用D-P算法簡化軌跡，時間復(fù)雜度還是O(n2)，不適用于大數(shù)據(jù)下的矢量軌跡壓縮。

為了進一步降低矢量軌跡壓縮算法的時間復(fù)雜度，提高算法的處理能力，擬提出余弦垂距判別(Cosine Vertical Distance Discrimination,CVDD)算法。首先，該算法借助D-P算法和垂距限值法的垂距思想，通過優(yōu)化角度限值法的角度判斷方式減少空間計算。其次，利用球面余弦定理降低球面上兩點間的距離誤差。最后，把待處理軌跡劃分為直道和彎道兩種軌跡，并對各路段中的中間元素進行求其與底邊線段上的垂距，將所得垂距與算法設(shè)定邊界垂距閾值進行對比，再對垂距值小的中間元素進行壓縮。最后,將該算法應(yīng)用到二次青藏科考線路、卡車和出租車真實軌跡數(shù)據(jù)集中進行壓縮實驗，以驗證所提算法的可行性和有效性。

1 預(yù)備知識

定義1球面坐標。地球表面上任意位置點P表示一個坐標對象P=(x,y,…)。其中：x表示位置所在的經(jīng)度；y表示位置所在的緯度。P可擴展多個屬性，如果移動物體在球面上運動，那么該物體在地球表面上t時刻的位置可以表示為Pt=(xt,yt,…)。

定義2矢量軌跡。運動物體在地球表面上按某種時間順序沿著任意方向移動，則該物體會在地球表面上形成一條軌跡，用Γ={P1,P2,…,Pn}表示。Γ是一個連續(xù)的序列集，軌跡Γ中的第i個軌跡點可表示為Γ[i]，或者Pi。

定義4球面距離。設(shè)球面上任意兩點PA(x1,y1)和PB(x2,y2)，兩點間距離為dAB，地球半徑為R，R≈6 370.856×103m，圓周率π=3.14，則可計算出PA的經(jīng)緯度角分別為

PB的經(jīng)緯度角分別為

進而得出PA和PB兩點之間的球面距離為

dAB=Rarccos[(cosβ1cosβ2cos (α1-α2)+sinβ1sinβ2)]

定義5三元組。在矢量軌跡集Γ中，按照時間順序依次序選取3個元素構(gòu)成的子序列為Γ{Pk,Pk+1,Pk+2}(0≤k

定義6球面三角形面積。假設(shè)球面上任意不同的3點為PA(x1,y1)，PB(x2,y2)和PC(x3,y3)。3點形成的球面上的三角形面積為S△ABC，則根據(jù)定義4和海倫公式可求得

其中，

于是，可根據(jù)所求面積S△ABC求得三角形任意邊對應(yīng)的垂直高度分別為

定義7球面三角余弦值。球面上任意不同3點PA(x1,y1)，PB(x2,y2)和PC(x3,y3)，設(shè)點PB與線段dBA和dBC所構(gòu)成夾角θB的余弦值為cosθB，則有

定義8壓縮率。假設(shè)原始曲線Γ中的元素總個數(shù)為n，壓縮后曲線中的個數(shù)是n′，壓縮率為η，則原始曲線的壓縮率為

其中,η越小，壓縮程度越大。反之，壓縮程度越小。

定義9最大位移。假設(shè)曲線上待壓縮點Pi與其前后兩點Pi-1和Pi+1所形成的線段的距離L為該待壓縮點Pi到壓縮后新曲線上的位移，則所有待壓縮點與其前后兩點所形成線段中位移最大的一個可設(shè)為Lmax。如圖1所示：P2為待壓縮點，則其與前后兩點P1和P3所形成線段的位移為L1；P7為待壓縮點，則其與前后兩點P6和P8所形成線段的位移為L2；P10也是待壓縮點，同理可以得到P10與前后兩點P9和P11所形成線段的位移為L3。通過對比可以得到位移最大的是L1。因此，所有待壓縮點與壓縮后新曲線上的最大位移的表達式為Lmax=max{L1,L2,L3}=L1。

圖1 最大位移示意圖

定義10位移之和。假設(shè)原始軌跡Γ中全部待壓縮點與其前后兩點所形成線段上位移的總和為S,則根據(jù)定義9可知

2 經(jīng)典壓縮算法

當前成熟的有損壓縮算法主要有垂距限值法、角度限值法以及經(jīng)典的D-P算法。這3種算法都需要預(yù)先設(shè)定一個可容忍的限差值d或θ，然后再將原始軌跡Γ劃分為一組組的三元組，通過對每組三元組進行節(jié)點間的距離計算或角度計算，把得到的距離d′或角度θ′分別與預(yù)設(shè)限差值進行對比判斷，保留值大于限差值的節(jié)點，壓縮值小于限差值的其他全部節(jié)點，從而達到矢量軌跡的有損壓縮。前兩種算法易于編程，操作簡單，處理速度快，時間復(fù)雜度都為O(n),但當遇到曲率較大的彎道或者連綿起伏的路段時，完全破壞了原始路線的形態(tài)要素，壓縮效果不佳。原始軌跡的形態(tài)要素被嚴重破壞情況如圖2曲線走勢所示。

圖2 原始軌跡的形態(tài)要素被嚴重破壞情況

第三種算法是一個從全局到局部的過程，通過不斷分割與遍歷查找，從中發(fā)現(xiàn)和保留分割后的每段曲線的完整形態(tài)要素，在很大程度上保證曲線的基本形狀不發(fā)生明顯改變。但是，時間復(fù)雜度較高，最大為O(n2)，當待處理軌跡節(jié)點過多時，需要耗費更多的處理時間。

2.1 垂距限值法

垂距限值法是一種沿著同一方向順序執(zhí)行的局部壓縮法。首先，設(shè)置一個可容忍的限差d，然后，從曲線的一端開始，每次順序選取3個點構(gòu)成三元組，構(gòu)建第一、三兩點間的直線，通過計算第二點d′到該直線的垂直距離，起點和終點除外，判斷d′與d的關(guān)系。如果d′

圖3 垂距限值法執(zhí)行過程

2.2 角度限值法

角度限制法和垂距限值法的處理方式類似，也需要預(yù)先定義一個可容忍的限差θ，從曲線一端逐次遍歷每個三元組，再進行每一步的角度值判斷。該算法是從曲線一端選取一對三元組，先將第二點和第三點分別與第一點連線，即起點和終點除外，計算兩線之間現(xiàn)成的夾角值為θ′。若θ′≥θ，則保留第二點，并以第二點為起點，繼續(xù)作第三、第四點與第二點之間的連線；否則壓縮第二點，并以第三點作為起點，重復(fù)以上工作，直到遍歷完成。角度限值法執(zhí)行過程如圖4所示。

圖4 角度限值法執(zhí)行過

2.3 D-P經(jīng)典算法

圖5 D-P算法執(zhí)行過程1

圖6 D-P算法執(zhí)行過程2

圖7 D-P算法執(zhí)行過程3

圖8 D-P算法執(zhí)行后最終壓縮效果

3 余弦垂距判別法

3.1 算法思想

為了彌補垂距限值法、角度限值法和D-P算法的共同不足之處，CVDD在對三元組處理時，把每組三元組分成兩種層面進行，在點層面對三元組中間元素的前后鄰邊距離作為首要條件。首先，識別三元組構(gòu)成為密集點集或稀疏點集。然后，過濾掉密集點集中間元素，在線層面先通過余弦值作為判斷條件將三元組按序連成的局部軌跡識別為曲直路段或彎道路段兩種情況。最后，再通過邊界垂距閾值dmax和dmin進行判斷是否壓縮各情況中三元組中的中間節(jié)點。整個處理過程考慮較為全面，進而將每一個不符合條件的中間元素進行壓縮。

處理結(jié)果會出現(xiàn)兩種極端情況，當閾值d非常大時，壓縮后的?！渲话瘘c和終點元素，壓縮率為η=2/n×100%，當閾值d過小時，又會出現(xiàn)壓縮率為100%，即一個元素也沒有壓縮。

3.2 算法步驟說明

步驟1先獲取原始矢量軌跡Γ，并以Γ構(gòu)建動態(tài)列表，設(shè)為Plist。

步驟2循環(huán)遍歷Plist，每次按序獲取一組三元組，并以該三元組上3個點Pi、Pi+1、Pi+2，構(gòu)建三角形，設(shè)為△ABC，并設(shè)其三角形三邊分別為a,b,c。

步驟3通過定義4分別計算△ABC的邊長a,b,c，若同時滿足a≤dmax，c≤dmax，則識別3點為密集點集路段，壓縮中間節(jié)點，并以Pi節(jié)點繼續(xù)承擔下次循環(huán)的起始點，循環(huán)繼續(xù)。否則，識別為稀疏點集路段，執(zhí)行下一步操作，其中，dmax取常量值，取值越大，原始軌跡處理后的失真程度越嚴重。因此，為了降低原始軌跡處理后的失真程度，實驗中設(shè)定垂距上限閾值dmax為3 m。

步驟4若步驟3判斷為稀疏點集路段，則通過步驟3所得三邊距離a,b,c分別與定義6和定義7計算的△ABC底邊上的高h和中間節(jié)點的余弦值cosB。如果cosB≤cosθ，則認為當前稀疏路段為曲直路段，包括直線。其中，cosθ是常量值，因為cos 180值為-1，為保留一定的誤差范圍，故取cosθ=-0.75。繼續(xù)使用底邊上的高h與dmax對比，若h≤dmax，則壓縮中間點，繼續(xù)以Pi為起始點，循環(huán)繼續(xù)。否則，保留中間點，并以中間點作為下次循環(huán)的起始點，循環(huán)繼續(xù)。

步驟5通過步驟4的判斷，如果cosB>cosθ，則認為當前的稀疏路段是彎道。將底邊上的高h與dmin進行對比，若h≤dmin，則直接壓縮中間節(jié)點，并以Pi繼續(xù)承擔起始點，循環(huán)繼續(xù)。否則，保留中間節(jié)點，以中間節(jié)點作為下次循環(huán)起始點，循環(huán)繼續(xù)，其中，dmin也是常量值，其取值越小，壓縮的坐標點數(shù)越少。因此，為了有效提高壓縮坐標點的數(shù)量，選取垂距下限閾值dmin為2 m。

環(huán)境溫度對礦化垃圾反應(yīng)床穩(wěn)態(tài)運行性能具有較大影響，主要表現(xiàn)在影響污染物去除性能及床體水力滲透性能2個方面。

步驟6持續(xù)步驟2～步驟4操作，直到算法遍歷完成，Plist中剩下的元素即為壓縮后的新數(shù)據(jù)集?！洹?/p>

3.3 復(fù)雜度分析

根據(jù)算法步驟易知，CVDD算法僅對矢量數(shù)據(jù)集進行一次掃描。因此，時間復(fù)雜度為O(n)，考慮在該算法操作中定義的都是常量值，空間復(fù)雜度為O(1)。

4 實例結(jié)果與分析

實驗共設(shè)3組真實數(shù)據(jù)集，分別是青藏科考數(shù)據(jù)集、北京出租車數(shù)據(jù)集以及北京卡車數(shù)據(jù)集，各組實驗數(shù)據(jù)集信息如表1所示。

表1 實驗數(shù)據(jù)集

4.1 實驗環(huán)境

實驗配置環(huán)境設(shè)定：硬件設(shè)備處理器為Intel(R) Core(TM) i7-8700 CPU @ 3.20 GHz 3.19 GHz，內(nèi)存條大小8 GB，硬盤大小500 GB,固態(tài)盤256 G；軟件為Window 10教育版64位，JDK1.8；開發(fā)工具為idea 2020.1,使用高德地圖；開發(fā)語言用Java。

4.2 實驗結(jié)果與分析

由于垂距限值法、角度限值法及D-P算法等都需要設(shè)置預(yù)先閾值。因此，在選取相同的限差值條件下，在同一臺電腦上進行3組實驗，每一組實驗中，都統(tǒng)計CVDD算法與對比3種算法，在隨著自變量即軌跡點數(shù)的變化所帶來的一系列因變量如執(zhí)行時間、壓縮坐標點數(shù)、壓縮前后位移的變化情況。最后，把4種算法分別在3組實驗中運行實驗，實驗數(shù)據(jù)匯總結(jié)果如表2所示，數(shù)據(jù)分析分別如圖9至圖17所示。

表2 垂距限值法與CVDD算法在3組實驗中的實驗結(jié)果

圖9 出租車組中不同算法的運行時間對比

圖10 出租車組中不同算法的運行時間合并對比

圖11 出租車組中不同算法的壓縮率對比

接下來對每一組實驗的折線圖進行對比討論。

1)在出租車組實驗中，通過圖9可知，隨著原始軌跡中坐標元素的數(shù)量增大，4種算法的處理速度也受到原始軌跡中線路的形態(tài)要素影響而波動。其中，D-P算法從箭頭指向的單位來看，使用時間最大，以107ms為單位，而其他的算法最大不超過800 ms。因此，從時間復(fù)雜度上判斷，D-P算法性能不好，執(zhí)行時間過長是因為其使用了大量的迭代操作。從圖10可以看出，角度限值法的處理速度比垂距限值法和CVDD算法的處理速度要略勝一籌。從圖11可以看出，隨著原始軌跡的坐標元素增大，角度限值法的壓縮效果反而不佳，壓縮率接近80%。根據(jù)定義8可知，壓縮比越大，壓縮程度越不好，而其他3種算法的壓縮率比走勢基本一致。但是，從菱形組合線可以看出，所提的CVDD算法的壓縮效果最佳。

圖12 卡車組中不同算法的運行時間對比

圖13 卡車組中不同算法的運行時間合并對比

2) 在卡車組實驗中，通過圖12可知，隨著原始軌跡中坐標元素的數(shù)量增大，4種算法的處理速度也會受原始軌跡中線路的形態(tài)要素影響而波動。通過圖13可知，角度限值法處理速度快，但通過圖14可知，角度限制法的壓縮率最大，壓縮程度不佳，CVDD算法的壓縮率最小，壓縮程度最佳。

圖14 卡車組中不同算法的壓縮率對比

圖15 科考組中不同算法的運行時間對比

3) 在科考組實驗中，通過圖15和圖16可以看出，4種算法的壓縮速度也隨著科考線路的形態(tài)要素變化而波動。除D-P算法外，其他3種算法的執(zhí)行時間都在130 ms以內(nèi)。從圖17可以看出，CVDD算法的壓縮效率也是最佳的。

圖16 科考組中不同算法的運行時間合并對比

圖17 科考組中不同算法的壓縮率對比

4.3 評價指標分析

矢量軌跡壓縮算法評價指標可分為效率指標和精度指標。前者主要指壓縮效率和執(zhí)行效率即運行時間，后者包括如最大位移、位移之和、位移平均誤差、位移標準差、面積偏差等多個方面。因此，將對CVDD算法進行不同的指標分析。

4.3.1 算法效率評價指標分析

根據(jù)實驗結(jié)果顯示，如圖9和圖10、圖12和圖13、圖15和圖16可知，隨著原始坐標點的量不斷增加，每組的執(zhí)行時間在不斷上升，前3種算法都是保持線性緩慢的增長，而 D-P算法的執(zhí)行時間急劇上升。從圖9和圖12中的第四現(xiàn)象子圖的y軸刻度可知，D-P的執(zhí)行時間是107ms。由圖10和圖13可以看出，角度限值法執(zhí)行時間較少，而垂距限值法和CVDD算法的執(zhí)行時間稍微高一些，但3種算法的執(zhí)行時間都在可控和可容忍時間范圍內(nèi)。垂距限值法和CVDD算法的執(zhí)行時間走勢基本一致，但從整體看來，CVDD算法比垂距限值法在執(zhí)行時間上較為穩(wěn)定。

在3組實驗中，從原始坐標數(shù)與執(zhí)行時間關(guān)系來看，角度限值法的處理速度最快，但通過圖11、圖14和圖17可以看出，角度限值法的壓縮效果最不佳，垂距限值法和CVDD算法的壓縮效果最佳，D-P算法的壓縮效果次之。通過對各種算法在3組實驗中的運行時間和壓縮率計算平均值，得出各種算法在3組實驗中的平均執(zhí)行時間和平均壓縮率，具體如圖18至圖19所示。

圖18 不同算法在相同實驗中的平均運行時間對比

圖19 不同算法在相同實驗中的平均壓縮率對比

從圖18和圖19可以看出，CVDD算法的平均執(zhí)行時間基本上比其他幾種算法快，平均壓縮率也比其他幾種算法優(yōu)，且比垂距限值法的平均壓縮率優(yōu)3～7個百分點。因此，CVDD算法與其他幾種算法對比具有較好的壓縮效率和執(zhí)行效率。

4.3.2 算法精度評價指標分析

通過算法效率評價指標分析初步得出，CVDD算法具有較好的壓縮效率和執(zhí)行效率。需要強調(diào)的是，壓縮率是在壓縮效果有效的范圍內(nèi)衡量，不能因為過度追求壓縮率而導致壓縮后線路失真。因此，需進一步對各算法進行精度上的評價指標分析。對3組真實軌跡數(shù)據(jù)集進一步實驗取證，對每組軌跡數(shù)據(jù)集各隨機選取部分路線繼續(xù)實驗，得出實驗結(jié)果如表2所示。通過表2中數(shù)據(jù)進行求平均位移計算，得出垂距限值法與CVDD算法在3組實驗中的平均位移如表3所示。

表3 垂距限值法與CVDD算法在3組實驗中的平均位移

由表3可知，CVDD算法在3組實驗中，位移平均誤差分別是0.01 m，0.08 m和0.01 m，精確到厘米級別，而垂距限值法的位移平均誤差分別是0.84 m，0.43 m和0.07 m，基本上只能精確到分米級別。因此，進一步證明CVDD算法的壓縮效率和壓縮效果要比垂距限值法優(yōu)。

5 結(jié)語

在矢量軌跡數(shù)據(jù)處理中，為了獲得有效的軌跡數(shù)據(jù)，提出了一種矢量軌跡有損壓縮CVDD算法。該算法使用球面距離公式有效地避免了傳統(tǒng)算法中通過平面歐式距離公式計算所帶來的實際距離誤差。將三元組進一步識別為密集點集與稀疏點集，不僅能有效地壓縮彎道中的大量稠密節(jié)點，還能有效地避免破壞原始軌跡中的形態(tài)要素。使用余弦值替代角度值作為判斷條件，能夠有效地減少節(jié)點間空間上的計算成本，加快算法的處理速度。同時，使用邊界垂距閾值(dmin，dmax)能夠更加精準地判斷是否壓縮當前待處理的中間節(jié)點，并比傳統(tǒng)算法中使用單一的垂距閾值d或θ更為靈活。最后，將該算法應(yīng)用到3組真實的軌跡線路中進行實驗測試。實驗結(jié)果表明，無論從算法效率評價指標分析，還是從算法的精度評價指標進行對比分析，CVDD算法的執(zhí)行時間和處理效果都優(yōu)于其他幾種傳統(tǒng)的壓縮算法。

CVDD算法是從原始軌跡的一端出發(fā)，逐步遍歷連續(xù)的每一組三元組數(shù)據(jù)，其不僅可以處理離線的矢量數(shù)據(jù)，還能處理實時的在線矢量數(shù)據(jù)?？紤]算法中使用的計算公式都可以延伸到多維空間中，CVDD算法還可擴展到多維空間的軌跡壓縮中。