基于LCSS的目標(biāo)航線規(guī)律快速匹配方法

徐秋坪, 趙 鍇, 屈德濤, 劉鋼墩

(中國(guó)電子科技集團(tuán)公司第二十八研究所, 江蘇 南京 210007)

0 引 言

現(xiàn)代戰(zhàn)爭(zhēng)中傳感器信息數(shù)量巨大,戰(zhàn)場(chǎng)態(tài)勢(shì)瞬息萬(wàn)變,指揮員需要在短時(shí)間內(nèi)感知整個(gè)戰(zhàn)場(chǎng)態(tài)勢(shì)變化趨勢(shì)并迅速做出決策,因此有必要開(kāi)展對(duì)空戰(zhàn)場(chǎng)態(tài)勢(shì)智能化分析領(lǐng)域的研究。考慮戰(zhàn)場(chǎng)實(shí)時(shí)目標(biāo)掌握信息有限的情況,如何利用日常積累的空戰(zhàn)場(chǎng)目標(biāo)歷史活動(dòng)航線規(guī)律經(jīng)驗(yàn)知識(shí),分析出與之匹配的活動(dòng)規(guī)律信息,為目標(biāo)識(shí)別判性、運(yùn)動(dòng)趨勢(shì)預(yù)測(cè)、威脅意圖研判等戰(zhàn)場(chǎng)態(tài)勢(shì)智能分析提供技術(shù)手段是一個(gè)值得研究的課題。

針對(duì)戰(zhàn)場(chǎng)實(shí)時(shí)目標(biāo)活動(dòng)航線規(guī)律匹配問(wèn)題,目前國(guó)內(nèi)外研究文獻(xiàn)很少,其中一些軌跡相似度量算法可提供一定的解決思路。軌跡相似度量方法一般包括:基于點(diǎn)方法,如編輯距離(edit distance on real sequence, EDR)、動(dòng)態(tài)時(shí)間規(guī)劃(dynamic time warping, DTW)、最長(zhǎng)公共子序列(longest common sub sequence, LCSS)等;基于形狀的方法,如Fréchet、Hausdorff;基于分段的方法,如單向距離(one way distance, OWD), 多線位置距離(locality in-between polylines, LIP)。DTW和歐式距離對(duì)軌跡的個(gè)別點(diǎn)差異性非常敏感,如果兩個(gè)時(shí)間序列在大多數(shù)時(shí)間段具有相似的形態(tài),僅僅在很短的時(shí)間具有一定的差異(即很小的差異也會(huì)對(duì)相似度衡量產(chǎn)生影響),歐式距離和DTW無(wú)法準(zhǔn)確衡量這兩個(gè)時(shí)間序列的相似度,而LCSS能處理這種問(wèn)題。文獻(xiàn)[13]以實(shí)時(shí)無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)為例,提出基于LCSS的多元數(shù)據(jù)集相似度計(jì)算算法。文獻(xiàn)[14-15]利用LCSS對(duì)客戶運(yùn)動(dòng)定位軌跡進(jìn)行分組,以找到熱點(diǎn)區(qū)域并提取客戶主要軌跡。文獻(xiàn)[16]探索了一種不改變汽車總行程的軌跡自適應(yīng)相似度匹配模式,并采用基于LCSS的時(shí)空相似度識(shí)別算法對(duì)所有匹配項(xiàng)進(jìn)行篩選。此外,文獻(xiàn)[17-18]從時(shí)空相似度維度考慮,提出了基于海量數(shù)據(jù)集的軌跡相似度匹配模型。文獻(xiàn)[19-22]針對(duì)軌跡數(shù)據(jù)地圖匹配問(wèn)題和不同類型軌跡數(shù)據(jù),利用隱馬爾可夫模型或權(quán)重自適應(yīng)隱馬爾可夫模型等模型提出了多種地圖匹配算法?；顒?dòng)航線規(guī)律和實(shí)時(shí)目標(biāo)飛行航跡均由離散航跡點(diǎn)組成,活動(dòng)航線規(guī)律空域跨度大、航線輪廓復(fù)雜、航跡點(diǎn)間距分布無(wú)規(guī)則,實(shí)時(shí)目標(biāo)運(yùn)動(dòng)具備時(shí)效性并且掌握的航跡點(diǎn)一般具有周期性,時(shí)間跨度較小,離散點(diǎn)間距相對(duì)較小。積累的目標(biāo)歷史活動(dòng)航線規(guī)律數(shù)據(jù)量相對(duì)較大,戰(zhàn)場(chǎng)實(shí)時(shí)目標(biāo)活動(dòng)范圍較為分散并且可能存在信息要素不完整,考慮實(shí)時(shí)目標(biāo)與航線規(guī)律的特征差異性,同時(shí)需要滿足對(duì)戰(zhàn)場(chǎng)態(tài)勢(shì)快速研判的需求,這些因素為活動(dòng)規(guī)律匹配算法模型提出了更高的時(shí)效性要求。如何快速地針對(duì)單批目標(biāo)從大量的規(guī)律知識(shí)庫(kù)中匹配出相應(yīng)的航線規(guī)律是文本研究的重點(diǎn)。

