基于坐標(biāo)映射距離差分的快速群分割算法

王　聰, 王海鵬, 何　友

(1. 海軍航空工程學(xué)院信息融合技術(shù)研究所, 山東 煙臺(tái) 264001;2.飛行器測(cè)控與通信教育部重點(diǎn)實(shí)驗(yàn)室, 重慶 400044)

?

基于坐標(biāo)映射距離差分的快速群分割算法

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

(1. 海軍航空工程學(xué)院信息融合技術(shù)研究所, 山東 煙臺(tái) 264001;2.飛行器測(cè)控與通信教育部重點(diǎn)實(shí)驗(yàn)室, 重慶 400044)

群分割技術(shù)作為群目標(biāo)跟蹤技術(shù)的首要環(huán)節(jié),其處理結(jié)果直接影響后續(xù)整個(gè)數(shù)據(jù)處理過(guò)程的效果。在深入研究目前已有的群分割技術(shù)的基礎(chǔ)上,提出了一種基于坐標(biāo)映射距離差分的快速群分割算法。首先將量測(cè)集的二維信息分解為兩組坐標(biāo)映射距離的一維信息,進(jìn)而分別進(jìn)行排序和分群處理,從而減小了算法的時(shí)間復(fù)雜度,最后將分別獲得的兩組預(yù)備群進(jìn)行取交關(guān)聯(lián),得到最終的分割群。通過(guò)與3種傳統(tǒng)算法在時(shí)間復(fù)雜度上的理論分析與比較,該方法在大視場(chǎng)回波稀疏條件下具有顯著的效率優(yōu)勢(shì)。經(jīng)過(guò)多場(chǎng)景的仿真分析表明,該算法的處理效能顯著高于傳統(tǒng)算法,且對(duì)復(fù)雜動(dòng)態(tài)場(chǎng)景具有較好的魯棒性。

群分割技術(shù); 群目標(biāo)跟蹤; 坐標(biāo)映射; 距離差分; 時(shí)間復(fù)雜度

0　引　言

隨著飛行器技術(shù)水平的不斷提高,低空飛行的飛機(jī)編隊(duì)、多發(fā)齊射的低空飛行導(dǎo)彈成為現(xiàn)代戰(zhàn)爭(zhēng)越來(lái)越普遍使用的常規(guī)化戰(zhàn)術(shù)。在雜波環(huán)境下,對(duì)該類運(yùn)動(dòng)方式相似、空間距離相近的目標(biāo)進(jìn)行精確跟蹤成為當(dāng)前目標(biāo)跟蹤領(lǐng)域的一個(gè)新的熱門問(wèn)題——群目標(biāo)跟蹤技術(shù)[1-4]。該技術(shù)可主要分為3部分:群的起始、群航跡的維持、群的撤銷。其中,如何準(zhǔn)確的起始一個(gè)群,是群目標(biāo)跟蹤首先需要解決的問(wèn)題。

在群目標(biāo)的起始技術(shù)中,又分為群的分割與互聯(lián)兩個(gè)技術(shù)環(huán)節(jié)。其中群分割技術(shù)作為后續(xù)算法的數(shù)據(jù)基礎(chǔ),是整個(gè)航跡跟蹤過(guò)程需要最先解決的問(wèn)題。本文主要針對(duì)群分割技術(shù)進(jìn)行了研究。

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

本文在借鑒上述算法的基礎(chǔ)上,并結(jié)合工程實(shí)際情況,提出了基于坐標(biāo)映射距離差分的群分割方法。該方法可對(duì)觀測(cè)點(diǎn)進(jìn)行有效的群分割,并顯著降低了計(jì)算復(fù)雜度,特別在雷達(dá)視場(chǎng)較大且回波稀疏等常見(jiàn)戰(zhàn)場(chǎng)情況下效果明顯,可有效縮短處理時(shí)間,能適應(yīng)工程應(yīng)用要求。

