基于高斯濾波的移動(dòng)對(duì)象軌跡化簡(jiǎn)實(shí)時(shí)算法

許惠，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院計(jì)算機(jī)系，上海201306）

基于高斯濾波的移動(dòng)對(duì)象軌跡化簡(jiǎn)實(shí)時(shí)算法

許惠，楊智應(yīng)

（上海海事大學(xué)信息工程學(xué)院計(jì)算機(jī)系，上海201306）

基于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à)值。

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

0 引言

隨著汽車、輪船及手持設(shè)備等移動(dòng)對(duì)象數(shù)量的增加，移動(dòng)位置信息也隨之飛速增長(zhǎng)。這些位置信息作為一種無(wú)限的數(shù)據(jù)流通過無(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)說是無(wú)法處理的。因此，通常需要對(duì)其進(jìn)行壓縮處理。

移動(dòng)對(duì)象軌跡化簡(jiǎ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ì)此問題本文基于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è)量同步誤差、多徑傳輸和各種噪聲干擾。從來(lái)源上來(lái)說誤差可以分為四類：與衛(wèi)星有關(guān)的誤差、與信號(hào)傳播有關(guān)的誤差、與接收機(jī)有關(guān)的誤差以及地球潮汐、負(fù)荷潮等造成的其他誤差。而與信號(hào)傳播有關(guān)的誤差包括電離層折射誤差、對(duì)流程折射誤差及多徑效應(yīng)誤差。GPS定位誤差由以下公式近似表示[3]：

其中σp為GPS定位標(biāo)準(zhǔn)偏差，σUERE為偽距測(cè)量的標(biāo)準(zhǔn)偏差，GDOP為幾何精度衰減因子（Geometric Dilution of Precision）。因此，對(duì)于一個(gè)特定地域來(lái)說，定位誤差并不是固定的，可以看作符合標(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）來(lái)判斷軌跡是否保留，并較早用于以無(wú)限時(shí)間序列方式生成的數(shù)據(jù)流的壓縮問題上，可以形式化地處理二維數(shù)據(jù)。NPLAZA結(jié)合移動(dòng)對(duì)象的軌跡特點(diǎn)，將其拓展為三維坐標(biāo)（二維空間和一維為時(shí)間）下的點(diǎn)的軌跡。如圖1所示。

圖1 NPLAZA算法示例圖

混合區(qū)域過濾算法結(jié)合垂距和角度兩個(gè)方面構(gòu)造安全區(qū)域，根據(jù)待測(cè)點(diǎn)所處位置決定點(diǎn)的取舍。基于閾值的抽樣算法（TPG）作為典型的區(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)最小邊界矩形的分割/合并操作以及選擇策略來(lái)對(duì)空間軌跡數(shù)據(jù)進(jìn)行化簡(jiǎn)。參考文獻(xiàn)[8]經(jīng)過研究改進(jìn)了MBR算法：采用最小包圍扇形來(lái)近似化簡(jiǎn)其移動(dòng)軌跡，提升了算法效率并減小了偏移誤差。如圖2所示。

圖2 基于MBS的化簡(jiǎn)算法

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ā)出定位信息開始，根據(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ì)算出其劃分角度θ=θε（i，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。

算法流程：

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é)束。

表1 各個(gè)算法的時(shí)間復(fù)雜度與空間復(fù)雜度

接下來(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)說，GPlaza算法有著較好的綜合性能。

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

圖3 算法性能綜合比較

實(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ū)的公交車（平均速度為50km/s）；（3）運(yùn)行中的上海地鐵16號(hào)線（平均速度為80~100 km/s）。實(shí)驗(yàn)記錄如表2。

表2 GPlaza算法模擬結(jié)果

由于正常情況下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ì)象壓縮率稍差，而線段空間偏移都較小。需要說明的是，由于地鐵通常運(yùn)行于地下，獲取不到衛(wèi)星定位信息，只能采用WiFi或基站定位，從而使定位偏差極度擴(kuò)大，繼而嚴(yán)重影響軌跡精度。

圖4 模擬GPlaza算法化簡(jiǎn)結(jié)果

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)。

[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í)空特性的GPS軌跡數(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-guaranteeddata 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.

Real-time trajectory sim p lification algorithm of moving object based on Gauss filtering

Xu Hui，Yang Zhiying
（College of Information and Engineering，Shanghai Maritime University，Shanghai 201306，China）

Based on PLAZA and Gauss image filtering，the research is about simplification algorithm of moving object trajectories with positioning error.The algorithm，which is mainly applied to the mobile terminal，is able to simplify the original trajectory of moving object，and reduce the communication and computation cost of mobile terminal.Thus the algorithm can improve the efficiency and value of track data.According to the thought of time series method and signal doeoising，the algorithm first process the original position data with gauss filter，which can decrease the influence of location error.And then simplify the trajectory according to the theory of PLAZA algorithm.The experimental results confirmed that the algorithm has better reduction rate and faster processing speed，the practical application show that this algorithm has better use value in real life.

moving object；real-time trajectory simplification；location error；filtering

TP301

A

1674-7720（2015）13-0012-05

2015-03-04）

許惠（1991-），男，碩士，主要研究方向：移動(dòng)對(duì)象數(shù)據(jù)庫(kù)。

楊智應(yīng)（1964-），男，博士，教授，主要研究方向：算法與復(fù)雜性、移動(dòng)計(jì)算、分布式計(jì)算與軟件工程。