異類傳感器數據融合的最近鄰-點拓撲關聯法?

胡朋啟 李蔚清

（南京理工大學計算機科學與工程學院 南京 210094）

1 引言

隨著現代傳感器技術和信息處理技術等領域的日新月異的快速發展，異類傳感器之間的多源信息融合逐步體現出巨大的需求［1］，主要的目的是對來自每個局部傳感器的局部信息和數據進行關聯、估計和融合，產生比單獨傳感器更全面的狀態信息或者更準確的估計值［2］。例如，目前常用的雷達和紅外異類傳感器組合可為復雜電磁環境中目標跟蹤提供解決思路［3］。目標關聯問題是多源異類傳感器信息融合的關鍵步驟。在對紅外數據和雷達數據分別進行濾波和時空配準后，將雷達和紅外數據轉化到了同一個觀測坐標系。由于隨機噪聲和傳感器系統偏差的影響，不同傳感器對同一個目標觀測位置可發生較大的偏離。針對同類傳感器的系統偏差，目前已提出了基于誤差估計和補償的方法。主要有實施質量控制法（Real Time Quality，RTQC）［4］、最小二乘法（Least Square，LS）［5～6］、極大似然法（Maximum Likelihood，ML）［7～8］、精確極大似然法（Exact Maximum Likelihood，EML）［9～10］等。但由于異類傳感器信息融合系統中傳感器觀測數據維度不同以及時空配準引入的復雜的非線性變換等原因，難以建立方程進行系統誤差估計和補償。可以看出偏差是時變的，且同一時刻不同目標的偏差也不一致。這為目標關聯提出了很大的挑戰。傳統的目標關聯算法如匈牙利算法［11］、拍賣算法［12］、蟻群算法［13］、最近鄰算法［14］等由于沒有充分考慮系統誤差的影響，很難取得較好的關聯效果。例如，最近鄰（Nearest Neighbor，NN）算法計算量小，易于工程實現。但是在系統偏差存在的情況下，其關聯失配概率較大。其中，最近提出的基于多目標拓撲圖的目標關聯算法在系統偏差條件下實現數據關聯表現出了很好的特性。但是，拓撲圖方法在目標拓撲結構會受到空間拓撲結構的影響，在沒有考慮到度量的情況下失配率也會很大，而且復雜度較高。

本文圍繞雷達-紅外傳感器信息融合系統，針對系統誤差難以估計補償的問題，提出了基于最近鄰-點拓撲圖的異類傳感器目標關聯算法。仿真表明，新算法較最近鄰算法關聯成功率有所提高，較點拓撲圖的運算時間有所減少。

2 最近鄰算法

通常，雷達-紅外目標關聯中的NN 關聯算法［13］流程描述如下：

步驟1 隨機選擇一個雷達目標；

步驟2 從紅外目標中選擇一個與其最近鄰的紅外目標；

步驟3 將關聯的雷達目標和紅外目標分別從數據集中移除；

步驟4 重復步驟1 至步驟3，直至對每一個雷達目標完成操作，直至結束。

通常，為了保證關聯成功率，步驟1 中優先選取威脅較大的目標。NN 關聯算法運算量小，但其關聯成功率較低。

3 點拓撲法

由于探測傳感器在探測過程中是存在不可避免的系統偏差，所以，通過動態實時位置數據進行關聯會造成一些困難。而統一目標群在不同類型的雷達探測傳感器中會有相似的拓撲結構信息，所以采用基于目標結構信息（ODT）的關聯算法能夠避免系統偏差對數據關聯過程的影響。在探測傳感器中，將要關聯的目標為中心，把其他的目標作為參照物研究，這種方式表現出的信息是目標拓撲結構信息。由于不同探測目標的拓撲結構信息會有很大的區別［15～16］，因此，通過拓撲結構信息可以區分不同的探測目標。

為了方便研究，可以對目標的拓撲結構信息進行量化。首先，以需要關聯的目標為中心，畫圓形并對圓形進行分區，可將其劃分若干個區域為N個扇形區和M 個環形區（M×N個單元格）。將每個單元格賦值為uij（單元格是否存在目標），圓周上的索引用j表示，徑向索引用i表示，則uij取值如下公式（1）：

根據上面的劃分，在單元格中，若有目標時則uij=1，若無目標時則uij=0。這樣就可以將目標的拓撲結構信息進行量化。

假定雷達信息在公共坐標平面的位置如圖1（構造目標拓撲結構信息矩陣）所示。

圖1 目標的點拓撲矩陣

基于ODT 特征的目標匹配算法的具體步驟如下。

步驟1：構造對應拓撲信息的矩陣并將矩陣元素初始化為0。

步驟2：為拓撲矩陣填充拓撲信息，將雷達二維信息和紅外二維信息獨立處理，對其中的每個目標pi 以該目標建立極坐標系，把周圍空間分成若干小方格，若有目標落在小方格內，則矩陣對應元素為1，遍歷所有目標，最終得到目標pi 的ODT 特征矩陣。

步驟3：將二維的目標拓撲矩陣變為一維的特征向量，通過計算ODT 特征向量來表示目標間的相關性，其值越大表示的關聯度越高。

其中：Vai表示雷達1 目標群中目標i 的特征向量，Vbj表示雷達2目標群中目標j的特征向量。

步驟4：對相關性矩陣J 按如下匹配準則匹配，得到最終關聯序列。匹配準則如下：

1）在相關矩陣J 中的某一行（i 行），在該行中取最大值并大于某個門限，如果該值也是所列中最大值（j列），則對應的列元素和行元素相關，然后同時去掉矩陣的該行（i行）和該列（j列）。

