基于大地距離計(jì)算相似度的海上目標(biāo)軌跡預(yù)測(cè)

趙一鑒，林利，王茜蒨，4*，聞鵬，楊東

基于大地距離計(jì)算相似度的海上目標(biāo)軌跡預(yù)測(cè)

趙一鑒1，2，林利3，王茜蒨1，2，4*，聞鵬5，楊東5

（1.北京理工大學(xué) 光電學(xué)院，北京 100081； 2.信息光子技術(shù)工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室（北京理工大學(xué)），北京 100081； 3.中國(guó)人民解放軍32011部隊(duì)，北京 100094； 4.北京理工大學(xué)長(zhǎng)三角研究院，浙江 嘉興 314033； 5.航天恒星科技有限公司，北京 100095）（ ? 通信作者電子郵箱qqwang@bit.edu.cn）

目前基于相似度的移動(dòng)目標(biāo)軌跡預(yù)測(cè)算法一般根據(jù)數(shù)據(jù)的時(shí)空特性進(jìn)行分類，無(wú)法體現(xiàn)算法自身的特點(diǎn)，為此提出一種基于算法特征的分類方法。軌跡相似度算法通常需要先計(jì)算兩點(diǎn)之間的距離，再開(kāi)展后續(xù)計(jì)算，而常用的歐氏距離（ED）只適用于目標(biāo)在小區(qū)域范圍內(nèi)移動(dòng)的問(wèn)題。針對(duì)現(xiàn)有基于相似度的軌跡預(yù)測(cè)算法無(wú)法適用于移動(dòng)范圍比較大的海上目標(biāo)軌跡預(yù)測(cè)的問(wèn)題，提出使用大地距離代替ED進(jìn)行相似度計(jì)算。首先，對(duì)軌跡數(shù)據(jù)進(jìn)行預(yù)處理和分段；其次采用離散弗雷歇距離（FD）作為相似性度量；最后，利用模擬數(shù)據(jù)和實(shí)際數(shù)據(jù)進(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，當(dāng)海上目標(biāo)移動(dòng)范圍較大時(shí)，采用ED算法可能會(huì)得到不正確的預(yù)測(cè)結(jié)果，而所提算法可輸出正確的目標(biāo)軌跡預(yù)測(cè)結(jié)果。

軌跡相似度；軌跡預(yù)測(cè)；歐氏距離；大地距離；弗雷歇距離

0 引言

移動(dòng)目標(biāo)軌跡預(yù)測(cè)指根據(jù)歷史數(shù)據(jù)預(yù)測(cè)目標(biāo)在未來(lái)的運(yùn)動(dòng)軌跡，它對(duì)于目標(biāo)的位置預(yù)測(cè)、目標(biāo)異常行為檢測(cè)、智能交通監(jiān)管、海上船只防撞預(yù)警等具有重要意義。

目前的移動(dòng)目標(biāo)軌跡預(yù)測(cè)方法可分為三類：基于概率統(tǒng)計(jì)的方法、基于機(jī)器學(xué)習(xí)的方法和基于軌跡相似度的方法。其中，基于概率統(tǒng)計(jì)的預(yù)測(cè)方法包括卡爾曼濾波、差分自回歸移動(dòng)平均、馬爾可夫模型、高斯混合模型、貝葉斯網(wǎng)絡(luò)等，優(yōu)點(diǎn)是數(shù)學(xué)方法成熟、應(yīng)用較廣，但預(yù)測(cè)精度嚴(yán)重依賴于軌跡數(shù)據(jù)本身的間隔和誤差，且無(wú)法對(duì)長(zhǎng)時(shí)間的軌跡進(jìn)行精準(zhǔn)預(yù)測(cè)［1］。基于機(jī)器學(xué)習(xí)的預(yù)測(cè)算法包括神經(jīng)網(wǎng)絡(luò)和深度學(xué)習(xí)，深度學(xué)習(xí)算法包括循環(huán)神經(jīng)網(wǎng)絡(luò)、長(zhǎng)短期記憶、極限學(xué)習(xí)機(jī)等，優(yōu)點(diǎn)是預(yù)測(cè)精度較高，但所需的訓(xùn)練數(shù)據(jù)量大、算法可解釋性低［1］。此外，還有一些基于混合模型的預(yù)測(cè)算法，如概率統(tǒng)計(jì)與深度學(xué)習(xí)相結(jié)合的方法［2］、馬爾可夫與神經(jīng)網(wǎng)絡(luò)相結(jié)合的方法［3］等，通過(guò)融合不同的預(yù)測(cè)方法來(lái)提高預(yù)測(cè)精度。無(wú)論是概率統(tǒng)計(jì)還是機(jī)器學(xué)習(xí)算法，都需要大量數(shù)據(jù)進(jìn)行概率分析或機(jī)器訓(xùn)練；當(dāng)歷史數(shù)據(jù)較少時(shí)，預(yù)測(cè)效果都不佳。基于軌跡相似度的預(yù)測(cè)方法假設(shè)目標(biāo)運(yùn)動(dòng)遵循一定的周期或規(guī)律，根據(jù)觀測(cè)到的一段軌跡，從歷史軌跡中尋找一條最相似的軌跡，并把此軌跡中的后續(xù)數(shù)據(jù)作為目標(biāo)預(yù)測(cè)軌跡。當(dāng)目標(biāo)歷史數(shù)據(jù)較少時(shí)，這種方法不失為一種可行的方法。謝彬等［4］利用軌跡相似度算法對(duì)移動(dòng)目標(biāo)進(jìn)行軌跡預(yù)測(cè)，王愛(ài)兵等［5］利用軌跡相似度算法對(duì)行人軌跡進(jìn)行預(yù)測(cè)，張春瑋等［6］利用軌跡相似度算法對(duì)船舶軌跡進(jìn)行聚類分析和異常檢測(cè)。軌跡相似度算法在其他方面的研究應(yīng)用包括出租車合乘、公交線路調(diào)整、軌跡社區(qū)發(fā)現(xiàn)、伴隨人員推薦等［7-10］。

軌跡相似度的算法很多。Magdy等［11］根據(jù)軌跡數(shù)據(jù)是否包含時(shí)間信息，把相似度算法分為空間相似度算法和時(shí)空相似度算法兩大類。Su等［12］根據(jù)軌跡數(shù)據(jù)是否包含時(shí)間信息以及軌跡是連續(xù)的還是離散的，把相似度算法分為連續(xù)序列、離散序列、連續(xù)時(shí)空和離散時(shí)空四類算法。這兩種分類方法更多關(guān)注的是數(shù)據(jù)本身的特性。本文根據(jù)算法自身的特點(diǎn)，把軌跡相似度算法分為三類：基于面積特性、基于距離特性和基于運(yùn)動(dòng)方向特性。

1）基于面積特性的算法。這類算法的思路是如果兩條軌跡重合，兩軌跡圍成的面積是零；如果軌跡不重合，則面積越小越相似。主要的算法有多線位置距離（Locality In-between Polylines， LIP）。

2）基于距離特性的算法。這類算法的思路是如果兩條軌跡是重合的，軌跡之間的距離是零；如果軌跡不重合，則軌跡之間的距離越小相似度越高。軌跡之間的距離既可以是多個(gè)點(diǎn)之間的平均距離，也可以是特征點(diǎn)之間的距離。歐氏距離（Euclidean Distance， ED）是最簡(jiǎn)單常用的一種算法［11-12］，它是兩條軌跡上對(duì)應(yīng)點(diǎn)之間距離的平均值，表達(dá)式如下：

基于平均距離特性的算法還包括：動(dòng)態(tài)時(shí)間規(guī)整（Dynamic Time Warping， DTW）、最長(zhǎng)公共子序列（Longest Common Sub-Sequence， LCSS）、編輯距離（Edit Distance on Real sequence， EDR）、單向距離（One Way Distance， OWD）、時(shí)間扭曲編輯距離（Time Warp Edit Distance， TWED）、帶有實(shí)數(shù)懲罰的編輯距離（Edit distance with Real Penalty， ERP）、融合距離（Merge Distance， MD）等［11-12］。

基于兩軌跡上特征點(diǎn)距離的算法包括豪斯多夫距離（Hausdorff Distance， HD）、弗雷歇距離（Fréchet Distance， FD）、最近鄰距離（Closest-Pair Distance， CPD）等。HD是兩條軌跡中最近點(diǎn)距離的最大值［11-12］，它的值越小，兩條軌跡越相似。FD算法與HD算法類似，只不過(guò)在計(jì)算最小距離時(shí)考慮了兩條曲線的流動(dòng)，不考慮從一個(gè)端點(diǎn)回溯到另一個(gè)端點(diǎn)的情形［11-12］。FD通常被稱為“遛狗距離”，假設(shè)一條狗和它的主人在兩條不同的路徑上行走，F(xiàn)D是連接狗和主人所需的最小繩子長(zhǎng)度，也可以把FD看作河流兩岸之間的最寬距離。CPD算法也是基于特征點(diǎn)的算法［13］，它是從兩條軌跡中找到最近的一對(duì)點(diǎn)，它們之間的距離就是最近鄰距離，此值越小說(shuō)明兩曲線越接近。

3）基于運(yùn)動(dòng)方向的算法。這類算法的思路是如果兩條軌跡重合，兩軌跡上各點(diǎn)的運(yùn)動(dòng)方向是相同的；如果軌跡不重合，則運(yùn)動(dòng)方向的夾角越小軌跡越相似。主要的算法包括基于形狀相似性的角度度量（Angular Metric for Shape Similarity， AMSS）、基于運(yùn)動(dòng)模式字符串的編輯距離（Edit Distance on Movement pattern strings， EDM）、軌跡匹配和運(yùn)動(dòng)時(shí)空關(guān)系匹配（Trajectory match and Moving spatiotemporal relation match， TM）等［11］。

以上軌跡相似度算法是最基本的，很多學(xué)者在此基礎(chǔ)上對(duì)算法進(jìn)行了改進(jìn)，以滿足不同場(chǎng)合下的實(shí)際需求。文獻(xiàn)［14］中在HD算法基礎(chǔ)上，提出了一種改進(jìn)的基于時(shí)間約束的算法；文獻(xiàn)［15］中在DTW算法的基礎(chǔ)上結(jié)合DNA序列校準(zhǔn)算法，提出了適用于不同采樣率、對(duì)噪聲魯棒的軌跡相似度算法；文獻(xiàn)［16］中利用軌跡壓縮方法對(duì)LCSS算法進(jìn)行改進(jìn)，提高了計(jì)算速度。此外，還有結(jié)合了文本信息的語(yǔ)義軌跡相似度［9］等新的相似度算法不斷涌現(xiàn)。

相似度算法一般都需要計(jì)算點(diǎn)與點(diǎn)之間的距離，目前采用的都是基于ED，這實(shí)際上是平面上兩點(diǎn)之間的距離公式。考慮到地球表面是個(gè)球面，ED應(yīng)用于移動(dòng)范圍比較大的海上目標(biāo)時(shí)，預(yù)測(cè)結(jié)果可能不正確，本文以下將進(jìn)行分析和驗(yàn)證。

1 海上目標(biāo)軌跡預(yù)測(cè)問(wèn)題

考慮地球上緯度相同、經(jīng)度相差1°的兩點(diǎn)，無(wú)論這兩點(diǎn)在地球表面上的任何地方，應(yīng)用ED得到的結(jié)果都相同?，F(xiàn)在考慮兩種情形：一種是在赤道上，大地距離是111.3 km；另一種是在緯度45°的地方，大地距離是78.8 km，兩者之比大致為1∶cos 45°。為了探究ED和大地距離對(duì)軌跡相似度計(jì)算的影響，下面以一個(gè)簡(jiǎn)單的模型進(jìn)行分析，并用FD作為兩條軌跡相似度的度量。

圖1　目標(biāo)的運(yùn)動(dòng)軌跡

代入式（3）、（4），得：

式（8）可進(jìn)一步簡(jiǎn)化為：

式（9）就是ED公式適用的邊界條件。為了直觀地表明它適用的區(qū)域范圍，以下給出一個(gè)具體的例子。

但對(duì)于在海上自由航行的船只來(lái)說(shuō)，由于船只的移動(dòng)范圍大，每段軌跡的長(zhǎng)度長(zhǎng)，式（9）在某些條件下會(huì)得到滿足。圖1的情形只是一個(gè)特殊的例子，但以上的分析計(jì)算對(duì)目標(biāo)的軌跡形狀并沒(méi)有特殊要求，目標(biāo)的軌跡形狀可以是任意的，只要在適當(dāng)?shù)臈l件下滿足式（9），采用ED算法預(yù)測(cè)的結(jié)果就不正確。因此對(duì)于海上移動(dòng)目標(biāo)的軌跡預(yù)測(cè)，必須采用大地距離公式。

