基于水平集的目標(biāo)分群方法

李 鏡，劉磊浩，劉 新，馬培博，郭勝楠

(1.中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081； 2.中國人民解放軍32299部隊，河北 石家莊 050081)

0 引言

目標(biāo)分群[1-3]是態(tài)勢評估[4-6]領(lǐng)域的熱點(diǎn)，目的是將獲得的大量戰(zhàn)斗實體聚合為多個戰(zhàn)斗群，輔助指揮人員理解各戰(zhàn)斗實體之間的關(guān)系，減輕指揮人員的認(rèn)知壓力，提高指揮人員的決策速度和效率[7-8]。

當(dāng)前目標(biāo)分群多是通過聚類[9-14]方法實現(xiàn)，即將屬性相同或相似、地理位置接近的目標(biāo)判為同一類。但此類方法往往需要事先指定參數(shù)，如K-means算法需要事先指定分類數(shù)K的值[12-13]；一旦參數(shù)選定，用戶在分群過程中不易施加干預(yù)。即使針對同一戰(zhàn)場目標(biāo)圖，不同用戶的理解也往往不同，導(dǎo)致同一方法產(chǎn)生的分群結(jié)果未必能滿足所有用戶。

基于幾何變形模型的水平集方法誕生于上世紀(jì)80年代，其中最具代表性的是1987年提出的Snake模型演化法[15]，該方法利用圖像數(shù)據(jù)作為曲線演化的約束條件，對曲線拓?fù)浣Y(jié)構(gòu)的變化可以很自然地處理。本文將目標(biāo)分群歸結(jié)為一個曲線演化問題，將目標(biāo)的分布情況視為對曲線演化的約束，提出了面向目標(biāo)分群的代價函數(shù)，通過對代價函數(shù)進(jìn)行優(yōu)化，迭代求解目標(biāo)分群問題。由于采用了迭代求解的方式，本文方法允許用戶通過曲線的變化趨勢了解戰(zhàn)場目標(biāo)分布情況，并允許用戶在曲線演化過程中，根據(jù)自己對戰(zhàn)場態(tài)勢的理解，實時調(diào)節(jié)算法參數(shù)修正曲線的演化趨勢。

1 問題描述

1.1 目標(biāo)分群的整體流程

目標(biāo)分群將關(guān)于目標(biāo)對象的可用數(shù)據(jù)按空間、功能及相互作用等屬性逐級分群，以揭示目標(biāo)之間的相互聯(lián)系，確定相互合作的功能，從而解釋問題領(lǐng)域的各種行為，如圖1所示。空間群的形成是目標(biāo)分群的基礎(chǔ)，起著承上啟下的作用。目標(biāo)分群過程通常包含以下4個步驟：

① 目標(biāo)對象評估：明確戰(zhàn)場目標(biāo)屬性；

② 形成空間群：按空間一維或多維簇分類分析而劃分的群，同一群中的成員歸屬一致、類型相同、空間位置相近、行為相似；

③ 形成相互作用群：明確空間群的作戰(zhàn)目標(biāo)以及相互之間的關(guān)系之間的系統(tǒng)關(guān)系，將同一組中的目標(biāo)，根據(jù)位置關(guān)系劃分空間群；

④ 形成敵方/我方/中立方群：將所有相互關(guān)系群按敵方、我方和中立方標(biāo)識劃分為3個大群，形成戰(zhàn)場的3個陣營。

圖1 目標(biāo)分群步驟

1.2 空間群構(gòu)建的數(shù)學(xué)模型

空間群的劃分通常包括2個步驟，首先通過預(yù)設(shè)條件，對敵我、類型、速度及方向等屬性進(jìn)行分組；然后將屬性相近的目標(biāo)按照地理空間拓?fù)潢P(guān)系劃分形成群組。在二維態(tài)勢圖上，任何一個空間群均可用至少一條閉合曲線C完全包絡(luò)。因此，按照地理空間拓?fù)潢P(guān)系劃分形成群組這一步驟的劃分可以轉(zhuǎn)化為曲線演化問題。

本文方法首先對戰(zhàn)場目標(biāo)進(jìn)行分組，即將屬性相同或相似的目標(biāo)劃分在同一組中；然后采用式(1)所示的函數(shù)描述分組的目標(biāo)在二維態(tài)勢圖上的分布：

(1)

式中，S為預(yù)設(shè)系數(shù)，本文將其設(shè)為255；xi，yi為第i個目標(biāo)在戰(zhàn)場中的坐標(biāo)；rc為預(yù)設(shè)門限值。該式的含義是，僅在目標(biāo)坐標(biāo)點(diǎn)附近不為0，而在其余位置均為0。因此，必定可以找到一條簡單閉合曲線C將函數(shù)u(x，y)的所有非零點(diǎn)包絡(luò)其中。設(shè)定曲線演化條件，用一條或多條盡可能短的曲線，將盡量多的非零點(diǎn)包絡(luò)其中，即可實現(xiàn)目標(biāo)的空間分群。

曲線C演化的動力分為內(nèi)力和外力2部分，本文將內(nèi)力定義為曲線周長最短，將外力定義為曲線內(nèi)部的非零區(qū)域最小。綜上所述，本文提出如式(2)所示的優(yōu)化模型：

(2)

