矢量軌跡有損壓縮余弦垂距判別法

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

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

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

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

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

進(jìn)而得出PA和PB兩點(diǎn)之間的球面距離為

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

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

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

其中，

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

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

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

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

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

圖1 最大位移示意圖

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

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

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

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

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

2.1 垂距限值法

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

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

2.2 角度限值法

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

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

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

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

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

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

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

3 余弦垂距判別法

3.1 算法思想

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

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

3.2 算法步驟說(shuō)明

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

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

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

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

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

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

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

3.3 復(fù)雜度分析

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)集

4.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

圖9 出租車(chē)組中不同算法的運(yùn)行時(shí)間對(duì)比

圖10 出租車(chē)組中不同算法的運(yùn)行時(shí)間合并對(duì)比

圖11 出租車(chē)組中不同算法的壓縮率對(duì)比

接下來(lái)對(duì)每一組實(shí)驗(yàn)的折線圖進(jìn)行對(duì)比討論。

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

圖12 卡車(chē)組中不同算法的運(yùn)行時(shí)間對(duì)比

圖13 卡車(chē)組中不同算法的運(yùn)行時(shí)間合并對(duì)比

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

圖14 卡車(chē)組中不同算法的壓縮率對(duì)比

圖15 科考組中不同算法的運(yùn)行時(shí)間對(duì)比

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

圖16 科考組中不同算法的運(yùn)行時(shí)間合并對(duì)比

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

4.3 評(píng)價(jià)指標(biāo)分析

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

4.3.1 算法效率評(píng)價(jià)指標(biāo)分析

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

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

圖18 不同算法在相同實(shí)驗(yàn)中的平均運(yùn)行時(shí)間對(duì)比

圖19 不同算法在相同實(shí)驗(yàn)中的平均壓縮率對(duì)比

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

4.3.2 算法精度評(píng)價(jià)指標(biāo)分析

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

表3 垂距限值法與CVDD算法在3組實(shí)驗(yàn)中的平均位移

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

5 結(jié)語(yǔ)

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

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