室內(nèi)移動對象軌跡重構(gòu)與相似性度量研究*

王雅楠，李博涵,2,3+，張 潮，鄭 偉，李俊潔，秦小麟,2

1.南京航空航天大學 計算機科學與技術(shù)學院，南京 210016

2.江蘇省軟件新技術(shù)與產(chǎn)業(yè)協(xié)同創(chuàng)新中心，南京 210016

3.江蘇易圖地理信息科技股份有限公司，江蘇 揚州 225000

4.成都航空職業(yè)技術(shù)學院，成都 610100

1 引言

隨著室內(nèi)定位技術(shù)[1]的發(fā)展，室內(nèi)移動對象數(shù)據(jù)管理[2]逐漸成為熱門研究領(lǐng)域，尤其在緊急救援、安全預(yù)防以及定位導航等領(lǐng)域具有廣泛的應(yīng)用前景。移動對象軌跡分析作為位置服務(wù)的重要基礎(chǔ)，通過對用戶位置數(shù)據(jù)和其移動軌跡數(shù)據(jù)進行深層次的提取和分析研究，可以有效地挖掘出用戶的行為偏好及異常等重要信息，這對異常軌跡檢測、社交推薦[3]、智能交通等應(yīng)用都有著重要的作用。

移動軌跡相似性度量是移動軌跡分析領(lǐng)域里的一個重要部分，指的是找到一種合適的軌跡距離計算方法來度量兩條移動軌跡之間的相似程度，包括軌跡形狀、空間距離、軌跡時間等。移動軌跡相似性度量在基于位置服務(wù)中有許多重要的實際應(yīng)用，例如通過計算用戶移動軌跡的相似性，聚集相似軌跡[4]，找到相似用戶，從而在社交網(wǎng)絡(luò)上進行朋友推薦等。

目前針對移動對象軌跡相似性度量的研究多基于室外空間，對室內(nèi)空間的研究較少。由于室內(nèi)空間和室外空間的結(jié)構(gòu)不同，移動對象定位方式不同，移動軌跡維度不同等因素，已有基于室外空間移動軌跡查詢研究不能直接應(yīng)用于室內(nèi)空間。然而，有數(shù)據(jù)統(tǒng)計表明人們活動的區(qū)域和時間約80%處于室內(nèi)環(huán)境，如：辦公樓、商場、地鐵站、機場等。在室內(nèi)環(huán)境下移動對象軌跡相似性查詢有眾多的應(yīng)用場景。例如商家可以通過對大量用戶移動軌跡相似性分析挖掘出用戶行為偏好，為商業(yè)決策及資源分配提供依據(jù)；在室內(nèi)公共區(qū)域，工作人員可以通過軌跡相似性度量來找出異常軌跡，從而預(yù)防車站、機場等人流密集地區(qū)犯罪事件的發(fā)生；室內(nèi)設(shè)計工作者可以通過對大量軌跡進行相似性分析得到用戶行為模式等信息，從而更好地進行結(jié)構(gòu)設(shè)計等。對于軌跡相似性度量的研究中，多以空間距離為主要研究對象，時間和位置語義的相似性僅僅作為考慮因素甚至直接忽略。然而，在室內(nèi)環(huán)境下，時間和位置語義卻占有重要角色。本文結(jié)合室內(nèi)移動軌跡的特點，提出一種新的適用于室內(nèi)空間的移動軌跡相似性度量方法IMTSM（indoor-space moving-object trajectory similarity measurement），將空間、時間和位置語義這三種主要影響因素分別度量，從而更好地適應(yīng)不同需求。

本文的主要貢獻如下：

（1）結(jié)合室內(nèi)空間結(jié)構(gòu)，定義一種新的三維軌跡特征點發(fā)現(xiàn)算法，在保證軌跡信息完整的前提下將冗雜的軌跡數(shù)據(jù)進行重構(gòu)，有效降低了計算復(fù)雜度。

（2）將移動對象軌跡時空距離計算由二維空間擴展到三維空間，利用軌跡投影提出室內(nèi)軌跡空間距離算法，并根據(jù)室內(nèi)軌跡相對較短的特性，獨立計算軌跡時間距離，得到室內(nèi)軌跡時空相似度。

