基于目標(biāo)預(yù)測(cè)的擴(kuò)展目標(biāo)量測(cè)集劃分算法

王文慧，李 鵬，胡韻迪

1.江蘇理工學(xué)院 藝術(shù)設(shè)計(jì)學(xué)院，江蘇 常州213001

2.江蘇理工學(xué)院 計(jì)算機(jī)工程學(xué)院，江蘇 常州213001

1 引言

傳統(tǒng)目標(biāo)跟蹤認(rèn)為，一個(gè)目標(biāo)在傳感器上顯示為一個(gè)點(diǎn)。但隨著傳感器技術(shù)不斷進(jìn)步，一個(gè)目標(biāo)可能在激光雷達(dá)、船舶雷達(dá)等高精度傳感系統(tǒng)中顯示為多個(gè)點(diǎn)，稱這種目標(biāo)為擴(kuò)展目標(biāo)。擴(kuò)展目標(biāo)跟蹤研究在車輛跟蹤、航船監(jiān)視、機(jī)器人視覺(jué)、定位導(dǎo)航等領(lǐng)域有著巨大的應(yīng)用價(jià)值，因此成為近年來(lái)各學(xué)者研究的熱點(diǎn)。

針對(duì)擴(kuò)展目標(biāo)跟蹤問(wèn)題，Mahler教授提出擴(kuò)展目標(biāo)PHD跟蹤算法[1]，為隨機(jī)有限集（Random Finite Set，RFS）理論在擴(kuò)展目標(biāo)跟蹤領(lǐng)域的應(yīng)用提供了理論指導(dǎo)，然而該算法由于似然函數(shù)求解困難，并未給出具體的程序?qū)崿F(xiàn)方案。Granstr?m 等人對(duì)上述理論框架進(jìn)行程序?qū)崿F(xiàn)，分別提出了ET-GM-PHD[2]和GIW-PHD[3-5]兩種不同的算法，可以有效地實(shí)現(xiàn)不同情況下多擴(kuò)展目標(biāo)的精準(zhǔn)跟蹤，并且國(guó)內(nèi)外眾多學(xué)者對(duì)上述兩種算法進(jìn)行了一定的改進(jìn)[6-8]。ET-GM-PHD算法適合在傳感器兩側(cè)噪聲已知的情景下使用，具有運(yùn)算速度快的優(yōu)勢(shì)，然而在目標(biāo)鄰近時(shí)性能下降。造成該情況的原因是量測(cè)集劃分算法不能有效地劃分鄰近目標(biāo)的量測(cè)集。

針對(duì)ET-GM-PHD 算法的量測(cè)集劃分問(wèn)題，Granstr?m 等人提出了一種基于子劃分思想的劃分算法，即DP-Kmeans++劃分算法[9]，首先利用距離劃分DP算法進(jìn)行初步劃分，然后利用Kmeans++算法[10-11]將可能包含多個(gè)目標(biāo)集合進(jìn)行子劃分，提高了目標(biāo)鄰近時(shí)的劃分效果。然而，ET-GM-PHD 算法在目標(biāo)鄰近時(shí)的性能依然不足，因此眾多學(xué)者對(duì)擴(kuò)展目標(biāo)劃分問(wèn)題展開(kāi)研究[12-14]。但這些研究成果僅降低了運(yùn)算時(shí)間代價(jià)，其劃分精度依然有待進(jìn)一步提高。

針對(duì)擴(kuò)展目標(biāo)的量測(cè)集劃分的精度問(wèn)題，本文提出一種DP-Kmeans++的改進(jìn)算法，稱之為DP-TP-Kmeans++算法。在原算法運(yùn)用的DP和Kmeans++步驟之中，插入一步基于目標(biāo)預(yù)測(cè)（Targets'Prediction，TP）的量測(cè)集分割步驟，進(jìn)一步提高了鄰近目標(biāo)的劃分精度。仿真結(jié)果表明，提出算法的OSPA誤差距離明顯小于其他量測(cè)集劃分算法。

2 擴(kuò)展目標(biāo)高斯混合濾波概述

2.1 ET-GM-PHD算法原理

ET-GM-PHD跟蹤算法通過(guò)高斯混合的方法來(lái)擬合目標(biāo)的PHD，令目標(biāo)狀態(tài)為：

