改進的DBSCAN 算法在室內多擴展目標跟蹤中的研究

王國林，于映

（南京郵電大學集成電路科學與工程學院，江蘇南京 210023）

近年來，無線電技術的快速進步，推動了目標跟蹤技術的進一步發展。由于全球定位系統GPS[1]在室內環境中的特殊性，所以無法繼續在室內環境中使用室外定位系統。與此同時，人們對室內人員的定位跟蹤需求也與日俱增，工廠、倉庫、地下停車場、監獄等場景都需要獲取準確的多個目標移動軌跡以便對人員進行實時監控，方便對人員的管理。在室內環境中，隨著現代雷達的分辨率的不斷提高，每一時刻能接收獲取目標多個量測數據，此時雷達采集的目標信息不再是點目標[3]的形式，而被稱為擴展目標[4]。傳統的多目標跟蹤算法例如最近鄰域法(GNN)[5]、聯合數據關聯概率算法(JPDA)[6]、多假設軌跡法(MHT)[7]都是基于點假設，通常利用量測點與目標點源之間的數據關聯將量測數據分配給某個目標。該類方法的關鍵在于數據關聯[8]，錯誤的關聯會導致跟蹤性能變差，甚至出現目標漏跟，并且由于點源量測數據量的增大與位置的不確定性影響數據關聯的復雜度和準確性，從而難以應對目標個數增加，雜波密集等環境，所以并不適用于擴展目標跟蹤。

雷達在室內環境下所獲取的目標量測數據的形式為擴展目標的形式，并且室內不同目標的量測數據分布密度近似，因此可以采用密度聚類的算法將擴展目標形式的量測數據轉換為點目標的形式。基于密度聚類算法(DBSCAN)[9]相比其他聚類算法，不需要預先確定聚類的簇數目，更適合對未知數量的目標量測數據進行聚類，并結合質心算法實現目標形式轉換。但室內環境復雜度日益增加，DBSCAN算法將會花費大量的時間用于數據聚類，導致系統無法達到實時跟蹤室內人員活動情況的目的。

針對室內雜波分布密集、擴展目標數量增加的環境下對多擴展目標難以進行實時跟蹤的問題，提出一種基于改進的DBSCAN 算法的室內多擴展目標跟蹤算法，旨在減少聚類的時間消耗，滿足室內雷達目標跟蹤系統的實時性要求。該方法通過KD 樹[10]算法，實現對量測數據先劃分再聚類，減少了對大量量測數據點的距離運算，滿足對目標實時跟蹤的需求。并且在點目標跟蹤算法中運用了Murty方法[11]來加速數據關聯，并采用UKF 算法[12]進行跟蹤濾波，不僅降低了室內多擴展目標跟蹤系統的算法復雜度，還提高了目標跟蹤系統的穩定性。

1 多擴展目標跟蹤算法原理

1.1 基于點形式目標跟蹤算法流程及局限性

基于點形式目標跟蹤算法主要分為兩個模塊，分別是數據關聯模塊和狀態估計模塊。數據關聯模塊的主要作用是關聯已起始的軌跡和新的量測數據。聯合概率數據互聯算法（JPDA)是數據關聯算法之一。JPDA 算法是應用于觀測數據落入跟蹤門相交的區域的情況，落入跟蹤門的數據有可能來源于多個目標。JPDA 算法的優點在于它不需要任何關于目標和雜波的先驗信息，廣泛適用于雜波環境中對多目標跟蹤系統。然而隨著目標的數量增加以及雷達采集的目標量測數據增多時，JPDA 算法會出現組合爆炸的情況，導致計算量增大，嚴重影響跟蹤系統的效率。狀態估計模塊主要采用卡爾曼濾波算法。卡爾曼濾波（Kalman Filtering）算法[13]是處理目標線性運動的主流算法，通過輸入的觀測數據，對目標的運動狀態進行最優的估計。卡爾曼濾波算法只能估計線性運動的目標，對于非線性運動目標的估計準確度嚴重不足，主要有兩種改進的方法，即擴展卡爾曼濾波（EKF）[14]和無跡卡爾曼濾波(UKF)。傳統點形式目標跟蹤算法流程如圖1 所示。

圖1 傳統點形式目標跟蹤算法流程

1.2 基于密度聚類的量測數據聚類算法

由于雷達采集的量測數據量大，并且分布密集，需要對量測數據進行分割，分割出屬于同一目標的量測數據，通過質心算法將擴展目標形式的量測數據轉化為點目標形式，實現以點代物。在量測數據分割的算法中，常見的有模型擬合、深度學習、區域增長等聚類方法等[15-16]。目標跟蹤系統常用的DBSCAN 聚類算法是一種基于密度的量測數據分割算法，該方法由于能夠有效解決噪聲的干擾、無需提前設定目標個數、在密集的點云數據中發現任意凸形狀的聚類目標等優點，廣泛適用于量測數據聚類。雷達跟蹤室內目標所獲取的量測數據具有相似的密度，更好地契合了DBSCAN 算法可以從樣本密度的角度來考慮目標之間的密度可達的特點。DBSCAN 使用一組關于“鄰域”的參數(ε,MinPts)來描述樣本分布的緊密程度，ε是一個點周圍鄰近區域的半徑，MinPts 是鄰近區域內至少包含點的個數，在ε鄰域內有至少MinPts 個鄰域內的點為核心點。DBSCAN 算法聚類如圖2 所示。