1　問(wèn)題提出

在進(jìn)行群的分割之前,首要要對(duì)群進(jìn)行定義。理論上,群被定義[11]為滿足以下3個(gè)條件的多目標(biāo):

(1)運(yùn)動(dòng)方向一致;

(2)速度基本相同;

(3)群中各目標(biāo)之間的空間距離遠(yuǎn)小于各群之間的距離。

根據(jù)上述對(duì)群的定義,假設(shè)Z(k)為傳感器在k時(shí)刻獲得的所有量測(cè)集,且

(1)

式中,mk為k時(shí)刻的量測(cè)個(gè)數(shù)。

(2)

若

(3)

則量測(cè)zi(k)與zj(k)屬于同一個(gè)群。這里d0為群內(nèi)目標(biāo)的稠密程度值,其取值取決于傳感器系統(tǒng)的群目標(biāo)目的。

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

2　本文算法

2.1坐標(biāo)映射距離

圖1　坐標(biāo)映射距離示意圖

2.2群分割方法

在獲得了所有量測(cè)點(diǎn)的坐標(biāo)軸映射距離后,這里對(duì)兩個(gè)軸分別進(jìn)行分群。以x軸為例,首先將所有量測(cè)點(diǎn)的x軸映射距離升序排列,即

(4)

進(jìn)而將該序列進(jìn)行差分運(yùn)算(后項(xiàng)減前項(xiàng)),即獲得一個(gè)表示相鄰兩點(diǎn)之間距離的序列

(5)

(6)

根據(jù)群的定義,通常情況下由于各個(gè)群之間距離較遠(yuǎn),但在某些情況下,各個(gè)群之間的距離相對(duì)較近,會(huì)出現(xiàn)單獨(dú)一個(gè)坐標(biāo)軸分群出現(xiàn)錯(cuò)誤的情況,如圖2所示。此時(shí),需要對(duì)兩組預(yù)備群進(jìn)行取交關(guān)聯(lián):

(7)

通過(guò)將所有預(yù)備群進(jìn)行關(guān)聯(lián),可以將各個(gè)群Uk的空間范圍確定在一個(gè)矩形區(qū)域內(nèi),由于各群之間距離遠(yuǎn)大于群內(nèi)目標(biāo)之間距離,因此確定的群具有唯一性。

2.3算法流程

綜上所述,基于坐標(biāo)映射距離差分的快速群分割算法的總體流程如圖3所示。從圖3中可以看出,該算法結(jié)構(gòu)簡(jiǎn)單易行,易于工程實(shí)現(xiàn)。

圖2　群分割示意圖

圖3　算法流程圖

2.4時(shí)間復(fù)雜度分析

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

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

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

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

表1　算法時(shí)間復(fù)雜度對(duì)比

3　仿真驗(yàn)證與分析

為了全面展示算法性能,本節(jié)模擬了兩種戰(zhàn)場(chǎng)常見(jiàn)的雷達(dá)量測(cè)場(chǎng)景與一種模擬工程應(yīng)用的復(fù)雜場(chǎng)景:小視場(chǎng)環(huán)境、大視場(chǎng)稀疏回波環(huán)境[20]、群分裂與群合并情景下的分群。由于群分割技術(shù)主要側(cè)重算法耗時(shí)與正確分群率(完全準(zhǔn)確的將屬于一個(gè)群的量測(cè)點(diǎn)標(biāo)記為一個(gè)群),因此仿真結(jié)果采用這兩個(gè)指標(biāo)做衡量標(biāo)準(zhǔn)。

場(chǎng)景 1常見(jiàn)的小視場(chǎng)環(huán)境仿真參數(shù)如表2所示。

表2　場(chǎng)景1仿真參數(shù)

