摘  要： 基于PLAZA和高斯圖像濾波，研究了帶有定位誤差的移動(dòng)對(duì)象軌跡化簡(jiǎn)算法。所設(shè)計(jì)的算法主要應(yīng)用于移動(dòng)終端設(shè)備，能夠?qū)Χㄎ辉O(shè)備采集到的移動(dòng)對(duì)象原始軌跡數(shù)據(jù)進(jìn)行簡(jiǎn)化，降低移動(dòng)終端的通信代價(jià)和計(jì)算開銷，提高軌跡數(shù)據(jù)的使用效率和價(jià)值。算法按照時(shí)間序列的處理思想，同時(shí)利用信號(hào)去噪的方法對(duì)原始的定位信號(hào)進(jìn)行濾波，可以達(dá)到降低誤差影響和減小數(shù)據(jù)冗余的效果。然后按照PLAZA算法的思想進(jìn)行化簡(jiǎn)。實(shí)驗(yàn)結(jié)果證實(shí)該算法具有較好的化簡(jiǎn)率和較快的處理速度，實(shí)際應(yīng)用表明該算法有較好實(shí)用價(jià)值。

　　關(guān)鍵詞： 移動(dòng)對(duì)象；實(shí)時(shí)軌跡化簡(jiǎn)；定位誤差；濾波

0 引言

　　隨著汽車、輪船及手持設(shè)備等移動(dòng)對(duì)象數(shù)量的增加，移動(dòng)位置信息也隨之飛速增長(zhǎng)。這些位置信息作為一種無限的數(shù)據(jù)流通過無線網(wǎng)絡(luò)發(fā)送到中央數(shù)據(jù)庫中，大量對(duì)象頻繁更新位置信息時(shí)，海量的數(shù)據(jù)將會(huì)以一種無法預(yù)測(cè)的高頻率傳送到中央處理器進(jìn)行處理，這對(duì)于傳統(tǒng)的數(shù)據(jù)庫管理系統(tǒng)來說是無法處理的。因此，通常需要對(duì)其進(jìn)行壓縮處理。

　　移動(dòng)對(duì)象軌跡化簡(jiǎn)問題作為移動(dòng)對(duì)象數(shù)據(jù)庫研究領(lǐng)域的重要分支之一，對(duì)于高效地管理和分析移動(dòng)對(duì)象數(shù)據(jù)有著至關(guān)重要的影響。在實(shí)際應(yīng)用中，由于定位系統(tǒng)存在定位誤差，很多廉價(jià)的定位裝置會(huì)在不利的環(huán)境產(chǎn)生不可忽視的誤差。針對(duì)此問題本文基于PLAZA方法和高斯濾波提出一種實(shí)時(shí)移動(dòng)軌跡化簡(jiǎn)方法（GPlaza），它的思想是針對(duì)具有較大誤差的定位裝置，首先對(duì)原始測(cè)量數(shù)據(jù)進(jìn)行高斯濾波，以減小GPS定位誤差的影響，然后構(gòu)建合理的誤差區(qū)域?qū)罄m(xù)的軌跡點(diǎn)進(jìn)行過濾化簡(jiǎn)。

1 問題建模

　　1.1 移動(dòng)對(duì)象軌跡模型

　　移動(dòng)對(duì)象軌跡化簡(jiǎn)就是從組成曲線的點(diǎn)序集合O中抽取一個(gè)點(diǎn)序集合O′，用這個(gè)子集作為一個(gè)新的信息源，在規(guī)定的精度范圍內(nèi)，該子集從內(nèi)容上盡可能地反映原子集O，而在數(shù)量上則盡可能地精簡(jiǎn)，即壓縮比盡可能的小。進(jìn)行矢量數(shù)據(jù)壓縮的核心是在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)原始采集數(shù)據(jù)進(jìn)行合理刪減[1]。