預(yù)測(cè)：先驗(yàn)?zāi)繕?biāo)的PHD表示為：

更新：后驗(yàn)?zāi)繕?biāo)的PHD通過(guò)Dk|k-1來(lái)更新，即：

其中，Lzk是偽似然函數(shù)，表示為：

其中，γ( )x 是量測(cè)數(shù)的期望，pD是檢測(cè)概率，wp是劃分權(quán)重，φzk是量測(cè)空間似然，λk是雜波數(shù)均值，ck是雜波空間似然。

2.2 DP-Kmeans++量測(cè)集劃分算法原理

量測(cè)集劃分是ET-GM-PHD 跟蹤算法中的重要步驟，將量測(cè)集Zk分割成有限數(shù)量個(gè)非空子集W ，即稱為一種劃分，記做p（為了易于理解，通常在不影響理解的情況下不對(duì)W 和p 添加標(biāo)號(hào)）。

DP-Kmeans++劃分算法的步驟如下：

步驟1 利用文獻(xiàn)[2]中的DP算法，用給定的n 個(gè)距離閾值得到n 種劃分結(jié)果。

步驟2 判定每種劃分中的非空子集W 由幾個(gè)目標(biāo)產(chǎn)生，判定公式如下：

步驟3 若某子集W 對(duì)應(yīng)的大于1，則用Kmeans++算法將W 劃分成個(gè)子類。

3 DP-TP-Kmeans++量測(cè)集劃分算法

DP-Kmeans++算法在目標(biāo)鄰近時(shí)精度不足，原因是DP 算法和Kmeans++算法都難以正確地分割鄰近目標(biāo)的量測(cè)集。因此，本文在兩種算法間插入一步基于TP的量測(cè)分割算法，提高了原算法的劃分精度。

3.1 問(wèn)題描述與核心思想

DP 算法僅利用量測(cè)間彼此距離來(lái)分割量測(cè)集，因此會(huì)將鄰近目標(biāo)的量測(cè)聚類為同一子集W 。Kmeans++算法同樣容易收斂到錯(cuò)誤的分割結(jié)果，造成劃分失敗。DP-Kmeans++算法的主要問(wèn)題有以下兩點(diǎn)：

（1）算法通過(guò)公式（5）、（6）來(lái)判定W 是否需要進(jìn)行子劃分，但由于目標(biāo)數(shù)量的隨機(jī)性，有時(shí)候兩個(gè)緊鄰目標(biāo)產(chǎn)生的量測(cè)數(shù)量?jī)H使N?=1，造成Kmeans++算法為被啟用，劃分失敗。

（2）Kmeans++算法對(duì)緊鄰目標(biāo)的劃分時(shí)，經(jīng)常產(chǎn)生如圖1 所示的錯(cuò)誤收斂現(xiàn)象。圖中左上角第一個(gè)子圖為真實(shí)量測(cè)結(jié)果，橢圓表示兩個(gè)目標(biāo)的輪廓；其他子圖為迭代過(guò)程，黑色圓圈表示類中心，可見(jiàn)劃分結(jié)果出現(xiàn)嚴(yán)重錯(cuò)誤。

針對(duì)DP-Kmeans++算法的問(wèn)題，提出算法保留了DP-Kmeans++算法的步驟。首先，利用DP 算法進(jìn)行初步劃分，區(qū)分量測(cè)集和雜波集。然后，執(zhí)行TP 步驟，對(duì)于DP 劃分結(jié)果的量測(cè)集，使用目標(biāo)預(yù)測(cè)的位置作為聚類中心，預(yù)測(cè)目標(biāo)的數(shù)量作為類的數(shù)量，利用量測(cè)與離類中心的距離來(lái)進(jìn)行一步的聚類。最后，對(duì)于TP 步驟的聚類結(jié)果，再利用公式（5）、（6）對(duì)量測(cè)數(shù)量進(jìn)行判定，對(duì)量測(cè)數(shù)量過(guò)多的量測(cè)子集依然使用Kmeans++算法進(jìn)行分割，進(jìn)一步保證了提出算法的精度。

3.2 DP-TP-Kmeans++的算法實(shí)現(xiàn)

令傳感器第k 次探測(cè)的量測(cè)集表示為Zk，則DPTP-Kmeans++算法可按照下述步驟實(shí)現(xiàn)：

步驟1 基于DP算法的初步劃分。

