地波雷達與自動識別系統目標點跡最優關聯算法

張 暉劉永信*張 杰紀永剛鄭志強

①(內蒙古大學電子信息工程學院 呼和浩特 010021)

②(國家海洋局第一海洋研究所 青島 266061)

地波雷達與自動識別系統目標點跡最優關聯算法

張 暉①劉永信*①張 杰②紀永剛②鄭志強①

①(內蒙古大學電子信息工程學院 呼和浩特 010021)

②(國家海洋局第一海洋研究所 青島 266061)

為了提高海洋探測精度和范圍，針對高頻地波雷達(HFSWR)和自動識別系統(AIS)目標點跡的融合利用問題，該文提出一種基于JVC(Jonker-Volgenant-Castanon)的點跡分狀態全局最優關聯算法。首先，通過判斷高頻地波雷達和AIS點跡的徑向速度，將點跡分為準靜態目標和動態目標。接著，選取徑向速度和點跡間的球面距離為特征參數，對不同狀態下目標點跡分別進行徑向速度和位置間球面距離粗關聯。最后，使用相對距離比的平均值進行關聯效果的評價，通過選擇合適的關聯門限參數，使用JVC算法實現高頻地波雷達和AIS的點跡最優關聯。實驗結果表明：該算法在關聯相同點跡對數的情況下，關聯精度高于最近鄰(NN)算法和Munkres關聯法，關聯用時少于最近鄰算法和Munkres關聯法。通過近3年內3組不同時刻實測目標點跡的驗證，該算法可以滿足關聯的實用性和實時性要求。

高頻地波雷達；自動識別系統；數據關聯；最優關聯；JVC(Jonker-Volgenant-Castanon)算法

1 引言

海洋是國民經濟可持續發展的戰略空間，也是國家安全的重要屏障。衛星、航空、艦載及岸基雷達、艦船自動識別系統(Automatic IdentificationSystem, AIS)是目前海上船只目標的主要探測手段。AIS能提供合作艦船的經度、緯度、速度、對地航向、船號、船的長度和寬度等信息，且定位精度較高。高頻地波雷達(High Frequency Surface Wave Radar, HFSWR)可實時監視監測并跟蹤船只，但空間分辨率較低，定位精度低于AIS。利用高頻地波雷達與AIS點跡數據融合信息，可以有效提高海上船只目標的探測范圍和精度。對于某一時刻的目標點跡融合，必須準確地判斷雷達和AIS點跡的對應關系，有效地判斷哪些目標點跡信息是來自同一個目標的信息。

現有的雷達和AIS的融合應用主要分為兩種：點跡融合[1,2]和航跡融合[3,4]。點跡融合主要關注某一時間點的目標分布情況，航跡融合則關注某一時間段的目標航跡情況。本文主要針對雷達和AIS點跡融合展開研究。國內外雷達和AIS的目標點跡融合主要集中在最近鄰(Nearest Neighbor, NN)算法[5]、統計分析法[6,7]、反向傳播(Back Propagation, BP)神經網絡關聯法[8]和模糊關聯法[9]等算法。文獻[5]將高頻地波雷達數據與AIS和合成孔徑雷達(Synthetic Aperture Radar, SAR)點跡數據使用最近鄰算法進行關聯，評估高頻地波雷達的船只探測跟蹤精度。文獻[6]和文獻[10]在分析雷達和AIS融合理論的基礎上，提出協方差矩陣計算方法，同時針對融合中數據不一致問題，做了詳細的分析。文獻[7]通過對高頻雷達探測中大量不同類型船只徑向距離和徑向速度等統計數據的分析，以AIS統計數據作為參考，從統計數據整體上評估雷達測試精度。文獻[8]］對AIS和雷達點跡間利用BP神經網絡進行關聯做了研究準備工作。文獻[9]使用一種基于最大隸屬度關系的改進模糊互相關算法融合大量的雷達和AIS觀測數據。文獻[11]通過高頻地波雷達和AIS信息的融合比對提出一種雷達天線校正算法。文獻[2]和文獻[12]通過徑向速度、徑向距離和方位角進行地波雷達與AIS點跡間的關聯，取得了很好的關聯效果。上述工作為地波雷達和AIS點跡關聯提供了方法借鑒和參考。

JVC(Jonker-Volgenant-Castanon)分配是由Jonker, Volgenant和Castanon 3人共同提出的一種線性分配算法，常用于解決數據關聯中的最優關聯計算問題。針對實際應用環境中高頻地波雷達和AIS目標點跡密集分布下的關聯問題，本文借鑒多傳感器的全局最優關聯算法[13]，將JVC算法引入目標點跡關聯中，以點跡間的球面距離作為代價函數，以相對平均距離比作為評價指標，進行最優球面距離的關聯優化，實現高頻地波雷達和AIS點跡的全局最優關聯，從而為密集環境中的雷達和AIS目標點跡關聯提供了一種新的實用算法。