以上采用的大圓弧長(zhǎng)公式是計(jì)算大地距離的一種近似方法，考慮到地球是橢球體，為了準(zhǔn)確計(jì)算兩點(diǎn)之間的大地距離，需要采用更精確的算法?，F(xiàn)有的用于解決大地主題問(wèn)題的方法中，有的適用于短距離（400 km以下），有的適用于中距離（400～1 000 km），有的適用于長(zhǎng)距離（1 000 km以上），其中比較典型的有勒讓德級(jí)數(shù)公式、高斯平均引數(shù)公式和白塞爾公式等［17］。勒讓德級(jí)數(shù)在30 km以下的精度相對(duì)高一些，高斯平均引數(shù)適合于200 km以下的大地主題解算，白塞爾公式的解算精度與距離長(zhǎng)短沒(méi)有關(guān)系，既適用于長(zhǎng)距離，也適用于短距離。如果使用Python語(yǔ)言編程，則可直接調(diào)用geopy庫(kù)中的大地距離計(jì)算函數(shù)。geopy庫(kù)中提供了兩種大地距離計(jì)算方法：Vincenty公式和Great Circle公式。Vincenty公式是文森特（Vincenty）于1975年以白塞爾公式為基礎(chǔ)，推導(dǎo)出的嵌套系數(shù)公式，計(jì)算速度較慢，但計(jì)算結(jié)果更為準(zhǔn)確；Great Circle公式是以球心和球面上兩點(diǎn)組成的大圓上連接兩點(diǎn)的最短弧長(zhǎng)距離。經(jīng)實(shí)際測(cè)試，Vincenty公式的計(jì)算時(shí)間大約是Great Circle公式的2倍。由于這兩種算法計(jì)算時(shí)間很短，一般在幾十到數(shù)百毫秒，因此在各種應(yīng)用中一般首選Vincenty公式。一個(gè)計(jì)算大地距離的例子如下所示：

