基于坐標映射距離差分的快速群分割算法

王　聰, 王海鵬, 何　友

(1. 海軍航空工程學院信息融合技術研究所, 山東 煙臺 264001;2.飛行器測控與通信教育部重點實驗室, 重慶 400044)

?

基于坐標映射距離差分的快速群分割算法

王聰1,2, 王海鵬1, 何友1

(1. 海軍航空工程學院信息融合技術研究所, 山東 煙臺 264001;2.飛行器測控與通信教育部重點實驗室, 重慶 400044)

群分割技術作為群目標跟蹤技術的首要環節,其處理結果直接影響后續整個數據處理過程的效果。在深入研究目前已有的群分割技術的基礎上,提出了一種基于坐標映射距離差分的快速群分割算法。首先將量測集的二維信息分解為兩組坐標映射距離的一維信息,進而分別進行排序和分群處理,從而減小了算法的時間復雜度,最后將分別獲得的兩組預備群進行取交關聯,得到最終的分割群。通過與3種傳統算法在時間復雜度上的理論分析與比較,該方法在大視場回波稀疏條件下具有顯著的效率優勢。經過多場景的仿真分析表明,該算法的處理效能顯著高于傳統算法,且對復雜動態場景具有較好的魯棒性。

群分割技術; 群目標跟蹤; 坐標映射; 距離差分; 時間復雜度

0　引　言

隨著飛行器技術水平的不斷提高,低空飛行的飛機編隊、多發齊射的低空飛行導彈成為現代戰爭越來越普遍使用的常規化戰術。在雜波環境下,對該類運動方式相似、空間距離相近的目標進行精確跟蹤成為當前目標跟蹤領域的一個新的熱門問題——群目標跟蹤技術[1-4]。該技術可主要分為3部分:群的起始、群航跡的維持、群的撤銷。其中,如何準確的起始一個群,是群目標跟蹤首先需要解決的問題。

在群目標的起始技術中,又分為群的分割與互聯兩個技術環節。其中群分割技術作為后續算法的數據基礎,是整個航跡跟蹤過程需要最先解決的問題。本文主要針對群分割技術進行了研究。

在現有的研究中,文獻[5-6]提出了一種最直觀的基于回波之間距離的分群方法。該方法從群定義的角度出發,實現根據量測點距離進行劃分,并且遍歷所有量測點間的距離,因此該方法雖然處理結果比較穩定可靠,但計算復雜度太大,不適合工程應用。文獻[7-9]對上述距離分割法進行了一定的改進,提出了基于循環閾值的分割方法。該方法根據已劃分量測進行外推,一定程度上減少了不必要的距離計算,因此可取得與基于目標距離方法相同的分割效果,并在一定程度上降低了計算復雜度。文獻[10]基于圖論的思想,將整個探測區域進行分割以能夠一次性確定多個群。該方法雖然直觀方便,但對于不同雜波條件以及選取的單位小區域面積不恰當時,會造成額外的計算量以及出現多個虛假群。

本文在借鑒上述算法的基礎上,并結合工程實際情況,提出了基于坐標映射距離差分的群分割方法。該方法可對觀測點進行有效的群分割,并顯著降低了計算復雜度,特別在雷達視場較大且回波稀疏等常見戰場情況下效果明顯,可有效縮短處理時間,能適應工程應用要求。

1　問題提出

在進行群的分割之前,首要要對群進行定義。理論上,群被定義[11]為滿足以下3個條件的多目標:

(1)運動方向一致;

(2)速度基本相同;

(3)群中各目標之間的空間距離遠小于各群之間的距離。

根據上述對群的定義,假設Z(k)為傳感器在k時刻獲得的所有量測集,且

(1)

式中,mk為k時刻的量測個數。

(2)

若

(3)

則量測zi(k)與zj(k)屬于同一個群。這里d0為群內目標的稠密程度值,其取值取決于傳感器系統的群目標目的。

傳統的基于空間距離的分割方法直接遍歷計算k時刻量測集Z(k)中任意兩個點的空間距離d[zi(k),zj(k)],最終可分為m個群,記為{U1,U2,…,Um}。

2　本文算法

2.1坐標映射距離

圖1　坐標映射距離示意圖

2.2群分割方法

在獲得了所有量測點的坐標軸映射距離后,這里對兩個軸分別進行分群。以x軸為例,首先將所有量測點的x軸映射距離升序排列,即

(4)