綜合考慮本文需要解決問(wèn)題的快速性、時(shí)效性、簡(jiǎn)單易于實(shí)現(xiàn)等需求,本文運(yùn)用LCSS,結(jié)合滑窗處理、最小矩形區(qū)域過(guò)濾等處理手段,提出了一種簡(jiǎn)單、快速、精度高并且易于工程實(shí)現(xiàn)的航線規(guī)律匹配算法模型,解決戰(zhàn)場(chǎng)實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡快速、準(zhǔn)確匹配問(wèn)題,可為實(shí)時(shí)目標(biāo)識(shí)別判性、運(yùn)動(dòng)趨勢(shì)預(yù)測(cè)、目標(biāo)異?；顒?dòng)告警等方面實(shí)際工程應(yīng)用提供一定的技術(shù)支撐,具有較大的工程實(shí)際應(yīng)用價(jià)值。

1 問(wèn)題描述

記={,,…,},>1表征積累的目標(biāo)活動(dòng)航線規(guī)律數(shù)據(jù)集。={,},1≤≤表征單條航線規(guī)律信息,其中，為該航線規(guī)律的基本信息,為由若干離散航跡點(diǎn)組成的規(guī)律航跡。記={,,,,,},其中為目標(biāo)所屬國(guó)家地區(qū)，為目標(biāo)名稱，(,,,)分別為最小經(jīng)度、最小緯度、最大經(jīng)度和最大緯度,構(gòu)成了該目標(biāo)航線規(guī)律的活動(dòng)陣位。記={,,…,},表示該規(guī)律航跡的總航跡點(diǎn)數(shù),其航跡點(diǎn)表示為={,,},1<<,其中,,分別表示該航跡點(diǎn)的經(jīng)度、緯度和高度。根據(jù)規(guī)律航跡可求得目標(biāo)航線規(guī)律的活動(dòng)陣位信息(,,,)。

實(shí)時(shí)目標(biāo)信息可描述為={,},其中為實(shí)時(shí)目標(biāo)的基本信息,為一段時(shí)間內(nèi)該目標(biāo)運(yùn)動(dòng)航跡。記={,},其中為實(shí)時(shí)目標(biāo)所屬國(guó)家地區(qū),為實(shí)時(shí)目標(biāo)名稱。記={,,…,},表征當(dāng)前掌握的該實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡點(diǎn)總數(shù),其單個(gè)航跡點(diǎn)信息可表示為={,,},1<<,其中,,分別表示該航跡點(diǎn)的經(jīng)度、緯度和高度。