2 數據源及數據預處理

實驗時間為2011年10月31日，實驗區在中國某海域，經緯度范圍35.0o～40.0oN, 117.5o～123.0oE。實驗數據包括覆蓋實驗區的高頻地波雷達和AIS目標點跡數據。

高頻地波雷達提供的目標點跡信息有探測頻率、經度、緯度、徑向速度、角度(與雷達主波束之間夾角)、探測距離。AIS信息包括經度、緯度、速度、對地航向、船號、船的長度和寬度等信息。鑒于不同運動狀態的船只的AIS信息更新頻率不同，選擇高頻地波雷達探測時間的前后5 min的AIS數據，從中選取雷達探測時間最近更新的AIS目標點跡信息作為該時刻的AIS目標點跡。

2011年10月31日:: 091850時刻高頻地波雷達目標點跡如圖1所示，AIS目標點跡如圖2所示。該時刻，高頻地波雷達共探測到336個目標點跡，AIS共探測到836個。從圖1和圖2中可以看出，AIS監測的范圍大于高頻地波雷達，圖2中經緯度在35.0o～37.0oN和117.5o～119.0oE范圍內的目標屬于高頻地波雷達所探測不到的區域，為了減少后續數據處理的復雜度，提前對AIS數據進行粗處理，對于監測范圍屬于35.0o～37.0oN, 117.5o～119.0oE的AIS目標不進行關聯分析。

3 基于JVC的分狀態數據關聯算法

圖1 2011年10月31日高頻地波雷達目標點跡分布

圖2 2011年10月31日AIS目標點跡分布

常用的數據關聯算法有最近鄰算法、全局最近鄰算法、聯合概率數據關聯(Joint Probability DataAssociation, JPDA)算法、多假設跟蹤算法(Multiple Hypothesis Tracking, MHT)等[13]。高頻地波雷達和AIS點跡數據探測范圍不同，屬于不同類別傳感器之間的數據關聯，點跡信息并不存在一一對應關系，干擾點不能通過雜波模型進行分析，JPDA和MHT算法無法應用。最近鄰算法適用于點跡稀疏的情況下進行點跡關聯，在點跡密集地區容易發生誤關聯。全局最近鄰算法從全局考慮，尋找全局代價最小的最優關聯，常見的最優關聯算法中Munkres和JVC算法的最優分配效果優于拍賣算法，JVC算法的容錯性優于Munkres算法和拍賣算法[14]。JVC算法在獲得一一關聯最優解的同時保持算法的高計算效率[13]，通過對數據的深入分析，采用分狀態JVC最優關聯算法進行高頻地波雷達與AIS目標點跡關聯。

3.1 特征向量的選擇及計算

高頻地波雷達的空間分辨率較低，如果高頻地波雷達和AIS點跡僅以位置數據關聯，在局部點跡密集區域，很容易造成誤關聯。為了提高關聯的準確性，減少誤關聯，采用徑向速度和距離作為關聯的特征參數。

3.1.1 徑向速度的計算 高頻地波雷達點跡數據中提供徑向速度，AIS點跡數據中未提供徑向速度，采用式(1)計算AIS速度在徑向角度的速度投影。

其中cogi為AIS點跡的對地航向，sogi為AIS點跡的航速，0w為雷達主波束角度。

3.1.2 點跡間球面距離的計算 高頻地波雷達和AIS采用兩點間的球面距離來進行關聯，高頻地波雷達與AIS兩點間的球面距離Dist采用式(2)進行計算。

其中R為地球近似半徑，lon, lat為高頻地波雷達與AIS點跡的經度和緯度。

3.2 點跡分狀態數據關聯算法流程

在數據關聯過程中，關聯門限的選擇至關重要，選擇合適的關聯門限，有助于對來自同一目標的不同傳感器的點跡進行關聯。船只在靜止狀態和運動狀態下，由于運動速度的不同，雷達距離測量誤差也會有所差別，因此本算法首先將準靜止狀態和運動狀態的船只進行分類，采用不同的距離關聯門限進行預關聯，再分別使用JVC算法進行分狀態最優距離關聯。分狀態數據關聯算法流程如圖3所示。

圖3 分狀態數據關聯算法流程圖

