基于水平集的目標分群方法

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

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

0 引言

目標分群[1-3]是態勢評估[4-6]領域的熱點，目的是將獲得的大量戰斗實體聚合為多個戰斗群，輔助指揮人員理解各戰斗實體之間的關系，減輕指揮人員的認知壓力，提高指揮人員的決策速度和效率[7-8]。

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

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

1 問題描述

1.1 目標分群的整體流程

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

① 目標對象評估：明確戰場目標屬性；

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

③ 形成相互作用群：明確空間群的作戰目標以及相互之間的關系之間的系統關系，將同一組中的目標，根據位置關系劃分空間群；

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

圖1 目標分群步驟

1.2 空間群構建的數學模型

空間群的劃分通常包括2個步驟，首先通過預設條件，對敵我、類型、速度及方向等屬性進行分組；然后將屬性相近的目標按照地理空間拓撲關系劃分形成群組。在二維態勢圖上，任何一個空間群均可用至少一條閉合曲線C完全包絡。因此，按照地理空間拓撲關系劃分形成群組這一步驟的劃分可以轉化為曲線演化問題。

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

(1)

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

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

(2)

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

2 數學模型的水平集解法

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

2.1 曲線C的構造

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

(3)

其中，δ()為Dirac函數；r為正常數?？梢姡瘮郸?x，y)表示三維空間中的一個圓錐曲面，此時曲線C表示以原點為中心，以r為半徑的圓。因此，只要r足夠大，就可保證曲線C將所有目標位置點包絡其中。

2.2 曲線C的演化

結合式(3)可知，曲線C的內外部區域分別對應φ(x，y)>0和φ(x，y)<0的區域，則

(4)

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

(5)

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

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

(6)

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

(7)

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

2.3 曲線C的計算

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

(8)

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

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

(9)

式中，ε為預設常數，ε越趨于0，則δε()越接近δ()，本文將ε統一選為0.1。

3 仿真試驗

本節依照上述算法對圖1所示的想定劃分空間群。目標分群腳本如圖2所示。

圖2 目標分群腳本

首先將式(1)中的參數rc選為400，根據式(1)計算目標組空間拓撲結構映射，如圖3(a)所示；再根據2.1節介紹的方法，構造包絡所有目標的曲線C，如圖3(b)所示。本文將式(9)中的迭代步長選為200，系數選為0.13×2552，將常數c選為30。

圖3 目標分群腳本

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

圖4 目標分群過程示意

圖5 目標最終分群結果

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

4 結束語

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