基于自適應DBSCAN的雷達目標跟蹤算法

張 巧， 楊紅雨,2， 劉 洪,2， 劉 宇,2， 閆 震

(1.四川大學視覺合成圖形圖像技術重點學科實驗室， 成都610065; 2.四川大學計算機學院， 成都610065)

1 引 言

三坐標航管一次雷達回波信號經過雷達信號處理單元后形成雷達點跡數據，但是對于民航等大型目標而言，目標本身尺寸較大，可以跨越多個距離及方位單元，在雷達信號處理之后同一目標仍會產生多個點跡信息.并且對于雜波環境下，由于各種雜波出現的不規則性[1]，特別是雷達在受到地雜波或海雜波影響的區域，每個周期都可能出現大量的點跡報告，給數據處理系統造成極大的壓力，嚴重影響雷達目標跟蹤效率[2].

國內外對該問題所提出的解決方案主要在雷達信號處理方面和進行航跡跟蹤時算法改進方面.

在雷達信號處理方面，主要是CFAR算法的研究及改進.CFAR檢測算法分成兩類：瑞利背景下的CFAR算法和非瑞利背景下的CFAR算法.

瑞利背景下的CFAR算法有4類，第一類是均值類(ML) CFAR算法，其中最經典的是單元平均算法(CA) CFAR算法[3].為了減小雜波邊緣的虛警，提出單元平均放大(GO) CFAR[4]算法；第二類是有序統計類恒虛警算法，最經典的是OS-CFAR算法[5]及剔除平均(TM) CFAR算法[6-7]；第三類是自適應CFAR算法，其中包括變化指數(VI)CFAR算法[8]及非均勻雜波估計(HCE)CFAR算法[9]；第四類是雜波圖CFAR算法[10].

非瑞利背景下的CFAR算法包括Log-tCFAR算法[11-12]等.

張欣[13]提出一種基于對數雜波圖的自適應恒虛警檢測算法，在復雜雜波背景環境下提高雷達系統的檢測性能，有效減少虛假航跡數.

進行航跡跟蹤時所用算法的改進方面，主要是對卡爾曼濾波算法的改進.Bar-Shalom等[14]提出擴展卡爾曼(EKF)濾波算法.文獻[15]提出無跡卡爾曼濾波，在一定程度上提高了濾波精度.針對高斯分布的非線性濾波問題，積分卡爾曼濾波和容積卡爾曼濾波[16]被提出.

隨著人工智能在工程上的大量運用，基于神經網絡的卡爾曼濾波被提出.張宇行等[17]提出的基于LSTM的航跡跟蹤.這些方法都可減少虛假航跡數.

本文轉換了角度，從雷達數據處理的角度出發，基于動態自適應DBSCAN 聚類算法，結合經典卡爾曼濾波跟蹤算法，提出DBSCAN-KALMAN混合算法.該算法包括兩個部分，分別是點跡數據精細化處理階段和目標跟蹤階段.在點跡數據精細化處理階段，DBSCAN-KALMAN以雷達掃描周期為時間片單位，對各時間片中的點跡數據，應用DBSCAN算法進行聚類，將聚類后的各類點跡數據依據質心算法分別計算點跡質心，以各類點跡數據與各類質心歐式距離最小的點跡作為此時間片最終輸出點跡，被DBSCAN標記為噪聲點的點跡也作為此時間片最終輸出點跡輸出；在跟蹤階段，應用經典卡爾曼濾波算法，對于多個時間片內的輸出點跡數據進行跟蹤處理，形成目標航跡.

三坐標航管一次雷達信噪比、地波干擾會產生大量虛假目標點跡干擾，但其嚴重程度并不至于干擾民航機等大目標.本方法適用于快速在低空空域范圍內發現非合作目標(即沒有提前報備的黑飛目標)的場景.利用動態自適應DBSCAN 聚類跟蹤混合算法，有效減少雜波造成的虛假點跡，快速跟蹤并形成民航飛機與黑飛目標航跡，這樣可以及時發現黑飛目標，將對正常民航飛機飛行的干擾降到最低.

