多目標跟蹤下點跡凝聚的實時優(yōu)化算法

吳春林，曹運合，王 蒙

(1.海軍航空大學青島校區(qū)， 山東 青島 266041； 2.西安電子科技大學， 西安 710071；3.北京機電工程研究所， 北京 100074)

1 引言

點跡凝聚作為雷達信號處理過程中重要的一環(huán)，幫助雷達在大量雜波干擾下準確的獲取目標的距離、速度、方位角等信息，為后續(xù)的目標跟蹤等算法提供有力的支撐。

在脈沖多普勒體制的雷達系統(tǒng)中，為了提高采樣信號的質(zhì)量，一般雷達系統(tǒng)的采樣頻率會大于奈奎斯特采樣頻率。這樣會導致對同一個目標點有多個檢測點，恒虛警處理后，還是會留下多余的點跡，所以需要使用點跡凝聚算法對其進行處理，保留最能反應目標參數(shù)的點，而篩除掉其他虛假的目標點[1-3]。

在需要凝聚的點數(shù)較少的情況下，常規(guī)的做法可以滿足實時性的需求。但針對現(xiàn)在的多目標，群目標跟蹤，由于目標個數(shù)的增加，恒虛警處理之后會產(chǎn)生大量的待凝聚點跡。當需要凝聚的點跡數(shù)量劇增時，常規(guī)的實現(xiàn)方案[4]就不能滿足實時性的需求了。為了能提升大數(shù)據(jù)量下點跡凝聚算法的實時性，有很多針對于特定平臺下的實現(xiàn)優(yōu)化[5-9]，點跡凝聚算法的實現(xiàn)還可以通過優(yōu)化數(shù)據(jù)結(jié)構(gòu)的使用和充分發(fā)掘并行性進行優(yōu)化。本文中在常規(guī)的點跡凝聚算法的實現(xiàn)方案[10-15]基礎(chǔ)上，通過預排序、HashMap優(yōu)化和多線程優(yōu)化來降低算法的執(zhí)行時間。在待凝聚點數(shù)較大時，最優(yōu)方案相對于常規(guī)的實現(xiàn)方案在點跡數(shù)量為有著顯著的加速效果。

2 常規(guī)點跡凝聚算法實現(xiàn)方案

點跡凝聚算法在工程上的常規(guī)實現(xiàn)方案是以恒虛警處理后目標回波的幅度值大小作為判斷依據(jù)，根據(jù)點跡在距離-多普雷矩陣中的位置確定凝聚處理的窗大小，進行凝聚處理。

假設(shè)有N個待凝聚的點跡，最終凝聚出來M個有效目標，算法主要的時間消耗在了2個步驟上：

1) 從剩余目標中找幅值最大點；

2) 遍歷所有剩余點確定是否在凝聚窗內(nèi)。

這2個操作都需要進行M次循環(huán)，每次循環(huán)需要操作的點跡個數(shù)為當前輪次的剩余點跡個數(shù)，設(shè)每次循環(huán)排除的點跡個數(shù)分別為n1，n2，n3，…，nM，操作每個點跡的時間為t，那么總的時間消耗為

Ttotal=(2N+2(N-n1)+2(N-n2-n1)+…+

2(N-nm-…-n2-n1))*t=

(2NM-[n1+(n2+n1)+…+

(nm+…+n2+n1)])*t

NMt

因此算法的時間復雜度為O(NM)。算法的優(yōu)化方向主要在優(yōu)化那2個耗時步驟上。

執(zhí)行流程如圖1所示。

圖1 常規(guī)方法實現(xiàn)點跡凝聚程序流程框圖Fig.1 Flow chart of conventional plots centroid method

算法實現(xiàn)偽代碼如下：

Algorithm 1 點跡凝聚算法的常規(guī)實現(xiàn)

Input： CFARRes

Output： CentroidRes

1 leftCFARRes=CFARRes;

2whileleftCFARRes is not emptydo

3 maxAmpItem=leftCFARRes[0];

4foritem in leftCFARRes do

5Ifitem.amplitude > maxAmpItem.amplitude then

6 maxAmpItem=item;

7endif

8endfor