（3）設(shè)計室內(nèi)位置語義分析樹（LSR_Tree）結(jié)構(gòu)來描述位置之間的語義關(guān)系，通過自底向上查詢并改進動態(tài)時間規(guī)整算法，將文本的絕對性比較巧妙地轉(zhuǎn)換為語義關(guān)系度計算，并給出位置語義距離提取算法，有效減少了將軌跡位置語義序列作為文本序列比較的誤差，最后通過數(shù)據(jù)標準化處理將不同數(shù)量級的差異數(shù)據(jù)進行歸一，得到室內(nèi)移動對象軌跡綜合相似度。

2 相關(guān)工作

目前，對于移動對象軌跡相似度的計算多集中于室外空間或路網(wǎng)空間[5-6]中。室外空間中的經(jīng)典距離度量方法歐氏距離[7]最先被應(yīng)用于計算移動軌跡序列的相似度。先通過對坐標點計算得到歐氏距離，再加權(quán)平均得到整條軌跡的相似度，該方法思想易于理解，計算簡單，但對于軌跡長度有嚴格要求，實際應(yīng)用范圍有限。DTW（dynamic time warping distance）[8]動態(tài)時間規(guī)整方法解決了位置點與采集時刻不對應(yīng)的問題，通過歷史坐標點值來實現(xiàn)兩條軌跡的局部時間轉(zhuǎn)換，可以計算長度不同的軌跡，但這種方法必須要求軌跡距離計算能夠適應(yīng)時間維度的拉伸。Vlachos等人[9]所提出的基于最長公共子序列LCSS（longest common subsequence）的度量方法，解決了對于軌跡長度的限制，將軌跡分割成片段并判定不同段的相似程度，對軌跡噪點的影響有所改善。該方法經(jīng)驗證表明其效果明顯優(yōu)于歐式距離以及經(jīng)典方法DTW。Lin等人[10]通過定義One Way Distance距離函數(shù)來度量移動軌跡空間形狀的相似度。這些方法都只考慮了軌跡在空間及形狀的相似度，并未考慮時間因素對軌跡相似性的影響。

Pelekis等人提出了一種針對室外空間的時空相似性度量方法，并給出LIP（locality in-between polylines）[11]算法，將兩條軌跡交疊所圍成的多個小區(qū)域面積作為計算空間相似度的依據(jù)，同時將小區(qū)域最大時間與兩條軌跡的時間和的比值作為時間相似度的考量，在綜合考慮時間和空間的影響因素下得到最終相似度。Skoumas等人[12]將軌跡看成是多條線段的組合，在兩條軌跡相對應(yīng)的時間段內(nèi)，對空間中水平距離和垂直距離進行計算，得到軌跡時空相似度。

除了利用時空距離和軌跡形狀的相似性來度量軌跡相似度的方法外，還有位置語義這一因素對移動軌跡相似性度量有著重要影響。Ying等人[13]首先在軌跡相似度計算中加入了位置語義信息，分別將語義位置標簽加入軌跡單元，再改進LCSS方法計算兩條軌跡的位置語義相似度，但此方法僅僅將位置語義形式化，適合在特定場景下應(yīng)用。Wang等人[14]利用歐氏距離結(jié)合編輯距離的方法，克服了僅把位置當作字符的缺陷，但此方法并不適用室內(nèi)空間。

室內(nèi)空間與室外空間的特征有顯著的不同，室內(nèi)軌跡為三維軌跡，以上用于室外空間的軌跡相似度量方法并不能直接應(yīng)用于室內(nèi)空間，因此出現(xiàn)了少量關(guān)于室內(nèi)軌跡相似性度量的研究工作。Kang等人[15]在2009年首先提出一種基于LCSS的方法用于室內(nèi)軌跡相似度的計算，將軌跡相似度用軌跡在同一位置的停留時間代替，該方法思想簡單，但對于軌跡的計算相對粗略，且對于語義位置信息僅用字符代替，很難得到實際的應(yīng)用。Jin等人[16]設(shè)計了SIT（similarity indoor trajectory）算法，他們認為相比于地理位置所表示的坐標信息，位置的語義信息更有利用價值。SIT算法給出了室內(nèi)分層移動模式的概念，并基于最長公共子序列算法LCSS度量位置語義信息之間的相似度，從而獲得用戶對位置的偏好程度。但LCSS主要用于計算兩個字符串之間最大公共子序列，然而對于移動對象軌跡的位置語義序列，不同語境可能產(chǎn)生不同語義，將位置語義序列作為字符串進行絕對性比較會出現(xiàn)計算誤差。