圖2 DBSCAN算法聚類示意圖

DBSCAN 算法將所有的量測數據分別定義為核心點、邊界點和噪聲點，不同類型的點對應不同的量測數據密度。通過密度來劃分不同的量測數據類型，區分干擾量測和有效量測。DBSCAN 算法采用的是線性查找的方法，但這種算法遍歷了每一個數據點，復雜度較高。隨著雷達分辨率的提高以及室內環境的復雜性增加，線性查找的方式顯然過于繁瑣，無法滿足跟蹤系統的實時性要求。通過對算法的分析，可以預先計算距離矩陣，再進行鄰域查找，可以有效降低復雜度。但是這種改進存在一定的缺陷，需要額外的計算空間。當數據量非常大時，會導致上位機的運行內存不足，致使目標跟蹤失敗。

2 改進的多擴展目標跟蹤算法原理

2.1 改進的點形式目標跟蹤算法流程

JPDA 算法在實際工程中被廣泛使用，算法的關鍵點在于聯合概率的計算。當目標數據與觀測值增多時，計算出的聯合概率數據會呈指數級增長，導致算法的復雜度大大提高，無法滿足實際工程中的實時性要求。

改進的目標跟蹤系統利用Murty 算法，在不計算所有目標與觀測值的聯合概率的情況下，得到K個概率最大的目標與量測數據的聯合概率。通過Murty 算法，在保持傳統JPDA 算法的精度的情況下，降低了算法的計算時間，提高系統的實時性。

傳統的跟蹤濾波算法主要采用卡爾曼濾波（KF）和擴展卡爾曼濾波（EKF），分別處理線性運動目標和非線性運動目標跟蹤。但當局部線性假設不成立時，會導致結果誤差比較大，影響跟蹤系統的穩定性。跟蹤系統通常采用的跟蹤濾波算法的UKF 算法，該算法通過不同采樣點的選擇來獲取相關的量測數據。改進的數據關聯和狀態估計算法流程如圖3 所示。

圖3 改進的數據關聯和狀態估計流程圖

2.2 改進的DBSCAN算法

DBSCAN 算法的核心是找到密度相連對象的最大集合。算法的復雜度主要在于對鄰域點的查找。為了實現該算法，采用逐點遍歷的方法，遍歷每一個數據點，判斷是否為核心點或者噪聲點，若為核心點則新建聚類，并將所有鄰域點加入聚類。對于鄰域點中的核心點，還要遞歸地將其鄰域點加入聚類。預先計算距離矩陣的方法可以減小算法的計算量，但是系統的空間如果不能滿足計算所需的額外空間，就會導致聚類失敗，從而影響室內目標跟蹤系統的性能。

改進的聚類算法采用索引方法查詢鄰域點，利用KD 樹對量測數據進行劃分與構建，在聚類之前生成每個數據點的鄰域對象集，遍歷每個數據點，并通過構造好的KD 樹進行近鄰點搜索，包含核心點、邊界點以及噪聲點。

當量測數據增大時，可以明顯地減少鄰域內的量測數據的查找次數，減少算法計算時間，滿足實時性的要求。改進后的聚類算法主要分為三個步驟，分別為KD 樹的創建、查找鄰域節點集合和聚類中心的提取。

2.2.1 KD樹的創建

KD Tree 是K-dimensional Tree 的縮寫，是一種獨特的二叉搜索樹結構，樹中每一層對應一個維度。KD 樹中左子樹給定維度的值小于父節點，而右子樹則大于父節點。KD 樹創建流程如圖4 所示。

圖4 KD樹的構建過程

2.2.2 查找鄰域節點集合

在利用建立好的KD 樹進行鄰域點的查詢前，需要對每一個節點根據DBSCAN 算法輸入的參數ε計算出邊界范圍（一般為正方形邊界范圍），再從KD 樹的根節點開始查找鄰近點，比較樹上的所有節點對應維度的值與邊界范圍，將在范圍內的數據節點添加到特定的標簽集合中。計算該集合中所有點到當前節點的距離，并與輸入參數ε比較，去除集合中距離大于參數ε的數據點。

當完成上述步驟的處理后，集合中所剩的數據點到當前節點的距離均小于參數ε。再次查看集合中點的個數是否大于DBSCAN 算法輸入的另一個參數Minpts，保留大于Minpts 的數據集合用于聚類，刪除不滿足條件的集合。對非集合中的點，重復上面的過程，直至遍歷所有節點，完成鄰域查找過程，得到聚類結果。算法中計算聚類特征采用歐氏距離公式：