from geopy import distance

p1 = （41， 103）

p2 = （40， 104）

print （distance.distance（p1， p2））

139.698 755 392 749 97 km

在上面的例子中，調(diào)用distance函數(shù)時(shí)缺省的算法就是Vincenty公式。

2 海上目標(biāo)軌跡預(yù)測(cè)方法

2.1　算法選擇

考慮到FD算法效率較高，應(yīng)用的場(chǎng)合較多，本文選擇FD算法進(jìn)行海上移動(dòng)目標(biāo)軌跡預(yù)測(cè)。FD算法分為連續(xù)FD和離散FD。實(shí)際的軌跡數(shù)據(jù)都是離散的，所謂的連續(xù)FD只不過(guò)是對(duì)離散的軌跡數(shù)據(jù)進(jìn)行插值處理使得離散的軌跡變成連續(xù)的，兩種算法的思路基本相同?？紤]到離散FD算法相對(duì)簡(jiǎn)單，便于編程實(shí)現(xiàn)，本文采用離散FD算法。它的算法公式如下，詳細(xì)的介紹見(jiàn)文獻(xiàn)［18］。

2.2　數(shù)據(jù)預(yù)處理

理想的軌跡數(shù)據(jù)按時(shí)間順序存放，并且沒(méi)有重復(fù)點(diǎn)和噪聲點(diǎn)。實(shí)際的數(shù)據(jù)情況千差萬(wàn)別，如有時(shí)會(huì)發(fā)現(xiàn)存在完全相同的兩個(gè)數(shù)據(jù)點(diǎn)，這兩個(gè)數(shù)據(jù)點(diǎn)連續(xù)存放，可能是數(shù)據(jù)存放時(shí)出現(xiàn)的問(wèn)題，也可能是信號(hào)本身的問(wèn)題；還有少部分?jǐn)?shù)據(jù)不是按時(shí)間的先后順序存放，有時(shí)會(huì)出現(xiàn)后一數(shù)據(jù)點(diǎn)的時(shí)間比前一個(gè)數(shù)據(jù)點(diǎn)時(shí)間靠前的情況。針對(duì)這些問(wèn)題，必須對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，首先去掉多余的相同數(shù)據(jù)，其次對(duì)數(shù)據(jù)按時(shí)間順序采用快速排序法進(jìn)行重新排列。對(duì)噪聲點(diǎn)的處理也是數(shù)據(jù)預(yù)處理的一項(xiàng)重要工作?；谄骄嚯x和面積特性的算法對(duì)噪聲點(diǎn)有一定的壓制作用，基于特征點(diǎn)距離的算法則對(duì)噪聲點(diǎn)比較敏感，所以必須設(shè)法去除噪聲點(diǎn)對(duì)算法的影響。針對(duì)不同的數(shù)據(jù)特點(diǎn)，選擇合適的降噪方法。當(dāng)數(shù)據(jù)量較小時(shí)，也可以結(jié)合人工經(jīng)驗(yàn)進(jìn)行判斷。