圖1 Kmeans++聚類結(jié)果

步驟2 基于TP的量測(cè)集分割。

令 ||?表示集合中元素的數(shù)量，則對(duì)于劃分p 的某量測(cè)子集W ，若 ||W =1 則認(rèn)為是雜波，若 ||W ＞1 則認(rèn)為是量測(cè)。令劃分p 中所有雜波組成集合Zclu，所有量測(cè)組成集合Zmea。令Jk|k-1表示k 時(shí)刻先驗(yàn)?zāi)繕?biāo)的數(shù)量，表示第j 個(gè)目標(biāo)的預(yù)測(cè)位置，則Zmea被分割為Jk|k-1個(gè)子集，第j 個(gè)子集表示為：

步驟3 基于Kmeans++的特殊量測(cè)集分割。

為了在預(yù)測(cè)目標(biāo)數(shù)不準(zhǔn)的情況下保證劃分精度，對(duì)于步驟2的結(jié)果中每個(gè)W ，依然需要利用公式（5）、（6）對(duì)量測(cè)數(shù)是否異常來(lái)進(jìn)行檢測(cè)。若N? 大于1，則用Kmeans++算法將對(duì)應(yīng)量測(cè)集子分割成N?個(gè)子類。

4 仿真實(shí)驗(yàn)

為驗(yàn)證提出算法的有效性，在兩組不同的場(chǎng)景中進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境為：仿真軟件：MATLAB 2012a，CPU：Intel?CoreTMi7-6700HQ。不同實(shí)驗(yàn)中目標(biāo)的軌跡如圖2所示。圖2（a）中目標(biāo)1和目標(biāo)2存在時(shí)間為1～100 s，目標(biāo)3 存在時(shí)間為21～80 s，目標(biāo)4 存在時(shí)間為41～60 s。圖2（b）中兩目標(biāo)的存在時(shí)間為1～100 s。

圖2 目標(biāo)軌跡

場(chǎng)景參數(shù)設(shè)定如下：

其中，Rk表示量測(cè)噪聲協(xié)方差矩陣，表示Qk過(guò)程噪聲協(xié)方差矩陣。S 表示傳感器探測(cè)面積。λkck表示每幀探測(cè)中單位面積的雜波率。場(chǎng)景中傳感器的幀間隔為T=1 s。目標(biāo)存活概率為PS=0.99。傳感器檢測(cè)概率為PD=0.99。

新生目標(biāo)的參數(shù)如下：

其中，m0為目標(biāo)初始狀態(tài)，x0和y0表示場(chǎng)景中真實(shí)目標(biāo)的新生坐標(biāo)。 P0表示目標(biāo)初始高斯協(xié)方差矩陣。初始目標(biāo)權(quán)重為w0=0.1。實(shí)驗(yàn)中的跟蹤結(jié)果誤差由OSPA 誤差距離[15]進(jìn)行量化。DP 算法的閾值集合為

為充分驗(yàn)證本文方法的有效性，以文獻(xiàn)[13]中SNN-AP方法作為對(duì)比實(shí)驗(yàn)，從精度和運(yùn)算代價(jià)兩個(gè)不同維度展示算法的性能。

4.1 多目標(biāo)交叉場(chǎng)景

本場(chǎng)景目標(biāo)軌跡如圖2（a）所示，共進(jìn)行了100次蒙特卡洛實(shí)驗(yàn)。

圖3（a）為100 次實(shí)驗(yàn)的平均OSPA 誤差距離結(jié)果。可以看出，ET-GM-PHD算法使用DP算法進(jìn)行量測(cè)集劃分時(shí)，在目標(biāo)鄰近時(shí)會(huì)造成OSPA 誤差增大，其原因?yàn)镈P 算法基于量測(cè)間的距離對(duì)量測(cè)集進(jìn)行分割，而多目標(biāo)鄰近時(shí)彼此量測(cè)集也鄰近，因此DP 算法失效導(dǎo)致跟蹤精度明顯下降。DP-Kmeans++作為DP算法的一種改進(jìn)算法，其在目標(biāo)鄰近時(shí)的劃分效果明顯提高，因此導(dǎo)致目標(biāo)緊鄰時(shí)的OSPA誤差雖然也明顯增加，但遠(yuǎn)小于DP算法。SNN-AP算法在目標(biāo)緊鄰時(shí)的誤差值介于DP與DP-Kmeans++之間，其原因是多個(gè)目標(biāo)同時(shí)緊鄰導(dǎo)致算法的初始化參數(shù)不夠準(zhǔn)確。提出的DP-TP-Kmeans++算法在目標(biāo)鄰近時(shí)的OSPA誤差略小于DP-Kmeans++，說(shuō)明提出算法加入的TP步驟有效地增加了鄰近目標(biāo)量測(cè)集的劃分精度，從而減小了整體跟蹤誤差。