式中，Cresult為曲線演化結(jié)果，即分群結(jié)果；F(C)為代價函數(shù)；μ為系數(shù)；length()為曲線周長；in-C為閉合曲線內(nèi)部區(qū)域；out-C為閉合曲線外部區(qū)域，c為正常數(shù)。式(2)的數(shù)學(xué)含義為，尋找一條曲線Cresult，使得該曲線能夠在周長盡量短的情況下，將函數(shù)u(x，y)的非零點(diǎn)包絡(luò)其中，從而完成目標(biāo)分群。不難發(fā)現(xiàn)，系數(shù)μ負(fù)責(zé)調(diào)節(jié)曲線周長在算法中占的比重，μ越大則意味著在曲線將盡可能的朝著的周長變短的方向演化。常數(shù)c控制著曲線面積所占的比重，c越大則曲線越朝著面積減小的方向演化。代價函數(shù)F(C)的第三項的作用是保證閉合曲線C的外部區(qū)域的非零元素盡可能的少，它可以保證在曲線演化過程中，函數(shù)u(x，y)的所有非零元素盡可能的分布在曲線內(nèi)部

2 數(shù)學(xué)模型的水平集解法

本節(jié)主要討論式(2)所示數(shù)學(xué)模型的水平集解法。水平集方法的基本思想是將曲線C視為曲面函數(shù)z=φ(x，y)在z=0處的一個特例[16]；從而將曲線C的演化問題轉(zhuǎn)化為曲面z=φ(x，y)的演化問題[17-18]。

2.1 曲線C的構(gòu)造

簡單閉合曲線C的構(gòu)造方法有很多，本文僅給出一種較為常見的曲線構(gòu)造方案[17]，如式(3)所示：

(3)

其中，δ()為Dirac函數(shù)；r為正常數(shù)。可見，函數(shù)φ(x，y)表示三維空間中的一個圓錐曲面，此時曲線C表示以原點(diǎn)為中心，以r為半徑的圓。因此，只要r足夠大，就可保證曲線C將所有目標(biāo)位置點(diǎn)包絡(luò)其中。

2.2 曲線C的演化

結(jié)合式(3)可知，曲線C的內(nèi)外部區(qū)域分別對應(yīng)φ(x，y)>0和φ(x，y)<0的區(qū)域，則

(4)

其中，H( )為Heaviside函數(shù)，即：

(5)

將曲線C對應(yīng)φ(x，y)=0的部分，根據(jù)文獻(xiàn)[13]可知，借助函數(shù)φ(x，y)，式(2)中曲線的周長length(C)可表述為：

length(C)=length(φ(x，y)=0)=
∮δ(φ(x，y))|φ(x，y)|dxdy

(6)

將式(4)、式(6)代入式(2)中，即可得曲線C的演化方程：

(7)

式(7)的含義是曲線C的演化結(jié)果Cresult對應(yīng)于曲面φ(x，y)的演化結(jié)果z=φresult(x，y)與平面z=0的交集，而φresult(x，y)可通過對代價函數(shù)F(φ)的優(yōu)化得出。

2.3 曲線C的計算

根據(jù)歐拉-拉格朗日方程，式(7)所示的最優(yōu)化問題可按下式迭代解出：

(8)

式中，Δt為迭代步長，式(8)中的迭代初始值依式(3)確定。

在實際計算中，為了避免由于計算誤差等原因陷入局部最優(yōu)解，通常選用式(9)所示的近似函數(shù)δε()替代Dirac函數(shù)δ()[15-16]：

(9)

式中，ε為預(yù)設(shè)常數(shù)，ε越趨于0，則δε()越接近δ()，本文將ε統(tǒng)一選為0.1。

3 仿真試驗

本節(jié)依照上述算法對圖1所示的想定劃分空間群。目標(biāo)分群腳本如圖2所示。

圖2 目標(biāo)分群腳本

首先將式(1)中的參數(shù)rc選為400，根據(jù)式(1)計算目標(biāo)組空間拓?fù)浣Y(jié)構(gòu)映射，如圖3(a)所示；再根據(jù)2.1節(jié)介紹的方法，構(gòu)造包絡(luò)所有目標(biāo)的曲線C，如圖3(b)所示。本文將式(9)中的迭代步長選為200，系數(shù)選為0.13×2552，將常數(shù)c選為30。

圖3 目標(biāo)分群腳本

在Matlab7.5.0下仿真算法，分別迭代2 000，3 200，6 300，6 800次的分群結(jié)果如圖4所示。在迭代6 800次后，結(jié)果趨于穩(wěn)定，本文將提取最終曲線并將其映射到地圖上，得到第1組目標(biāo)的最終分群結(jié)果如圖5所示。

圖4 目標(biāo)分群過程示意

圖5 目標(biāo)最終分群結(jié)果

綜上所述，由于采用了曲線演化的方式，能夠直觀地顯示分群結(jié)果和趨勢。曲線演化過程可以輔助指揮人員理解戰(zhàn)場態(tài)勢，指揮人員也可以隨時終止迭代過程，或者改變演化參數(shù)，控制演化結(jié)果。

4 結(jié)束語

本文將水平集曲線演化理論引入目標(biāo)分群應(yīng)用中，提出了一種新的解決方法。該方法將目標(biāo)的空間分布結(jié)構(gòu)視為曲線演化的約束條件，使曲線自動地在目標(biāo)邊沿處停止演化，從而實現(xiàn)分群。需要指出的是，目標(biāo)分群技術(shù)本質(zhì)上是利用計算機(jī)來模擬人大腦思考的過程。即使針對同一戰(zhàn)場情形，不同人的理解也可能存在偏差。即使同一種方法，當(dāng)參數(shù)選擇不同數(shù)值時，結(jié)果也會有偏差。從現(xiàn)階段看，這2種偏差都是難以徹底克服的。本文方法允許用戶觀察曲線演化的全過程，因此，即使最終分群結(jié)果與用戶的理解存在偏差，用戶也可參考曲線演化過程理解戰(zhàn)場態(tài)勢。