在上述仿真情況下,由于有雜波存在,即在雷達(dá)掃描區(qū)域內(nèi)有單個(gè)點(diǎn)的存在,該類點(diǎn)既有可能是單個(gè)目標(biāo)的航跡點(diǎn),也有可能是隨機(jī)雜波,但在本文仿真中,只劃分“群目標(biāo)”與“非群目標(biāo)”,因此在數(shù)據(jù)處理過(guò)程中將該類點(diǎn)標(biāo)記為“非群目標(biāo)”,以備后續(xù)點(diǎn)航關(guān)聯(lián)使用。仿真場(chǎng)景如圖4所示(雜波為隨機(jī)的)。

仿真實(shí)驗(yàn)結(jié)果如表3所示。

通過(guò)表3可以看出,在處理的正確率上,本文算法跟經(jīng)典距離分割法及循環(huán)閾值法處理水平相當(dāng),顯著高于圖解法。在算法效率上,本文算法的處理耗時(shí)顯著低于其他3種算法,與經(jīng)典的距離分割法相比,處理效率幾乎要高出一個(gè)量級(jí);與循環(huán)閾值法及圖解法相比,耗時(shí)減少一半。通過(guò)在這兩項(xiàng)指標(biāo)上的仿真實(shí)驗(yàn)結(jié)果可以看出,本文提出的算法與目前常用的算法相比,可以獲得相似或者更高的處理準(zhǔn)確率,且處理耗時(shí)更短,具有更高效的處理效率。

圖4　場(chǎng)景1示意圖

算法耗時(shí)/s正確分群率/%距離分割法10.625100循環(huán)閾值法5.326100圖解法3.01294.5本文算法2.41499.5

場(chǎng)景 2大視場(chǎng)稀疏回波環(huán)境仿真參數(shù)如表4所示。

表4　場(chǎng)景2仿真參數(shù)

在該場(chǎng)景中,視場(chǎng)范圍較大,回波總數(shù)較為稀疏,符合許多傳感器真實(shí)應(yīng)用條件下的探測(cè)態(tài)勢(shì)。仿真場(chǎng)景如圖5所示。圖中3個(gè)小圖為3個(gè)目標(biāo)群的放大示意圖。

仿真結(jié)果如表5所示。

在場(chǎng)景2的條件下,應(yīng)用圖解法對(duì)整個(gè)視場(chǎng)環(huán)境進(jìn)行劃分顯然比較浪費(fèi)資源,因?yàn)樵摲椒ǖ奶摂M網(wǎng)格中大部分的位置都是空閑的,但卻需要遍歷這些網(wǎng)格。如表5所示,圖解法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)高于其他3種算法,這說(shuō)明在該場(chǎng)景條件下,不適宜應(yīng)用圖解法進(jìn)行分群處理。比較本文算法與另外兩種經(jīng)典分群算法,三者的分群正確率相同,而本文算法的處理時(shí)間顯著低于其他二者,這說(shuō)明本文在該場(chǎng)景下的整體效率顯著優(yōu)于傳統(tǒng)算法。

圖5　場(chǎng)景2示意圖

算法耗時(shí)/s正確分群率/%距離分割法8.45999.5循環(huán)閾值法3.86499.5圖解法28.47197.5本文算法1.96399.0

縱觀兩個(gè)場(chǎng)景的仿真結(jié)果,距離分割法與循環(huán)閾值法的處理正確率較為穩(wěn)定,這主要也源于其算法思路是對(duì)群定義的直接實(shí)現(xiàn),但算法的耗時(shí)取決于當(dāng)前時(shí)刻的傳感器回波個(gè)數(shù),不適用于多目標(biāo)及多雜波情況。圖解法在小視場(chǎng)條件的表現(xiàn)較優(yōu),耗時(shí)較短,但在大視場(chǎng)條件的耗時(shí)顯著增大,因此其應(yīng)用條件較苛刻,不適合實(shí)際應(yīng)用需求。本文提出的算法在兩種仿真條件下的分群正確率較穩(wěn)定,且耗時(shí)均為最小,在大視場(chǎng)稀疏回波條件下的效果尤為突出。因此,本文提出的算法可應(yīng)用于所有真實(shí)戰(zhàn)場(chǎng)環(huán)境,對(duì)后續(xù)的群跟蹤數(shù)據(jù)處理環(huán)節(jié)提供更準(zhǔn)確高效的分群結(jié)果。

