改進的DBSCAN 算法在室內(nèi)多擴展目標(biāo)跟蹤中的研究

王國林，于映

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

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

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

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

1 多擴展目標(biāo)跟蹤算法原理

1.1 基于點形式目標(biāo)跟蹤算法流程及局限性

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

圖1 傳統(tǒng)點形式目標(biāo)跟蹤算法流程

1.2 基于密度聚類的量測數(shù)據(jù)聚類算法

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

圖2 DBSCAN算法聚類示意圖

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

2 改進的多擴展目標(biāo)跟蹤算法原理

2.1 改進的點形式目標(biāo)跟蹤算法流程

JPDA 算法在實際工程中被廣泛使用，算法的關(guān)鍵點在于聯(lián)合概率的計算。當(dāng)目標(biāo)數(shù)據(jù)與觀測值增多時，計算出的聯(lián)合概率數(shù)據(jù)會呈指數(shù)級增長，導(dǎo)致算法的復(fù)雜度大大提高，無法滿足實際工程中的實時性要求。

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

傳統(tǒng)的跟蹤濾波算法主要采用卡爾曼濾波（KF）和擴展卡爾曼濾波（EKF），分別處理線性運動目標(biāo)和非線性運動目標(biāo)跟蹤。但當(dāng)局部線性假設(shè)不成立時，會導(dǎo)致結(jié)果誤差比較大，影響跟蹤系統(tǒng)的穩(wěn)定性。跟蹤系統(tǒng)通常采用的跟蹤濾波算法的UKF 算法，該算法通過不同采樣點的選擇來獲取相關(guān)的量測數(shù)據(jù)。改進的數(shù)據(jù)關(guān)聯(lián)和狀態(tài)估計算法流程如圖3 所示。

圖3 改進的數(shù)據(jù)關(guān)聯(lián)和狀態(tài)估計流程圖

2.2 改進的DBSCAN算法

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

改進的聚類算法采用索引方法查詢鄰域點，利用KD 樹對量測數(shù)據(jù)進行劃分與構(gòu)建，在聚類之前生成每個數(shù)據(jù)點的鄰域?qū)ο蠹闅v每個數(shù)據(jù)點，并通過構(gòu)造好的KD 樹進行近鄰點搜索，包含核心點、邊界點以及噪聲點。

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

2.2.1 KD樹的創(chuàng)建

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

圖4 KD樹的構(gòu)建過程

2.2.2 查找鄰域節(jié)點集合

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

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

2.2.3 聚類中心的提取

在得到聚類結(jié)果后，同一幀內(nèi)屬于同一標(biāo)簽集合的點為該時刻同一目標(biāo)的量測數(shù)據(jù)信息，通過對聚類得到的不同目標(biāo)的點云數(shù)據(jù)，運用質(zhì)心算法，提取聚類中心點，代替原來點云數(shù)據(jù)，實現(xiàn)了對擴展目標(biāo)向點目標(biāo)的轉(zhuǎn)化。質(zhì)心算法公式為：

其中，xi為輸入的量測數(shù)據(jù)有限點集。

3 仿真實驗

3.1 仿真實驗環(huán)境配置

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

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

噪聲系數(shù)G和方差陣Q分別為：

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

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

其中，sigmaR=1。

3.2 實驗結(jié)果與分析

3.2.1 仿真實驗一

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

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

圖5 室內(nèi)實現(xiàn)三個擴展目標(biāo)跟蹤所需時間

圖6 EKF和UKF仿真精度對比

3.2.2 仿真實驗二

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

室內(nèi)擴展目標(biāo)跟蹤系統(tǒng)所消耗的時間由兩部分組成，即聚類算法消耗的時間和點目標(biāo)跟蹤消耗的時間。由表1 可以看出，兩部分耗時都與室內(nèi)擴展目標(biāo)個數(shù)呈正相關(guān)的趨勢，并且目標(biāo)的跟蹤誤差也隨目標(biāo)個數(shù)的增加逐漸增大。當(dāng)擴展目標(biāo)個數(shù)不斷增加時，改進的聚類算法依舊保持較低的時間消耗，能夠?qū)崿F(xiàn)30 個擴展目標(biāo)左右的實時跟蹤。

表1 改進的算法在不同擴展目標(biāo)個數(shù)下所需總時間

但繼續(xù)分析表1 可以發(fā)現(xiàn)，當(dāng)室內(nèi)擴展目標(biāo)增加到一定數(shù)量后，整體系統(tǒng)耗時主要由數(shù)據(jù)關(guān)聯(lián)算法產(chǎn)生。為了更加滿足室內(nèi)多擴展目標(biāo)跟蹤系統(tǒng)實時性的要求，就需要更加高效的數(shù)據(jù)關(guān)聯(lián)算法。

4 結(jié)論

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