　　理論上，通常將移動(dòng)對(duì)象O的軌跡表示為三維空間中的一條折線。三維空間中的兩個(gè)維和空間相關(guān)，第三維是時(shí)間；即Oi={xi，yi，ti}。為了簡(jiǎn)化計(jì)算復(fù)雜性需要將三維空間的折線投影到二維空間平面上。

　　1.2 定位方法原理及誤差分析

　　衛(wèi)星導(dǎo)航接收機(jī)是通過接收衛(wèi)星廣播的星歷信息，獲取信號(hào)的傳播時(shí)間從而解算接收機(jī)坐標(biāo)[2]。在信號(hào)發(fā)送、傳輸和接收等環(huán)節(jié)存在著各種干擾和誤差，如測(cè)量同步誤差、多徑傳輸和各種噪聲干擾。從來源上來說誤差可以分為四類：與衛(wèi)星有關(guān)的誤差、與信號(hào)傳播有關(guān)的誤差、與接收機(jī)有關(guān)的誤差以及地球潮汐、負(fù)荷潮等造成的其他誤差。而與信號(hào)傳播有關(guān)的誤差包括電離層折射誤差、對(duì)流程折射誤差及多徑效應(yīng)誤差。GPS定位誤差由以下公式近似表示[3]：

　　其中為GPS定位標(biāo)準(zhǔn)偏差，?滓UERE為偽距測(cè)量的標(biāo)準(zhǔn)偏差，GDOP為幾何精度衰減因子（Geometric Dilution of Precision）。因此，對(duì)于一個(gè)特定地域來說，定位誤差并不是固定的，可以看作符合標(biāo)準(zhǔn)正態(tài)分布。

2 相關(guān)工作

　　移動(dòng)對(duì)象軌跡的化簡(jiǎn)方法主要使用線性推測(cè)，利用垂距閾值、角度限定和混合區(qū)域過濾三種思想進(jìn)行化簡(jiǎn)。

　　垂距閾值算法通常使用線性預(yù)測(cè)為應(yīng)用場(chǎng)景，通過引入最大偏離誤差閾值對(duì)顯著軌跡進(jìn)行識(shí)別[4]。比較早也是目前最通用的算法是Douglas-Peucker算法[5]。隨之產(chǎn)生了很多實(shí)時(shí)算法，如線性外推（LEx）算法和連接-保持推測(cè)算法（CDRM）等。

　　角度限定通過定義方向向量在一定誤差范圍的角度對(duì)移動(dòng)對(duì)象方向誤差進(jìn)行限定，若方向偏差超過限定值則進(jìn)行更新。線性分段化簡(jiǎn)方法（Piecewise Linear Approximation）是一個(gè)針對(duì)時(shí)間序列的有效壓縮方法[6]。PLAZA通過分區(qū)角度（Zoing Angle）來判斷軌跡是否保留，并較早用于以無限時(shí)間序列方式生成的數(shù)據(jù)流的壓縮問題上，可以形式化地處理二維數(shù)據(jù)。NPLAZA結(jié)合移動(dòng)對(duì)象的軌跡特點(diǎn)，將其拓展為三維坐標(biāo)（二維空間和一維為時(shí)間）下的點(diǎn)的軌跡。如圖1所示。

　　混合區(qū)域過濾算法結(jié)合垂距和角度兩個(gè)方面構(gòu)造安全區(qū)域，根據(jù)待測(cè)點(diǎn)所處位置決定點(diǎn)的取舍?；陂撝档某闃铀惴ǎ═PG）作為典型的區(qū)域過濾算法，通過給定的閾值和已知信息（包括過去軌跡點(diǎn)的位置、速度和方向等），構(gòu)建下一個(gè)軌跡點(diǎn)的安全區(qū)域（SA），然后判斷是否保存該軌跡點(diǎn)。

