一種基于編隊中心的目標跟蹤算法

郭榮華，李曉，李耀煒，周穎

（1.中國洛陽電子裝備試驗中心，洛陽 471099；2.中國光電技術發展中心，洛陽 471099）

一種基于編隊中心的目標跟蹤算法

郭榮華1，李曉2，李耀煒1，周穎1

（1.中國洛陽電子裝備試驗中心，洛陽 471099；2.中國光電技術發展中心，洛陽 471099）

摘 要：提出了一種將多目標作為一個編隊進行整體跟蹤的方法，包括編隊生成、編隊分離、編隊合批和編隊跟蹤維持，解決了多目標的整體跟蹤問題。結合交互式多模型粒子濾波算法（IMM-UPF），在實踐中，有效地減輕了計算負擔，節約了系統資源，具有實用性。

關鍵詞：編隊；目標跟蹤；編隊中心；IMM-UPF

*項目簡介：自然科學基金（61303061）。

本文引用格式：郭榮華，李曉，李耀煒，等.一種基于編隊中心的目標跟蹤算法[J].新型工業化，2015，5(4)：40-47

1　引言

當多個目標以編隊方式進行機動時，利用編隊進行跟蹤控制可以減少系統代價，增加系統的魯棒性和效率，具有較強的重構能力和結構靈活性。編隊控制有著廣泛的應用，比如，危險環境中的安全巡邏、搜救，軍事任務中為完成區域覆蓋和偵察的任務編隊，多顆衛星協同有助于節約能源和擴展其感知能力[1-2]。對于地面編隊目標（包括軍事裝備、民用車輛等）跟蹤，由于地面目標距離相對較近、運動的不確定性及回波環境的復雜性，相對于空中目標跟蹤，其問題尤為突出。Bar-Shalom等[3-4]提出了將一個“聚”作為一個群對待，做了大量的研究工作。Taenzer[5]在“質心”跟蹤的基礎上，提出了編隊跟蹤起始、維持和分離的一些方法。近年來，粒子濾波由于其濾波精度高的優點，以及與交互式多模型的結合使用，為編隊目標跟蹤提供了一種可行的解決途徑[6-8]。

針對地面編隊目標機動性強、干擾大的特點，給出了編隊生成、編隊分離、編隊合批以及編隊跟蹤維持的邏輯處理方法，并與交互式多模型粒子濾波算法（IMM-UPF）結合，提出了一種基于編隊幾何中心的目標跟蹤算法，并在工程中進行了實踐。

2　編隊目標跟蹤邏輯處理方法

2.1編隊定義

判定能否將多目標作為一個編隊進行考慮，有如下兩種規則：

規則1：如果在連續時序內，多個目標距離相近，在任一時刻具有相同的速率和運動方向，也即它們的空間結構穩定，就把這幾個目標稱為一個編隊。

規則2：如果在連續時序內，多個目標“聚”在一塊，與其它目標距離相距較遠，就把這樣的“聚”稱為一個編隊。

規則1的條件約束較強，規則2的定義比較寬泛。編隊跟蹤算法中采用規則1的定義。

2.2編隊維持

編隊目標跟蹤維持可以選擇編隊最小外接矩形、最小外接圓或最小閉包的幾何中心，且采用幾何中心跟蹤法對編隊進行跟蹤維持。在編隊合批后，對編隊幾何中心進行修正操作。因為當新目標加入后，該編隊目標的關聯區域就會產生變化。如果繼續使用原有的幾何中心，就會出現對新編隊目標跟蹤不準確的問題。因此，編隊進行合批后，必須對原有的編隊幾何中心進行重新修正。對于編隊目標最小外接矩形，長與寬始終分別與笛卡爾坐標系的X軸與Y軸平行。

2.2.1目標預測的最小外接矩形的確定

對于三個以上的目標，無論多個目標是處于一條直線上或不在一條直線上，處理方法是一樣的。這里考慮一般情況，假設有N個目標組成一個編隊，如圖1所示。N個目標的二維笛卡爾坐標位置向量分別記為：T1(x1, y1), T2(x2, y2), , Ti(xi, yi), , TN(xN, yN).

設目標預測最小外接矩形的四個頂點分別為A(xa, ya)、B(xb, yb)、C(xc, yc)和D(xd, yd)，矩形幾何中心為O(xO, yO)，則有

2.2.2確定目標預測最小外接矩形的中心

矩形幾何中心點O的位置向量可以根據矩形四個頂點的向量確定

2.2.3建立矩形中心與編隊中各目標的對應關系

也即Ti→O: [Δxi, Δyi]。因此，整個編隊中的所有目標與中心O的對應關系可以表示為

