基于幾何法的航跡關(guān)聯(lián)算法研究

李 東，陳 健

（海軍大連艦艇學(xué)院，遼寧 大連 116018）

0 引言

為了提高目標(biāo)發(fā)現(xiàn)的概率和準(zhǔn)確率，一艘艦艇通常都會(huì)安裝盡可能多的探測(cè)設(shè)備，不同的探測(cè)設(shè)備對(duì)同一目標(biāo)所記錄的航跡通常不會(huì)完全重合，同一目標(biāo)的不同航跡最終都會(huì)在相同時(shí)間匯集到信息中心。為了后續(xù)對(duì)目標(biāo)航跡進(jìn)行航跡融合，中心系統(tǒng)需要對(duì)不同探測(cè)設(shè)備返回的航跡信息加以判斷或檢驗(yàn)是否屬于同一目標(biāo)，也就是通常所說(shuō)的航跡關(guān)聯(lián)。

航跡關(guān)聯(lián)的理論方法有很多，包括基于統(tǒng)計(jì)概率的關(guān)聯(lián)方法，基于信號(hào)處理的方法，基于目標(biāo)優(yōu)化約束的方法，基于模糊綜合決策的關(guān)聯(lián)方法等，這些方法都是將航跡作為一個(gè)整體進(jìn)行分析，并且都是在一定數(shù)量樣本點(diǎn)基礎(chǔ)上。而實(shí)際應(yīng)用中，航跡點(diǎn)都是實(shí)時(shí)更新、實(shí)時(shí)傳送的，并且戰(zhàn)場(chǎng)態(tài)勢(shì)下對(duì)于關(guān)聯(lián)速度也有很高的要求，所以，這些方法在工程應(yīng)用上存在一定的弊端。本文提出的航跡關(guān)聯(lián)算法基于幾何圖形，對(duì)航跡點(diǎn)數(shù)量沒(méi)有要求，并且可以實(shí)時(shí)地隨著點(diǎn)跡的增加累積計(jì)算，不需要每次接收數(shù)據(jù)都重新對(duì)整個(gè)航跡進(jìn)行計(jì)算，大大節(jié)省了計(jì)算時(shí)間，在此基礎(chǔ)上還提出了航跡簡(jiǎn)化算法，進(jìn)一步降低了計(jì)算復(fù)雜度，可以很好地應(yīng)用到工程實(shí)踐中。

1 航跡關(guān)聯(lián)算法及編程實(shí)現(xiàn)

進(jìn)行航跡關(guān)聯(lián)的最終結(jié)果是要呈現(xiàn)關(guān)聯(lián)航跡的相似度，在這里將相似度定義如下：

把其中一條航跡（以下稱(chēng)作航跡1）當(dāng)作一條具有一定寬度的長(zhǎng)帶（如下頁(yè)圖1 所示），計(jì)算實(shí)時(shí)另一航跡（以下稱(chēng)作航跡2）在長(zhǎng)帶中的長(zhǎng)度與其總長(zhǎng)度的比值即為相似度。

圖1 梯形帶

1.1 梯形帶頂點(diǎn)的計(jì)算

最開(kāi)始出于簡(jiǎn)單考慮，把每段線段對(duì)應(yīng)的區(qū)域看作一個(gè)矩形，如圖2 所示，但是由于一些缺口的存在，導(dǎo)致在實(shí)際操作中計(jì)算結(jié)果誤差較大。所以，使用梯形（如圖1 所示）代替矩形，來(lái)保證結(jié)果的準(zhǔn)確性。在距離航跡1 的每一條航跡段上、下w（w 為梯形帶寬度的一半，在實(shí)際應(yīng)用中，w 的選擇應(yīng)該綜合考量探測(cè)設(shè)備的測(cè)量精度，以及目標(biāo)的速度、類(lèi)型等屬性，結(jié)合實(shí)際的航跡數(shù)據(jù)，通過(guò)歸納總結(jié)得到的值會(huì)更加精確）處分別做平行線。在航跡1 同一側(cè)的所有平行線相交而成的折線段序列即為梯形帶的一邊，如此形成的兩條折線段序列圍成航跡1 的梯形帶（梯形帶的始末兩個(gè)梯形均為直角梯形）。所以首先要計(jì)算每個(gè)梯形的頂點(diǎn)。

圖2 矩形帶

梯形帶一邊所在直線的一般式方程（Ax+By+C=0）中，常量均用符號(hào)C表示，另一邊所對(duì)應(yīng)的所有直線一般式方程中常量均用C表示。與一條直線平行且距離相等的直線有兩條，區(qū)別是C 的不同，梯形帶兩邊對(duì)C 的選取是難點(diǎn)。解決方法是利用航跡點(diǎn)的先后順序，給兩個(gè)航跡點(diǎn)所形成的線段賦予方向。利用線段的方向來(lái)解決帶兩邊C、C的選取問(wèn)題（如圖3 所示）。該方法編程設(shè)計(jì)如下：

圖3 C1、C2 的選取