2.3　軌跡分段

由于歷史軌跡數(shù)據(jù)和當(dāng)前測(cè)量數(shù)據(jù)在數(shù)據(jù)文件中連續(xù)存放，因此必須對(duì)數(shù)據(jù)進(jìn)行合理的分段，然后計(jì)算最后測(cè)量時(shí)段的軌跡與各個(gè)歷史分段軌跡的相似度。軌跡分段主要基于數(shù)據(jù)特點(diǎn)進(jìn)行。由于目標(biāo)的運(yùn)動(dòng)軌跡并不是連續(xù)觀測(cè)到的，而是在不同的時(shí)間段和不同地點(diǎn)觀測(cè)到的，本文綜合考慮距離和時(shí)間因素進(jìn)行分段。如果前后兩個(gè)相鄰數(shù)據(jù)點(diǎn)的時(shí)間差大于某一數(shù)值，比如1 d或3 d，則從后一數(shù)據(jù)點(diǎn)開(kāi)始認(rèn)為是一段新的觀測(cè)數(shù)據(jù)。其次，考慮到目標(biāo)是連續(xù)移動(dòng)的，如果前后兩個(gè)相鄰數(shù)據(jù)點(diǎn)的距離差大于某一閾值時(shí)，則認(rèn)為兩個(gè)點(diǎn)分屬兩段數(shù)據(jù)。軌跡分段的具體算法流程如圖2所示。

