摘  要： 基于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ì)算開(kāi)銷，提高軌跡數(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)。這些位置信息作為一種無(wú)限的數(shù)據(jù)流通過(guò)無(wú)線網(wǎng)絡(luò)發(fā)送到中央數(shù)據(jù)庫(kù)中,，大量對(duì)象頻繁更新位置信息時(shí),，海量的數(shù)據(jù)將會(huì)以一種無(wú)法預(yù)測(cè)的高頻率傳送到中央處理器進(jìn)行處理，這對(duì)于傳統(tǒng)的數(shù)據(jù)庫(kù)管理系統(tǒng)來(lái)說(shuō)是無(wú)法處理的,。因此,，通常需要對(duì)其進(jìn)行壓縮處理。

　　移動(dòng)對(duì)象軌跡化簡(jiǎn)問(wèn)題作為移動(dòng)對(duì)象數(shù)據(jù)庫(kù)研究領(lǐng)域的重要分支之一,，對(duì)于高效地管理和分析移動(dòng)對(duì)象數(shù)據(jù)有著至關(guān)重要的影響,。在實(shí)際應(yīng)用中，由于定位系統(tǒng)存在定位誤差,，很多廉價(jià)的定位裝置會(huì)在不利的環(huán)境產(chǎn)生不可忽視的誤差,。針對(duì)此問(wèn)題本文基于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)行過(guò)濾化簡(jiǎn),。

1 問(wèn)題建模

　　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ī)是通過(guò)接收衛(wèi)星廣播的星歷信息，獲取信號(hào)的傳播時(shí)間從而解算接收機(jī)坐標(biāo)[2],。在信號(hào)發(fā)送、傳輸和接收等環(huán)節(jié)存在著各種干擾和誤差，如測(cè)量同步誤差,、多徑傳輸和各種噪聲干擾,。從來(lái)源上來(lái)說(shuō)誤差可以分為四類：與衛(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è)特定地域來(lái)說(shuō),，定位誤差并不是固定的,，可以看作符合標(biāo)準(zhǔn)正態(tài)分布。

2 相關(guān)工作

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

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

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

　　混合區(qū)域過(guò)濾算法結(jié)合垂距和角度兩個(gè)方面構(gòu)造安全區(qū)域，根據(jù)待測(cè)點(diǎn)所處位置決定點(diǎn)的取舍,?；陂撝档某闃铀惴ǎ═PG）作為典型的區(qū)域過(guò)濾算法，通過(guò)給定的閾值和已知信息（包括過(guò)去軌跡點(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)算法,，該算法通過(guò)一套針對(duì)標(biāo)準(zhǔn)最小邊界矩形的分割/合并操作以及選擇策略來(lái)對(duì)空間軌跡數(shù)據(jù)進(jìn)行化簡(jiǎn)。參考文獻(xiàn)[8]經(jīng)過(guò)研究改進(jìn)了MBR算法：采用最小包圍扇形來(lái)近似化簡(jiǎn)其移動(dòng)軌跡,，提升了算法效率并減小了偏移誤差,。如圖2所示。

3 方法提出

　　3.1 目前算法分析

　　對(duì)于無(wú)定位誤差數(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ā)出定位信息開(kāi)始,，根據(jù)設(shè)定的濾波模板大小n,，前n-1個(gè)點(diǎn)不做處理；從第n個(gè)更新點(diǎn)開(kāi)始,，每次更新時(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的位置信息到來(lái)時(shí)計(jì)算，并且結(jié)合給定的距離誤差閾值δ以及時(shí)間差k-j與時(shí)刻j處的瞬時(shí)速度vk計(jì)算出來(lái)的距離范圍共同構(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)生一定的幫助,，但并沒(méi)有解決定位裝置的誤差對(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 [email protected] GHz,，內(nèi)存為2 GB,；軟件環(huán)境為Windows 7操作系統(tǒng)和Eclipse開(kāi)發(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é)束,。

　　接下來(lái)利用上述實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)平臺(tái)，使用Java編程語(yǔ)言來(lái)實(shí)現(xiàn)算法,，從簡(jiǎn)化率,、線段空間偏移,、測(cè)評(píng)角度以及運(yùn)行時(shí)間四個(gè)方面以量化類的指標(biāo)來(lái)比較分析這7種算法的性能特點(diǎn)，其結(jié)果如圖3所示,。從圖中可以看出,，GPlaza算法的化簡(jiǎn)率在比較的算法中有很大的優(yōu)勢(shì)；但由于GPlaza算法的濾波特性,，使得其空間偏移較大,，而對(duì)于有較大定位誤差的數(shù)據(jù)，較大的相對(duì)誤差不一定是壞事,；而GPlaza算法擁有相對(duì)較好的相對(duì)誤差和較快的處理速度,。因此，綜合來(lái)說(shuō),，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)用開(kāi)發(fā)中利用百度地圖Android SDK v3.2.0應(yīng)用程序開(kāi)發(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)化后的軌跡與原始軌跡重合較好,，線段空間偏移較小,。綜合來(lái)看，對(duì)于高速運(yùn)動(dòng)的對(duì)象,，GPlaza算法化簡(jiǎn)壓縮率較好,，而低速運(yùn)動(dòng)的對(duì)象壓縮率稍差，而線段空間偏移都較小,。需要說(shuō)明的是,，由于地鐵通常運(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ì)無(wú)效軌跡進(jìn)行判定和修復(fù),，如何利用較少的簡(jiǎn)化軌跡更好地重建和檢索歷史軌跡，以及如何更好地預(yù)測(cè)未來(lái)軌跡將是以后的工作重點(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.