算法選取速度是否0.5≤kn來區分準靜態和運動點跡，AIS準靜態點跡所占的比例較高。準靜態下，關聯門限以式(3)實現，關聯門限與高頻地波雷達點的徑向距離成比例，比例系數為K1。點跡距離雷達的徑向距離越遠，探測誤差越大，關聯門限越大。

其中DmaxQS,i為準靜態下第i個雷達點的關聯門限值，SR,i為第i個雷達點的徑向距離。

運動狀態下，以高頻地波雷達動態點跡遍歷AIS點跡，首先進行速度關聯，對于徑向速度差小于0.5 kn的點跡進一步判斷距離門限是否符合關聯要求[8]，運動狀態下的關聯門限以式(4)實現，動態情況下的關聯門限與徑向距離和徑向速度有關，距離和徑向速度越大，測量誤差越大，關聯門限值越大。

其中DmaxD,i為動態下第i個雷達點的關聯門限值，VR,i為第i個雷達點的徑向速度，K2為距離比例參數，K3為徑向速度比例參數。

3.3 基于JVC最優距離匹配算法實現

JVC算法的模型是指在c[i,j]-u[i]-v[j ]≥0(i=1,2,…,m;j=1,2,…,n)的條件下求

其中c[i,j]為代價函數，算法選擇高頻地波雷達和AIS兩點間的球面距離作為代價函數，u[i]和v[j]分別代表行變量和列變量的分配代價，分別代表在最優解的過程中變量改變所導致的目標值的變化量[15]。最優解的求解過程就是尋找最佳的一對一點跡關聯，使得關聯點跡間的總球面距離最短。

在文獻[16]的基礎上，將JVC算法應用于高頻地波雷達和AIS的點跡關聯中，JVC算法最優距離匹配主要步驟為：

步驟1 將所有高頻地波雷達點跡信息輸入到先進先出的隊列，選擇隊首的點跡信息開始處理。

步驟2 尋找與該高頻地波雷達點跡距離最小的兩個AIS點跡。

步驟3 計算兩個AIS點跡的分配代價，初始分配代價為0，計算當前兩條最佳匹配點跡的差值。

步驟4 分配高頻地波雷達點跡到距離最小的AIS點跡，如果匹配成功，為已匹配AIS點跡的高頻地波雷達點跡重新計算新的分配代價；如果該點跡已與其他點跡匹配，則重新計算分配代價，為沖突的點跡重新尋找最優匹配。

步驟5 繼續下一點跡的匹配，直到所有雷達點跡匹配完畢或小于迭代閾值時，算法結束。

4 參數選擇及算法驗證

4.1 參數選擇

關聯算法的門限需要設置合適的參數K1, K2, K3，以達到匹配數與配對距離的平衡，采用試探法來選擇各關聯門限參數。考慮到隨著雷達點跡徑向距離的不同，雷達的測距誤差會有明顯的差別[2]。對于關聯效果的評價，選擇點跡間的相對距離比值的平均值作為主要評價因子。相對距離比計算如式(6)所示：

其中Disti為第i個關聯雷達點跡與關聯AIS點跡間的球面距離。經過測算在徑向距離為200 km時，兩點間的距離可以達到19 km[2]，選擇0.095作為相對距離比的平均值的參考上限。

4.1.1 準靜態門限參數K1的選擇 如表1所示，隨著K1值的逐步增大，準靜態下相對距離比的平均值和關聯點數也逐步增加，當K1=0.29時，相對距離比的平均值迅速增大到0.1104，考慮到準靜態下的誤差距離值較小，選擇K1=0.28。

表1 K1的取值對準靜態關聯的影響

4.1.2 動態門限參數K2的選擇 考慮到徑向距離對距離的測算影響較大，所以選擇K2作為影響動態關聯的主要因素。選擇K3=0時，隨著K2的增加，動態關聯情況變化如表2所示，當K2=0.20時，相對距離比的平均值變化較大，增大到0.0974，超出0.095，所以選擇K2=0.19，由K3進行微調。

4.1.3 動態門限參數K3的選擇 確定參數K2后，對K3的參數進行調整，K3變化對關聯情況的影響如表3所示。當K3=0.15，相對距離比的平均值增大到0.1012，但是關聯對數無明顯變化，因此選擇K3=0.11。

表2 K2的取值對動態關聯的影響

表3 K3的取值對動態關聯的影響

4.2 算法驗證及比較

分別采用最近鄰算法、Munkres算法、分狀態JVC關聯算法對2011年10月31日:: 091850時的336個雷達目標點跡和443個AIS點跡進行點跡關聯比較。