3 基礎(chǔ)知識

3.1 問題描述

室內(nèi)空間由于房間、走廊、樓梯等因素的限制，使得歐式距離、路網(wǎng)距離等不再適用，必須重新定義符合室內(nèi)空間約束的三維軌跡空間距離度量方法。而且，在室內(nèi)空間中，移動軌跡的時間距離和位置語義距離對軌跡相似性度量有重要影響。如圖1所示，移動軌跡T和R的空間形狀走向極為相似，但考慮到時間屬性，便不能再認為是相似軌跡。

Fig.1 Moving trajectory time distance profile圖1 移動軌跡時間距離圖

傳統(tǒng)的軌跡分析研究中多將語義信息符號化，但在室內(nèi)環(huán)境中，位置語義信息應(yīng)用需求較高，例如在大型機場中，人們通常的描述為“我在登機口”而不是“我在位置A”，因此空間形狀相似的軌跡在位置語義的角度可能出現(xiàn)很大的差異。有時用戶的查詢需要會有所側(cè)重，例如查詢某一時間段的相似軌跡，那么時間相似度就相對重要。本文將空間、時間、位置語義分別度量，用戶可以根據(jù)自己的需要對其中一個或多個方面著重度量，以更好地適應(yīng)不同需求。

3.2 形式化定義

室內(nèi)環(huán)境中，移動對象的位置信息通常通過室內(nèi)部署的傳感器來獲取，因此可以使用傳感器序列標號來表示室內(nèi)移動對象軌跡。

定義1（室內(nèi)定位記錄）一個室內(nèi)移動對象的位置記錄可以由一個四元組表示，表示為：

其中，objectID表示移動對象，readerID表示傳感器標號，label表示此處位置語義標簽，ts表示移動對象進入傳感器范圍的時刻，te表示移動對象離開傳感器范圍的時刻。

定義2（室內(nèi)移動對象軌跡）由室內(nèi)定位記錄序列構(gòu)成室內(nèi)移動對象軌跡，表示為：

4 室內(nèi)移動軌跡相似性度量

4.1 軌跡重構(gòu)

移動軌跡數(shù)據(jù)是由一系列的離散的記錄點組成，采樣點個數(shù)越多，軌跡的完整性和精度越高，但是存儲和計算的代價也越高。提取軌跡特征點是移動軌跡分析經(jīng)常采用的策略，即提取軌跡中具有典型特征或是軌跡變化幅度較大的特征點重新構(gòu)建軌跡。本文結(jié)合室內(nèi)空間的特點，定義一種新的算法TRS（trajectory restructure）提取軌跡特征點重構(gòu)軌跡，對冗雜的移動軌跡進行壓縮，保證了在軌跡信息完整的前提下減少軌跡的數(shù)據(jù)量和簡化軌跡相似性計算的復(fù)雜度。

定義3（軌跡特征點）TR={p1,p2,…,pn}為一條室內(nèi)移動對象軌跡，其軌跡特征點表示為：

其中，ω為角度偏移閾值，d為位置偏移距離閾值，對于軌跡TR中任意采樣點pi，記Dpi為pi的位置偏移距離，Dθpi為pi的角度偏移距離。若采樣點位置語義標簽pi.label=“l(fā)ift”，或Dpi>d，或Dθpi>ω，則pi定義為一個特征點ci，軌跡的開始點和結(jié)束點自動歸為特征點。

如圖2所示，假設(shè)pc是一個特征點，pc+1是下一個特征點，則定義pcpc+1為標記向量，并隨著特征點的增加而后移。假設(shè)pi到標記向量pcpc+1的最小歐式距離為位置偏移距離Dpi，若向量pcpi和pipc+1夾角α以及向量pc+1pi和pc+1pc夾角β均為銳角或存在直角，則最小距離為pi到標記向量pcpc+1的垂線段d1；若α和β中有鈍角存在，則最小距離為：