圖3（b）為100 次實(shí)驗(yàn)的平均目標(biāo)數(shù)估計(jì)結(jié)果。可以看出，DP 和SNN-AP 算法在目標(biāo)鄰近時(shí)的目標(biāo)數(shù)估計(jì)結(jié)果明顯低于真實(shí)值，說(shuō)明其未能分割鄰近目標(biāo)的量測(cè)集，造成目標(biāo)數(shù)漏估計(jì)。DP-Kmeans++算法和提出的DP-TP-Kmeans++算法在目標(biāo)鄰近時(shí)的目標(biāo)數(shù)估計(jì)結(jié)果大致相同，且略高于真實(shí)值，說(shuō)明兩種算法都可以分割鄰近目標(biāo)的量測(cè)集。對(duì)比圖3（a）結(jié)果，說(shuō)明提出算法優(yōu)于DP-Kmeans++算法的原因不是勢(shì)估計(jì)的精度提高，是劃分結(jié)果的精度提高。

圖3 多目標(biāo)交叉場(chǎng)景100次實(shí)驗(yàn)平均結(jié)果

圖4 單次實(shí)驗(yàn)的劃分結(jié)果

圖4是單次跟蹤實(shí)驗(yàn)各劃分算法的結(jié)果圖。圖4（a）是提出算法劃分結(jié)果的宏觀結(jié)果，其中黃色點(diǎn)為提出算法在距離閾值為30時(shí)，通過(guò)DP算法初步劃分得到的雜波，可見(jiàn)利用距離閾值可有效分辨大部分由白噪聲產(chǎn)生的雜波。圖4（b）是目標(biāo)1、目標(biāo)2、目標(biāo)3緊鄰時(shí)，閾值取30時(shí)提出算法的劃分結(jié)果。圖中用不同符號(hào)標(biāo)出奇、偶數(shù)幀的目標(biāo)預(yù)測(cè)位置，目的是更清晰地表示出同幀目標(biāo)的位置。同幀不同的顏色、符號(hào)點(diǎn)分別代表不同的量測(cè)子集。圖中可見(jiàn)提出算法在目標(biāo)緊鄰時(shí)能較為正確地根據(jù)預(yù)測(cè)信息劃分出量測(cè)集。圖4（c）是DP-Kmeans++算法在距離閾值為30 時(shí)的劃分結(jié)果，可見(jiàn)多幀出現(xiàn)了目標(biāo)數(shù)的過(guò)估計(jì)、漏估計(jì)顯現(xiàn)，在貝葉斯迭代過(guò)程中這些錯(cuò)誤會(huì)向前傳遞，因此累積的劃分錯(cuò)誤是造成其目標(biāo)緊鄰時(shí)OSPA誤差值過(guò)大的主要原因。圖4（d）是SNN-AP劃分的結(jié)果，可見(jiàn)大致劃分結(jié)果與提出方法類似，僅個(gè)別幀出現(xiàn)了錯(cuò)誤，例如坐標(biāo)（80，10）附近出現(xiàn)了預(yù)測(cè)目標(biāo)的過(guò)估計(jì)情況（同幀的兩個(gè)三角形），其原因是上一時(shí)刻跟蹤系統(tǒng)的狀態(tài)估計(jì)結(jié)果不準(zhǔn)而導(dǎo)致，說(shuō)明SNN-AP算法劃分精度低于提出算法，導(dǎo)致目標(biāo)狀態(tài)估計(jì)精度（位置、速度、誤差矩陣等）隨貝葉斯過(guò)程累加降低，有時(shí)會(huì)出現(xiàn)目標(biāo)數(shù)錯(cuò)估的重大誤差，導(dǎo)致EM算法在圖3（a）中平均OSPA誤差略高于提出算法。