9foritem in leftCFARRes do

10ifitem in maxAmpItem’s centroid window then

11 delete item;

12endif

13endfor

14 insert maxAmpItem to CentroidRes;

15endwhile

3 使用預排序優(yōu)化算法的實現(xiàn)

對基本實現(xiàn)方案進行編程實現(xiàn)，對程序分塊計時分析由表1可知，算法執(zhí)行時間近半耗費在從剩余點跡中獲取幅值最大點的操作。可以通過對點跡根據(jù)幅值信息進行預排序進行優(yōu)化。工程上常用的排序算法是快速排序算法，因此我們選擇快速排序算法對算法進行優(yōu)化。

表1 常規(guī)實現(xiàn)方案中找幅值最大值時間消耗占比

執(zhí)行流程如圖2所示。

圖2 使用預排序優(yōu)化的程序流程框圖Fig.2 Flow chart of using pre-sort optimization

算法實現(xiàn)偽代碼如下：

Algorithm 2 使用預排序優(yōu)化點跡凝聚算法的實現(xiàn)

Input： CFARRes

Output： CentroidRes

1 sort CFARRes with quick sort algorithm by amplitude;

2i=0;

3whilei

4ifCFARRes[i].visited == 0 then

5 Insert CFARRes[i] to CentroidRes;

6j=i+1;

7whilej

8ifCFARRes[j] in

9 CFARRes[i]’s centroid windowthen

10 CFARRes[j].visited=1;

11endif

12j++;

13endwhile

14endif;

15i++;

16endwhile

相對于常規(guī)方案的點跡凝聚算法，本方案的優(yōu)化點在于優(yōu)化了尋找剩余點跡中幅值最大點這一操作，凝聚窗內(nèi)點跡的方法不變。對N個點跡，如果經(jīng)過算法處理最終凝聚成M個目標，其快速排序的時間復雜度為O(NlogN)，而常規(guī)方案中，尋找剩余點跡中幅值最大點的操作的時間復雜度為O(MN)。這里，還可以采用基數(shù)排序的方法對待凝聚點跡進行排序，基數(shù)排序的理論算法復雜度更優(yōu)?；谏鲜隹梢苑治龀觯斝枰鄣狞c數(shù)較多時，應該采用預排序的方法對執(zhí)行時間進行優(yōu)化。

4 HashMap優(yōu)化算法實現(xiàn)

在預排序的前提下，還可以進一步優(yōu)化凝聚窗內(nèi)點跡的操作。對于每一個目標點，我們在其距離維和多普勒維開一個窗口，判斷剩余點跡是否在這個窗內(nèi)，需要遍歷所有的剩余點跡，我們可以預先建立點跡在距離-多普勒矩陣中的位置到其在排序后的點跡數(shù)據(jù)中的位置的映射，便可以在常數(shù)時間內(nèi)鎖定窗內(nèi)的點是否在點跡數(shù)組中。使用HashMap的數(shù)據(jù)結(jié)構(gòu)可以實現(xiàn)這種映射關(guān)系。

使用HashMap這一數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵點在于鍵值key的選取、桶的個數(shù)的確定和沖突解決方案的選擇。假定點跡在距離-多普勒矩陣中的坐標為(x，y)，經(jīng)過分析和測試，最終選擇(x<<16)+y作為鍵值，使用大于點跡個數(shù)的最小素數(shù)作為桶的個數(shù)，使用拉鏈法來解決哈希沖突的方案來構(gòu)造HashMap這一數(shù)據(jù)結(jié)構(gòu)。該方案能夠較為均勻的將點跡分布在各個桶里，保證能在常數(shù)時間內(nèi)確定映射關(guān)系。

相對于常規(guī)的實現(xiàn)方案，使用HashMap進行優(yōu)化的點集中在降低凝聚窗內(nèi)點跡的復雜度上。對于N個點跡，凝聚成M個目標來說，之前的方案中這一操作的時間復雜度為O(MN)，使用HashMap優(yōu)化后，時間復雜度降低為O(M)，這種優(yōu)化對性能的提升是巨大的。

算法的程序流程如圖3所示。