航線規(guī)律主要表征了目標(biāo)歷史頻繁行動(dòng)的軌跡輪廓特性,其規(guī)律航跡點(diǎn)主要表現(xiàn)為空間特征,且航跡點(diǎn)分布較為稀疏。另外,不同目標(biāo)的航線規(guī)律活動(dòng)陣位分布較散,空間跨度相差較大。實(shí)時(shí)目標(biāo)記錄的航跡點(diǎn)信息一般具有周期性,時(shí)間跨度較小,與航線規(guī)律的航跡點(diǎn)密度相差較大。此外,在工程實(shí)踐應(yīng)用中,實(shí)時(shí)目標(biāo)基本信息感知度較低,存在掌握的基本信息要素不全問(wèn)題,基于國(guó)家地區(qū)、目標(biāo)名稱信息直接檢索相應(yīng)航線規(guī)律存在局限性。另外,戰(zhàn)場(chǎng)態(tài)勢(shì)瞬息萬(wàn)變,為滿足目標(biāo)快速識(shí)別研判需求,對(duì)實(shí)時(shí)目標(biāo)航線匹配的時(shí)效性提出了更高要求,復(fù)雜的匹配算法模型顯然是不可取的。考慮上述問(wèn)題和需求,基于掌握的實(shí)時(shí)目標(biāo)信息,本文提出了一種簡(jiǎn)單、快速、高效并且易于工程實(shí)現(xiàn)的航線規(guī)律匹配算法。

2 航線規(guī)律匹配模型

針對(duì)上述問(wèn)題,在積累的目標(biāo)航線規(guī)律數(shù)據(jù)基礎(chǔ)上,采用滑動(dòng)窗口處理、活動(dòng)陣位特征過(guò)濾、數(shù)據(jù)格式化處理等手段,基于LCSS求解兩航跡最長(zhǎng)公共子序列方式,提出了一種快速實(shí)用的航線規(guī)律匹配算法,具有較高的匹配效率和準(zhǔn)確度。本文提出的航線規(guī)律匹配算法模型邏輯處理流程如圖1所示。

圖1 航線規(guī)律匹配模型邏輯處理流程Fig.1 Logic processing flow of trajectory rule matching model

首先對(duì)實(shí)時(shí)目標(biāo)采用動(dòng)態(tài)滑動(dòng)窗口機(jī)制進(jìn)行處理,提取滿足一定時(shí)間約束的航跡信息并分析其活動(dòng)陣位,以保證目標(biāo)運(yùn)動(dòng)特征的時(shí)效性;其次,基于實(shí)時(shí)目標(biāo)基本信息、活動(dòng)陣位特征等信息,對(duì)積累的航線規(guī)律數(shù)據(jù)集進(jìn)行過(guò)濾,提取與實(shí)時(shí)目標(biāo)有關(guān)聯(lián)度的航線規(guī)律,以減少用于匹配的規(guī)律數(shù)據(jù)量;進(jìn)一步,采用區(qū)域滑窗機(jī)制對(duì)相關(guān)聯(lián)的航線規(guī)律提取有效航跡段信息,以減小匹配模型計(jì)算量,降低內(nèi)存消耗;然后,基于實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡特征對(duì)相關(guān)航線規(guī)律的有效航跡進(jìn)行數(shù)據(jù)格式化處理,避免航線規(guī)律數(shù)據(jù)因跨度大導(dǎo)致的航跡點(diǎn)稀疏問(wèn)題;最后,基于格式化處理的有效航線規(guī)律和實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡數(shù)據(jù),求解最長(zhǎng)公共子航跡序列,計(jì)算航線規(guī)律匹配度。

匹配模型具體設(shè)計(jì)過(guò)程描述如下。

(1) 采用動(dòng)態(tài)滑窗處理模式提取實(shí)時(shí)目標(biāo)有效航跡段,并計(jì)算目標(biāo)當(dāng)前活動(dòng)陣位。

該滑窗是根據(jù)實(shí)時(shí)目標(biāo)航跡點(diǎn)數(shù)量來(lái)設(shè)計(jì)窗口大小,該窗口大小是動(dòng)態(tài)變化的。假設(shè)實(shí)時(shí)目標(biāo)最大航跡點(diǎn)數(shù)量為,那么窗口最大長(zhǎng)度可視為個(gè)航跡點(diǎn)組成的長(zhǎng)度。