圖2　軌跡分段算法流程

2.4　算法流程

應(yīng)用FD算法進(jìn)行軌跡預(yù)測(cè)的流程如圖3所示：首先，進(jìn)行數(shù)據(jù)預(yù)處理，把數(shù)據(jù)按時(shí)間順序排好，并去除掉噪聲點(diǎn)，存放到數(shù)組中；其次，對(duì)數(shù)據(jù)進(jìn)行分段，分別存放到另外的數(shù)組中；接著，把最后一段的軌跡數(shù)據(jù)和前面的歷史軌跡數(shù)據(jù)逐一進(jìn)行相似度比較，從中選取FD最小者，此段歷史軌跡就是軌跡預(yù)測(cè)的基礎(chǔ)；然后找到最后觀測(cè)點(diǎn)與相似軌跡上最近的點(diǎn)，此點(diǎn)以后的軌跡就是預(yù)測(cè)的目標(biāo)未來(lái)軌跡。根據(jù)需要也可附加上必要的預(yù)測(cè)時(shí)間信息。

圖3　基于FD算法的軌跡預(yù)測(cè)流程

3 實(shí)驗(yàn)與結(jié)果分析

采用軌跡相似度算法，對(duì)兩組模擬數(shù)據(jù)進(jìn)行了仿真計(jì)算。當(dāng)數(shù)據(jù)較多時(shí)，數(shù)據(jù)點(diǎn)密集重合在一起，不便于直觀顯示預(yù)測(cè)效果。為此，采用最后觀測(cè)數(shù)據(jù)附近的少量數(shù)據(jù)進(jìn)行測(cè)試。測(cè)試結(jié)果如圖4所示。經(jīng)過(guò)預(yù)處理后的軌跡數(shù)據(jù)按照觀測(cè)時(shí)間順序依次以數(shù)字進(jìn)行標(biāo)注。實(shí)線（黑色）表示經(jīng)過(guò)分段處理后的子軌跡段，各子軌跡段之間以虛線相連。三角形圖例（藍(lán)色）代表最后觀測(cè)到的子軌跡，圓形圖例（紅色）代表預(yù)測(cè)的目標(biāo)未來(lái)軌跡。紅色線所在的子軌跡段為算法找到的最相似的軌跡。找到最相似度軌跡后，在預(yù)測(cè)目標(biāo)未來(lái)運(yùn)動(dòng)趨勢(shì)時(shí)，在最相似軌跡上有兩種運(yùn)動(dòng)可能：向前運(yùn)動(dòng)或向后運(yùn)動(dòng)。和觀測(cè)軌跡運(yùn)動(dòng)方向一致的就是目標(biāo)的運(yùn)動(dòng)方向。具體方法是：先在最相似子軌跡上找到與最后觀測(cè)點(diǎn)距離最近的點(diǎn)（圖4（a）的20點(diǎn)和圖4（b）中的5點(diǎn)），分別計(jì)算此點(diǎn)與子軌跡上前后相鄰兩點(diǎn)的向量（即分別計(jì)算圖4（a）中20點(diǎn)和19點(diǎn)之間的向量以及20點(diǎn)和21點(diǎn)之間的向量，圖4（b）中則是5點(diǎn)與4點(diǎn)和5點(diǎn)與6點(diǎn)之間的向量），再計(jì)算觀測(cè)軌跡上最后兩點(diǎn)的向量，它與目標(biāo)歷史軌跡運(yùn)動(dòng)向量方向一致（實(shí)際中可設(shè)為小于90°）的就是預(yù)測(cè)的目標(biāo)運(yùn)動(dòng)方向。從此點(diǎn)以后直到子軌跡結(jié)束的軌跡點(diǎn)就是預(yù)測(cè)的目標(biāo)未來(lái)軌跡，如圖4中的點(diǎn)劃線（紅色）所示。