圖3 使用預排序+HashMap優(yōu)化的程序流程框圖Fig.3 Flow chart optimized using pre-sorting+HashMap

算法實現(xiàn)偽代碼如下：

Algorithm 3 使用預排序+HashMap優(yōu)化點跡凝聚算法的實現(xiàn)

Input： CFARRes

Output： CentroidRes

1 sort CFARRes with quick sort algorithm by amplitude;

2 initial hashMap by build map relationship

3 from target position to its index in CFARRes;

4i=0;

5whilei

6ifCFARRes[i].visited == 0then

7 insert CFARRes[i] to CentroidRes;

8foritem in CFARRes[i]’s centroid windowdo

9ifitem’s position in hashMapthen

10 CFARRes[hashMap(Item’s position)].

visited=1;

11endif

12endfor

13endif

14i++;

15endwhile

5 多線程優(yōu)化算法的實現(xiàn)

隨著摩爾定律的逐漸失效，現(xiàn)代處理器的處理主頻已經(jīng)接近其物理上限了，不能夠像之前一樣，通過提升處理器主頻來提升處理器的性能。多核便成為了現(xiàn)代處理器必然的發(fā)展方向。核心數(shù)32個的商用桌面級CPU已經(jīng)很常見，TI的c66x系列DSP的最高核心數(shù)也達到了8個。為了使算法能夠利用多核處理器的優(yōu)勢，需要充分的發(fā)掘算法執(zhí)行中的并行性，使用多線程的優(yōu)化方案是建立在預排序和HashMap優(yōu)化的基礎(chǔ)上。本文給出2種多線程的優(yōu)化方法。這2個方案都是建立在需要凝聚的點跡在距離-多普勒矩陣中的分布是呈現(xiàn)多點聚簇的樣式，對于在大范圍內(nèi)連續(xù)的點跡是不適用的。

方案1：假設(shè)處理器有N個核心，則開辟N個線程。N個線程根據(jù)點跡的距離單元來劃分各自負責的區(qū)域，各線程之間的處理沒有重疊。各線程進行第一輪點跡凝聚之后，再開辟N-1個線程，每個線程負責的區(qū)域為第一輪線程間的鄰接部分。距離維的長度為設(shè)置的距離維的窗的大小。

舉例說明，距離-多普勒矩陣的大小為24*8，距離維窗大小為4，線程數(shù)為4。在第一輪次的處理中，線程1負責的距離單元為[1，6]，線程2負責的距離單元為[7，12]，線程3負責的距離單元為[13，18]，線程4負責的距離單元為[19，24]。將第一輪此凝聚出的點，選擇出距離單元在[5，8]∪[11，14]∪[17，20]的點跡，繼續(xù)進行第二輪次的凝聚，第二輪次的線程數(shù)為3，線程1負責的距離單元為[5，8]，線程2負責的距離單元為[11，14]，線程3負責的距離單元為[17，20]。第二輪凝聚結(jié)束，即得到了最終的凝聚結(jié)果。示意圖如圖4。

圖4 多線程方案1示意圖Fig.4 Diagram of multi-threading scheme 1

方案2：假設(shè)處理器有N個核心，則開辟N個線程。N個線程根據(jù)點跡的距離單元來劃分各自負責的區(qū)域，各線程之間的處理有一定的重疊。重疊區(qū)域的大小大于等于設(shè)定的距離維窗大小，對每個線程凝聚出的點跡進行篩選，每個線程只負責輸出重疊區(qū)域中靠近自己處理的非重疊部分的半邊。

在點跡凝聚的處理中，線程1負責的距離單元為[1，8] 的點跡，線程2負責的距離單元為[5，14] 的點跡，線程3負責的距離單元為[11，20] 的點跡，線程4負責的距離單元為[17，24] 的點跡。在點跡的輸出過程中，線程1負責輸出距離單元為[1，6] 的點跡，線程2負責輸出距離單元為[7，12] 的點跡，線程3負責輸出距離單元為[13，18] 的點跡，線程4負責輸出距離單元為[19，24] 的點跡。示意圖如圖5。

圖5 多線程方案2示意圖Fig.5 Diagram of multi-threading scheme 2

