許惠，楊智應(yīng)

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

基于高斯濾波的移動對象軌跡化簡實時算法

許惠，楊智應(yīng)

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

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

移動對象；實時軌跡化簡；定位誤差；濾波

0 引言

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

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

1 問題建模

1.1 移動對象軌跡模型

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

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

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

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

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

2 相關(guān)工作

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

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

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

圖1 NPLAZA算法示例圖

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

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

圖2 基于MBS的化簡算法

3 方法提出

3.1 目前算法分析

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

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

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

算法描述如下：

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

輸出：簡化序列S。

算法流程：

3.2 定位誤差情況分類

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

4 實驗分析及估計

4.1 算法性能分析

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

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

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

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

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

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

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

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

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

圖3 算法性能綜合比較

實際應(yīng)用選取HTC5088手機為測試平臺，具體配置如下：CPU型號：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)行定位和顯示。

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

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

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

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

5 總結(jié)

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

[1]米學(xué)軍，盛廣銘，張婧，等.GIS中面積偏差控制下的矢量數(shù)據(jù)壓縮算法[J].地理學(xué)報，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á)夫，張昕明.基于時空特性的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].情報處理學(xué)會論文誌.データベース，2013，6（3）：40-49.

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

[9]李惠芬，蔣向前，李柱.高斯濾波穩(wěn)健性能的研究與改進(jìn)[J].儀器儀表學(xué)報，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-），男，碩士，主要研究方向：移動對象數(shù)據(jù)庫。

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