最近鄰算法在閾值選取較小的時候關聯效果較好。但當閾值增大時，最近鄰算法關聯效果會明顯變差，關聯51對時，關聯如圖4所示，圖中實線連接表示實線兩端的雷達點跡和AIS點跡為關聯點跡對。

Munkres關聯算法采用式(4)計算關聯門限，關聯效果如圖5所示，關聯51對時，相對距離比的平均值為0.1159。

圖4 最近鄰算法關聯效果

圖5 Munkres算法關聯效果

圖6 分狀態JVC關聯效果

分狀態JVC關聯算法關聯效果如圖6所示，在關聯51對的情況下，相對距離比的平均值為0.0950。

在同樣關聯51對點跡的情況下，各算法關聯結果比較如表4所示。最近鄰算法關聯的相對距離比的平均值最大，Munkres算法次之，分狀態JVC關聯算法最小，同時分狀態關聯算法計算時間也明顯優于最近鄰和Munkres算法。

表4 3種數據關聯算法的比較

4.3 算法實用性和實時性

為了驗證算法的實用性，分別采用2012年4月23日10:10:45時和2013年9月6日09:18:45時的兩組實驗數據，進行分狀態JVC數據關聯驗證，其中2012年4月23日的數據共包含273個雷達點跡和474個AIS點跡；2013年9月6日共包含262個雷達點跡和874個AIS點跡。

算法的實驗結果如表5所示，選擇相對距離比的平均值的比值不大于0.095的最大關聯情況作為關聯條件，分狀態JVC數據關聯算法可以保持約15%的關聯比例，對于273個雷達點跡和474個AIS點跡的數據關聯，在硬件環境為Intel Core i3 CPU @3.3 GHz處理器和4 G內存的普通計算機上可以在10 s內完成，滿足數據關聯的實時性要求。

5 結束語

本文針對高頻地波雷達與AIS點跡信息融合應用問題，將線性分配JVC算法應用于雷達與AIS點跡的最優匹配中，實現了點跡間距離的最優化匹配，解決了點跡密集分布環境下的數據關聯。在關聯過程中，為了提高運算速度和匹配精度，通過徑向速度的判斷將點跡信息劃分為準靜態和動態點跡，對于不同狀態的點跡分別進行JVC最優匹配，有效實現了分狀態下目標點跡的最優關聯。實驗結果表明，該算法在同樣關聯51對點跡的情況下，關聯精度高于最近鄰算法和Munkres法，關聯用時少于最近鄰法和Munkres法，為地波雷達與AIS目標點跡關聯提供了一種可行的方法。但是，由于雷達的目標定位精度較低，雷達與AIS的點跡關聯比例較低，下一步可以考慮進一步融合高精度的SAR圖像數據進行船只點跡目標融合探測，以便提高海洋探測的精度和范圍，同時可以起到校準雷達精度的作用。

表5 不同獲取時刻的數據關聯情況

[1] Dobson C, Holenstein K, Smith M, et al.. Monostatic vessel detection statistics from the CODAR SeaSonde[C]. Proceedings of the OCEANS 2013 MTS/IEEE Conference, San Diego, United States, 2013: 1-4.

[2] Ji Y G, Zhang J, Meng J M, et al.. Point association analysis of vessel targets detection with SAR, HFSWR and AIS[J]. Acta Oceanologica Sinica, 2014, 33(9): 73-81.

[3] Habtemariam B K, Tharmarasa R, Meger E, et al.. Measurement level AIS/radar fusion for maritime surveillance[C]. Proceedings of the SPIE Defense, Security, and Sensing symposium, Maryland, USA, 2012, 83930I: 1-8.

[4] Chen J and Xie L. Research of Kalman filtering in shiptrack[C]. Proceedings of the 2nd International Conference on Transportation Information and Safety: Improving Multimodal Transportation Systems-Information, Safety, and Integration, Wuhan, China, 2013: 2464-2469.

[5] Gurgel K W, Schlick T, Horstmann J, et al.. Evaluation of an HF-radar Ship detection and tracking algorithm by comparison to AIS and SAR data[C]. Proceedings of the International Waterside Security Conference (WSS), Marina di Carrara, Italy, 2010: 1-6.

[6] Kazimierski W and Stateczny A. Fusion of data from AIS and tracking radar for the needs of ECDIS[C]. Proceedings of the Signal Processing Symposium, 2013, Serock, Poland, 2013: 1-6.

[7] Dzvonkovskaya A and Rohling H. HF radar performance analysis based on AIS ship information[C]. Proceedings of the 2010 IEEE Radar Conference, Washington DC, USA, 2010: 1239-1244.

[8] Hu X R and Lin C C. A preliminary study on targets association algorithm of radar and AIS using BP neural network[J]. Procedia Engineering, 2011, 15: 1441-1445.