進而將該序列進行差分運算(后項減前項),即獲得一個表示相鄰兩點之間距離的序列

(5)

(6)

根據群的定義,通常情況下由于各個群之間距離較遠,但在某些情況下,各個群之間的距離相對較近,會出現單獨一個坐標軸分群出現錯誤的情況,如圖2所示。此時,需要對兩組預備群進行取交關聯:

(7)

通過將所有預備群進行關聯,可以將各個群Uk的空間范圍確定在一個矩形區域內,由于各群之間距離遠大于群內目標之間距離,因此確定的群具有唯一性。

2.3算法流程

綜上所述,基于坐標映射距離差分的快速群分割算法的總體流程如圖3所示。從圖3中可以看出,該算法結構簡單易行,易于工程實現。

圖2　群分割示意圖

圖3　算法流程圖

2.4時間復雜度分析

時間復雜度[12-16]是衡量一個算法性能優劣的重要指標。在理論上,算法運行所耗費的時間并不能計算出來,必須上機測試,但仍可通過理論分析執行算法所需要的計算工作量,來比較衡量各個算法。因此本節將距離分割法、循環閾值法、圖解法與本文提出的基于坐標映射距離差分的群分割算法進行理論分析與比較,為后續仿真提供理論依據。這里,假設在單傳感器條件下,某時刻回波個數為n。

距離分割法的計算量主要集中在遍歷所有回波點兩兩之間的距離,因此T1(n)=Ο(n2)。

圖解法的計算量不僅取決于傳感器探測范圍內的回波個數,還與探測區域被分割成的個數l2有關。該方法第一步將回波劃歸小區域時,時間復雜度為Ο(nl),第二步更新小區域比重時,復雜度為Ο(l2),則T3=Ο(nl)+Ο(l2)。由此可以看出,當l?n時,T3≈Ο(l2);當l與n相當量級時,T3≈Ο(n2)。因此,當l?n時,即視場內的雷達回波較為稀疏條件下,該算法的時間復雜度由視場分割數l2決定。

通過對上述4種算法的時間復雜度的理論分析,可得如表1所示時間復雜度對比圖。從表1可以看出,在最好情況下,循環閾值法的時間復雜度最低;最差情況下,當l?n時,圖解法的時間復雜度最高;平均條件下,本文算法的時間復雜度最低,理論上效率最高。

表1　算法時間復雜度對比

3　仿真驗證與分析

為了全面展示算法性能,本節模擬了兩種戰場常見的雷達量測場景與一種模擬工程應用的復雜場景:小視場環境、大視場稀疏回波環境[20]、群分裂與群合并情景下的分群。由于群分割技術主要側重算法耗時與正確分群率(完全準確的將屬于一個群的量測點標記為一個群),因此仿真結果采用這兩個指標做衡量標準。

場景 1常見的小視場環境仿真參數如表2所示。

表2　場景1仿真參數

在上述仿真情況下,由于有雜波存在,即在雷達掃描區域內有單個點的存在,該類點既有可能是單個目標的航跡點,也有可能是隨機雜波,但在本文仿真中,只劃分“群目標”與“非群目標”,因此在數據處理過程中將該類點標記為“非群目標”,以備后續點航關聯使用。仿真場景如圖4所示(雜波為隨機的)。

仿真實驗結果如表3所示。

通過表3可以看出,在處理的正確率上,本文算法跟經典距離分割法及循環閾值法處理水平相當,顯著高于圖解法。在算法效率上,本文算法的處理耗時顯著低于其他3種算法,與經典的距離分割法相比,處理效率幾乎要高出一個量級;與循環閾值法及圖解法相比,耗時減少一半。通過在這兩項指標上的仿真實驗結果可以看出,本文提出的算法與目前常用的算法相比,可以獲得相似或者更高的處理準確率,且處理耗時更短,具有更高效的處理效率。

圖4　場景1示意圖

算法耗時/s正確分群率/%距離分割法10.625100循環閾值法5.326100圖解法3.01294.5本文算法2.41499.5

場景 2大視場稀疏回波環境仿真參數如表4所示。

表4　場景2仿真參數

在該場景中,視場范圍較大,回波總數較為稀疏,符合許多傳感器真實應用條件下的探測態勢。仿真場景如圖5所示。圖中3個小圖為3個目標群的放大示意圖。

仿真結果如表5所示。