另外,本文仿真的大視場(chǎng)與小視場(chǎng)環(huán)境并不是絕對(duì)的,二者在某些情況下是可以互相轉(zhuǎn)化的。如當(dāng)場(chǎng)景2中的傳感器由于某些原因?qū)е禄夭〝?shù)增多,達(dá)到n與l相當(dāng)量級(jí)時(shí),既轉(zhuǎn)化為了場(chǎng)景1。在工程應(yīng)用中需要分群算法能夠在場(chǎng)景多變的條件下也具有較好的適應(yīng)性與兼容性。而本文提出的算法在這兩種場(chǎng)景中均表現(xiàn)優(yōu)異,可適應(yīng)復(fù)雜多變的實(shí)際應(yīng)用場(chǎng)景,多場(chǎng)景兼容性優(yōu)異,因此具有寬廣的工程應(yīng)用前景。

場(chǎng)景 3群分裂與合并情景下的環(huán)境仿真:設(shè)在雷達(dá)視場(chǎng)x～[-1.6e4-0.4e4]、y～[0.6e42.2e4]內(nèi)存在兩個(gè)勻速直線運(yùn)動(dòng)的編隊(duì),其中群1存在5個(gè)成員、群2存在2個(gè)成員。群1中的2個(gè)成員機(jī)動(dòng)運(yùn)動(dòng)逐漸與群1分離,隨后慢慢合并到群2中。各個(gè)目標(biāo)的初始運(yùn)動(dòng)狀態(tài)如表6所示,表中G1-1表群1的第一個(gè)目標(biāo),以此類推。其中G12-1則表示開(kāi)始在群1中,后來(lái)在群2中的目標(biāo)。G12-1與G12-2這兩個(gè)目標(biāo)的加速度為[5 m/s2-10 m/s2]。雜波的生成為在矩形雷達(dá)視場(chǎng)的內(nèi),每個(gè)時(shí)刻產(chǎn)生均勻分布的20個(gè)雜波。

雷達(dá)位于坐標(biāo)原點(diǎn)(0,0),測(cè)向誤差σθ=0.2°、測(cè)距誤差σρ=20 m。

表6　場(chǎng)景3目標(biāo)初始運(yùn)動(dòng)參數(shù)

在該場(chǎng)景中,既存在群的分離,也存在群的合并,同時(shí)還存在一定密度的雜波,因此場(chǎng)景較為復(fù)雜,前60個(gè)時(shí)刻的量測(cè)點(diǎn),分布如圖6所示。群1從圖中的右下至左上運(yùn)動(dòng),群2從中部頂端運(yùn)動(dòng)至左下。顯然,群1中的兩個(gè)目標(biāo)脫離了群1,經(jīng)過(guò)機(jī)動(dòng)拐彎后合并到群2中。

圖6　場(chǎng)景3量測(cè)分布圖

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

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

圖7　場(chǎng)景3群分裂與合并時(shí)刻量測(cè)放大圖

圖8　群分裂判決時(shí)刻分布曲線圖

圖9　群合并判決時(shí)刻分布曲線圖

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

表7　群分裂與合并的平均判決時(shí)刻