2）在相關矩陣J 中的某一行，在該行中取最大值（大于某個門限），如果該值不是所列（j 列）中的最大值，則暫時擱置，然后繼續選擇下一行進行重復判斷。

3）對相關矩陣的所有行進行1）2）兩步處理，然后對2）中的擱置請況進行1）2）步的相關處理，按照以上步驟重復多次。

4）相關矩陣中仍有不能相關的行列，可以認為是該目標點沒有量測數據，或是雜波或新目標。

4 基于最近鄰-點拓撲圖的目標關聯算法

NN 關聯算法運算量小但是失配概率較大，而單純的基于拓撲圖的算法在拓撲結構畸變嚴重的情況下失配概率較大且運算量較大［17］。為此，基于以上兩點，我們提出基于最近鄰-點撲圖的目標關聯算法。 基于最近鄰-點拓撲圖的目標關聯算法流程如圖2所示。

圖2 最近鄰-點拓撲目標關聯算法流程

記雷達目標集合和紅外目標集合分別為R'：算法流程可描述如下。

步驟1：首先M 個雷達目標拓撲結構的幾何核心，記為Rc=(Rx，Ry)，求得N 個紅外目標拓撲結構的幾何形心，記為Ic=(Ix，Iy)。兩者幾何形心的偏差為

對于雷達目標集合中的每個目標都減去幾何形心偏差，得到新的雷達目標集合為

對于每個目標的集合，分別采取最近鄰原則，尋找紅外目標F 在鄰域x 內的雷達目標，其對象的目標集合分別記為。

步驟3：對步驟2的在紅外集合I的目標和雷達子集合R 進行利用ODT 特征的目標匹配算法來計算相似度，并記下相似度和相關矩陣。

相似度計算公式如下：

式（5）中，Sim 是代表紅外目標i 和雷達目標j的目標相似度，Xi代表第i 個紅外目標的位置，Yj代表第j個雷達目標的位置，函數β（）是表示通過紅外目標和雷達目標數據計算出兩個的關聯相似度。

基于ODT 特征的目標匹配算法的具體步驟如下。

1）構造對應拓撲信息的矩陣并將矩陣元素初始化為0。

2）為拓撲矩陣填充拓撲信息，將雷達二維信息和紅外二維信息獨立處理，以紅外目標pi 建立極坐標系，把周圍空間分成若干小方格，若有目標落在小方格內，則矩陣對應元素為1，遍歷所有目標，最終得到目標pi 的ODT 特征矩陣。

3）將二維的目標拓撲矩陣變為一維的特征向量，通過計算ODT特征向量來表示目標間 的相關性，其值越大表示的關聯度越高。

其中：Vai表示雷達1 目標群中目標i 的特征向量，Vbj表示雷達2目標群中目標j的特征向量。

步驟4：對于每個紅外目標集合，重復步驟3得到對應的拓撲相似對和對應的頂點相關矩陣。

步驟5：每個目標對應每行最小值就是其對應的解。

5 算法仿真及結果分析

5.1 仿真數據

仿真數據設置了兩個場景共計6 個樣本，其中場景設置4個紅外目標，4個雷達目標，每個目標包含100 點數據，方位角偏差在-1～0.5，俯仰角偏差在-1.5～-1之間。

5.2 仿真結果及分析

對場景的6 個樣本分別對最近鄰算法、點拓撲法、最近鄰-點拓撲算法進行仿真，如圖3所示。

圖3 目標關聯成功率結果對比圖

通過上圖可以看出，在實驗的樣本中，在目標關聯成功率上最近鄰-點拓撲算法較最近鄰算法和點拓撲法有所提高。在第四個樣本中，最近鄰算法略高于NN-點拓撲法，產生這樣的結果主要原因是點拓撲圖網格密度的選取。總體上講，本文章提出的算法較最近鄰算法和點拓撲法在目標關聯成功率上有所提高。

下面來簡要分析NN-點拓撲圖算法時間復雜度，假如雷達和紅外目標個數分別為M 和N，則步驟1 共完成2 次均值計算以及M 次減法運算；步驟2 共完成M*N 次計算距離計算以及過濾每個雷達目標所對應的紅外目標子集I={I1，I2，…，IP}；步驟3 共完成P*M 次目標相似度計算，相似度需要完成M*N+M*P 次拓撲矩陣計算；步驟4 共完成M 次目標關聯相似度計算；步驟5 共完成P 次比較。故其時間復雜度為O(M3P(N+P))量級。而點拓撲圖的時間復雜度為O(2M3N2) ，當N 取的值比較大時，后者的算法復雜度大于前者。對比實驗如圖4。

圖4 運行時間對比

本算法是將系統偏差補償和目標關聯有機的耦合在一起，受系統誤差的影響的比較小，關聯性能比較高。由于系統偏差的影響，最近鄰近法性能受到影響。而新的算法對系統偏差不敏感，性能較好。本文算法有一定的適用范圍。當傳感器出現大量的虛警和漏報時，整個拓撲結構發生嚴重的冗余或者缺失時，基于最近鄰-點拓撲圖的目標關聯算法性能下降。

6 結語

本文通過對異類傳感器目標關聯算法的深入研究，針對同一時刻系統誤差對各目標大小不一且系統誤差難以實時估計補償的情況，提出了基于最近鄰-拓撲圖的目標關聯算法。新算法巧妙地避免了系統誤差對目標關聯的影響，很好地解決了異類傳感器目標關聯成功概率較低的問題，且降低了算法的復雜度。仿真實驗表明新方法的目標關聯成功概率已經達到70%以上，但同時本文算法還有待改進的地方，比如算法中鄰域半徑的選擇如何做到自適應以及點拓撲序列的優化是下一步值得研究的地方。