Fig.2 Sketch of trajectory characteristic points threshold圖2 軌跡特征點閾值示意圖

同時，軌跡的轉(zhuǎn)向角反映了軌跡的運動趨勢，pcpc+1為標記向量，若pi為軌跡下一個采樣點，此處向量pcpc+1與向量pc+1pi的夾角為θ，則角度偏移距離Dθpi為：

算法1軌跡重構(gòu)算法TRS

輸入：室內(nèi)移動軌跡T，角度偏移閾值ω，距離偏移閾值d。

輸出：由特征點集合組成的重構(gòu)軌跡R。

4.2 空間距離

目前，已有的對于軌跡空間距離的計算方法大多數(shù)基于歐式空間或者網(wǎng)格空間，對于室內(nèi)環(huán)境下的研究較少。LIP[11]算法在室外軌跡時空相似度方面取得很好的效果，本文針對室內(nèi)復(fù)雜三維空間，將其所提出的距離函數(shù)作了改進，提出一種新的適用于室內(nèi)軌跡空間距離度量算法SIP（spatial locality inbetween polygon of indoor）。對于每一條移動軌跡，根據(jù)特征點提取算法可以獲得以特征點表示的位置集合C={c1,c2,…,cs}。特征點序列中，每兩個相鄰的特征點按到達時間的先后組成一條軌跡段L，由此該條軌跡便可以表示為多個3D線段組成的有向序列。如圖3所示：假設(shè)軌跡線段表示為T={L1,L2,…,Lm}，R={L1,L2,…,Ln}，軌跡T′為軌跡T在軌跡R所在二維平面的投影軌跡，記軌跡相交點為I={I1,I2,…,Iq}。

Fig.3 Trajectory space projection圖3 軌跡空間投影示意圖

定義4（高度距離）假設(shè)投影后軌跡T′與軌跡R相交點個數(shù)為k，當k>1時，定義其高度距離hi(0≤i＜k)為投影后相鄰相交點之間軌跡所圍成的封閉多邊形內(nèi)投影高度平均值；當k≤1時，定義高度距離hi(0≤i＜k)為整條軌跡投影高度平均值。

定義5（相交面積）假設(shè)投影后軌跡T′與軌跡R相交點個數(shù)為k，當k>1時，定義軌跡相交面積Areai(0≤i＜k)為投影后相鄰相交點之間軌跡所圍成的封閉多邊形的面積；當k≤1時，定義軌跡相交面積Areai(0≤i＜k)為軌跡T′與軌跡R的首尾端點所圍成封閉多邊形面積，即相交面積取為最大值。

定義6（權(quán)重系數(shù)）當k>1時，定義lengthT和lengthR分別表示移動軌跡T和R的軌跡長度，即軌跡特征點個數(shù)。lengthT(Ii,Ii+1)和lengthR(Ii,Ii+1)分別表示封閉多邊形Areai(0≤i＜k)內(nèi)移動軌跡T和R的軌跡長度，則權(quán)重系數(shù)的計算公式為：

其中，0≤i＜k；當k≤1時，軌跡投影后不相交或只有一個相交點，封閉多邊形不存在，ωi取為最大值1。

定義7（空間距離）定義移動軌跡T和R的空間相似度Dspace為：

其中，0≤i＜k。

算法2空間相似距離算法SIP

輸入：室內(nèi)移動軌跡T和R。

輸出：軌跡T和R的空間距離。

4.3 時間距離

文獻[11-12]中考慮到時間距離對軌跡相似度的影響，將其融入到空間距離計算之中，取得一定的成果，但這種方式更適用于軌跡長度較長的環(huán)境中。在室內(nèi)空間，軌跡相對較短，容易做到將整條軌跡的時間作為度量單元，若將空間和時間的度量分開計算，能夠在一定程度上提高計算效率。