2 自適應DBSCAN算法

2.1 算法原理

聚類算法被廣泛應用于用戶圖像[18]、 文本處理[19]等領域.DBSCAN是一種基于密度的聚類算法，該算法不需要事先給定聚類類別數目，不僅可適用凸樣本集，也同樣適用于非凹樣本集.將所有各組緊密相連的樣本化為各個不同的類別，就能得到最終的聚類結果.

2.2 DBSCAN密度定義

DBSCAN參數(ε,MinPtrs)用來描述領域的樣本分布緊密程度，其中，ε描述某一樣本的領域距離閾值；MinPtrs描述某一樣本的距離為ε的領域內包含樣本個數的閾值.文獻[20]給出了DBSCAN具體密度描述關鍵定義.

2.3 自適應DBSCAN參數設置

DBSCAN聚類結果對ε與MinPtrs取值敏感，人工選取，可能造成聚類不準確.已有不少文獻提出若干參數自適應方法. 文獻[21]根據數據集在每個維度的密度分布，動態設置ε，但仍需要輸入MinPtrs，沒有實現聚類的全自動化.Kim等[22]提出AA-DBSCAN算法，基于四叉樹的新樹結構來定義數據集的密度層，以實現不均勻密度數據集的聚類，但算法仍需輸入相關參數.Khan等[23]提出的AD-DBSCAN自適應聚類算法需要提前指定簇的數量，無法自動識別簇類數目.夏魯寧等[24]提出的SA-DBSCAN聚類算法，利用逆高斯擬合KNN分布并分解峰值點以確定ε.

本文采用文獻[25-26]的DBSCAN自適應參數方法，繪制K-距離曲線與數據點距離升序曲線，取K-距離曲線的第一個谷底位置與數據點距離升序曲線最密集的位置對應的距離的中間值作為ε，而根據雷達跟蹤目標飛行特性來確定MinPtrs.

雷達目標跟蹤是通過相關和濾波處理建立起目標的運動軌跡，包括對目標運動狀態所做的估計和預測，進而對目標進行評估.雷達跟蹤最重要的環節就是建立航跡時選用的濾波算法，選用合適的濾波算法可以影響雷達跟蹤精度.最常用的濾波算法就是卡爾曼濾波算法.卡爾曼濾波算法主要由以下公式組成[27].

狀態一步預測如下式.

(1)

協方差一步預測如下式.

P(k+1|k)=F(k)P(k|k)F′(k)+Q(k)

(2)

量測的預測協方差為

S(k+1)=H(k+1)P(k+1|k)H′(k+1)+

R(k+1)

(3)

卡爾曼增益如下式.

K(k+1)=P(k+1|k)H′(k+1)S-1(k+1)

(4)

狀態更新如下式.

K(k+1)v(k+1)

(5)

4.1 DBSCAN-KALMAN算法定義

4.1.1 點跡數據劃分時間片 由于三坐標航管一次雷達點跡錄取器中錄取到的點跡是以雷達掃描周期為單位，因此點跡屬于時間序列數據，所以需要以雷達掃描周期為時間片單位將點跡集合分成若干小的時間片點跡集合.以下是數學公式描述.

f[T,t0,X(t,x,y,z)]=P(t,n,xn,yn,zn)

(6)

其中,T為雷達掃描周期；t0為初始時刻；t為各點跡錄取時刻；X(t,x,y,z)為錄取器錄取到的點跡數據；n為時間片數；P(t,n,xn,yn,zn)為根據T為單位劃分的第n個時間片點跡集合.

4.1.2 基于時間片聚類 理論上同一目標在不同時間片點跡集合中僅會有一個點跡信息，但實際上由于存在虛警與大目標跨越多個距離及方位單元情況，同一目標在相同時間片點跡集合中存在多個點跡信息.