2.2.4由坐標差對求下一時刻的各目標預測位置向量

注意，記錄坐標差對[Δxi, Δyi]比記錄OTi之間的距離和角度更方便，計算更直接、快速。

2.2.5目標量測處理

對于編隊目標的量測，與編隊目標預測一樣，首先確定量測的最小外接矩形及其中心，然后建立各量測與其矩形中心的對應關系。其演化過程如圖3所示。

圖1.目標預測與量測最小外接矩形及其幾何中心的確定Fig.1 Determine the minimum enclosing rectangle of target predicted and measurement positions, and their geometric centre

圖2　編隊預測中心演化Fig.2 The evolution of the prediction centre of a formation

圖3　編隊量測幾何中心演化Fig.3 The evolution of the measurement centre of a formation

3　編隊分離和合批

編隊的分離和合批都屬于編隊邏輯處理的范疇，為了方便描述編隊分離和合批算法原理，一些符號定義如表1和圖4所示。

表1　一些符號定義Table 1.Definitions of some symbols

3.1編隊的分離算法

(1) 如果Fj(di)＞Fj(r)且Tj(di)＜Tj(r)，將目標i從編隊中分離出去，成為新目標，參與合批。

(2) 如果編隊中的目標外推跟蹤次數超出設定值（即無關計數器NoRelationCounter(i) ≥ m）或者Tj(di)＞Tj(r)，將該目標從編隊中分離并且丟棄。

圖4　編隊分離和合批符號定義示意Fig.4 The Representations of symbols on formation separating and combining

3.2編隊的合批算法

(1) 初始化，每個編隊只有1個目標或者跟蹤指定的編隊目標。

(2) 如果發現新目標，計算新目標與所有跟蹤編隊中心最近的距離min{Fj*(dl)}。若min{Fj*(dl)}＜Fj(r)，則將該目標添加到距離最近的編隊；否則，把該目標作為1個新的編隊，新目標的產生由滑動窗口方法確定或者由編隊的分離過程產生。

4　FC-IMM-UPF算法

由于編隊的空間結構相對穩定，這里采用基于群幾何中心的IMM-UPF算法（FC-IMM-UPF）。算法原理描述如下（從k-1時刻到k時刻的一次循環）。

1.計算編隊的中心、所有目標與編隊中心的偏移量和量測的中心。

xi,k表示編隊中k時刻目標i的狀態估計向量，編隊幾何中心的狀態估計與狀態預測向量分別用xk和xk+1|k表示；zi,k表示編隊中k時刻目標i的量測向量，編隊幾何中心的量測與量測預測向量分別用zk和zk+1|k表示；Δxi,k是k時刻編隊中目標i相對于群幾何中心的偏移量。

(1) 根據式(1)和式(2)，k-1時刻的編隊目標中心狀態估計為xk-1，計算編隊目標中心的狀態一步預測xk|k-1。

(2) 根據式(3)和式(4)，計算編隊中k-1時刻目標i相對于群幾何中心的偏移量Δxi,k -1。

(3) 根據量測zi,k，計算k時刻編隊目標量測中心向量zk。

2.更新k時刻編隊的中心、所有目標的狀態更新及一步預測。

5　仿真與分析

將FC-IMM-UPF算法用于編隊狀態的跟蹤維持、新目標增加（編隊合批）和目標丟失（編隊分離）過程中，利用編隊跟蹤方式和多目標跟蹤方式，分別對一個跟蹤實例進行處理，分析編隊中目標個數對不同跟蹤方式的影響。目標運動模型使用CV（常速模型1）和CT（轉彎模型2）模型進行模擬。采用建議的量測模型獲得量測數據，采樣時間T=1s。

模型1（CV）：

模型2（CT）：

量測模型：

5.1測試用例

1.想定。編隊中的目標從（0m, 0m）處開始，以20m/s的速率作蛇形機動，整個機動時間持續125s，采樣間隔為T=1s。編隊起始時，由四個目標成菱形組成，具有相同的速度和運動方向。編隊目標真實運動航跡和局部放大圖如圖5(a)和(b)所示。當編隊目標機動至20s時，新目標（目標5）出現，并加入到編隊中，如圖5(c)所示。當編隊目標機動至100s時，目標5從編隊中消失，如圖5 (d)所示。

圖5　編隊目標運動真實航跡Fig.5 Formation target movement real track

2.仿真條件。模式變遷矩陣為

對于FC-IMM-UPF算法，粒子數N=200，每個模型粒子數設為100。

5.2性能分析

