張家碧，楊智應(yīng)（上海海事大學信息工程學院，上海 201306）

基于最小邊界扇形的移動對象軌跡實時化簡算法的進一步研究

張家碧，楊智應(yīng)
（上海海事大學信息工程學院，上海 201306）

隨著各種便攜式個人通信設(shè)備增加，帶有GPS定位功能的設(shè)備在日常生活中日漸普及。在方便人們?nèi)粘Ｉ畹耐瑫r也帶來海量數(shù)據(jù)的管理等問題。提出一種新的基于最小邊界扇形的移動對象實時化簡算法，提出了關(guān)鍵點（key point）的概念。在具有基本定位功能的設(shè)備上，更好地獲得接近原始軌跡的簡化軌跡，同時基本保持原有的通信代價和計算開銷。還提出一種新的基于區(qū)域面積的誤差度量方式。實驗結(jié)果證實該算法有較好的化簡率和較快的處理速度，得到的化簡結(jié)果更加接近實際。

移動對象；實時化簡；誤差

0　引言

隨著社會的進步和科技的發(fā)展，內(nèi)置定位功能的設(shè)備在人們的生活中得到了普及，人們在使用這些設(shè)備的同時產(chǎn)生的海量數(shù)據(jù)通過無線網(wǎng)絡(luò)傳輸?shù)搅酥醒霐?shù)據(jù)庫［1］，針對這些按時間標記的位置信息的傳輸，處理，存儲都成了棘手的問題。在現(xiàn)實場景中，常常對各類移動設(shè)備產(chǎn)生的數(shù)據(jù)進行壓縮處理。其中，移動對象軌跡化簡問題作為近年來備受關(guān)注的問題，對有效減少服務(wù)器負載和降低通訊代價有著至關(guān)重要的影響。簡單地說，移動對象簡化問題，就是針對原始軌跡，重新計算出一條新的盡量包含少的軌跡點的軌跡，并盡可能接近原始軌跡。

實際上原始軌跡數(shù)據(jù)在被壓縮，降低開銷的同時也損失了較多的軌跡特征。這在一些場景中是不利的。例如通過對船舶軌跡的分析，可發(fā)掘出海洋交通流的特征與規(guī)律，為海上交通管理部門提供依據(jù)［2］。過多的數(shù)據(jù)采集可能造成數(shù)據(jù)冗余等問題，加大了數(shù)據(jù)處理的難度；過多的軌跡點簡化則會損失較多的軌跡特征，不利于數(shù)據(jù)分析。針對類似問題本文在基于最小邊界扇形（MBS）的移動對象實時化簡算法的基礎(chǔ)上提出了一種新的實時的移動對象軌跡化簡算法，力求在少量增加通信代價和計算開銷的前提下，適當增加較能體現(xiàn)軌跡原本特征的軌跡點。它在繼承基于最小邊界扇形的移動對象軌跡實時化簡算法簡單，高效，對終端設(shè)備要求低等優(yōu)秀特性的同時又能更好的體現(xiàn)出軌跡的特征。

1　相關(guān)工作

王欣然等人根據(jù)GPS系統(tǒng)中存在定位誤差的實際情況，針對只有基本定位功能的GPS設(shè)備，提出了一種基于最小邊界矩形（MBS）的實時軌跡化簡算法。移動對象在本質(zhì)上是隨時間而變化的集合實體［3］。下面首先給出移動對象軌跡化簡問題中所涉及到的一些定義。

定義1原始序列。在給定的歐氏空間中，原始軌跡序列O=｛o1，o2，…，on｝是有序的離散軌跡點Si=（p＜x，y＞，t）所構(gòu)成的序列，其中（1≤i≤n）。

定義2 簡化序列。簡化序列S=｛s1，s2，…，sm｝可理解為：在歐氏空間中，原始序列簡化后所形成的序列，其中m≤n。

1.1GPS誤差分析