但同一目標在相同時間片點跡集合中的不同點跡之間本身屬性差異并不大，在空間分布上符合按密度堆積，即同一目標的不同點跡間通常聚集形成密度稠密的類簇，不同目標間的點跡一般相隔較大，密度稀疏，不會形成類簇.

基于以上特點，使用基于密度的典型聚類方法DBSCAN算法，對時間片點跡集合進行聚類，會形成不同類簇集合.以下是數學公式描述.

g[P(t,n,xn,yn,zn),ε,MinPtrs]=

Y(t,n,c,xc,yc,zc)

(7)

其中,ε為DBSCAN的半徑閾值；MinPtrs為DBSCAN的樣本閾值；Y(t,n,c,xc,yc,zc)為第n個時間片聚類后第c類的點跡集合.

4.1.3 基于時間片的各類簇計算質心 根據上一步得到類簇集合，以及同一類簇集合間的各點跡間屬性差異不大的特點，且聚類后的類簇是同一類目標，因此只需要選擇這些點跡集合中的一個點跡代表此類簇即可，這樣可以使用于之后的航跡跟蹤的候選點跡數量減少.

隨機選取同一類簇集合的點跡代表此類簇，會為最終的航跡跟蹤結果引入了隨機性，所以需尋找一個基準，以此基準來選擇哪個點跡代表本類簇.

考慮到點跡信息包括距離、方位、俯仰三個維度及聚類后形成的類簇質心表征本類屬性的特點，所以對這三個維度分別取質心，即分別取三個維度的中心，并組成最終基準.以下是數學公式描述基準的形成.

Y(t,n,c,xc,yc,zc)=

Z(t,n,c,xcenter,ycenter,zcenter)

(8)

其中,Z(t,n,c,xcenter,ycenter,zcenter)為使用質心算法后第n個時間片聚類后第c類質心點跡.

4.1.4 基于時間片的各類簇點跡選擇 根據上一步計算得到的各類簇基準，以與基準的歐式距離最小的各類簇點跡來代表各類簇.以下是數學公式描述.

Dis[Y(t,n,c,xc,yc,zc),Z(t,n,c,xcenter,ycenter,zcenter)]=

(9)

Y′(t,n,c,xc,yc,zc)=Min{Dis[Y(t,n,c,xc,yc,zc),

Z(t,n,c,xcenter,ycenter,zcenter)]}

(10)

我們選取使Dis最小的對應的點跡Y′(t,n,c,xc,yc,zc)作為此時間此類的最終點跡.

4.1.5 卡爾曼濾波航跡跟蹤 經過以上步驟，將所有基于時間片得到的點跡作為候選點跡集合進行航跡跟蹤，得到不同目標形成的點跡集合，即航跡.以下是數學公式描述.

H[Y′(t,n,c,xc,yc,zc)]=Ti(t,xc,yc,zc)

(11)

其中,Ti(t,xc,yc,zc)為卡爾曼濾波跟蹤到的第i條航跡的點跡集合.

4.2 基于自適應DBSCAN的雷達目標跟蹤算法實現

基于自適應DBSCAN的雷達目標跟蹤算法的主要步驟如算法1所示.

算法1基于自適應DBSCAN的雷達目標跟蹤算法

輸入：三坐標航管一次雷達某一時間段點跡集X(t,x,y,z)，待雷達目標跟蹤點跡空隊列Queue.

輸出：跟蹤到的各條航跡對應的點跡集合Ti(t,xc,yc,zc).

Begin

Step1通過分析某一時間段的雷達錄取器中的點跡分布，確定DBSCAN的閾值MinPtrs，并在所有時間片聚類過程中保持不變；

Step2將點跡集拆分成多個以雷達掃描周期為單位的時間片集合τ(t1、t2，…)，對每個時間片繪制出K-距離曲線與數據點距離升序曲線，取K-距離曲線的第一個谷底位置與數據點距離升序曲線最密集的位置對應的距離的中間值，作為此時間片的DBSCAN的半徑ε；