方案1中，優(yōu)點在于每一輪次各線程負責的距離單元數(shù)是均勻的，且相對于方案二較少，但會有第二輪次的處理，第二輪次處理的點數(shù)較少，但線程調(diào)度的開銷不小。方案2，只有一個輪次的處理，但每個線程負責的距離單元數(shù)要大于方案1，且第一個和最后一個線程的負載相對于其他線程不同，優(yōu)點在于沒有第二輪次的處理。

上述的2個多線程方案中目標在距離維呈現(xiàn)均勻分布時才能取得良好的加速效果。由于實際情況中，目標的分布狀況是未知的。為了提高多線程方案的適用性，需要在進行多線程處理前，使用任務預分配方法合理劃分每個線程的處理區(qū)間。方法的執(zhí)行步驟和復雜度分析如下所述。

第一步需要維護一個長度等于距離單元個數(shù)的計數(shù)數(shù)組，該數(shù)組初始化為零，然后對所有的目標點進行一次遍歷，在遍歷過程中，記錄對應距離單元的目標數(shù)。第二步從起始位置遍歷計數(shù)數(shù)組，對計數(shù)數(shù)組中每個點(對應著不同的距離單元)，累加統(tǒng)計從起始位置到該距離單元的目標數(shù)。第三步根據(jù)目標的總個數(shù)除以劃分的線程個數(shù)可確定每個線程要處理的目標點個數(shù)，再從第二步的計數(shù)數(shù)組中找到每個線程的合理處理區(qū)間，該劃分可盡最大可能平均每個線程處理的目標點個數(shù)，從而使整體獲得良好的平均加速效果。

對于N個目標點，第一步的時間復雜度為O(N)，第二步和第三步實現(xiàn)時可合并處理，對于L個距離單元，其時間復雜度為O(L)。任務預分配方法的整體時間復雜度是線性的，不改變算法的整體時間復雜度。

6 各案執(zhí)行情況

為了對比各執(zhí)行方案的執(zhí)行效率，編程實現(xiàn)所有的方案并在同一環(huán)境下進行性能測試。實驗環(huán)境如表2所示，點跡凝聚算法的參數(shù)如表3所示。

表2 實驗環(huán)境

表3 算法參數(shù)

為了保證測試的公平性，在測試時對以下幾點做出保證：確保每種方案的代碼經(jīng)過同等級的優(yōu)化，不刻意從代碼實現(xiàn)層面制造性能差異；對于多線程代碼，為降低線程建立之類的系統(tǒng)調(diào)用對程序性能的影響，預先執(zhí)行一遍多線程代碼，在再次重復執(zhí)行時對程序進行計時；性能測試結(jié)果采用多次測試取平均值的方案。最終的測試結(jié)果如表4所示。

表4 各方案執(zhí)行性能

7 結(jié)論

1) 在需要處理的待凝聚點數(shù)較少的情況下，常規(guī)的實現(xiàn)方案的性能和優(yōu)化的方案差別很小，由于優(yōu)化帶來的額外的開銷，常規(guī)的方案甚至略有優(yōu)勢。

2) 隨著待凝聚點數(shù)的增加，常規(guī)方案的執(zhí)行時間大幅增加，使用預排序+HashMap優(yōu)化的方案能夠大幅降低算法的執(zhí)行時間，具有很大的優(yōu)勢。

3) 多線程代碼相對于單線程代碼，在待凝聚點數(shù)較少時，由于線程調(diào)度之類的開銷的存在，使得執(zhí)行時間比單線程還長。但隨著數(shù)據(jù)規(guī)模的增加，多線程方案相對于單線程的執(zhí)行時間比近似于1：線程數(shù)，有著明顯的加速效果。

4) 多線程的優(yōu)化方案相對于單線程的方案，在數(shù)據(jù)規(guī)模較大時，加速比接近線程數(shù)目，可充分利用現(xiàn)代處理器的多核特性。優(yōu)化措施和多線程處理，能夠使得點跡凝聚算法在大數(shù)據(jù)量下仍能滿足雷達信號處理實時性的需求，對今后的工程實現(xiàn)有著巨大的意義。