如圖4所示，假設(shè)軌跡T和R在軌跡開始點和結(jié)束點的時間段內(nèi)無時間交集，則時間距離為第一段軌跡開始點與第二段軌跡結(jié)束點差值的絕對值。否則，時間距離為第一段軌跡開始點到第二段軌跡結(jié)束點時間差值減去兩條軌跡相交區(qū)域時間段，如式（8）所示：

Fig.4 Trajectory time distance圖4 軌跡時間距離

4.4 位置語義距離

由于移動軌跡的位置語義序列所代表的含義是根據(jù)其所在場景定義的，傳統(tǒng)應(yīng)用字符串序列比較來衡量軌跡位置語義序列相似性的方法精確度較低。本文利用位置語義之間的相互關(guān)系來計算位置語義距離，其中葉子節(jié)點表示室內(nèi)空間中實際位置所對應(yīng)的語義屬性，即位置語義標簽。如圖5所示的位置語義分析樹結(jié)構(gòu)LSR_Tree，非葉子節(jié)點表示下層節(jié)點所屬位置類別，其所在層次越高，所代表的位置范圍就越大，位置語義相似度就越小。反之，則相似度越大。在LSR_Tree結(jié)構(gòu)中，通過兩個軌跡特征點所訪問的葉子節(jié)點，尋找到其最小公共父親節(jié)點，并定義公共父親節(jié)點所在層次高度與LSR_Tree高度之比為特征點之間的位置語義距離。根據(jù)語義位置分析樹，提出位置語義距離提取算法LSE（location semantic extract），并改進DTW函數(shù)，使其適用于室內(nèi)軌跡位置語義的相似性度量。

假設(shè)由特征點表示的移動軌跡T={T1,T2,…,Tm},R={R1,R2,…,Rn}，m和n分別為軌跡T和R的特征點個數(shù)，即軌跡長度。這里改進動態(tài)時間規(guī)整算法DTW后得到位置語義距離函數(shù)：

Fig.5 Location semantic analysis LSR_Tree圖5 位置語義分析樹LSR_Tree

其中，Ti為軌跡T中某一時刻的特征點，Rj為軌跡R中某一時刻的特征點，0＜i＜m,0＜j＜n。特征點Ti與Rj之間的距離dist(Ti,Rj)為位置語義分析樹中最小公共父節(jié)點高度與樹高度的比值。

位置語義距離計算公式：

公式中前一部分引用動態(tài)時間規(guī)整DTW的方法度量兩條軌跡的位置語義距離，但此方法未考慮到軌跡長度的差異，公式后一部分引入軌跡長度比值，解決軌跡長度不相等的情況。若兩條軌跡T和R是完全相同的，那么distTR(T,R)為零，公式計算結(jié)果為1，即軌跡完全相似。

算法3位置語義距離算法LSE

輸入：兩條室內(nèi)移動軌跡T、R以及語義位置分析樹LSR_Tree。

輸出：軌跡T、R的位置語義相似度。

4.5 室內(nèi)移動對象軌跡相似度

在得到軌跡空間、時間和位置語義距離三方面的度量結(jié)果后，根據(jù)用戶需求的不同，按不同比例綜合三個因素即可得到整條軌跡的時空語義相似度?？紤]到不同單位和數(shù)量級，采用極差標準化（min-max normalization）方法將差異數(shù)據(jù)進行統(tǒng)一。將原始數(shù)據(jù)進行線性變換，設(shè)maxA和minA分別為屬性集合A的最大值和最小值，將A的一個原始值x通過min-max標準化映射成為區(qū)間[0,1]之間的數(shù)值x′，公式如下：

假設(shè)經(jīng)過標準化后的空間距離為D′space，時間距離為D′time，語義距離為D′sem，給出總的室內(nèi)空間移動軌跡相似度計算公式：

其中，δ、η和λ為用戶用來調(diào)節(jié)各個影響因素的所占比重，δ+η+λ=1。

5 實驗及分析

5.1 實驗環(huán)境

本文實驗的硬件環(huán)境為Intel?CoreTMi7-2670QM 2.20 GHz CPU，4 GB內(nèi)存，軟件環(huán)境為Windows 7操作系統(tǒng)和Visual Studio 2010開發(fā)環(huán)境。由于目前無法獲得真實的室內(nèi)移動對象軌跡數(shù)據(jù)集，本文采用隨機數(shù)據(jù)生成器進行仿真模擬實驗，模擬應(yīng)用場景為室內(nèi)大型機場，人員流動視為移動對象。