對于此想定，在不同的噪聲條件下，對FC-IMM-UPF算法進行了100次蒙特卡羅仿真。

1.估計精度或RMSE性能。利用FC-IMM-UPF算法對編隊目標進行跟蹤，得到編隊中心估計和局部放大圖如圖6(a)和(b)所示。可見，該算法能夠對編隊目標進行有效跟蹤，當新目標加入和目標離開編隊時，算法也可以對編隊中心迅速進行跟蹤處理。在弧頂處，狀態估計略有偏差，不過沒有發生濾波發散現象，編隊目標跟蹤比較正常。

2.計算時間復雜度。為了分析地面機動目標跟蹤中編隊目標個數與所采取的跟蹤方式（編隊目標跟蹤和多目標跟蹤）在時間復雜度方面的影響，將想定中的編隊目標個數設定為10個、20個、30個，分別計算目標跟蹤處理的單步計算時間，如表2所示。編隊跟蹤采用編隊目標跟蹤處理方法和IMM-UPF算法，多目標跟蹤算法采用IMM-UPF算法和NNDA數據關聯算法[9]。從表2可以看出，隨著編隊中目標個數的增加，以編隊方式進行跟蹤的效率越高，相對多目標跟蹤方式，優勢越明顯。

圖6　編隊中心狀態估計Fig.6 The estimation of formation centre

表2　編隊目標個數與跟蹤方式的計算時間對比Table 2.A comparison of computing time for the number of targets in a formation and tracking mode

6　結論

采用群幾何中心跟蹤算法在工程實踐中，能夠實現對多目標的整體跟蹤，當新目標加入和目標丟失時，可以正常跟蹤處理，解決了多目標的整體跟蹤問題，從而減少了計算量，節約了系統資源，因此具有實用性。

參考文獻:

[1]Do KD.Formation tracking control of unicycle-type mobile robots[C].2007 IEEE International Conference on Robotics and Automation, 2005: 2391-2396.

[2]Scharf DP, Hadaegh FY, Ploen SR.A Survey of Spacecraft Formation Flying Guidance and Control (Part 11): Control[C].Proceedings of the 2004 American Control Conference, 2004, 4: 2976-2985.

[3]Bar-Shalom Y, Li X R.Multi target-multi sensor tracking: principles and techniques[M].New Orleans: University of New Orleans, 1995.

[4]Bar-Shalom Y, Li X R, Kirubarajan T.Estimation with Applications to Tracking and Navigation: Theory, Algorithm and Software[M].New York: Wiley, 2001.

[5]Taenzer E.Tracking multiple targets simultaneously with a phased array radar[J].IEEE Transactions on Aerospace and Electronic Systems.1980, 16(5): 604-614.

[6]Ronghua Guo, Zheng Qin.An unscented particle filter for ground maneuvering target tracking[J].Journal of Zhejiang University SCIENCE-A, 2007, 8(10): 1588-1595.

[7]Kwangjae S, Hwangnam K.Bayesian navigation system with particle filtering and dead reckoning in urban canyon environments[C].The 9th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON).2012: 73-75.

[8]Guo R H, Qin Z, Li G B, Li X N.An IMM-AUPF algorithm with a re-sampling controller[J].Journal of Tsinghua University, 2010, 50(4): 539-542.

[9]Bar-Shalom Y.Tracking methods in a multitarget environment[J].IEEE Transactions on Automatic Control, 1978, 23: 618-626.

A Center-based Formation Target Tracking Algorithm

GUO Ronghua1, LI Xiao2, LI Yaowei1, ZHOU Ying1
(1.electronic equipment test center satellite navigation laboratory, Luoyang 471099, China; 2.China Opto-Electro Technology Center, Luoyang 471099, China)

Abstract:Based on the formation center (FC), a logical method to formation target tracking, which include formation initiation, formation separation, formation merging and formation updating, is proposed according to the kinetics of formation moving.The method addresses the tracking problem of taking multi-targets tracking as a whole.Integrating with the IMM-UPF, a FC-based interacting multiple model unscented particle filter (FC-IMM-UPF) is presented.Simulation shows that the FC-IMM-UPF algorithm improves the estimating accuracy and reduces the computational complexity.

Keywords：formation; target tracking; formation center (FC); IMM-UPF

DOI：10.3969/j.issn.2095-6649.2015.04.06

作者簡介：郭榮華(1972-)，男，湖北，副研究員，博士，主要研究方向：信息安全。

Citation: GUO Ronghua, Li Xiao, Li Yaowei, et al..A Center-based Formation Target Tracking Algorithm [J].The Journal of New Industrialization, 2015, 5(4): 40?47.