輸入：航跡1

輸出：梯形2 頂點(diǎn)（梯形帶同一側(cè)交點(diǎn)均用intp1 表示，另一側(cè)交點(diǎn)均用intp2 表示）

偽代碼：

1.2 梯形頂點(diǎn)再存儲(chǔ)

梯形頂點(diǎn)按上述算法“梯形頂點(diǎn)生成算法”輸出后，進(jìn)行重新存儲(chǔ)（4 個(gè)頂點(diǎn)為一個(gè)單位，逆時(shí)針存儲(chǔ)，為“一條線段在一個(gè)梯形內(nèi)的長(zhǎng)度計(jì)算算法”輸入做準(zhǔn)備），簡(jiǎn)略算法如下：

第1 次輸入原頂點(diǎn)集合中連續(xù)的前4 個(gè)點(diǎn)，將第3 個(gè)和第4 個(gè)位置的點(diǎn)相互調(diào)換后，輸出這4 個(gè)點(diǎn)；第k 次輸入原頂點(diǎn)集合中的第2k-1 到第2k+2個(gè)點(diǎn)，將第3 個(gè)和第4 個(gè)位置的點(diǎn)相互調(diào)換后，輸出這4 個(gè)點(diǎn)；當(dāng)k=n-1 時(shí)，輸出后結(jié)束（2n 表示原頂點(diǎn)集合中頂點(diǎn)個(gè)數(shù)）。

1.3 一條線段在一個(gè)梯形內(nèi)的長(zhǎng)度計(jì)算

要計(jì)算一條航跡和一個(gè)航跡帶的相似度，則必須計(jì)算這條航跡所有航跡段在航跡帶內(nèi)的總長(zhǎng)度，這個(gè)過(guò)程的單位過(guò)程即是計(jì)算一條線段在一個(gè)梯形內(nèi)的長(zhǎng)度（如下頁(yè)圖4 所示）。

圖4 相似度計(jì)算示意圖

通過(guò)判斷梯形的4 個(gè)頂點(diǎn)和線段所在直線的3種位置關(guān)系（頂點(diǎn)在直線上，在直線兩側(cè)，在直線一側(cè)）以及分別滿足這3 種位置關(guān)系的頂點(diǎn)個(gè)數(shù)來(lái)判斷線段是否有在梯形內(nèi)的部分，若是，求出線段在梯形內(nèi)的長(zhǎng)度；否則，輸出長(zhǎng)度為0。算法思路如下：

符號(hào)：

5）d 表示求得的線段在梯形內(nèi)的長(zhǎng)度。

通過(guò)判斷線段所在直線與梯形的兩個(gè)交點(diǎn)及線段的兩個(gè)端點(diǎn)這4 個(gè)點(diǎn)的位置關(guān)系，來(lái)計(jì)算線段在梯形內(nèi)的長(zhǎng)度。利用夾角在（0°，180°］之間的兩個(gè)共線（此處指在同一條直線上，而不僅僅是平行）向量間的位置關(guān)系，來(lái)計(jì)算兩個(gè)向量重合部分的大小。

偽代碼如下：

輸入：梯形4 個(gè)頂點(diǎn)，線段兩個(gè)頂點(diǎn)

輸出：線段和梯形的相交長(zhǎng)度

步驟：

Step 2：判斷：若所有梯形頂點(diǎn)均在線段所在直線l 的同一側(cè)，或者只有一個(gè)梯形頂點(diǎn)在直線l 上，而其他頂點(diǎn)在直線l 的同一側(cè)，則輸出d=0，轉(zhuǎn)Step 10；否則，轉(zhuǎn)Step 3；

Step 3：判斷：若只有兩個(gè)梯形頂點(diǎn)在直線l 上，另外兩個(gè)頂點(diǎn)在直線l 的同一側(cè)，轉(zhuǎn)Step 7；否則，轉(zhuǎn)Step 4；

Step 4：判斷：若只有一個(gè)梯形頂點(diǎn)在直線l 上，其他3 個(gè)頂點(diǎn)分布在直線l 的兩側(cè)，轉(zhuǎn)Step 8；否則，轉(zhuǎn)Step 5；

Step 5：判斷：若只有兩個(gè)梯形頂點(diǎn)在直線l 上，其他兩個(gè)頂點(diǎn)分布在直線l 的兩側(cè)，轉(zhuǎn)Step 7；否則，轉(zhuǎn)Step 6；

Step 6：除了Step 1 到Step 5 的情況外，剩下的情況是4個(gè)梯形頂點(diǎn)分布在直線l 的兩側(cè)，即直線l 與梯形的兩邊相交，轉(zhuǎn)Step 8；否則，輸出“出錯(cuò)”，轉(zhuǎn)Step 10；

Step 7：判定在直線l 上的兩個(gè)梯形頂點(diǎn)，分別記為int p、int p，轉(zhuǎn)Step 9；

Step 8：計(jì)算直線l 與梯形的兩交點(diǎn)int p、int p；