圖4　模擬數(shù)據(jù)仿真結(jié)果

在以上仿真實(shí)驗(yàn)的基礎(chǔ)上，采用某移動(dòng)目標(biāo)的實(shí)際數(shù)據(jù)進(jìn)行測(cè)試，結(jié)果如圖5所示，其中三角形圖例（藍(lán)色）是最后一段觀測(cè)數(shù)據(jù)，圓形圖例（紅色）是預(yù)測(cè)的目標(biāo)未來(lái)軌跡。

圖5　實(shí)際數(shù)據(jù)測(cè)試結(jié)果

從圖4、5可以直觀看出，觀測(cè)軌跡與最相似軌跡之間的距離比其他軌跡與觀測(cè)軌跡之間的距離小。假如目標(biāo)的運(yùn)動(dòng)具有周期性規(guī)律，采用軌跡相似度算法的預(yù)測(cè)結(jié)果與目標(biāo)的實(shí)際運(yùn)動(dòng)軌跡將會(huì)很接近。

前面分析討論了當(dāng)目標(biāo)活動(dòng)范圍較大時(shí)，采用ED的預(yù)測(cè)結(jié)果有時(shí)會(huì)不正確，圖6展示了這種情況。由于大地距離更真實(shí)地反映了球面上兩軌跡間的間隔，因而當(dāng)目標(biāo)活動(dòng)區(qū)域較大時(shí)，應(yīng)采用大地距離公式。

圖6　ED和大地距離兩種算法預(yù)測(cè)的不同結(jié)果

4 結(jié)語(yǔ)

針對(duì)目前的軌跡相似度算法分類方法無(wú)法體現(xiàn)算法自身特征的問(wèn)題，本文提出了基于算法特征的分類方法，可簡(jiǎn)單清晰地區(qū)分各類常見(jiàn)算法。本文的分析表明，對(duì)于海上船只等在大范圍內(nèi)移動(dòng)的目標(biāo)軌跡預(yù)測(cè)問(wèn)題，采用ED有時(shí)會(huì)得到不正確的結(jié)果。為避免這種情況，可用大地距離代替ED進(jìn)行相似度計(jì)算。本文在大地距離計(jì)算的基礎(chǔ)上，應(yīng)用離散FD算法進(jìn)行軌跡相似度計(jì)算，實(shí)現(xiàn)了對(duì)海上目標(biāo)的運(yùn)動(dòng)軌跡預(yù)測(cè)。模擬和實(shí)際數(shù)據(jù)的測(cè)試結(jié)果表明，算法可輸出正確的預(yù)測(cè)結(jié)果。本文方法也適用于草原動(dòng)物和候鳥(niǎo)遷徙的路線預(yù)測(cè)等問(wèn)題。為了進(jìn)一步提高預(yù)測(cè)精度，還可考慮對(duì)預(yù)測(cè)軌跡進(jìn)行距離修正，即計(jì)算觀測(cè)軌跡與最相似軌跡之間的平均距離，然后對(duì)預(yù)測(cè)的每個(gè)軌跡點(diǎn)都附加上平均距離。

［1］ 劉文，胡琨林，李巖，等. 移動(dòng)目標(biāo)軌跡預(yù)測(cè)方法研究綜述［J］. 智能科學(xué)與技術(shù)學(xué)報(bào)， 2021， 3（2）：149-160. （LIU W， HU K L， LI Y， et al. A review of prediction methods for moving target trajectories［J］. Chinese Journal of Intelligent Science and Technology， 2021， 3（2）：149-160.）