GPS測量是通過地面接收設(shè)備接收衛(wèi)星傳送來的信息，對于GPS衛(wèi)星、衛(wèi)星信號傳播過程和地面接收設(shè)備都會對GPS測量產(chǎn)生誤差。主要誤差來源可分為：與GPS衛(wèi)星有關(guān)的誤差；與信號傳播有關(guān)的誤差；與接收設(shè)備有關(guān)的誤差。其中第一類主要包括星歷誤差，星鐘誤差，地球自轉(zhuǎn)效應(yīng)誤差等。這類誤差通過軌道松弛法，差分法可以去除。最后一類誤差則是接收機的固有誤差，這類誤差是無法消除的。文中所討論的誤差主要是這里提到的第二類誤差，指的是不能由用戶測量或由校正模型來計算的傳播延時誤差［4］。GPS定位誤差由以下公式近似表示［5］：

其中σp為GPS定位誤差的標準偏差，σUERE為偽距測量誤差的標準偏差，GDOP為幾何精度衰減因子。

1.2軌跡化簡算法的研究

軌跡化簡算法的研究主要的思路主要有三種：軌道壓縮、推算定位和區(qū)域過濾［6］。軌道壓縮方法的應(yīng)用場景是早期的軌跡離線應(yīng)用場景，通過引入線性化簡算法和壓縮算法等方法對歷史軌跡數(shù)據(jù)進行化簡，這類方法的壓縮率較高，但壓縮效率較低，不利于軌道數(shù)據(jù)的遠程實時壓縮［7］?；谕扑愣ㄎ凰枷氲能壽E化簡算法引入最大偏離誤差閾值對未來位置進行預測［8］，簡單的說這種算法的思路能表述為：無論何時只要對象的實際位置與其數(shù)據(jù)庫位置的距離超過一個給定的閾值th，就執(zhí)行一次數(shù)據(jù)庫的更新。這類方法一般用于聯(lián)機簡化?；趨^(qū)域過濾的方法一般通過給定的閾值和相關(guān)信息（如過去某些時刻的軌跡點位置，移動對象的速度方向等），構(gòu)建安全區(qū)域（SA），再根據(jù)實際的軌跡點是否位于該區(qū)域內(nèi)做出是否保留該軌跡點的判定。這種方法的缺點是缺乏對方向變化累計所帶來的簡化誤差，且部分采取速度和方向絕對閾值的優(yōu)化思路在處理不穩(wěn)定參數(shù)時化簡率難以提高［9］。

以上所提到的軌跡化簡算法大多針對的是較為精準的移動設(shè)備，它們大多不僅能提供基本的位置信息還能提供移動對象的速度，方向等信息。在實際應(yīng)用中這類設(shè)備往往比較昂貴。大多情景下的移動設(shè)備只有基本的定位功能（如車載終端，移動手機等）。在目前的研究中針對這種情況的算法較少。文獻［10］首先提出了一種基于最小邊界矩形的實時軌跡化簡方法 （以下簡稱為MBR算法）并提出了一種基于封閉面積的誤差度量方式來解決此類問題。在MBR算法中，首先構(gòu)造包含相同軌跡點個數(shù)的最小包圍矩形集合，將得到最小矩形面積與給定的標準面積大小的比較，最后通過針對最小邊界矩形的分割/合并操作對原始軌跡數(shù)據(jù)進行簡化。該算法提供了一種設(shè)計軌跡化簡算法的新思路，即利用標準圖形去逐段匹配整個軌跡［4］。但MBR算法本身也存在掩蓋了較多原始軌跡特征，算法較復雜等問題。

1.3MBS