在場景2的條件下,應用圖解法對整個視場環境進行劃分顯然比較浪費資源,因為該方法的虛擬網格中大部分的位置都是空閑的,但卻需要遍歷這些網格。如表5所示,圖解法的運行時間遠遠高于其他3種算法,這說明在該場景條件下,不適宜應用圖解法進行分群處理。比較本文算法與另外兩種經典分群算法,三者的分群正確率相同,而本文算法的處理時間顯著低于其他二者,這說明本文在該場景下的整體效率顯著優于傳統算法。

圖5　場景2示意圖

算法耗時/s正確分群率/%距離分割法8.45999.5循環閾值法3.86499.5圖解法28.47197.5本文算法1.96399.0

縱觀兩個場景的仿真結果,距離分割法與循環閾值法的處理正確率較為穩定,這主要也源于其算法思路是對群定義的直接實現,但算法的耗時取決于當前時刻的傳感器回波個數,不適用于多目標及多雜波情況。圖解法在小視場條件的表現較優,耗時較短,但在大視場條件的耗時顯著增大,因此其應用條件較苛刻,不適合實際應用需求。本文提出的算法在兩種仿真條件下的分群正確率較穩定,且耗時均為最小,在大視場稀疏回波條件下的效果尤為突出。因此,本文提出的算法可應用于所有真實戰場環境,對后續的群跟蹤數據處理環節提供更準確高效的分群結果。

另外,本文仿真的大視場與小視場環境并不是絕對的,二者在某些情況下是可以互相轉化的。如當場景2中的傳感器由于某些原因導致回波數增多,達到n與l相當量級時,既轉化為了場景1。在工程應用中需要分群算法能夠在場景多變的條件下也具有較好的適應性與兼容性。而本文提出的算法在這兩種場景中均表現優異,可適應復雜多變的實際應用場景,多場景兼容性優異,因此具有寬廣的工程應用前景。

場景 3群分裂與合并情景下的環境仿真:設在雷達視場x～[-1.6e4-0.4e4]、y～[0.6e42.2e4]內存在兩個勻速直線運動的編隊,其中群1存在5個成員、群2存在2個成員。群1中的2個成員機動運動逐漸與群1分離,隨后慢慢合并到群2中。各個目標的初始運動狀態如表6所示,表中G1-1表群1的第一個目標,以此類推。其中G12-1則表示開始在群1中,后來在群2中的目標。G12-1與G12-2這兩個目標的加速度為[5 m/s2-10 m/s2]。雜波的生成為在矩形雷達視場的內,每個時刻產生均勻分布的20個雜波。

雷達位于坐標原點(0,0),測向誤差σθ=0.2°、測距誤差σρ=20 m。

表6　場景3目標初始運動參數

在該場景中,既存在群的分離,也存在群的合并,同時還存在一定密度的雜波,因此場景較為復雜,前60個時刻的量測點,分布如圖6所示。群1從圖中的右下至左上運動,群2從中部頂端運動至左下。顯然,群1中的兩個目標脫離了群1,經過機動拐彎后合并到群2中。

圖6　場景3量測分布圖

在群的分裂與合并時,為了后續處理過程(例如互聯、濾波等)具有良好的數據保障,要求分群算法對目標的量測具有較高的劃分準確性,即當群發生分裂時,能較早的將成員劃分為不同的群。圖7為在群分裂與合并相關時刻的目標量測分布圖,為了清晰顯示目標量測,這里已刪去雜波。如圖7(a)所示,在13時刻,群1已分為兩個群,但這兩群之間仍處于分群的臨界距離,因此,判斷群分裂的時刻越靠近13時刻,越有利于后續的態勢處理。同理,如圖7(b)所示,在48時刻時,兩群已合并為一個群,因此,在此時刻左右需要更準確的分群能力。因此,為了對比算法對動態運動場景的魯棒性,這里通過對準確分群的判決時刻,來對比各算法的表現。

通過1 000次蒙特卡羅仿真,各算法在12～17時刻對群分裂的判決次數曲線如圖8所示;在45～50時刻對群合并的判決次數如圖9所示。群分裂與合并的平均判決時刻如表7所示。

圖7　場景3群分裂與合并時刻量測放大圖

圖8　群分裂判決時刻分布曲線圖

圖9　群合并判決時刻分布曲線圖