記表征該滑窗大小,如果記錄的實(shí)時(shí)目標(biāo)航跡點(diǎn)數(shù)目小于,那么為當(dāng)前數(shù)量航跡點(diǎn)組成的長(zhǎng)度;如果記錄的實(shí)時(shí)目標(biāo)航跡點(diǎn)數(shù)目不小于,那么為個(gè)航跡點(diǎn)組成的長(zhǎng)度?；按笮】擅枋鰹?/p>

(1)

基于航跡點(diǎn)數(shù)量的滑窗提取實(shí)時(shí)目標(biāo)有效航跡點(diǎn)時(shí),均從最新記錄時(shí)刻的航跡點(diǎn)開(kāi)始,以保證用于航線規(guī)律匹配分析數(shù)據(jù)的時(shí)效性,如圖2所示。進(jìn)而,用于匹配分析的實(shí)時(shí)目標(biāo)航跡可描述為={,,…,},可以看出,應(yīng)滿足≤。進(jìn)一步,可根據(jù)航跡點(diǎn)特征信息,計(jì)算該目標(biāo)當(dāng)前活動(dòng)陣位{,,,},其中,,,分別為最小經(jīng)、緯度和最大經(jīng)、緯度。

圖2 實(shí)時(shí)目標(biāo)有效航跡提取的滑窗設(shè)計(jì)Fig.2 Design of sliding window for real time target effective trajectory extraction

(2) 基于實(shí)時(shí)目標(biāo)基本信息、活動(dòng)陣位特征過(guò)濾獲取相關(guān)聯(lián)的航線規(guī)律數(shù)據(jù)。

考慮到掌握的航線規(guī)律數(shù)據(jù)量較大,直接將目標(biāo)實(shí)時(shí)有效航跡與規(guī)律航跡進(jìn)行匹配,則計(jì)算量太大,耗時(shí)較高。因此,可通過(guò)實(shí)時(shí)目標(biāo)基本信息、有效航跡的活動(dòng)陣位特征進(jìn)行過(guò)濾處理,得到與之相關(guān)聯(lián)的規(guī)律航線數(shù)據(jù)。

假設(shè)活動(dòng)陣位關(guān)聯(lián)閾值為,基于實(shí)時(shí)目標(biāo)活動(dòng)陣位特征{,,,},可構(gòu)建最小矩形區(qū)域。根據(jù)該矩形區(qū)域和航線規(guī)律活動(dòng)陣位信息,判斷二者的相關(guān)性,提取與實(shí)時(shí)目標(biāo)相關(guān)聯(lián)的航線規(guī)律,如圖3所示。通過(guò)遍歷所有航線規(guī)律,根據(jù)各規(guī)律活動(dòng)陣位{,,,}組成的矩形區(qū)域與是否存在交集來(lái)判斷該條規(guī)律是否與目標(biāo)具備初步相關(guān)性。如果相關(guān),則記錄該條規(guī)律,否則跳過(guò)處理下一條規(guī)律,如圖3中航線規(guī)律和與目標(biāo)具備初步相關(guān)性,則不相關(guān)。

圖3 基于活動(dòng)陣位的航線規(guī)律過(guò)濾示意圖Fig.3 Schematic diagram of trajectory rule filtering based on active positions

如果能夠獲悉實(shí)時(shí)目標(biāo)的所屬國(guó)家地區(qū)、機(jī)型等基本信息,則可利用基本信息進(jìn)行預(yù)先檢索,進(jìn)一步加快航線規(guī)律過(guò)濾效率,縮短過(guò)濾時(shí)間。

(3) 提取與實(shí)時(shí)目標(biāo)相關(guān)聯(lián)的航線規(guī)律有效航跡段。