MBS算法沿著MBR算法所提出的使用標準圖形去匹配每段軌跡的思路，使用最小包圍扇形來近似化簡移動對象軌跡。其化簡的大概過程為：在每次接收到新的軌跡點信息時，重新構(gòu)造最小邊界新扇形。最后通過判斷原始點到其估計點的距離是否超過用戶所設(shè)定的誤差閾值來決定是否向服務(wù)器更新移動對象的位置信息。其中原始點到其估計點間的距離是通過基于等極徑的誤差度量方式完成的。將所構(gòu)造的扇形置于極坐標系環(huán)境中，以其余原始軌跡點到扇形頂點（同時也是極點）的距離的最大值為半徑，極點為圓心做圓弧，圓弧與扇形角平分線的交點即為該原始軌跡點的估計點。如圖1所示是某最小邊界扇形中的原始軌跡點與其對應(yīng)的估計點。其中o1，…，o5表示原始軌跡點，ole表示扇形的角平分線。在圖1中s3即o3的估計點。MBS算法對終端的要求低，與MBR算法比較保留了移動的軌跡運動特征，但仍不能令人滿意，且MBS算法對于移動速度較慢或存有較大誤差的移動對象其化簡結(jié)果不甚理想。MBS算法對原始數(shù)據(jù)中的每個軌跡點數(shù)據(jù)只瀏覽一次，其時間復雜度是線性的，空間復雜度根據(jù)構(gòu)造扇形的方法不同而有所區(qū)別。

圖1　原始軌跡點與其對應(yīng)的估計點

2　本文方法

2.1基于扇形面積的誤差度量方式

在移動對象軌跡化簡問題中，為了衡量簡化軌跡S和原始軌跡O之間的區(qū)別，我們要根據(jù)算法的特性選擇不同的誤差度量方式，不同的誤差度量方式對于同一軌跡數(shù)據(jù)的化簡過程，結(jié)果是不同的，進而影響到存儲空間、處理速度等關(guān)鍵指標?，F(xiàn)有的誤差度量方式通常分為垂直歐氏距離，同步歐氏距離和Fréchet距離［11］。本文結(jié)合算法實際，從利于關(guān)鍵點的判斷和減小計算開銷出發(fā)，在基于等極徑的誤差度量方式的基礎(chǔ)上提出了一種新的誤差度量方式。根據(jù)基于等極徑的誤差度量方式，只要控制了扇形中等腰三角形底邊的長（即圖2中的d），便能對整個簡化過程進行誤差控制，在MBS算法中是通過比較d和st_error（用戶設(shè)定的閾值）的大小來決定是否向服務(wù)器端更新對象位置信息。因此在扇形的頂角θ確定后，以st_error作為d的值，根據(jù)扇形公式，可以得到在頂角下的扇形的最大面積，記為smax。具體的誤差度量方法是當每次接受新的位置點信息后，首先在構(gòu)造的邊界扇形內(nèi)，以扇形的頂點作為極坐標的極點，扇形的一邊作為極軸。接著判斷頂角θ是否發(fā)生變化，在θ不變的情況下，判斷所構(gòu)建的扇形面積ssec與smax的大小關(guān)系。當ssec＞smax時，向服務(wù)器端更新該移動對象的位置信息數(shù)據(jù)，并發(fā)送關(guān)鍵點的位置信息到服務(wù)器端。假設(shè)頂角θ大小變化發(fā)生變化，則重新計算smax，再與ssec的面積進行比較。與原先的誤差度量方式相比，新的誤差度量方式由于不需要計算每個點的估計點位置以及估計點到其自身的距離，計算開銷減小。另外，新的誤差度量方式也為新的算法判斷關(guān)鍵點提供了方便。

圖2　基于等極徑的誤差度量方式

圖3　基于扇形面積的誤差度量方式

2.2一種新的基于最小邊界扇形的移動對象軌跡實時化簡算法

為了設(shè)計出針對只有基本定位功能的GPS設(shè)備（即只能提供移動對象的基本位置信息，不能提供方向，速度等更詳細的信息）實時軌跡化簡算法，本文提出了一種新的基于最小邊界扇形的移動對象軌跡實時化簡算法（以下簡稱為NMBS算法），在只有基本位置信息的前提下，通過算法化簡得到的軌跡數(shù)據(jù)能更好地體現(xiàn)移動對象的軌跡特征，同時算法的主要性能特征（包含運行時間、存儲開銷、計算開銷等）與其他主流化簡算法相比并無明顯劣勢。使用盡可能小的代價達到提高數(shù)據(jù)的處理效率，降低數(shù)據(jù)規(guī)模，提高數(shù)據(jù)可靠性。