Step3對時間片ti進行DBSCAN聚類；

Step4對Step 3聚類完成后形成的非噪聲類簇求質心，質心屬性使用下面公式分別求解：

距離屬性：

(12)

方位屬性：

(13)

俯仰屬性：

(14)

Step5選擇此類簇中點跡與其質心點跡歐式距離最小對應的點跡作為此類簇最終點跡輸出，并添加到待目標跟蹤點跡隊列Queue中；

Step6對Step 3聚類完成后形成的噪聲類不做處理，直接添加到Queue中；

Step7重復Step 2～Step 6步驟，直到全局聚類；

Step8將Queue的點跡作為雷達目標跟蹤算法輸入數據進行跟蹤.

End.

5 實 驗

表1 三坐標場面監視一次雷達部分點跡數據

5.1 雷達聚類前點跡分布

文章使用三坐標航管一次雷達于2019年4月29日在南充某機場錄取到的點跡數據作為分析依據，聚類前雷達點跡數據分布，如圖1所示.

圖1 聚類前雷達點跡數據分布

5.2 雷達聚類前航跡跟蹤結果

經過航跡起始、跟蹤、濾波、平滑處理后，跟蹤到多條航跡.從聚類前跟蹤的航跡明顯可以看出，航跡存在分叉、虛假航跡、部分航跡長度很短等干擾情況，航跡分布如下圖2所示.

圖2 聚類前雷達跟蹤到的航跡

5.3 基于自適應DBSCAN的雷達點跡跟蹤

5.3.1 雷達掃描周期內進行點跡聚類 選擇點跡數最多的一個雷達掃描周期作為分析區間.使用Matlab計算得到一個雷達掃描周期內最多有62個點跡，位于第298個時間片位置.

本文選擇K= 4.計算排序的4-距離曲線圖與數據點距離升序曲線，如圖3和圖4所示.

圖3 4-距離曲線圖

圖4 數據點距離曲線

根據文獻[10-11]提出了自適應DBSACN的參數配置方法與改進方法，確定第298個時間片的DBSCAN參數分別為設置ε= 100與MinPtrs= 4，距離采用歐式距離,求類簇中心屬性使用本文提出的質心屬性求解公式.聚類運行結果如圖5所示.聚類結果如表2所示.

圖5 自適應DBSCAN聚類結果

5.3.2 點跡跟蹤 全局聚類后對所有時間片輸出點跡進行航跡跟蹤.實驗表明，跟蹤后的航跡質量提高，雜波點進一步減少，運算速度提高，跟蹤后航跡分布如圖6所示.

表2 聚類結果表

圖6 聚類后雷達跟蹤到的航跡

實驗對聚類前后結果進行了簡單對比，對比如表3所示.

表3 聚類前后對比表

對比以上結果表明，運用提出的混合算法有一定的有效性，能減少無效點跡，航跡質量也得到了提高，但被DBSCAN標記為噪聲類的點跡集合中存在小部分有效點跡，為了保證不丟失任何有效點跡，保留所有噪聲類點跡并輸出，這是限制此算法效果的主要因素.因此需要繼續優化算法，將噪聲類點再進行細分，將真實的噪聲點濾除掉，以達到最優效果.

6 結 論

本文有效解決了雷達點跡形成航跡過程運算量大、形成虛假航跡多、航跡質量不好等問題.對每個掃描周期進行自適應DBSCAN聚類，減少了每個掃描周期內點跡數.使用質心算法計算聚類后各類簇質心，選擇使該類質心與該類點跡的歐式距離最小的點跡及被標記為噪聲點的點跡作為該類點跡輸出，并對所有時間片輸出點跡進行航跡跟蹤.航跡跟蹤后表明無效點跡減少，航跡質量提高，跟蹤時間縮短.而如何繼續減少無效點跡點，仍然是未來雷達領域的研究主要方向.