針對(duì)航線規(guī)律存在空域跨度大的特點(diǎn),對(duì)于存在陣位相關(guān)的航線規(guī)律而言,雖然與實(shí)時(shí)目標(biāo)活動(dòng)陣位有一定交集,但是該規(guī)律可能與目標(biāo)當(dāng)前陣位相關(guān)聯(lián)的有效航跡段只占據(jù)整個(gè)航線規(guī)律中的較少部分。如果直接將航線規(guī)律與目標(biāo)實(shí)時(shí)航跡進(jìn)行匹配,不僅增加了不必要的計(jì)算量和計(jì)算時(shí)間,也增加了內(nèi)存消耗,不利于快速分析計(jì)算。因此,有必要對(duì)具有相關(guān)性的航線規(guī)律進(jìn)一步處理,提取其有效航跡段信息。

圖4 提取航線規(guī)律的有效航跡Fig.4 Effective track extraction of trajectory rule

(2)

有效航跡段對(duì)應(yīng)的航跡點(diǎn)數(shù)可表示為

(3)

經(jīng)過(guò)上述處理可得到與實(shí)時(shí)目標(biāo)相關(guān)聯(lián)的航線規(guī)律及其有效航跡數(shù)據(jù),為便于描述,記為={,,…,},≤,單條航線規(guī)律可描述為={,},1≤≤。

(4) 航線規(guī)律有效航跡段數(shù)據(jù)格式化處理。

為避免航線規(guī)律有效航跡段的稀疏、空間跨度大以及有效航跡點(diǎn)數(shù)量較少帶來(lái)的匹配誤差,可對(duì)規(guī)律航跡數(shù)據(jù)進(jìn)行格式化處理。

圖5 有效航跡段數(shù)據(jù)格式化處理示意圖Fig.5 Schematic diagram of effective track segment data format processing

(5) 基于格式化處理的有效航線規(guī)律和實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡,求解最長(zhǎng)公共子航跡序列,計(jì)算匹配度。

最長(zhǎng)公共子航跡序列計(jì)算方法可描述為

(4)

在計(jì)算最長(zhǎng)公共子航跡序列過(guò)程中,對(duì)于Dis(,)<條件下的航跡點(diǎn)對(duì),可計(jì)算其點(diǎn)對(duì)之間的距離計(jì)算其距離匹配程度,本文采用距離的線性關(guān)系計(jì)算點(diǎn)對(duì)距離匹配度:

(5)

式中:為點(diǎn)對(duì)距離匹配因子,且0<<1。本文取=025,則的取值范圍為075～1。

考慮公共航跡子序列匹配情況,航跡點(diǎn)距匹配度可表示為

(6)

公共子序列航跡點(diǎn)數(shù)匹配度可表示為

(7)

基于公共子序列的航跡點(diǎn)距匹配度以及航跡點(diǎn)數(shù)匹配度,進(jìn)一步可計(jì)算兩航跡綜合匹配度:

=+

(8)

式中:,分別表示航跡點(diǎn)距匹配度因子和航跡點(diǎn)數(shù)匹配度因子,且滿足+=1,>0,>0。本文在仿真中取=02,=08。

3 仿真分析

3.1 實(shí)時(shí)目標(biāo)航跡匹配效果

模擬產(chǎn)生一批空中目標(biāo),在其飛行過(guò)程中對(duì)其不同時(shí)段進(jìn)行采樣匹配分析,用記錄的航跡點(diǎn)數(shù)來(lái)表征其在不同時(shí)段航跡掌握情況,基于本文提出的航線規(guī)律匹配模型,其在不同階段的匹配分析結(jié)果如圖6所示,相應(yīng)匹配結(jié)果參數(shù)如表1所示。圖6中藍(lán)、粉紅、黑、綠、黃色標(biāo)注的各離散點(diǎn)表征實(shí)時(shí)目標(biāo)在不同階段用于匹配分析的航跡點(diǎn)信息,亮藍(lán)線和紅點(diǎn)表征的是與實(shí)時(shí)目標(biāo)各階段運(yùn)動(dòng)航跡相匹配的航線規(guī)律信息,其中紅色點(diǎn)為航線規(guī)律的各航跡點(diǎn)。仿真結(jié)果表明,基于本文提出的規(guī)律匹配模型,基于實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡可以有效匹配出與之關(guān)聯(lián)的航線規(guī)律,并提供相應(yīng)的匹配度指數(shù)。在匹配分析時(shí)如果實(shí)時(shí)目標(biāo)記錄的航跡點(diǎn)數(shù)目超過(guò)設(shè)定值,則用于匹配計(jì)算的目標(biāo)航跡為截止當(dāng)前最新的個(gè)航跡點(diǎn),其早期記錄的若干航跡點(diǎn)不作為匹配計(jì)算范疇,如圖6(d)和圖6(e)所示,不僅充分利用了對(duì)當(dāng)前目標(biāo)分析的時(shí)效性,而且大大減少了計(jì)算所耗時(shí)長(zhǎng),提高匹配效率。此模型計(jì)算時(shí)長(zhǎng)隨著航跡點(diǎn)數(shù)的增加而增大,當(dāng)達(dá)到后,計(jì)算時(shí)間相對(duì)穩(wěn)定,從千余條航跡規(guī)律中匹配分析計(jì)算時(shí)間約在1 s左右。

