(中國西南電子技術(shù)研究所，成都 610036)

基于最長公共子序列的非同步相似軌跡判斷*

劉 宇，王前東**

(中國西南電子技術(shù)研究所，成都 610036)

針對非同步相似軌跡判斷問題，提出了一種基于最長公共子序列理論的相似軌跡判斷新算法。首先，求出查詢軌跡線段與候選軌跡線段之間的距離；其次，利用最長公共子序列算法，計算兩軌跡的最長公共子軌跡長度；最后，根據(jù)相似度門限，判斷軌跡是否相似。數(shù)值實例驗證了所提算法能夠提高非同步軌跡的相似度。

偵察監(jiān)視；最長公共子序列；非同步相似軌跡；最長公共子軌跡

1 引 言

近年來，目標的行為活動規(guī)律備受關(guān)注。在目標偵察監(jiān)視系統(tǒng)中，目標經(jīng)常在某個區(qū)域進行著相似的偵察行動，這使得目標的運動軌跡具有較強的相似性。通過對獲取的目標的軌跡進行分析、理解并判斷目標的行為活動規(guī)律是偵察監(jiān)視系統(tǒng)的重要任務(wù)之一。

對于目標軌跡的分析，關(guān)鍵是軌跡間相似性的判斷。軌跡間的相似性判斷可以通過軌跡間的距離來表示?，F(xiàn)有的軌跡距離表示方法主要有歐式距離(Euclidean)、動態(tài)時間彎曲距離(Dynamic Time Warping,DTW)[1]、最長公共子序列[2-14](Longest Common Subsequence,LCS)等。歐式距離法使用較早、計算簡單，但要求所有的軌跡不能有強噪聲，而且所有的軌跡必須有相同的點數(shù)。動態(tài)時間彎曲距離法對所有的軌跡不再要求有相同的點數(shù)，但要求所有的軌跡不能有強噪聲。最長公共子序列法對所有的軌跡不再要求有相同的點數(shù)，能處理具有少量強噪聲的軌跡，即最長公共子序列方法既能處理不同點數(shù)的軌跡，又能處理具有強噪聲的軌跡，已成為軌跡相似判斷的重要方法之一。

文獻[3]將軌跡看作序列，將相似軌跡問題轉(zhuǎn)化為最長公共子序列問題，提供了一個基于最長公共子序列算法的相似度量，用實驗證明了該度量既能處理不同點數(shù)的軌跡，又能處理具有強噪聲的軌跡，比常用的歐式距離和動態(tài)時間彎曲距離魯棒，但該文沒有處理軌跡不同步的情形。

在實際中，獲取的目標軌跡起點不同，采樣周期也不同，因此目標軌跡是不同步的。本文利用文獻[3]的思想，針對這種非同步的軌跡，將軌跡之間點與點的比較轉(zhuǎn)化為軌跡之間線段與線段的比較，提出一種基于最長公共子序列的相似軌跡判斷新算法。

2 相似軌跡基礎(chǔ)知識

2.1最長公共子序列

設(shè)兩序列Qm=(q1,q2,…,qm)與Cn=(c1,c2,…,cn)的公共子序列為Zr=(z1,z2,…,zr)，則Zr必須滿足

(1)

Zr為兩序列Qm與序列Cn的最長公共子序列，當且僅當Zr為滿足上述條件中最長的公共子序列。

令L(m,n)表示序列Qm與序列Cn的最長公共子序列長度，則L(m,n)有如下遞推計算公式：

(2)

L(m,n)為一般的最長公共子序列算法，其推導見參見文獻[1]。L(m,n)計算的時空復雜度為O(mn)。

2.2基于最長公共子序列的相似軌跡

設(shè)有軌跡Qm=((qx,1,qy,1),…,(qx,m,qy,m))與軌跡Cn=((cx,1,cy,1),…,(cx,n,cy,n))，則有如下定義：

定義1 令ε>0為距離閾值，令L1ε(m,n)為軌跡Qm與軌跡Cn按點跡距離定義的最長公共子軌跡長度，則L1ε(m,n)可由如下遞推公式求出：

(3)

其中：dis(qi,cj)為兩點qi與cj的歐式距離。計算L1的初始值為：對任意i≥0，L1ε(i,0)=0；對任意j≥0，L1ε(0,j)=0。

根據(jù)公式(3)求出的L1ε(m,n)即為L1ε(Qm,Cn)。

定義2 令ε>0為距離閾值，令f1為軌跡Qm與軌跡Cn按點跡距離定義的相似度，則f1可由如下公式求出：

(4)

定義3 令λ>0為相似度閾值，則軌跡Cn與軌跡Qm按點跡距離相似軌跡當且僅當：