在移動對象的運動過程中，本文使用最小邊界扇形 （Minimum Bounding Sector，MBS）來匹配其運動軌跡，結(jié)合基于扇形面積的誤差度量方式，在構(gòu)造最小邊界扇形時，以上一次簡化更新后的下一個位置點或感知剛開始的位置點為頂點，其余點到頂點的距離的最大值為半徑的方法向前構(gòu)造包圍扇形。這種構(gòu)造包圍扇形的方法如圖4所示。

圖4　構(gòu)造最小邊界扇形

在NMBS算法中有一個關(guān)鍵的概念∶關(guān)鍵點（key point），下面給出關(guān)鍵點的定義：

定義3關(guān)鍵點。當新構(gòu)造的扇形滿足向服務(wù)器更新的條件時，若某原始軌跡點oi（3≤i≤n）的前2個或2個以上的點位于扇形角平分線的一側(cè)或角平分線上，而oi位于角平分的另一側(cè)或角平分線上，則稱該點為關(guān)鍵點。

通過以上定義可以看出，關(guān)鍵點是較能體現(xiàn)出軌跡變化特征的點。假設(shè)在某一時刻i，根據(jù)NMBS算法所構(gòu)造的邊界扇形滿足更新條件，在向服務(wù)器發(fā)送新的位置信息的前，先判斷關(guān)鍵點。并將關(guān)鍵點的位置信息一并發(fā)送給服務(wù)器。通過增加較能體現(xiàn)移動對象軌跡特征的關(guān)鍵點，使簡化后的軌跡更加接近原始軌跡。

圖5　MBS中的關(guān)鍵點

根據(jù)關(guān)鍵點的定義，假設(shè)針對某一閾值st_error，如圖5所示在接收到軌跡點o8時，滿足更新條件，則點o5，o7，o8是關(guān)鍵點，向服務(wù)器更新o1，o5，o7，o8的位置信息。具體的算法如算法1所示，算法的第一個輸入?yún)?shù)st_error是用戶設(shè)定的誤差閾值，第二個參數(shù)Traj表示原始軌跡數(shù)據(jù)集合。函數(shù)CalcMBS（buf，point）用于計算當前的最小邊界扇形，其中buf表示存儲歷史軌跡點的集合，point表示最新得到的位置信息；函數(shù) area （newMBS）用于計算當前構(gòu)造的扇形面積，其中newMBS表示當前扇形信息；函數(shù)CalcCen（newMBS）用于計算當前扇形的圓心角大小；Calcarea（θ，st_error）用于計算在給定閾值st_error和圓心角下扇形的理論面積；函數(shù)keypoint（point）用來判斷當前的點是否是關(guān)鍵點；Key是關(guān)鍵點的集合；函數(shù)BoundInfor（newMBS）用于獲得當前扇形的邊界信息包括扇形中心點坐標，以及距離該坐標點的最大值和到中心點與X軸所成最大角、最小角四個數(shù)據(jù)。

算法1 NMBS method

分析算法可知，由于NMBS是由一重循環(huán)構(gòu)成，時間復雜度為o（n）（其中n表示軌跡點數(shù)）；在算法的執(zhí)行過程中，由于關(guān)鍵點的判定，需要保留每個點的相對位置信息，因此，算法的空間復雜度為o（n）。這種新的基于最小邊界扇形的移動對象軌跡實時化簡算法雖然增大了存儲開銷，但由于每個點的信息僅僅是其位置信息（并不包含瞬時速度，方向等其他信息），使得這種增大在合理可接受的范圍內(nèi)。同時由于新的誤差度量方式的提出，縮減了計算開銷和處理時間。總的來說，該算法的特點是：算法本身對輸入要求小（僅需要位置點信息和誤差閾值），能較好地描述運動對象的運動趨勢。

3　實驗分析及估計