軌跡數(shù)據(jù)信息如表1所示，實驗設(shè)置6組實驗數(shù)據(jù)，移動對象個數(shù)分別為150、300、600、1 200、2 400、4 800，所生成軌跡數(shù)目分別為1 000、2 000、5 000、10 000、20 000、40 000條，每條軌跡平均包含約30個位置記錄。

Table 1 Data of indoor moving object trajectory表1 室內(nèi)移動對象軌跡數(shù)據(jù)表

5.2 軌跡重構(gòu)有效性

軌跡重構(gòu)需要最大程度保留原始軌跡的特性同時節(jié)省算法執(zhí)行開銷。本實驗采用經(jīng)典Top-K查詢算法NRA（random access algorithm）[17]取Top-10條相似軌跡相似值并計算其平均值，如圖6所示，將原軌跡IMTSM-NC與重構(gòu)軌跡IMTSM在同一場景下進行軌跡相似性度量對比實驗。軌跡數(shù)目與Top-10相似軌跡相似值均值呈同趨勢增長，且原軌跡數(shù)據(jù)與重構(gòu)軌跡數(shù)據(jù)的軌跡相似值平均值非常接近，差值均小于0.5%，在軌跡數(shù)目達10 000條時兩種軌跡數(shù)據(jù)的相似值均值重合，因此相對于原始軌跡IMTSM-NC，重構(gòu)軌跡IMTSM對軌跡相似性計算的改變非常小，說明本文所提出的軌跡重構(gòu)算法可以很好地保留原始軌跡特征。

Fig.6 Similarity contrast of reconstruct trajectories and original trajectories圖6 重構(gòu)軌跡與原軌跡相似性對比

圖7為原始軌跡IMTSM-NC與重構(gòu)軌跡IMTSM在算法執(zhí)行時間方面的對比實驗，在軌跡數(shù)目小于5 000條時，兩種軌跡數(shù)據(jù)的執(zhí)行時間差距較小，隨著軌跡數(shù)目的增長，重構(gòu)軌跡IMTSM的算法執(zhí)行時間明顯小于原始軌跡IMTSM-NC，且軌跡數(shù)目越大，算法執(zhí)行的時間差越大，說明本文所提出的軌跡重構(gòu)方法可以有效提高室內(nèi)軌跡相似性算法執(zhí)行效率。

Fig.7 Algorithm execution time contrast圖7 算法執(zhí)行時間對比

5.3 用戶參數(shù)對軌跡相似性的影響

式（12）中，參數(shù)δ、η和λ分別為用戶對空間、時間和位置語義在IMTSM算法中設(shè)置的權(quán)重。本實驗取軌跡數(shù)目為20 000條時Top-10條相似軌跡，計算其平均相似值，并分別對用戶參數(shù)極端分布情況和均勻分布情況進行實驗分析。實驗結(jié)果如表2所示。

Table 2 User parameter ratio extreme and uniform表2 用戶參數(shù)比極端分布與均勻分布

其中算法執(zhí)行時間在用戶參數(shù)為極端分布和均勻分布兩種情況下均為3.1 s，說明用戶參數(shù)分布對IMTSM算法的執(zhí)行效率沒有影響。而Top-10條相似軌跡的平均相似值在用戶參數(shù)均勻分布時略高，這是因為用戶沒有對哪一種影響因素特殊考慮時相似軌跡的選擇范圍較大。相對于用戶參數(shù)均勻分布的情況，軌跡相似值在極端分布時的變動幅度可以說明空間、時間和位置語義三種因素對IMTSM算法的影響程度。如表2所示，空間權(quán)重δ極端大時，變動幅度為0.03，時間權(quán)重η極端大時，變動幅度為0.04，位置語義權(quán)重λ極端大時，變動幅度為0.09，說明對于室內(nèi)移動對象軌跡相似性計算，位置語義因素影響最大，其次是時間因素和空間因素。因此，結(jié)合用戶的不同需求，通過設(shè)定相應(yīng)的參數(shù)分布，獨立計算其位置語義相似度，時間相似度和空間相似度可以更為有效地計算出不同需求下的室內(nèi)移動對象軌跡相似性。