4.2 目標(biāo)長(zhǎng)時(shí)間鄰近場(chǎng)景

本場(chǎng)景目標(biāo)軌跡如圖2（b）所示，共進(jìn)行了100次蒙特卡洛實(shí)驗(yàn)。

圖5 目標(biāo)長(zhǎng)時(shí)間鄰近場(chǎng)景100次實(shí)驗(yàn)平均結(jié)果

圖5（a）為100次實(shí)驗(yàn)的平均OSPA誤差結(jié)果。可以看出，使用DP算法的OSPA誤差遠(yuǎn)高于其他劃分算法，說(shuō)明其他算法對(duì)比DP算法均能有效提高鄰近目標(biāo)量測(cè)集的劃分精度。SNN-AP算法的誤差值與DP-Kmeans++算法大體上相同，說(shuō)明在兩目標(biāo)緊鄰情況下兩者的精度基本相同。提出算法的誤差略低于SNN-AP 和DPKmeans++算法，說(shuō)明提出算法在目標(biāo)長(zhǎng)時(shí)間鄰近情況下依然能保證較高的劃分精度。

圖5（b）為100 次實(shí)驗(yàn)的平均目標(biāo)數(shù)估計(jì)結(jié)果。可以看出，DP算法導(dǎo)致目標(biāo)數(shù)估計(jì)結(jié)果低于真實(shí)值，說(shuō)明其會(huì)導(dǎo)致目標(biāo)數(shù)漏估計(jì)現(xiàn)象發(fā)生。DP-Kmeans++算法和提出算法的目標(biāo)數(shù)估計(jì)結(jié)果大致相同，且略高于真實(shí)值，說(shuō)明其會(huì)對(duì)鄰近目標(biāo)的量測(cè)集進(jìn)行分割，但有時(shí)會(huì)發(fā)生將兩個(gè)目標(biāo)的量測(cè)集分割成多個(gè)的現(xiàn)象。SNN-AP算法的值明顯高于真實(shí)值，說(shuō)明該場(chǎng)景下導(dǎo)致SNN-AP算法精度下降的主要原因是AP算法多度分割了緊鄰量測(cè)集。

圖6為100次實(shí)驗(yàn)的平均運(yùn)算代價(jià)結(jié)果。運(yùn)算代價(jià)數(shù)據(jù)的獲取方法為在100次的實(shí)驗(yàn)中，MATLAB程序中記錄劃分算法總執(zhí)行秒數(shù)的平均值來(lái)獲得。可見(jiàn)，SNN-AP算法的運(yùn)算代價(jià)明顯小于其他算法；DP算法的時(shí)間代價(jià)略小于DP-Kmeans++算法；提出的DP-TPKmeans++算法的時(shí)間代價(jià)明顯高于其他三種算法。結(jié)合圖5 結(jié)果，說(shuō)明在該場(chǎng)景下SNN-AP 算法取得與DPKmeans++相似精度的情況下，可以極大地減小系統(tǒng)的運(yùn)算代價(jià)，適合于對(duì)運(yùn)算速度要求較高的實(shí)時(shí)跟蹤系統(tǒng)。而提出算法在提高了整體精度的同時(shí)，也增大了其運(yùn)算代價(jià)，因此提出的DP-TP-Kmeans++算法適合于精度要求較高而對(duì)運(yùn)算代價(jià)要求低的跟蹤系統(tǒng)。

圖6 時(shí)間代價(jià)結(jié)果

5 結(jié)論

針對(duì)擴(kuò)展目標(biāo)緊鄰時(shí)量測(cè)集劃分精度下降問(wèn)題，提出了DP-TP-Kmeans++量測(cè)集劃分算法。創(chuàng)新點(diǎn)如下：

（1）提出利用目標(biāo)預(yù)測(cè)信息來(lái)劃分鄰近目標(biāo)的量測(cè)集的方法，提高了劃分精度。

（2）結(jié)合了DP-Kmeans++算法的步驟，提出DPTP-Kmeans++算法，并應(yīng)用于ET-GM-PHD算法。

實(shí)驗(yàn)結(jié)果表明，提出的DP-TP-Kmeans++算法的劃分精度高于其他算法，但時(shí)間代價(jià)也高于其他算法。下一步的工作可以圍繞降低提出算法的時(shí)間代價(jià)展開(kāi)，以增加提出算法的總體性能。