為對算法進行分析和性能評估，實驗平臺選取臺式電腦做為測試硬件平臺，具體的實驗平臺配置為：Pentium Dual-Core CPU E5500@2.80GHz，內(nèi)存為2GB；實驗環(huán)境為Windows 7操作系統(tǒng)和Eclipse開發(fā)環(huán)境。實驗所使用的數(shù)據(jù)是從INFATI（Intelligent Farttilpasning）［12］得到。INFATI的位置信息是由2000-2001年期間從分成兩組一共20輛行駛在丹麥的汽車上采集得到的，它由20個GPS數(shù)據(jù)集構(gòu)成。為了進一步分析與評估NMBS算法的性能，本文選取了以下參數(shù)：

軌跡化簡率：化簡后到的軌跡中的軌跡點數(shù)量與原始軌跡中軌跡點數(shù)量的比值。

實際誤差相遇于誤差閾值的比值：某一時刻i，某簡化軌跡點Si與其對應(yīng)原始軌跡點oi的之間的距離與所設(shè)定的誤差閾值之比。

實際誤差相當于實際距離的比值：某一時刻i，某簡化軌跡點Si與其對應(yīng)原始軌跡點oi的之間的距離與實際相鄰的兩個軌跡點之間距離的比值。

軌跡的化簡率體現(xiàn)了原始軌跡中的軌跡點被化簡的多少，當這個值越小時，體現(xiàn)了原始軌跡中被化簡掉的點越多，算法的簡化程度越好。實際誤差相遇于誤差閾值的比值和相對實際距離的比值則反映了算法對誤差控制的影響，是算法的質(zhì)量指標。實際誤差相遇于誤差閾值的比值越接近1則說明算法有很好的誤差控制［4］；實際誤差相當于實際距離的比值越小則說明誤差對實際距離的影響越小。

實驗首先對算法的時間復雜度和空間復雜度進行了比較，結(jié)果如表1所示，其中n表示軌跡點的數(shù)量，m表示給定的存儲空間的大小。

表1　各種算法的時間復雜度和空間復雜度的比較

接著，針對以上算法從簡化率，與實際的誤差大小，運行時間等角度，進行性能的分析和比較，具體的結(jié)果如圖6所示。分析以下結(jié)果，可以看出文章所提出的算法有較好的穩(wěn)定性，從處理時間來看，NMBS并沒有因為增加要保留的點而使得算法運行時間與其余算法有明顯劣勢，能較好地保證實時性；從簡化誤差來看，算法體現(xiàn)了較好的誤差控制。綜合來說，NMBS算法有較好的綜合性能。

圖6　幾種算法的性能比較

另外實驗中還使用手機作為載體，對算法進行了實際的檢測。本次實驗中選取華為榮耀3c作為測試手機，手機的具體配置為：CPU型號：MTK6582，CPU頻率：1.3GHz，CPU數(shù)：4核，RAM容量：2GB，ROM容量：8GB。手機搭配Android 4.4.2操作系統(tǒng)，開發(fā)中使用了百度地圖的Android SDK v6.2.進行定位。實驗中，每隔10s進行一次定位，試驗中將誤差閾值設(shè)置為5m。

表2　NMBS算法的實驗結(jié)果記錄

實驗記錄了3種場景：在道路上行走方向隨意的行人，其行走速度約為4-10km/h；第二種是速度為15-20km/h的自行車，最后一種是正常行駛的公交車，速度約為30-40km/h。本次實驗的結(jié)果記錄如表2所示。實驗結(jié)果表明，算法有著較好的化簡率，圖7是實驗中的部分截圖，從圖7來看，化簡后的軌跡能較好地和原軌跡重合（其中紅色細實線表示原始軌跡，綠色粗實線表示簡化后的軌跡），體現(xiàn)原軌跡的特征。從結(jié)果我們也能看出，當移動對象是行人時，其運動范圍較小，運動速度較慢，由于受到GPS定位誤差等影響。軌跡的繪制較為混亂，有一定誤差，不夠細致。當移動對象的運動范圍較大，簡化軌跡能較好地反映出原始軌跡的特點?？偟膩碚f算法的適用對象較為廣泛，算法性能較為優(yōu)秀。

4　結(jié)語