[9] Liu C, Lin B, Liu X M, et al.. Fuzzy correlation algorithm for multi-target fusion of automatic identification system and radar[J]. Journal of Computational and Theoretical Nanoscience, 2013, 10(12): 2826-2830.

[10] Kazimierski W. Problems of data fusion of tracking radar and AIS for the needs of integrated navigation systems at sea[C]. Proceedings of the 14th International Radar Symposium, Dresden, Germany, 2013: 270-275.

[11] 田文龍, 李高鵬, 許榮慶. 利用自動識別系統信息進行高頻地波雷達天線陣校正[J]. 電子與信息學報, 2012, 34(5): 1065-1069.

Tian W L, Li G P, and Xu R Q. High frequency surface wave radar antenna array alibration using automatic identification system data[J]. Journal of Electronics & Information Technology, 2012, 34(5): 1065-1069.

[12] 紀永剛, 張杰, 王祎鳴, 等. 雙頻率高頻地波雷達船只目標點跡關聯與融合處理[J]. 系統工程與電子技術, 2014, 36(2): 266-271.

Ji Y G, Zhang J, Wang Y M, et al.. Ship detection point association surface and fusion with dual-frequency HF wave radar[J]. Systems Engineering and Electronics, 2014, 36(2): 266-271.

[13] 盛衛東, 林兩魁, 安瑋, 等. 基于全局最優的被動多傳感器多目標軌跡關聯算法[J]. 電子與信息學報, 2010, 32(7): 1621-1625.

Sheng W D, Lin L K, An W, et al.. A passive multisensor multitarget track association algorithm based on global optimization[J]. Journal of Electronics & Information Technology, 2010, 32(7): 1621-1625.

[14] Kadar I, Eadan E R, and Gassner R R. Comparison of robustized assignment algorithms[C]. Proceedings of the Aerospace Defence Sensing and Control (AeroSense) Conference, Orlando, FL, USA, 1997: 240-249.

[15] Jonker R and Volgenant A. A shortest augmenting path algorithm for dense and sparse linear assignment problems[J]. Computing, 1987, 38(4): 325-340.

[16] Malkoff D B. Evaluation of the Jonker-Volgenant-Castanon (JVC) assignment algorithm for track association[C]. Proceedings of the Aerospace Defence Sensing and Control (AeroSense) Conference, Orlando, FL, USA, 1997: 228-239.

張 暉： 男，1983年生，博士生，研究方向為圖像處理、多傳感器數據融合等.

劉永信： 男，1955年生，教授，研究方向為圖像處理、多傳感器數據融合等.

張 杰： 男，1963年生，研究員，研究方向為海洋遙感探測等.

Target Point Tracks Optimal Association Algorithm with Surface Wave Radar and Automatic Identification System

Zhang Hui①Liu Yong-xin①Zhang Jie②Ji Yong-gang②Zheng Zhi-qiang①

①(College of Electronic Information Engineering, Inner Mongolia University, Hohhot 010021, China)
②(First Institute of Oceanography, State Oceanic Administration, Qingdao 266061, China)

In order to solve the problem that of High Frequency Surface Wave Radar (HFSWR) and Automatic Identification System (AIS) target point tracks fusion, a point tracks association algorithm using Jonker-Volgenant-Castanon (JVC) global optimal matching for different status is proposed. Firstly, the HFSWR and AIS target point tracks are divided into the quasi-static and dynamic data by the radial velocity. Then the radial velocity and spherical distance are selected as the feature parameters, and the different status data are respectively pre-associated by the radial velocity and spherical distance. Finally, the average of relative distance ratio is used to evaluate the effect of association. According to the selection of threshold parameter, the HFSWR and AIS point tracks are optimal associated with the JVC algorithm. The experimental results indicate that the proposed algorithm, in the condition of equal number point tracks associated, is superior to the Nearest Neighbor (NN) algorithm and Munkres association algorithm in the association accuracy, and the associate time is less than the NN algorithm and Munkres association. Moreover, three different time data gained from the target traits measured in nearly three years demonstrate that the feasibility and real-time of the proposed method.

High Frequency Surface Wave Radar (HFSWR); Automatic Identification System (AIS); Data association; Optimal association; Jonker-Volgenant-Castanon (JVC) algorithm

TN958

A

1009-5896(2015)03-0619-06

10.11999/JEIT140678

2014-05-21收到，2014-09-22改回

國家自然科學基金(61362002)和海洋公益性科研專項(200905029)資助課題

*通信作者：劉永信 yxliu@imu.edu.cn