　　以上軌跡化簡(jiǎn)算法都是針對(duì)精確的數(shù)據(jù)所做的化簡(jiǎn)，而實(shí)際應(yīng)用中，精確的定位設(shè)備往往比較昂貴，因此使用相比較少；而大部分使用的是廉價(jià)的定位裝置，由此產(chǎn)生的帶有較大誤差的位置信息會(huì)在很大程度上影響化簡(jiǎn)算法結(jié)果的準(zhǔn)確性和壓縮率，因此產(chǎn)生了考慮定位誤差的移動(dòng)對(duì)象化簡(jiǎn)算法。參考文獻(xiàn)[7]提出了一種基于MBR的實(shí)時(shí)軌跡化簡(jiǎn)算法，該算法通過一套針對(duì)標(biāo)準(zhǔn)最小邊界矩形的分割/合并操作以及選擇策略來對(duì)空間軌跡數(shù)據(jù)進(jìn)行化簡(jiǎn)。參考文獻(xiàn)[8]經(jīng)過研究改進(jìn)了MBR算法：采用最小包圍扇形來近似化簡(jiǎn)其移動(dòng)軌跡，提升了算法效率并減小了偏移誤差。如圖2所示。

3 方法提出

　　3.1 目前算法分析

　　對(duì)于無定位誤差數(shù)據(jù)的實(shí)時(shí)軌跡方法已經(jīng)有較好的研究，如上面提到的線性化簡(jiǎn)、TPG算法和NPLAZA算法等。其中PLAZA算法簡(jiǎn)化率和誤差范圍在相同復(fù)雜度的算法中已接近最優(yōu)。而針對(duì)考慮定位誤差的實(shí)時(shí)化簡(jiǎn)算法目前還較少。根據(jù)目前所知，有MBR和改進(jìn)的MBS算法等，相比之下MBS在實(shí)際應(yīng)用中有較好的效果。但是實(shí)際應(yīng)用中MBS的化簡(jiǎn)率為50%左右，對(duì)于存在較大誤差、速度較慢的移動(dòng)對(duì)象，其化簡(jiǎn)結(jié)果不甚理想。

　　考慮到相鄰移動(dòng)對(duì)象軌跡點(diǎn)之間的相關(guān)性非常大，且定位誤差是一種服從高斯分布的隨機(jī)誤差，即白噪聲，由于高斯濾波對(duì)隨機(jī)噪聲有良好處理效果[9]，本文使用高斯濾波器對(duì)誤差定位信號(hào)進(jìn)行預(yù)處理，用于減小誤差。雖然誤差不可避免，但利用濾波處理后的數(shù)據(jù)可以有效減小誤差的影響，對(duì)軌跡進(jìn)行平滑。然后考慮NPLAZA算法對(duì)軌跡數(shù)據(jù)處理具有高效性和很好的處理結(jié)果，對(duì)數(shù)據(jù)運(yùn)用NPLAZA算法進(jìn)行化簡(jiǎn)和存儲(chǔ)，具體方法如下。

　　首先，對(duì)象從發(fā)出定位信息開始，根據(jù)設(shè)定的濾波模板大小n，前n-1個(gè)點(diǎn)不做處理；從第n個(gè)更新點(diǎn)開始，每次更新時(shí)對(duì)之前的n個(gè)點(diǎn)進(jìn)行高斯變換，結(jié)果作為新的第n/2個(gè)數(shù)據(jù)，然后判斷是否更新。具體實(shí)現(xiàn)方法如下：對(duì)于已知的兩個(gè)軌跡點(diǎn)Pi，Pj，先計(jì)算出其劃分角度，當(dāng)下一時(shí)刻k的軌跡點(diǎn)Pk的位置信息到來時(shí)計(jì)算，并且結(jié)合給定的距離誤差閾值δ以及時(shí)間差k-j與時(shí)刻j處的瞬時(shí)速度vk計(jì)算出來的距離范圍共同構(gòu)建安全區(qū)域SA，若Pk在SA范圍內(nèi)則將軌跡點(diǎn)Pk忽略，并執(zhí)行進(jìn)一步縮小劃分角度的范圍；否則將Pk-1以及Pk作為新的起點(diǎn)。如圖1所示。