2.2.3 聚類中心的提取

在得到聚類結果后，同一幀內屬于同一標簽集合的點為該時刻同一目標的量測數據信息，通過對聚類得到的不同目標的點云數據，運用質心算法，提取聚類中心點，代替原來點云數據，實現了對擴展目標向點目標的轉化。質心算法公式為：

其中，xi為輸入的量測數據有限點集。

3 仿真實驗

3.1 仿真實驗環境配置

假設仿真環境存在多個目標，目標的運動模型為勻速圓周運動（CT）模型，雷達檢測時間為20 s，檢測時間間隔為0.2 s，檢測概率為0.9。由于室內環境噪聲、多徑等影響產生大量的量測雜波，雜波分布滿足泊松分布。在1 000×1 000 cm2的范圍內，產生雜波的數量為1 000 個，并且每個目標每一幀產生20 個量測點，產生的量測點滿足泊松分布。目標運動模型和量測方程為：

其中，X(t)=(xyVxVyθ)；x、y為目標所在位置，Vx、Vy為目標移動速度，θ為目標做勻速圓周運動的轉動角速度；狀態轉移矩陣F為：

噪聲系數G和方差陣Q分別為：

其中，sigmaV=1，sigmaOmega=π/180。

量測矩陣H和觀測噪聲矩陣V為：

其中，sigmaR=1。

3.2 實驗結果與分析

3.2.1 仿真實驗一

室內環境中存在的擴展目標個數為3，目標的運動模型為CT 模型，數據關聯算法采用Murty 算法改進后的JPDA 算法，跟蹤濾波算法分別采用UKF 算法和EKF 算法。經過100 次Monte Carlo 仿真實驗，對比了三種聚類算法以及兩種不同濾波算法處理100幀量測數據所需時間以及多擴展目標跟蹤系統的均方根誤差（RMSE）。

由圖5 可以看出，KD 樹改進的DBSCAN 算法相較于其他兩種算法，極大地減少了跟蹤系統所消耗的時間。并且采用傳統的DBSCAN 算法進行目標跟蹤時，在處理第64 幀數據時，該幀處理的時間超過0.2 s，在實際工程中會直接導致系統的跟蹤精度下降，甚至會出現跟蹤目標丟失的情況。而改進的算法在100 次仿真實驗中所消耗的時間都在一個較低的水平，三種算法跟蹤目標的RMSE 都為3.506 cm，而K-means 算法的RMSE 為386.84 cm。實驗說明改進的DBSCAN 算法在保證目標跟蹤精度的同時，有效地解決了環境噪聲帶來的影響，并且極大地減少了系統所消耗的時間。對比DBSCAN 算法與K-means 算法可以看出，由于噪聲點的干擾，K-means 算法不論是從跟蹤誤差上還是系統時間消耗上都遠大于改進的聚類算法。通過圖6 兩種濾波算法的誤差對比可以看出，UKF 算法的RMSE 總體上小于EKF 算法，說明目標在室內做勻速圓周運動時，UKF 算法跟蹤效果更加穩定，有更好的魯棒性。

圖5 室內實現三個擴展目標跟蹤所需時間

圖6 EKF和UKF仿真精度對比

3.2.2 仿真實驗二

室內擴展目標個數逐漸增加，個數分別為3、5、10、15、20、30，其余仿真場景配置與仿真實驗一相同。經過100 次Monte Carlo 仿真實驗得到目標跟蹤系統所需時間以及計算擴展目標跟蹤系統的RMSE。

室內擴展目標跟蹤系統所消耗的時間由兩部分組成，即聚類算法消耗的時間和點目標跟蹤消耗的時間。由表1 可以看出，兩部分耗時都與室內擴展目標個數呈正相關的趨勢，并且目標的跟蹤誤差也隨目標個數的增加逐漸增大。當擴展目標個數不斷增加時，改進的聚類算法依舊保持較低的時間消耗，能夠實現30 個擴展目標左右的實時跟蹤。

表1 改進的算法在不同擴展目標個數下所需總時間

但繼續分析表1 可以發現，當室內擴展目標增加到一定數量后，整體系統耗時主要由數據關聯算法產生。為了更加滿足室內多擴展目標跟蹤系統實時性的要求，就需要更加高效的數據關聯算法。

4 結論

為了滿足室內多擴展目標跟蹤系統實時性的要求，必須提高聚類的效率以滿足實時性的要求，通過仿真實驗提出了一種適用于幀內擴展目標量測數據快速聚類的算法。不僅在保證跟蹤精度的情況下，有效地濾除了雜波，還能很快地檢測出擴展目標，以點代物，大大提高了目標跟蹤的效率。在實際工程運用中，改進的算法也可以實現幀間數據聚類的算法對目標的跟蹤，跟蹤精度更高。由于室內擴展目標個數不可控，當數量達到一定的閾值時，繼續提高聚類算法計算效率或許無法滿足系統的實行性需求，則需要更加快速的數據關聯算法和跟蹤濾波算法。