［2］ 石慶研，岳聚財(cái)，韓萍，等. 基于LSTM-ARIMA模型的短期航班飛行軌跡預(yù)測(cè)［J］. 信號(hào)處理， 2019， 35（12）： 2000-2009. （SHI Q Y， YUE J C， HAN P， et al. Short-term flight trajectory prediction based on LSTM-ARIMA model［J］. Journal of Signal Processing， 2019， 35（12）： 2000-2009.）

［3］ PECHER P， HUNTER M， FUJIMOTO R. Data-driven vehicle trajectory prediction［C］// Proceedings of the 2016 ACM SIGSIM Conference on Principles of Advanced Discrete Simulation. New York： ACM， 2016： 13-22.

［4］ 謝彬，張琨，張?jiān)萍儯? 基于軌跡相似度的移動(dòng)目標(biāo)軌跡預(yù)測(cè)算法［J］. 計(jì)算機(jī)工程， 2018， 44（9）：177-183. （XIE B， ZHANG K， ZAHNG Y C， et al. Trajectory prediction algorithm for mobile target based on trajectory similarity［J］. Computer Engineering， 2018， 44（9）：177-183.）

［5］ 王愛(ài)兵，劉亞朋，夏輝，等. 基于軌跡相似度的行人軌跡預(yù)測(cè)方法研究［J］. 石家莊職業(yè)技術(shù)學(xué)院學(xué)報(bào)， 2021， 33（2）：5-8. （WANG A B， LIU Y P， XIA H， et al. On the trajectory similarity and prediction of pedestrian trajectory［J］. Journal of Shijiazhuang University of Applied Technology， 2021， 33（2）： 5-8.）

［6］ 張春瑋，馬杰，牛元淼，等. 基于行為特征相似度的船舶軌跡聚類方法［J］. 武漢理工大學(xué)學(xué)報(bào)（交通科學(xué)與工程版）， 2019， 43（3）： 517-521. （ZHANG C W， MA J， NIU Y M， et al. Clustering method of ship trajectory based on similarity of behavior pattern［J］. Journal of Wuhan University of Technology （Transportation Science and Engineering）， 2019， 43（3）： 517-521.）

［7］ 吳玥琳，袁振洲，陳秋芳，等.考慮軌跡相似度的綜合客運(yùn)樞紐出租車合乘方法研究［J］.交通運(yùn)輸系統(tǒng)工程與信息，2020，20（2）：188-195. （WU Y L， YUAN Z Z， CHEN Q F， et al. Taxi pooling method of urban integrated passenger transport hub with trajectory similarity［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（2）： 188-195.）

［8］ 程志華. 通過(guò)計(jì)算公交線路軌跡相似度檢測(cè)線路是否調(diào)整的方法［J］. 公路交通科技（應(yīng)用技術(shù)版）， 2020（1）： 371-373. （CHENG Z H. A method of detecting whether the bus line should be adjusted by calculating the similarity of bus line trajectory［J］. Journal of Highway and Transportation Research and Development （Applied Technology）， 2020（1）： 371-373.）

［9］ 柳帥. 基于時(shí)空和語(yǔ)義相似度的軌跡社區(qū)發(fā)現(xiàn)方法研究［D］. 沈陽(yáng)： 東北大學(xué)， 2015： 10-11. （LIU S. Research on trajectory community detection based on spatial-temporal similarity and semantic similarity［D］. Shenyang： Northeastern University， 2015： 10-11.）

［10］ 廖聞劍，田小虎，邱秀連. 基于軌跡相似度的伴隨人員推薦［J］. 計(jì)算機(jī)系統(tǒng)應(yīng)用， 2018， 27（4）： 157-161. （LIAO W J， TIAN X H， QIU X L. Companion recommendation based on trajectory similarity［J］. Computer Systems & Applications， 2018， 27（4）： 157-161.）

［11］ MAGDY N， SAKR M A， MOSTAFA T， et al. Review on trajectory similarity measures［C］// Proceedings of the IEEE 7th International Conference on Intelligent Computing and Information Systems. Piscataway： IEEE， 2015： 613-619.

［12］ SU H， LIU S， ZHENG B， et al. A survey of trajectory distance measures and performance evaluation［J］. The VLDB Journal， 2020， 29（1）： 3-32.

［13］ CAI X. Effective algorithms for the closest pair and related problems［D］. Storrs， CT： University of Connecticut， 2020： 8-11.