Step 9：判斷int p、int p、a、b 這4 個(gè)點(diǎn)在直線l 上的先后位置關(guān)系，求得兩條線段int pint p和ab 重合部分的長(zhǎng)度d即為線段ab 在梯形內(nèi)長(zhǎng)度，輸出d，轉(zhuǎn)Step 10；

Step 10：結(jié)束。（如圖5 所示）

圖5 線段在梯形內(nèi)長(zhǎng)度求解示意

1.4 實(shí)驗(yàn)驗(yàn)證

實(shí)驗(yàn)先模擬生成一條航跡（如圖6 所示），然后對(duì)航跡上的每個(gè)點(diǎn)做隨機(jī)浮動(dòng)，生成50 條新航跡（如圖7 所示），將這50 條新航跡與原始航跡做匹配求相似度（圖8 為某一條航跡與原航跡的比較）。之后改變航跡的梯形帶寬度，再分別計(jì)算相似度，得到了預(yù)期的結(jié)果，證明了算法的正確性。

圖6 原始航跡

圖7 新航跡生成

圖8 相似度計(jì)算

2 航跡簡(jiǎn)化

采用1 中的算法進(jìn)行航跡關(guān)聯(lián)時(shí)，航跡點(diǎn)的數(shù)量成為影響算法速度的主要因素，尤其現(xiàn)在的探測(cè)設(shè)備采樣頻率普遍較高，收集到的航跡點(diǎn)比較密集，數(shù)量巨大。因此，為了能更好地適應(yīng)戰(zhàn)場(chǎng)需求，減少計(jì)算時(shí)間，本文提出如下算法對(duì)航跡進(jìn)行簡(jiǎn)化，刪除那些對(duì)構(gòu)建梯形帶影響較小的航跡點(diǎn)，抽取其中的關(guān)鍵點(diǎn)用作關(guān)聯(lián)計(jì)算。

若連續(xù)的多個(gè)點(diǎn)幾乎在一條直線上，則中間的點(diǎn)可去掉，如此即能用一條線段代替原來(lái)的多條折線段。因此，算法基本思想如下：

1）連續(xù)3 個(gè)采樣點(diǎn)，判斷中間一個(gè)采樣點(diǎn)是否舍去（如圖9 所示）。

圖9 單采樣點(diǎn)取舍

過(guò)第1 個(gè)和第3 個(gè)采樣點(diǎn)做一條直線，計(jì)算第2 個(gè)采樣點(diǎn)到直線的距離，若該距離小于距離閾值（事先給定），則舍去第2 個(gè)采樣點(diǎn)；否則，保留第2個(gè)采樣點(diǎn)。

2）連續(xù)n 個(gè)采樣點(diǎn)（n＞3），判斷倒數(shù)第n-1 個(gè)采樣點(diǎn)是否舍去（如圖10 所示）。

圖10 多采樣點(diǎn)取舍

過(guò)第1 個(gè)采樣點(diǎn)和第n 個(gè)采樣點(diǎn)做一條直線，分別計(jì)算中間n-2 個(gè)采樣點(diǎn)到直線的距離，若所有距離均小于距離閾值，則舍去第n-1 個(gè)采樣點(diǎn)；否則，保留第n-1 個(gè)采樣點(diǎn)。

符號(hào)：

p、p代表兩個(gè)航跡點(diǎn)，s、e 是點(diǎn)的下標(biāo)，s 小于e，p為p、p之間的某個(gè)點(diǎn)，d為p距離p、p連線的距離，d為距離閾值。

輸入：航跡點(diǎn)，d

輸出：簡(jiǎn)化后的航跡點(diǎn)

算法偽代碼如下：

本次實(shí)驗(yàn)通過(guò)一些測(cè)試數(shù)據(jù)進(jìn)行檢驗(yàn)，測(cè)試數(shù)據(jù)都是人造的航跡點(diǎn)。圖11 和圖12 是某次測(cè)試數(shù)據(jù)的簡(jiǎn)化前后散點(diǎn)圖。

圖11 簡(jiǎn)化前

圖12 簡(jiǎn)化后

從圖中可以明顯看到，簡(jiǎn)化后的航跡點(diǎn)少了很多，并且關(guān)鍵點(diǎn)也基本都保留了下來(lái)，所以算法的正確性基本得到驗(yàn)證。

3 結(jié)論

本文主要提出了一種基于幾何法的航跡關(guān)聯(lián)算法，在此基礎(chǔ)上通過(guò)提出一種航跡簡(jiǎn)化方法提高了該算法的計(jì)算效率，并給出了編程實(shí)現(xiàn)的方法，設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證了算法的準(zhǔn)確性。與其他航跡關(guān)聯(lián)算法相比，該算法從最直觀的圖形角度出發(fā)，不依賴(lài)航跡點(diǎn)的數(shù)量，可以實(shí)時(shí)對(duì)航跡進(jìn)行關(guān)聯(lián)，計(jì)算復(fù)雜度低，非常適合工程上應(yīng)用。