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

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

0 引言

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

　　移動對象軌跡化簡問題作為移動對象數據庫研究領域的重要分支之一，對于高效地管理和分析移動對象數據有著至關重要的影響。在實際應用中，由于定位系統存在定位誤差，很多廉價的定位裝置會在不利的環境產生不可忽視的誤差。針對此問題本文基于PLAZA方法和高斯濾波提出一種實時移動軌跡化簡方法（GPlaza），它的思想是針對具有較大誤差的定位裝置，首先對原始測量數據進行高斯濾波，以減小GPS定位誤差的影響，然后構建合理的誤差區域對后續的軌跡點進行過濾化簡。

1 問題建模

　　1.1 移動對象軌跡模型

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

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

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

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

　　其中為GPS定位標準偏差，?滓UERE為偽距測量的標準偏差，GDOP為幾何精度衰減因子（Geometric Dilution of Precision）。因此，對于一個特定地域來說，定位誤差并不是固定的，可以看作符合標準正態分布。

2 相關工作

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

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

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

　　混合區域過濾算法結合垂距和角度兩個方面構造安全區域，根據待測點所處位置決定點的取舍。基于閾值的抽樣算法（TPG）作為典型的區域過濾算法，通過給定的閾值和已知信息（包括過去軌跡點的位置、速度和方向等），構建下一個軌跡點的安全區域（SA），然后判斷是否保存該軌跡點。

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

3 方法提出

　　3.1 目前算法分析

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

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

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

　　算法描述如下：

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

　　輸出：簡化序列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 定位誤差情況分類

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

4 實驗分析及估計

　　4.1 算法性能分析

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

　　化簡率：是指矢量數據壓縮后的數據量與壓縮前的數據量之比。

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

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

　　化簡率是數據壓縮算法的數量指標，追求較小的壓縮比是進行數據壓縮算法設計的根本出發點，線段空間偏移和相對誤差控制是數據壓縮的質量指標（越小越好），一個好的壓縮算法應該是結合實際需求，對以上3個指標進行最大限度的平衡。

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

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

　　4.2 實際應用化簡結果分析

　　實際應用選取HTC5088手機為測試平臺，具體配置

如下：CPU型號：Spreadtrum（展訊）Shark（4核Cortex-A7架構）；CPU頻率：1 024 MHz；RAM容量：512 MB；操作系統：Android OS 4.1.2。Android應用開發中利用百度地圖Android SDK v3.2.0應用程序開發包進行定位和顯示。

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

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

5 總結

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

參考文獻

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

　　[2] 趙琳，丁繼成，馬雪飛.衛星導航原理與應用[M].西安：西北工業大學出版社，2011.

　　[3] 袁建平，羅建軍，岳曉奎.衛星導航原理與應用[M].北京：宇航出版社，2003.

　　[4] 張達夫，張昕明.基于時空特性的ＧＰＳ軌跡數據壓縮算法[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]. 情報處理學會論文誌. データベース， 2013， 6（3）： 40-49.

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

　　[9] 李惠芬，蔣向前，李柱.高斯濾波穩健性能的研究與改進[J].儀器儀表學報，2004，25（5）：633-637.

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