造成上述結(jié)果的原因是:圖解法的算法思路決定了其對(duì)量測(cè)點(diǎn)精細(xì)距離判斷的模糊性,因此在需要精細(xì)判決的條件下表現(xiàn)最差。而本文算法與距離分割法和循環(huán)閾值法均基于點(diǎn)與點(diǎn)之間的距離進(jìn)行分割,因此較為精確。本文算法思路將二維信息轉(zhuǎn)化為兩個(gè)一維信息分別處理,因此對(duì)量測(cè)點(diǎn)之間的距離更敏感。從該場(chǎng)景仿真結(jié)果可以看出,本文算法在動(dòng)態(tài)復(fù)雜條件(群的分裂與合并)下,表現(xiàn)出了比3種經(jīng)典算法更準(zhǔn)確更穩(wěn)定的分群效能,對(duì)動(dòng)態(tài)場(chǎng)景具有較好的魯棒性。

4　結(jié)　論

本文所提出的基于坐標(biāo)映射距離差分的快速群分割算法在理論上減小了算法的時(shí)間復(fù)雜度,改進(jìn)傳統(tǒng)算法在實(shí)時(shí)性上的不足。并通過(guò)3個(gè)常見(jiàn)戰(zhàn)場(chǎng)環(huán)境進(jìn)行仿真驗(yàn)證。該算法能夠在保證分群正確率的同時(shí)有效縮減運(yùn)行時(shí)間,提高算法整體效能。在動(dòng)態(tài)場(chǎng)景群的分裂與合并條件下仍保持較高的分群準(zhǔn)確率,對(duì)各種場(chǎng)景均具有較好的魯棒性。該算法結(jié)構(gòu)簡(jiǎn)單,時(shí)效性顯著,魯棒性好,可在工程實(shí)踐中廣泛應(yīng)用。本文下一步工作是基于算法容錯(cuò)性繼續(xù)對(duì)本文的分群算法進(jìn)行研究,從而為算法的優(yōu)化奠定基礎(chǔ)。

[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.(耿文東.編隊(duì)目標(biāo)跟蹤綜述[C]∥第十屆全國(guó)雷達(dá)學(xué)術(shù)年會(huì),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.(王海鵬,熊偉,何友,等.集中式多傳感器群目標(biāo)灰色精細(xì)航跡起始算法[J].系統(tǒng)工程與電子技術(shù),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.(何友,王海鵬,熊偉,等.基于相對(duì)位置矢量的群目標(biāo)灰色精細(xì)航跡起始算法[J].航空學(xué)報(bào),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變換的多編隊(duì)航跡起始算法[J].海軍航空工程學(xué)院學(xué)報(bào),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.(何友,修建娟,張晶煒.雷達(dá)數(shù)據(jù)處理及應(yīng)用[M].2版.北京:電子工業(yè)出版社,2011:170-178.)

[11] Wang H P. Study of multi-sensor group targets tracking algorithm[D]. Yantai: Naval Aeronautical and Astronautical University, 2012. (王海鵬. 多傳感器編隊(duì)目標(biāo)跟蹤算法研究[D]. 煙臺(tái): 海軍航空工程學(xué)院, 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.(賈丹,張興.基于分析法的算法時(shí)間復(fù)雜度的度量方法研究[J].遼寧工業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版),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ī)噪聲雷達(dá)稀疏成像方法[J].系統(tǒng)工程與電子技術(shù), 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；網(wǎng)絡(luò)優(yōu)先出版日期：2016-06-07。

飛行器測(cè)控與通信教育部重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(CTTC-FX201302)資助課題

TP 953

A

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

王聰(1987-),男,講師,博士,主要研究方向?yàn)槿耗繕?biāo)跟蹤、航跡關(guān)聯(lián)。

E-mail:congnavy@hotmail.com

王海鵬(1985-),男,講師,博士,主要研究方向?yàn)槿耗繕?biāo)跟蹤、航跡關(guān)聯(lián)。

E-mail:armystudent@sohu.com

何友(1956-),男,中國(guó)工程院院士,教授,主要研究方向?yàn)槔走_(dá)信號(hào)處理、信息融合。

E-mail:heyoumail@sohu.com

網(wǎng)絡(luò)優(yōu)先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20160607.1140.006.html