f1ε(Qm,Cn)≥λ。

(5)

例1：基于最長公共軌跡的相似軌跡判斷

設(shè)有如下3個軌跡序列：查詢軌跡Q={10，20，30，40，50，60，70，80，90，100}及兩候選軌跡C1={1，11，21，31，41，51，61，71，81，91，101}和C2={5，15，25，35，45，55，65，75，85，95，105}。

令距離閾值為ε=2，λ=0.5，則軌跡Q與C1的相似度f1ε(Q,C1)= 100%>λ，兩軌跡Q與C1相似；軌跡Q與C2的相似度f1ε(Q,C2)=0<λ，兩軌跡Q與C2不相似。這兩軌跡Q與C2判為不相似與實際不符。實際上，Q與C2明顯是同一軌跡，只是采樣點時間不同步造成了軌跡數(shù)值有差異。

3 非同步相似軌跡判斷新算法

設(shè)有軌跡Qm=((qx,1,qy,1),…,(qx,m,qy,m))與軌跡Cn=((cx,1,cy,1),…,(cx,n,cy,n))，則有如下定義：

(6)

其中：dis(qi,c)為兩點qi與c的歐式距離。

(7)

定義6 令ε>0為距離閾值，令L2ε(Qm,Cn)為軌跡Qm與軌跡Cn按線段距離定義的最長公共子軌跡長度，則L2ε(Qm,Cn)可由如下遞推公式求出：

(8)

其中：計算L2的初始值為L2ε(i,1)=0或L2ε(1,j)=0,i=2,3,…,m；j=2,3,…,n。

根據(jù)公式(8)求出的L2ε(m,n)即為L2ε(Qm,Cn)。

定義7 令f2為軌跡Qm與軌跡Cn按線段距離定義的相似度，則f2可由如下公式求出：

(9)

定義8 令λ>0為相似度閾值，則軌跡Cn與軌跡Qm按線段距離相似當且僅當

f2ε(Qm,Cn)≥λ。

(10)

根據(jù)以上定義，有如下的非同步軌跡相似判斷的計算流程：

Step1 用0初始化長度為m、n的公共軌跡長度矩陣L(m,n)。

Step2 利用公式(8)，通過兩重循環(huán)算法計算兩軌跡的公共軌跡長度矩陣L(m,n)，L(m,n)即為Qm與Cn的最長公共軌跡長度L2ε(Qm,Cn):

Fori=2:m

Forj=2:n

L(i,j)=L(i-1,j-1)+1;

Else

L(i,j)=max(L(i-1,j),L(i,j-1));

End

End

End

Step3 根據(jù)公式(9)計算兩軌跡的相似度f2ε(Qm,Cn)。

Step4 根據(jù)公式(10)和設(shè)定的閾值λ判斷兩軌跡是否相似。

根據(jù)以上的計算流程可以看出有如下兩個定理成立：

定理1 令ε>0為距離閾值，計算軌跡Qm與軌跡Cn的最長公共子軌跡長度L2ε(Qm,Cn)的時間復雜度為O(mn)，其中m、n分別為查詢軌跡Qm、候選軌跡Cn的軌跡長度。

證明：從計算流程中可以看出，Step1，初始化矩陣L的時間復雜度為O(mn)；Step2，為計算L(m,n)的關(guān)于m、n的兩重循環(huán)，其時間復雜度為O(mn)；Step3與Step4的時間復雜度為O(1)。故計算L2ε(Qm,Cn)的時間復雜度為O(mn)。

定理2 令ε>0為距離閾值，f1和f2分別為軌跡Qm與軌跡Cn按點跡距離和按線段距離定義的相似度，則有f2≥f1。

證明：由點跡距離與線段距離定義可有如下結(jié)論成立：

利用此結(jié)論，由最長公共子序列遞推公式(3)和公式(8)可推出如下結(jié)論成立：

L1ε(m,n)≤L2ε(m,n)+1 。

(11)

由此即可推出如下結(jié)論成立：

(12)

兩序列的最長公共子序列長度肯定小于等于兩序列長度定義，即

L2ε(m,n)

(13)

由公式(12)和公式(13)，有

(14)

利用此不等式，由相似度定義可推出f1ε(Qm,Cn)≤f2ε(Qm,Cn)。

4 數(shù)值實例

例2：改進的相似軌跡判斷