由于移動對象的移動規(guī)律、運動方向、速率、等因素的不可預知性，使得某一算法很難在多種情境下都體現(xiàn)出令人滿意的性能。本文針對只具備基本定位功能的設(shè)備，設(shè)計出了NMBS實時算法。該算法確保了在某些環(huán)境下增加了信息量，有助于軌跡數(shù)據(jù)的挖掘，研究。同時實驗結(jié)果表明NMBS的運行時間，開銷等并沒有因此有明顯的增大。當然這種通過增加保留點數(shù)量的方法對保留軌跡點的數(shù)量的不可控性，能否在更新位置信息時做到對保留軌跡點數(shù)目的控制，以及使得保留的點更有價值，將是今后所需研究的問題。

圖7　NMBS算法的化簡結(jié)果

［1］王欣然，楊智應(yīng).基于PLAZA的移動對象軌跡實時化簡方法［J］.計算機應(yīng)用研究，2014，31（5）∶1316-1319.

［2］陳金海.海洋運輸船舶軌跡分析研究進展［J］.中國航海，2012，35（3）∶54-57.

［3］Guting R H，Schneider M.Moving Objects Databases［M］.1版.高等教育出版社，2009∶25-30.

［4］王欣然，楊智應(yīng).基于最小邊界扇形的移動對象軌跡實時化簡算法［J］.計算機應(yīng)用，2014，34（8）∶2409-2414.

［5］Kaplan E D，Hegarty C J.Understanding GPS∶Principles and Applications［M］.Artech house，2006.

［6］李文海，程志光，衛(wèi)東，向隆剛，郭曉倩.基于自適應(yīng)安全區(qū)域的軌道實時化簡方法［J］.計算機學報.2014，37（9）∶1923-1935.

［7］Potamias M，Patroumpas K，Sellis T.Amnesic Online Synopses for Moving Object/Proceedings of the 15th International Conference on Information and Konwledge Management.Glasgow，UK，2006∶784-785.

［8］Zhang R，Qi J Z，Lin d.A Highly Optimized Algorithm for Continuous Intersection Join Queries over Moving Objects.The Very Large Database Journal，2008，21（4）∶561-586.

［9］Cao H，Wolfson O，Trajcevski G.Spatio-Temporal Data Reduction with Deterministic Errorbounds.The Very Large Database Journal，2006，15（3）∶211-228.

［10］LIU G，IWAI M，SEZAKI K.An Online Method for Trajectory Simplification under Uncertainty of GPS［J］.Information and Media Technologies，2013，8（3）∶665-647.

［11］張玥，張宏莉，張偉哲.基于冪律分布的網(wǎng)絡(luò)用戶跨蘇排序算法［J］.中文信息學報，2012，26（4）∶122-128

［12］C S Jensen，H Lahrmann，S Pakalnis，J Runge.The INFATI Data［Z］.Technical Report，Database and Programming Technologies Institute at Aalborg University，2004.

Moving Object；Real-Time Simplification；Error

Further Research on the Moving Object Trajectory Real-Time Simplification Algorithm Based on Minimum Boundary Sector

ZHANG Jia-bi，YANG Zhi-ying
（College of Information Engineering，Shanghai Maritime University 201306）

With a variety of portable personal communications equipment increased，with GPS positioning function equipment has become more and more popular in daily life，in the convenience of people's daily life，but also brings massive data management issues.Presents a new realtime moving object boundary minimum simplification algorithm based on sector，and puts forward the key point concept.The basic positioning devices，better gets the simplified trajectory closer to the original trajectory，and keeps the communication cost and computation cost of the original.Proposes a new error metric based on the area the way.Experimental results show that this algorithm has better of simple and fast processing speed，simplifies the results closer to the actual.

1007-1423（2016）20-0029-07

10.3969/j.issn.1007-1423.2016.20.006

張家碧（1991-），男，安徽合肥人，碩士研究生，研究方向為算法設(shè)計與分析、移動對象數(shù)據(jù)庫

楊智應(yīng)（1964-），男，博士，教授，研究方向為算法設(shè)計與分析、并行與分布式計算、移動自組網(wǎng)、RFID傳感器網(wǎng)絡(luò)與物聯(lián)網(wǎng)

2016-03-15

2016-07-10