　　算法描述如下：

　　輸入：角度閾值ε、距離閾值δ以及原始序列O；

　　輸出：簡(jiǎn)化序列S。

　　算法流程：

　　i=1；；j=3；

　　FOR EACH（Pj in O）DO

　　Pj=filter（n）{

　　Template[n]=[a，b，c，...]；

　　Pj={Pj-1*template[0]+Pj*template[1]+…

　　+Pj+1*template[n-1]}/sum（template）；}；

　　oangle=angle

　　angle=angle∩；

　　distant=||Pj-1，Pj||；

　　sdistant=Pj-1.vt*（Pj.t-Pj-1.t）；

　　IF（（angle!=0）&&（ABS（sdistant-distant）<=δ））

　　THEN j=j+1；

　　ELSE

　　output Pj And oangle；

　　i=j-1；

　　angle=；

　　j=j+1；

　　END IF

　　END FOR

　　3.2 定位誤差情況分類

　　由于定位誤差的不確定性，例如隨著接收裝置精度或者所處環(huán)境的不同，接收裝置定位的誤差可能有很大變化：目前正常狀態(tài)手持設(shè)備和車載系統(tǒng)的定位誤差是10 m左右，而環(huán)境差異較大時(shí)可能是50 m甚至是幾百米。借助基站定位對(duì)GPS定位的補(bǔ)充，會(huì)對(duì)定位產(chǎn)生一定的幫助，但并沒有解決定位裝置的誤差對(duì)化簡(jiǎn)算法的影響。而誤差的大小對(duì)算法化簡(jiǎn)的結(jié)果是不一樣的，比如對(duì)于可認(rèn)為是精確定位的點(diǎn)，若使用高斯濾波將影響數(shù)據(jù)的可靠性，而對(duì)于超出可以接受的誤差進(jìn)行濾波又會(huì)降低數(shù)據(jù)的精確度。因此本文使用一種對(duì)誤差進(jìn)行自適應(yīng)判斷的方法。首先對(duì)誤差進(jìn)行范圍劃分：確定一個(gè)閾值δ1使之作為精確定位數(shù)據(jù)和有誤差數(shù)據(jù)的分界線。然后對(duì)精確定位數(shù)據(jù)的處理時(shí)利用簡(jiǎn)單的PLAZA算法進(jìn)行化簡(jiǎn)，而對(duì)可處理的誤差數(shù)據(jù)首先利用高斯濾波進(jìn)行預(yù)處理，之后利用PLAZA算法（即GPlaza算法）進(jìn)行化簡(jiǎn)。

4 實(shí)驗(yàn)分析及估計(jì)

　　4.1 算法性能分析

　　實(shí)驗(yàn)選取臺(tái)式電腦作為測(cè)試硬件平臺(tái)，具體配置為：Pentium（R）Dual-Core CPU E5500@2.80 GHz，內(nèi)存為2 GB；軟件環(huán)境為Windows 7操作系統(tǒng)和Eclipse開發(fā)環(huán)境。實(shí)驗(yàn)數(shù)據(jù)是從項(xiàng)目INFATI（INtelligent FArtTIlpasning）[10]得到。INFATI的位置數(shù)據(jù)信息是從2001年2月到3月期間，從9輛行駛在丹麥的汽車中采集得到的。為了更好地分析各個(gè)算法，本文定義了以下參數(shù)：

　　化簡(jiǎn)率：是指矢量數(shù)據(jù)壓縮后的數(shù)據(jù)量與壓縮前的數(shù)據(jù)量之比。

　　線段空間偏移：某一時(shí)刻實(shí)際簡(jiǎn)化結(jié)果與定位結(jié)果之間的距離與設(shè)置誤差閾值的比值。

　　相對(duì)誤差：是指壓縮后新生成的線段與被壓縮的曲線在空間的偏移量，使用實(shí)際簡(jiǎn)化結(jié)果與定位結(jié)果之間的距離與實(shí)際相鄰兩個(gè)定位結(jié)果之間的距離比值。