設(shè)有3個軌跡序列：查詢軌跡Q={(0,1 000),(1 000,2 000),(2 000,4 000),(3 000,6 000),(4 000,9 000),(5 000,8 000),(6 000,6 000),(7 000,3 000),(8 000,4 000),(9 000,6 000)}m及兩候選軌跡C1={(0,1 001),(1 000,2 001),(2 000,4 001),(3 000,6 001),(4 000,9 001),(5 000,8 001),(6 000,6 001),(7 000,3 001),(8 000,4 001),(9 000,6 001)}m和C2={(500,1 500),(1 500,3 000),(2 500,5 000),(3 500,7 500),(4 000,9 000),(4 500,8 500),(5 500,7 000),(6 500,4 500),(7 000,3 000),(7 500,3 500),(8 500,5 000)}m。其中軌跡Q與軌跡C1是同步軌跡(點數(shù)和周期都相同)，每點位置距離只差1 m，如圖1中的同步軌跡所示；軌跡C2與軌跡Q是異步軌跡(點數(shù)和起點都不相同)，除了C2中的第5點(4 000,9 000)m和第9點(7 000,3 000)m分別與Q中的第5點和第8點相同外，軌跡C2中其他點與軌跡Q的點之間的距離至少相差500 m，如圖1中的異步軌跡所示。

圖1 同步與異步軌跡圖Fig.1 Synchronous track and asynchronous track

令距離閾值為ε=2，λ=0.5，則按文獻[3]的方法計算的軌跡Q與C1的最長公共軌跡長度為10，軌跡Q與C1的相似度f1ε(Q,C1)= 100%，兩軌跡Q與C1判為相似；軌跡Q與C2只有兩點接近，軌跡Q與C2的最長公共軌跡的長度為2，軌跡Q與C2的相似度f1ε(Q,C2)=20%，兩軌跡Q與C2判為不相似。

同樣令距離閾值為ε=2，λ=0.5，按本文新方法計算的軌跡Q與C1的公共軌跡的長度為9，軌跡Q與C1的相似度f2ε(Q,C1)= 100%，兩軌跡Q與C1判為相似；軌跡Q與C2的公共軌跡長度為9，軌跡Q與C2的相似度f2ε(Q,C2)=100%，兩軌跡Q與C2判為相似。

從上面的例子看出，本文的新方法既可以用于同步軌跡(Q與C1)的判斷，又可以用于非同步軌跡(Q與C2)的判斷。

5 數(shù)值仿真試驗

在某次仿真實驗中，仿真了12個目標的6組典型軌跡，6組軌跡幾乎不同步(軌跡起始點和終止點不同，軌跡點數(shù)不同，軌跡采樣周期不同)。6組12個目標的運動軌跡如圖2所示。

圖2 目標的運動軌跡圖Fig.2 Motion track of targets

從圖2中可以看出，12個目標組成的6組軌跡{T1，T2}、{T3，T4}、{T5，T6}、{T7，T8}、{T9，T10}、{T11，T12}幾乎相同，故可用這6組數(shù)據(jù)進行軌跡相似性檢驗。

設(shè)距離閾值ε為1～10 km，則6組目標按點跡距離計算的相似度和按線段距離計算的相似度分別為f1和f2，如圖3所示。

圖3 不同距離門限閾值的相似度圖Fig.3 Similarity measure for different distance gate

從圖3可以看出，針對不同目標和不同距離門限閾值，本文提出的新方法計算的相似度f2都比文獻[3]提出的相似度f1高，本文提出的方法更能適應(yīng)非同步的相似軌跡的判斷；隨著門限值增大，本文提出的新方法計算的相似度f2逐漸逼近文獻[3]提出的相似度f1。

6 結(jié) 論

本文利用線段距離，通過LCS算法改進軌跡相似度判斷方法，使算法更適用于不同步軌跡之間的判斷。數(shù)值實例表明，本文的改進方法更適用于非同步的軌跡判斷中。數(shù)值仿真實驗表明，本文計算的相似度f2比文獻[3]計算的相似度f1高，本文算法能夠提高非同步軌跡計算的相似度。

本文算法可以進一步應(yīng)用于軌跡的聚類、軌跡的規(guī)律分析及軌跡的查詢、識別等。在實際應(yīng)用中，相似度的計算跟距離閾值ε有關(guān)，閾值的大小需要根據(jù)具體的應(yīng)用要求修改。

[1] AGRAWAL R,FALOUTSOS C,SWAMI AN. Efficient similarity search in sequence databases[C]// Proceedings of International Conference on Foundations of Data Organization and Algorithms. Chicago:Springer-Verlag,1993:69-84.

[2] LI Q,SUN M. On discovery of learned paths from taxi origin-destination trajectories[C]// Proceedings of 2015 34th Chinese Control Conference (CCC).Hangzhou:IEEE，2015:3896-3901.