5.4 室內(nèi)軌跡相似性度量算法有效性

LIP算法[11]是當前較為流行的軌跡時空相似性度量算法之一，SIT算法[16]為目前最新的可用于室內(nèi)軌跡相似性度量的算法。本實驗采用LIP算法和SIT算法與本文所提算法IMTSM進行對比實驗，在相同軌跡數(shù)據(jù)集、相同查詢軌跡、相同用戶參數(shù)分布情況下，取Top-10條相似軌跡相似值并計算其平均值。

Fig.8 Indoor trajectory similarity algorithm contrast圖8 室內(nèi)軌跡相似性算法對比

如圖8所示，是相同場景下三種算法的軌跡相似度計算對比實驗結(jié)果，當軌跡數(shù)目小于2 000條時，三種算法的軌跡相似值較為接近，當軌跡數(shù)目超過20 000條時，IMTSM算法產(chǎn)生明顯優(yōu)勢，且隨著軌跡數(shù)目的不斷增加，優(yōu)勢越明顯。這是因為LIP算法雖然在軌跡時空相似性計算方面取得很好的成果，但其算法更適合應(yīng)用于室外空間。首先LIP算法采用二維軌跡距離計算，而室內(nèi)環(huán)境下多為三維軌跡；其次，LIP算法并未加入位置語義相似度的考量，在室內(nèi)環(huán)境下度量準確性較低。另外，SIT算法設(shè)計了語義分層模式擴充位置語義距離計算，其度量準確性也高于LIP，相比于LIP算法更適合室內(nèi)環(huán)境。然而，SIT算法未考慮軌跡時間距離，并且仍然基于最長公共子序列LCSS算法計算位置語義相似度，而LCSS主要用于計算兩個字符串之間的最大公共子序列，基于LCSS算法計算移動對象軌跡中的位置語義序列，將字符等同性作為相似依據(jù)，忽略了位置語義序列與字符串序列的不同。

IMTSM算法將時間因素從軌跡時空距離中提取進行獨立計算，利用軌跡投影相交面積設(shè)計了室內(nèi)軌跡空間距離算法，并且基于位置語義分析樹直接提取位置語義距離。相比于SIT算法，IMTSM算法增加了軌跡相似性影響因素，減少了語義模式分析過程，避免了文本相似計算所帶來的誤差，可以更加精確地查詢室內(nèi)相似軌跡。

如圖9所示，取Top-10條相似軌跡并將其抽象化，（a）為原始查詢軌跡，（b）為IMTSM算法所得Top-10條相似軌跡，（c）為SIT算法所得Top-10條相似軌跡。從圖中可以看出，采用IMTSM算法得到的相似軌跡與SIT算法相比更為接近原始查詢軌跡，而且SIT算法得到的相似軌跡中明顯存在軌跡偏離及中斷的情況。因此，采用IMTSM算法所得到的軌跡相似性要高于SIT算法，說明所提出的IMTSM算法能夠更好地應(yīng)用于查詢室內(nèi)相似移動對象軌跡。

Fig.9 Top-10 similar indoor trajectories圖9 Top-10相似室內(nèi)軌跡

6 結(jié)束語

隨著室內(nèi)位置服務(wù)的多元化發(fā)展，室內(nèi)移動對象軌跡相似性查詢具有重要的研究價值。本文給出了一種適用于室內(nèi)空間的移動對象軌跡相似性度量方法IMTSM，并對其進行了相關(guān)闡述。根據(jù)室內(nèi)空間特點，提出將時間距離獨立計算并給出新的時空距離計算方法，設(shè)計位置語義分析樹結(jié)構(gòu)并基于此給出語義位置距離提取算法，很好地解決了文本絕對性比較直接應(yīng)用于軌跡相似性計算不夠精確和代價過高的問題。最后，通過實驗對IMTSM方法的準確性和有效性進行了驗證。下一步研究的重點主要集中在結(jié)合室內(nèi)空間索引技術(shù)實現(xiàn)高效的室內(nèi)相似軌跡查詢。