［14］ 張曉濱，楊東山. 基于時(shí)間約束的Hausdorff距離的時(shí)空軌跡相似度量［J］. 計(jì)算機(jī)應(yīng)用研究， 2017， 34（7）：2077-2079. （ZHANG X B， YANG D S. Hausdorff distance about spatial-temporal trajectory similarity based on time restriction［J］. Application Research of Computers， 2017， 34（7）： 2077-2079.）

［15］ 郭巖，羅珞珈，汪洋，等. 一種基于DTW改進(jìn)的軌跡相似度算法［J］. 國(guó)外電子測(cè)量技術(shù)， 2016， 35（9）： 66-71. （GUO Y， LUO L J， WANG Y， et al. Improved DTW algorithm for trajectory similarity［J］. Foreign Electronic Measurement Technology， 2016， 35（9）： 66-71.）

［16］ 王前東.經(jīng)典軌跡的相似度量快速算法［J］.系統(tǒng)工程與電子技術(shù)，2020，42（10）：2189-2196. （WANG Q D. Fast algorithm of similarity measurement for classical trajectory［J］. Systems Engineering and Electronics， 2020， 42（10）： 2189-2196.）

［17］ 周振宇，郭廣禮，賈新果.大地主題解算方法綜述［J］.測(cè)繪科學(xué)，2007，32（4）：190-191，174，200. （ZHOU Z Y， GUO G L， JIA X G. A review on solution of geodetic problem［J］. Science of Surveying and Mapping， 2007， 32（4）： 190-191， 174， 200.）

［18］ EITER T， MANNILA H. Computing discrete Fréchet distance， CD-TR 94/64［R/OL］. ［2022-07-10］.http：//www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf.

Trajectory prediction of sea targets based on geodetic distance similarity calculation

ZHAO Yijian1，2， LIN Li3， WANG Qianqian1，2，4*， WEN Peng5， YANG Dong5

（1，，100081，；2，（），100081，；332011，100094，；4，314033，；5，100095，）

The existing similarity-based moving target trajectory prediction algorithms are generally classified according to the spatial-temporal characteristics of the data， and the characteristics of the algorithms themselves cannot be reflected. Therefore， a classification method based on algorithm characteristics was proposed. The calculation of the distances between two points is required for the trajectory similarity algorithms to carry out the subsequent calculations， however， the commonly used Euclidean Distance （ED） is only applicable to the problem of moving targets in a small region. A method of similarity calculation using geodetic distance instead of ED was proposed for the trajectory prediction of sea targets moving in a large region. Firstly， the trajectory data were preprocessed and segmented. Then， the discrete Fréchet Distance （FD） was adopted as similarity measure. Finally， synthetic and real data were used to test. Experimental results indicate that when sea targets move in a large region， the ED-based algorithm may gain incorrect prediction results， while the geodetic distance-based algorithm can output correct trajectory prediction.

trajectory similarity; trajectory prediction; Euclidean Distance (ED); geodetic distance; Fréchet Distance (FD)

ZHAO Yijian， born in 1998， M. S. candidate. Her research interests include photoelectronic imaging， data processing.

1001-9081（2023）11-3594-05

10.11772/j.issn.1001-9081.2022101639

2022?11?02；

2023?01?06；

趙一鑒（1998—），女，河南洛陽(yáng)人，碩士研究生，主要研究方向：光電成像、數(shù)據(jù)處理； 林利（1976—），男，河北滄州人，高級(jí)工程師，碩士，主要研究方向：信息通信、航天信息處理； 王茜蒨（1970—），女，江蘇徐州人，教授，博士，主要研究方向：光電成像和檢測(cè)； 聞鵬（1986—），男，陜西漢中人，高級(jí)工程師，碩士，主要研究方向：大數(shù)據(jù)及數(shù)據(jù)倉(cāng)庫(kù)應(yīng)用； 楊東（1985—），男，山東聊城人，高級(jí)工程師，碩士，主要研究方向：人工智能應(yīng)用。

TP301.6

A

2023?01?31。

LIN Li， born in 1976， M. S.， senior engineer. His research interests include information communication， aerospace information processing.

WANG Qianqian， born in 1970， Ph. D.， professor. Her research interest include photoelectronic imaging and detection.

WEN Peng， born in 1986， M. S.， senior engineer. His research interest include applications of big data and data warehouse.

YANG Dong， born in 1985， M. S.， senior engineer. His research interest include applications of artificial intelligence.