　　化簡(jiǎn)率是數(shù)據(jù)壓縮算法的數(shù)量指標(biāo)，追求較小的壓縮比是進(jìn)行數(shù)據(jù)壓縮算法設(shè)計(jì)的根本出發(fā)點(diǎn)，線段空間偏移和相對(duì)誤差控制是數(shù)據(jù)壓縮的質(zhì)量指標(biāo)（越小越好），一個(gè)好的壓縮算法應(yīng)該是結(jié)合實(shí)際需求，對(duì)以上3個(gè)指標(biāo)進(jìn)行最大限度的平衡。

　　首先對(duì)上文中算法的時(shí)間復(fù)雜度和空間復(fù)雜度進(jìn)行比較，如表1所示，其中n為軌跡點(diǎn)的數(shù)量，m為給定的存儲(chǔ)空間的大小。結(jié)果顯示，GPlaza算法和大多數(shù)實(shí)時(shí)算法一樣，可以在線性時(shí)間內(nèi)結(jié)束。

　　接下來利用上述實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)平臺(tái)，使用Java編程語言來實(shí)現(xiàn)算法，從簡(jiǎn)化率、線段空間偏移、測(cè)評(píng)角度以及運(yùn)行時(shí)間四個(gè)方面以量化類的指標(biāo)來比較分析這7種算法的性能特點(diǎn)，其結(jié)果如圖3所示。從圖中可以看出，GPlaza算法的化簡(jiǎn)率在比較的算法中有很大的優(yōu)勢(shì)；但由于GPlaza算法的濾波特性，使得其空間偏移較大，而對(duì)于有較大定位誤差的數(shù)據(jù)，較大的相對(duì)誤差不一定是壞事；而GPlaza算法擁有相對(duì)較好的相對(duì)誤差和較快的處理速度。因此，綜合來說，GPlaza算法有著較好的綜合性能。

　　4.2 實(shí)際應(yīng)用化簡(jiǎn)結(jié)果分析

　　實(shí)際應(yīng)用選取HTC5088手機(jī)為測(cè)試平臺(tái)，具體配置

如下：CPU型號(hào)：Spreadtrum（展訊）Shark（4核Cortex-A7架構(gòu)）；CPU頻率：1 024 MHz；RAM容量：512 MB；操作系統(tǒng)：Android OS 4.1.2。Android應(yīng)用開發(fā)中利用百度地圖Android SDK v3.2.0應(yīng)用程序開發(fā)包進(jìn)行定位和顯示。

　　本文記錄了三次實(shí)驗(yàn)的記錄，應(yīng)用場(chǎng)景分別是：（1）行走于上海海事大學(xué)內(nèi)的行人（平均速度是7~10 km/s）；（2）行進(jìn)于上海市臨港區(qū)的公交車（平均速度為50 km/s）；（3）運(yùn)行中的上海地鐵16號(hào)線（平均速度為80~100 km/s）。實(shí)驗(yàn)記錄如表2。

　　由于正常情況下GPS系統(tǒng)的誤差是10 m，因此本文采用15 m作為精確定位數(shù)據(jù)和有誤差數(shù)據(jù)的分界線。本次實(shí)驗(yàn)選取的定位采樣頻率為10 s，誤差閾值設(shè)置為20 m或30 m不等，圖4顯示的是上述實(shí)驗(yàn)結(jié)果的軌跡結(jié)果（其中細(xì)實(shí)線段為原始軌跡，粗實(shí)折線為簡(jiǎn)化后的軌跡）。實(shí)驗(yàn)結(jié)果表明：本文使用的算法有較好的化簡(jiǎn)率，從圖中可以看出簡(jiǎn)化后的軌跡與原始軌跡重合較好，線段空間偏移較小。綜合來看，對(duì)于高速運(yùn)動(dòng)的對(duì)象，GPlaza算法化簡(jiǎn)壓縮率較好，而低速運(yùn)動(dòng)的對(duì)象壓縮率稍差，而線段空間偏移都較小。需要說明的是，由于地鐵通常運(yùn)行于地下，獲取不到衛(wèi)星定位信息，只能采用WiFi或基站定位，從而使定位偏差極度擴(kuò)大，繼而嚴(yán)重影響軌跡精度。