從圖8中可以看出,本文算法與距離分割法和循環閾值法的曲線相近,具有相近的處理能力,均顯著高于圖解法。且主要判決時刻集中在13與14時刻,較接近真實條件。從圖9中可以看出,4種算法的判決時刻主要集中在47與48時刻,但本文算法在48時刻的判決次數高于其他算法。從表7可以看出,無論在群分裂還是合并的情況,本文算法在平均判決時刻均更接近13與48時刻,因此,本文算法在動態場景下的算法效能最高。

表7　群分裂與合并的平均判決時刻

造成上述結果的原因是:圖解法的算法思路決定了其對量測點精細距離判斷的模糊性,因此在需要精細判決的條件下表現最差。而本文算法與距離分割法和循環閾值法均基于點與點之間的距離進行分割,因此較為精確。本文算法思路將二維信息轉化為兩個一維信息分別處理,因此對量測點之間的距離更敏感。從該場景仿真結果可以看出,本文算法在動態復雜條件(群的分裂與合并)下,表現出了比3種經典算法更準確更穩定的分群效能,對動態場景具有較好的魯棒性。

4　結　論

本文所提出的基于坐標映射距離差分的快速群分割算法在理論上減小了算法的時間復雜度,改進傳統算法在實時性上的不足。并通過3個常見戰場環境進行仿真驗證。該算法能夠在保證分群正確率的同時有效縮減運行時間,提高算法整體效能。在動態場景群的分裂與合并條件下仍保持較高的分群準確率,對各種場景均具有較好的魯棒性。該算法結構簡單,時效性顯著,魯棒性好,可在工程實踐中廣泛應用。本文下一步工作是基于算法容錯性繼續對本文的分群算法進行研究,從而為算法的優化奠定基礎。

[1] Jian L, Li X R. Tracking of maneuvering non-ellipsoidal extended object or target group using random matrix[J].IEEETrans.onSignalProcessing, 2014, 62(9):2450-2463.

[2] Feldmann M, Franken D, Koch W. Tracking of extended objects and group targets using random matrices[J].IEEETrans.onSignalProcessing, 2011, 59(4):1409-1420.

[3] Hyondong O, Seungkeun K, Hyo S S, et al. Coordinated standoff tracking of moving target groups using multiple UAVs[J].IEEETrans.onAerospaceandElectronicSystems,2015,51(2):1501-1514.

[4] Ziho K, Landry S J. An eye movement analysis algorithm for a multielement target tracking task: maximum transition-based agglomerative hierarchical clustering[J].IEEETrans.onHuman-MachineSystems, 2015, 45(1):13-24.

[5] Bar S Y. Extension of the probabilistic data association filter in multi-target tracking[C]∥Proc.ofthe5thSymposiumonNonlinearEstatimation, 1974: 16-21.

[6] Geng W D. Summarizing of group-target tracking[C]∥Proc.ofthe10thChinaRadarConference,2008:367-371.(耿文東.編隊目標跟蹤綜述[C]∥第十屆全國雷達學術年會,2008:367-371.)

[7] Wang H P, Xiong W, He Y, et al. Gray refined track initiation algorithm for centralized multi-sensor group targets[J].SystemsEngineeringandElectronics,2012,34(11):2249-2255.(王海鵬,熊偉,何友,等.集中式多傳感器群目標灰色精細航跡起始算法[J].系統工程與電子技術,2012,34(11):2249-2255.)

[8] He Y, Wang H P, Xiong W,et al.Gray refined track initiation algorithm of group targets based on relative position vector[J].ActaAeronauticaetAstronauticaSinica,2012,33(10):1850-1863.(何友,王海鵬,熊偉,等.基于相對位置矢量的群目標灰色精細航跡起始算法[J].航空學報,2012,33(10):1850-1863.)

[9] Xing F Y, Xiong W, Wang H P. A formation target track initiation algorithm based on clustering and hough transform[J].JournalofNavalAeronauticalandAstronauticalUniversity, 2010, 25(6):624-629.(邢鳳勇,熊偉,王海鵬.基于聚類和Hough變換的多編隊航跡起始算法[J].海軍航空工程學院學報,2010,25(6):624-629.)

[10] He Y, Xiu J J, Zhang J W.Radardataprocessingwithapplications[M]. 2nd ed. Beijing: Publishing House of Electronics Industry Press, 2011:170-178.(何友,修建娟,張晶煒.雷達數據處理及應用[M].2版.北京:電子工業出版社,2011:170-178.)