圖6 不同階段下規(guī)律匹配結(jié)果Fig.6 Rule matching results in different periods

表1 不同階段匹配參數(shù)

3.2 不同航跡窗口下對(duì)比分析

不同決定了用于匹配分析時(shí)實(shí)時(shí)目標(biāo)航跡過(guò)濾窗口以及用于匹配計(jì)算的航跡點(diǎn)數(shù)量,通過(guò)設(shè)置不同的分析其對(duì)匹配效果的影響。仿真數(shù)據(jù)采用上述模擬目標(biāo)在800點(diǎn)時(shí)的運(yùn)動(dòng)狀態(tài),設(shè)置不同仿真結(jié)果如圖7所示,相應(yīng)匹配參數(shù)如表2所示。仿真結(jié)果表明,值越大,則計(jì)算時(shí)間會(huì)相對(duì)較長(zhǎng),但對(duì)實(shí)時(shí)目標(biāo)分析的實(shí)效性和快速性相對(duì)較低。不同的對(duì)攝取的航線規(guī)律航跡點(diǎn)數(shù)量不同,考慮規(guī)律航跡點(diǎn)稀疏程度不確定性,如果確定的窗口范圍內(nèi)航線規(guī)律航跡點(diǎn)數(shù)較為稀疏且航跡點(diǎn)間距跨域較大,則會(huì)增加有效航跡段數(shù)據(jù)格式化處理時(shí)間。值越小,雖然可以減少計(jì)算時(shí)間,但是存在不能充分表征目標(biāo)運(yùn)動(dòng)特性的風(fēng)險(xiǎn),造成匹配規(guī)律存在虛警現(xiàn)象。采用本文提出的模型能夠綜合考慮戰(zhàn)場(chǎng)態(tài)勢(shì)分析的時(shí)效性和匹配分析的快速性,有效避免采用所有航跡點(diǎn)進(jìn)行匹配分析所帶來(lái)的長(zhǎng)耗時(shí)問(wèn)題。在實(shí)際工程使用中,值可根據(jù)具體需求綜合考慮分析的時(shí)效性以及快速性進(jìn)行調(diào)優(yōu)。

圖7 不同Nmax的匹配結(jié)果Fig.7 Matching results with different Nmax

表2 不同Nmax的匹配參數(shù)

4 結(jié) 論

本文提出的算法模型能夠快速、有效地實(shí)現(xiàn)實(shí)時(shí)目標(biāo)運(yùn)動(dòng)航跡與活動(dòng)航線規(guī)律知識(shí)的準(zhǔn)確匹配。該方法簡(jiǎn)單可行,易于工程實(shí)現(xiàn),并且能夠綜合考慮戰(zhàn)場(chǎng)態(tài)勢(shì)分析的時(shí)效性和快速性,可為實(shí)時(shí)目標(biāo)識(shí)別判性、運(yùn)動(dòng)趨勢(shì)預(yù)測(cè)、目標(biāo)異?；顒?dòng)告警等方面的態(tài)勢(shì)智能化分析提供一定的技術(shù)支撐,具有較大的工程實(shí)際應(yīng)用價(jià)值。