5 總結(jié)

　　移動(dòng)對(duì)象軌跡有其獨(dú)特的方面，比如數(shù)據(jù)的多維性、信號(hào)的連續(xù)和冗余性、測(cè)量數(shù)據(jù)存在誤差等。針對(duì)這些特點(diǎn)，本文將信號(hào)濾波的思想運(yùn)用到移動(dòng)對(duì)象數(shù)據(jù)化簡(jiǎn)算法上，結(jié)合時(shí)間序列處理的方法，提出了基于高斯濾波的角度分區(qū)線性化簡(jiǎn)算法。由于高斯濾波在去噪方面的良好表現(xiàn)，該算法在處理針對(duì)GPS定位誤差的定位數(shù)據(jù)時(shí)顯現(xiàn)出很大的優(yōu)勢(shì)。在實(shí)際應(yīng)用中，加上合適的濾波模板和閾值設(shè)定，得到了較好的應(yīng)用。實(shí)驗(yàn)表明，該算法有高效的軌跡化簡(jiǎn)性能，并且得到的簡(jiǎn)化軌跡與原始軌跡之間的誤差穩(wěn)定可控。由于在某些環(huán)境（室內(nèi)或地下），不能獲得定位信息，因此會(huì)導(dǎo)致軌跡信息失準(zhǔn)，因此如何對(duì)無效軌跡進(jìn)行判定和修復(fù)，如何利用較少的簡(jiǎn)化軌跡更好地重建和檢索歷史軌跡，以及如何更好地預(yù)測(cè)未來軌跡將是以后的工作重點(diǎn)。

參考文獻(xiàn)

　　[1] 米學(xué)軍，盛廣銘，張婧，等.GIS中面積偏差控制下的矢量數(shù)據(jù)壓縮算法[J].地理學(xué)報(bào)，2012（10）：1236-1240.

　　[2] 趙琳，丁繼成，馬雪飛.衛(wèi)星導(dǎo)航原理與應(yīng)用[M].西安：西北工業(yè)大學(xué)出版社，2011.

　　[3] 袁建平，羅建軍，岳曉奎.衛(wèi)星導(dǎo)航原理與應(yīng)用[M].北京：宇航出版社，2003.

　　[4] 張達(dá)夫，張昕明.基于時(shí)空特性的ＧＰＳ軌跡數(shù)據(jù)壓縮算法[J].交通信息與安全，2013，6（31）：6-9.

　　[5] 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 and Geovisualization， 1973，10（2）：112-122.

　　[6] SOROUSH E， WU K， PEI J. Fast and quality-guaranteed data streaming in resource-constrained sensor networks[C]. In Proceedings of the 9th ACM International Symposium on Mobile ad Hoc Networking and Computing， ACM，2008：391-400.

　　[7] GUANGWEN L， MASAYUKI I， KAORU S. An online method for trajectory simplification under uncertainty of GPS[J]. 情報(bào)處理學(xué)會(huì)論文誌. データベース， 2013， 6（3）： 40-49.

　　[8] 王欣然，楊智應(yīng).基于MBS的移動(dòng)對(duì)象軌跡實(shí)時(shí)化簡(jiǎn)算法[J].計(jì)算機(jī)應(yīng)用，2014，34（8）：2409-2414.

　　[9] 李惠芬，蔣向前，李柱.高斯濾波穩(wěn)健性能的研究與改進(jìn)[J].儀器儀表學(xué)報(bào)，2004，25（5）：633-637.

　　[10] JENSEN C S， LAHRMANN H， PAKALNIS S， et al. The INFATI data[M]. arXiv preprint cs/0410001， 2004.