[11] Wang H P. Study of multi-sensor group targets tracking algorithm[D]. Yantai: Naval Aeronautical and Astronautical University, 2012. (王海鵬. 多傳感器編隊目標跟蹤算法研究[D]. 煙臺: 海軍航空工程學院, 2012.)

[12] Pietro S O, Carsten Witt. Improved time complexity analysis of the simple genetic algorithm[J].TheoreticalComputerScience, 2015, 605(9):21-41.

[13] Jia D, Zhang X. Research on time complexity measure method based on analysis method[J].JournalofLiaoningUniversityofTechnology(NaturalScienceEdition), 2015, 35(4):231-240.(賈丹,張興.基于分析法的算法時間復雜度的度量方法研究[J].遼寧工業大學學報(自然科學版),2015,35(4):231-240.)

[14] Xia J, Shang P, Wang J, et al. Permutation and weighted-permutation entropy analysis for the complexity of nonlinear time series[J].CommunicationsinNonlinearScienceandNumericalSimulation, 2016, 31(1):60-68.

[15] Hu J, Chen L Y, Zeng L M, et al. Performance testing based on time complexity analysis for embedded[C]∥Proc.oftheInternationalConferenceonEmbeddedSoftwareandSystems, 2008:243-247.

[16] Pakhira M K. A linear time-complexityk-means algorithm using cluster shifting[C]∥Proc.ofthe6thInternationalConferenceonComputationalIntelligenceandCommunicationNetworks, 2014:1047-1051.

[17] Dong F G, Fan H, Yuan D. A novel image median filtering algorithm based on incomplete quick sort algorithm[J].InternationalJournalofDigitalContentTechnologyandItsApplications, 2010, 4(6):244-256.

[18] Wang X. Analysis of the time complexity of quick sort algorithm[C]∥Proc.ofthe4thInternationalConferenceonInformationManagement,InnovationManagementandIndustrialEngineering, 2011:408-410.

[19] Hu F, Wang G Y, Feng L. Fast knowledge reduction algorithms based on quick sort[C]∥Proc.ofthe3thInternationalTechnologyinComputerScience,RoughSetsandKnowledgeTechnology, 2008:72-79.

[20] Zhu F, Zhang Q, Hong W, et al. Sparse imaging method with strip-map random noise radar based on compressive sensing[J].SystemsEngineeringandElectronics, 2012, 34(1):56-63. (朱豐, 張群, 洪文, 等. 基于壓縮感知的條帶隨機噪聲雷達稀疏成像方法[J].系統工程與電子技術, 2012, 34(1):56-63.)

Fast algorithm of group segmentation based on coordinates transformations and distance differentiations

WANG Cong1,2, WANG Hai-peng1, HE You1

(1. Naval Aeronautical and Astronautical University, Institute of Information Fusion, Yantai 264001, China;2. Key Lab for Spacecraft TT&C and Communication under the Ministry of Education, Chongqing 400044, China)

As a primary technology of group targets tracking, the result of group segmentation is the key to the outcome of the entire data processing progress. Based on the state-of-art researches, a fast algorithm of group segmentation based on coordinates transformations and distance differentiations is proposed. Firstly, the two-dimension information of acquired sets is decomposed into two one-dimensional information of coordinate distance. Then, the sets are sorted and segmented, which make time complexity reduced. Finally, the final segmentation group is obtained by extracting the intersection of two under-processed groups. Compared to three traditional methods in theory analysis of time complexity, the proposed method is more effective especially under the condition of large field of vision with sparse radar echoes. The simulation results of multi-scences show that, the proposed algorithm is much more efficient than the traditional methods, and has excellent robustness to dynamic scenes.

technology of group segmentation;group targets tracking;coordinates transformations;distance differentiations; time complexity

2016-01-21；

2016-04-28；網絡優先出版日期：2016-06-07。

飛行器測控與通信教育部重點實驗室開放基金(CTTC-FX201302)資助課題

TP 953

A

10.3969/j.issn.1001-506X.2016.08.02

王聰(1987-),男,講師,博士,主要研究方向為群目標跟蹤、航跡關聯。

E-mail:congnavy@hotmail.com

王海鵬(1985-),男,講師,博士,主要研究方向為群目標跟蹤、航跡關聯。

E-mail:armystudent@sohu.com

何友(1956-),男,中國工程院院士,教授,主要研究方向為雷達信號處理、信息融合。

E-mail:heyoumail@sohu.com

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160607.1140.006.html