[3] VLACHOS M,GUNOPOULOS D,KOLLIOS G. Discovering similar multidimensional trajectories[C]// Proceedings of International Conference on Data Engineering. San Jose:IEEE Computer Society,2002:673.

[4] PELEKIS N,KOPANAKIS I,MARKETOS G,et al. Similarity search in trajectory databases[C]// Proceedings of International Symposium on Temporal Representation and Reasoning. Alicante:IEEE,2007:129-140.

[5] SKOUMAS G,SKOUTAS D,VLACHAKI A. Efficient identification and approximation of k-nearest moving neighbors[C]//Proceedings of ACM Sigspatial International Conference on Advances in Geographic Information Systems. New York:ACM,2013:264-273.

[6] YUAN Y H,RAUBAL M. Measuring similarity of mobile phone user trajectories-a spatio-temporal edit distance method[J].International Journal of Geographical Information Science,2014,28(3):496-520.

[7] YING J C,LU H C,LEE W C,et al. Mining user similarity from semantic trajectories[C]//Proceedings of ACM Sigspatial International Workshop on Location Based Social Networks. San Jose:ACM,2010:19-26.

[8] WANG H,LIU K. User oriented trajectory similarity search[C]//Proceedings of ACM SIGKDD International Workshop on Urban Computing. Beijing: ACM, 2012:103-110.

[9] WANG H,ZHONG J,ZHANG D. A duplicate code checking algorithm for the programming experiment[C]//Proceedings of Second International Conference on Mathematics and Computers in Sciences and in Industry. Sliema:IEEE,2016:39-42.

[10] REKABDAR B,NICOLESCU M,NICOLESCU M,et al. Scale and translation invariant learning of spatio-temporal patterns using longest common subsequences and spiking neural networks[C]//Proceedings of International Joint Conference on Neural Networks. Killarney:IEEE,2015:1-7.

[11] GU Y,CHEN M,REN F,et al. HED:handling environmental dynamics in indoor wifi fingerprint localization[C]//Proceedings of Wireless Communications and NETWORKING Conference. Doha,IEEE,2016:1-6.

[12] HO S S,DAI P,RUDZICZ F. Manifold learning for multivariate variable-length sequences with an application to similarity search.[J].IEEE Transactions on Neural Networks & Learning Systems,2015,27(6):1333-1344.

[13] BEAL R,AFRIN T,FARHEEN A,et al. A new algorithm for the LCS problem with application in compressing genome resequencing data[C]//Proceedings of IEEE International Conference on Bioinformatics and Biomedicine. Washington DC:IEEE,2015:69-74.

[14] PROZOROV D,YASHINA A. The extended longest common substring algorithm for spoken document retrieval[C]//Proceedings of International Conference on Application of Information and Communication Technologies. Rostov-on-Don,Russia:IEEE,2015:88-90.

ComputingSimilarMeasurebetweenTwoAsynchronousTrajectoriesBasedonLongestCommonSubsequenceMethod

LIU Yu，WANG Qiandong
(Southwest China Institute of Electronic Technology,Chengdu 610036,China)

For the problem of judging the asynchronous similar trajectory,a new algorithm for computing the similar trajectories is proposed based on the Longest Common Subsequence (LCS) method. Firstly,the line segment distances,which are between line segments of the query trajectory and the line segments of the candidate trajectory,are computed by the line segment distance. Secondly,the length of the longest common sub-trajectory,which is between the query trajectory and the candidate trajectory,is computed by the LCS method. Finally,the similarity measure between two trajectories is computed and the similar trajectory is got. Simulation shows the new method can improve the similarity measure between two asynchronous trajectories.

reconnaissance and surveillance;longest common subsequence;asynchronous similar trajectory;longest common sub-trajectory

date:2017-04-01；Revised date：2017-08-23

**通信作者：wangqiandong@sohu.com Corresponding author：wangqiandong@sohu.com

TN957.52

A

1001-893X(2017)10-1165-06

劉宇(1977—)，男，四川廣漢人，2000年于四川大學獲學士學位，現(xiàn)為工程師，主要研究方向為情報偵察及情報處理；

王前東(1977—)，男，四川西充人，2004年獲碩士學位，現(xiàn)為高級工程師，主要從事情報數(shù)據(jù)融合處理研究。

Email:wangqiandong@sohu.com

10.3969/j.issn.1001-893x.2017.10.011

劉宇，王前東.基于最長公共子序列的非同步相似軌跡判斷[J].電訊技術(shù)，2017,57(10):1165-1170.[LIU Yu，WANG Qiandong.Computing similar measure between two asynchronous trajectories based on longest common subsequence method[J].Telecommunication Engineering,2017,57(10):1165-1170.]

2017-04-01；

2017-08-23