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

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

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

劉 宇，王前東**

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

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

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

1 引 言

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

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

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

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

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

2.1最長公共子序列

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

(1)

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

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

(2)

L(m,n)為一般的最長公共子序列算法，其推導(dǎo)見參見文獻(xiàn)[1]。L(m,n)計(jì)算的時(shí)空復(fù)雜度為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按點(diǎn)跡距離定義的最長公共子軌跡長度，則L1ε(m,n)可由如下遞推公式求出：

(3)

其中：dis(qi,cj)為兩點(diǎn)qi與cj的歐式距離。計(jì)算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按點(diǎn)跡距離定義的相似度，則f1可由如下公式求出：

(4)

定義3 令λ>0為相似度閾值，則軌跡Cn與軌跡Qm按點(diǎn)跡距離相似軌跡當(dāng)且僅當(dāng)：

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判為不相似與實(shí)際不符。實(shí)際上，Q與C2明顯是同一軌跡，只是采樣點(diǎn)時(shí)間不同步造成了軌跡數(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)為兩點(diǎn)qi與c的歐式距離。

(7)

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

(8)

其中：計(jì)算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按線段距離相似當(dāng)且僅當(dāng)

f2ε(Qm,Cn)≥λ。

(10)

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

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

Step2 利用公式(8)，通過兩重循環(huán)算法計(jì)算兩軌跡的公共軌跡長度矩陣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)計(jì)算兩軌跡的相似度f2ε(Qm,Cn)。

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

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

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

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

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

證明：由點(diǎn)跡距離與線段距離定義可有如下結(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ù)值實(shí)例

例2：改進(jìn)的相似軌跡判斷

設(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是同步軌跡(點(diǎn)數(shù)和周期都相同)，每點(diǎn)位置距離只差1 m，如圖1中的同步軌跡所示；軌跡C2與軌跡Q是異步軌跡(點(diǎn)數(shù)和起點(diǎn)都不相同)，除了C2中的第5點(diǎn)(4 000,9 000)m和第9點(diǎn)(7 000,3 000)m分別與Q中的第5點(diǎn)和第8點(diǎn)相同外，軌跡C2中其他點(diǎn)與軌跡Q的點(diǎn)之間的距離至少相差500 m，如圖1中的異步軌跡所示。

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

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

同樣令距離閾值為ε=2，λ=0.5，按本文新方法計(jì)算的軌跡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ù)值仿真試驗(yàn)

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

圖2 目標(biāo)的運(yùn)動軌跡圖Fig.2 Motion track of targets

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

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

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

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

6 結(jié) 論

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

本文算法可以進(jìn)一步應(yīng)用于軌跡的聚類、軌跡的規(guī)律分析及軌跡的查詢、識別等。在實(shí)際應(yīng)用中，相似度的計(jì)算跟距離閾值ε有關(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年于四川大學(xué)獲學(xué)士學(xué)位，現(xiàn)為工程師，主要研究方向?yàn)榍閳?bào)偵察及情報(bào)處理；

王前東(1977—)，男，四川西充人，2004年獲碩士學(xué)位，現(xiàn)為高級工程師，主要從事情報(bào)數(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