基于Hausdorff距離的反艦導彈目標選擇方法

潘 哲

（海軍裝備部，重慶 400042）

導引頭的目標選擇技術是反艦導彈末制導中的核心技術，直接制約導彈作戰(zhàn)效能的發(fā)揮。目前，主動末制導雷達反艦導彈對目標的選擇主要有距離選擇區(qū)法和擴展搜索圖選擇法，這些方法的實質(zhì)是人工射前瞄準選擇目標，受導彈自控終點的散布誤差和目標的機動影響較大，因而不適合應用于超視距反艦導彈。依據(jù)高技術戰(zhàn)場的迫切需求，反艦導彈已在射程和搜索能力上實現(xiàn)由視距向超視距的跨躍，亟待解決的問題是如何正確選擇預定目標[1]。

文獻[1]提出了一種利用艦艇編隊相互位置關系的預定目標選擇方法。文獻[2-3]所研究的目標選擇方法中也利用了編隊的相互位置關系，且其理論依據(jù)與文獻[1]類似。由于利用了編隊形狀，該類方法可實現(xiàn)打擊任意指定目標的戰(zhàn)術意圖，并具備一定的抗干擾能力，而且不受一致運動(包括自控終點散布誤差和編隊整體機動)的影響。但該類方法在比較兩個編隊的相互位置關系時，需要根據(jù)經(jīng)驗或試驗事先獲得一個門限值[1]。此外，文獻[4]利用了部分Hausdorff距離(PHD)序列的二階差分的最大值來剔除遠處干擾點，但同樣需要事先根據(jù)經(jīng)驗設定一個門限。

如果門限選小了，就可能誤將相似部分剔除掉，如果選大了，就不能較好地剔除外部點的干擾，因此，上述方法都面臨門限選擇困難的問題。

本文基于Hausdorff距離提出一種新的部分匹配途徑，以自適應剔除干擾并保留形狀相似部分的作用，從而獲得一種抗干擾能力更好的預定目標選擇方法。

1 問題描述

設反艦導彈發(fā)射平臺的火控雷達探測到遠距離處的一個艦艇編隊A(如圖1所示，這里給出了3種編隊隊形，每個編隊中的各艦艇用ai表示)。依據(jù)戰(zhàn)術任務要求，反艦導彈的攻擊目標為a1。在導彈發(fā)射時刻，通過發(fā)射平臺的火控系統(tǒng)向?qū)椦b訂由火控雷達探測到的編隊目標的位置信息，并對預定目標進行標記。經(jīng)過自控段后，末制導雷達開機，雷達在其最大搜索區(qū)域搜索一遍，錄入所有探測到的目標信息，然后進行預定目標選擇。預定目標選擇的任務就是使末制導雷達開機后捕獲到a1，而非其他目標。

圖1 艦艇編隊

火控雷達裝訂的編隊信息和末制導雷達搜索得到的編隊信息都可以用平面上的點集來描述。預定目標選擇實際上是對應點的匹配，即從末制導雷達獲得的點集中尋找火控雷達裝訂目標點(即預定目標)的對應點。

以往基于Hausdorff距離的眾多部分匹配方法都不能自動給出最相匹配的部分形狀。有的需要根據(jù)經(jīng)驗或試驗給出L0和K0的估計值L和K，如Huttenlocher 等人提出的雙向部分Hausdorff距離[5]，Tan 等人通過引入平均算子提出的LTS-HD[6]，Paumard 等人提出的CHD[7]，Han 等人提出的HDEP[8]，以及Rucklidge 用一個包含模板中有用形狀的矩形框來確定L和K的方法[9]。有的需要通過設定一個門限來剔除外部點的影響，如Kwon 改進的M-HD[10]以及Huttenlocher 等人利用給定門限下的Hausdorff 分數(shù)作為形狀的相似性度量的方法[11]。

由于探測概率、虛警概率因不同的編隊目標的特征以及不同的海情而不同，并且敵方編隊釋放沖淡干擾的情況更是未知的，因而不可能事先準確獲知L0和K0。以往的諸多部分匹配理論應用實例中，形狀是由大量的點構成，一般通過事先大致估計得到L和K的取值。此時，由于(L?L0)/p以及(K?K0)/q很小，因而對匹配結果的影響較小。但本文研究中，A和B是由少量稀疏的點構成，如果通過事先大致估計得到L和K的取值，由于(L?L0)/p以及(K?K0)/q較大，會顯著增大匹配誤差。

本文通過定義一種新的部分Hausdorff距離提出了一種新的部分匹配途徑。該新途徑下不需要事先確定L和K的值，也不需要通過設置門限來剔除外部點(其定義見2.2節(jié))，而是逐個剔除最能引起兩個形狀不相似的外部點，自適應獲取最優(yōu)L0和K0。

此外，進行部分匹配時需要獲得兩個點集在所有可能的平移和旋轉(zhuǎn)變換下的“最小距離”。對于兩個編隊之間的平移和旋轉(zhuǎn)變換，可用剛體變換來統(tǒng)一描述?！白钚【嚯x”對應的剛體變換就是“最佳匹配位置”。因此，獲取“最小距離”的過程也是搜索“最佳匹配位置”的過程。為了減輕計算負擔，本文設計一種二級匹配模型來搜索最佳匹配位置。在最佳匹配位置下，兩個點集的對應點之間距離最近，因而可在此最佳匹配位置下采用最近鄰準則獲取對應點，從而實現(xiàn)預定目標選擇。本文采用了雙向最近鄰準則來選擇對應點以提高選擇結果的正確概率。

2 部分匹配

2.1 Hausdorff距離

其中，

h(A,B)稱為從A到B的單向Hausdorff距離。它對A中各個點按照其到B中最近點的距離進行了有效的排序，并用最大值點(也就是A中最不匹配的點)作為結果距離。同理可定義從 B到A的單向Hausdorff距離h(B,A)。H(A,B)是h(A,B)和h(B,A)的最大值，通過測量A中到B中任何點距離最遠的點，以及測量B中到A中任何點距離最遠的點，H(A,B)就度量了A、B之間的不匹配程度。

從A到B的部分Hausdorff距離為

對于給定的點集A和B，Hausdorff距離[5]定義為：

其含義是：對于A中等每個點，計算它到B中與之距離最近點的距離，然后按照這個距離值對A中的所有點進行排序，并選取序列的第L個值作為結果。可見hL(A,B)自動從A中選擇了L個最佳匹配點。同理可定義從B到A的部分Hausdorff距離hK(B,A)。

2.2 部分匹配新途徑

兩個存在部分相似性的點集A和B，必然存在A中L0個點構成的子集 0LA與B中K0個點構成的子集BK0之間最相似，于是L0和K0就是K和L的最優(yōu)值。稱構成 0LA和BK0的點為“共同點”，其余點為“外部點”。共同點表示了形狀的相似部分，外部點表示了引起形狀不相似的那些點，匹配過程希望保留共同點，同時剔除或削弱外部點的影響。

假設給定的點集A和B 已處于最佳匹配位置(搜索最佳匹配位置的方法將在3.2節(jié)介紹)，若h(A,B)>h(B,A)，說明最能引起A、B不相似的點在A中，否則在B中。如果最能引起A、B不相似的外部點在A中，剔除它之后，A中剩余點構成的形狀與B的不相似程度應減??；如果最能引起A、B不相似的外部點不在A中，剔除A中一個點后，A中剩余點構成的形狀與B的不相似程度不會減?。蝗绻鸄和B中不存在外部點，那么從A中剔除任何一個點(也就是剔除了一個共同點)后，A中剩余點構成的形狀與B的不相似程度一定會增大。基于上述事實，定義從A到B的新的部分Hausdorff距離(New Partial Hausdorff Distance，NPHD)為

式中，Ap-1為由hp-1(A,B)所確定的A的子集，Hp-1(A,B)的作用是考察從A中去掉一個點后對兩個形狀相似程度的影響。

首先計算hp-1(A,B)，獲得剔除A中一點后的剩余部分 Ap-1，然后計算 B到Ap-1的不相似程度h(B,Ap-1)，取h(B,Ap-1)和hp-1(A,B)的最大值為剔除A中一點之后兩個形狀的不相似程度，即Hp-1(A,B)。若Hp-1(A,B)H(A,B)，說明此過程剔除了A、B的共同點；若Hp-1(A,B)=H(A,B)，說明最能引起A、B不相似的點不在A中。

以往定義的hL(A,B)可以獲得A中的一系列子集AL(L=1,…,p?1)，但hL(A,B)不能檢測出剔除共同點的操作。在NPHD 定義中通過計算h(B,Ap-1)，使得剔除共同點的操作得以體現(xiàn)。因此在NPHD 定義下，任何破壞兩個形狀相似性的部分形狀增減都會通過它體現(xiàn)出來。

同樣可以定義從B到A的NPHD為：

式中，Bq-1為由hq-1(B,A)所確定的B的子集，Hq-1(B,A)的作用是考察從B中去掉一個點后對A、B形狀相似程度的影響。

基于上述NPHD的定義，可通過如下程序逐個剔除最能引起兩個點集不相似的點，最終獲取最佳的部分形狀。

1)初始化。讓A、B作為初始處理點集，計算h(A,B)、h(B,A)和H(A,B)。

2)若h(A,B)>h(B,A)，則轉(zhuǎn)至3)，否則轉(zhuǎn)至4)。

3)從A中剔除外部點。計算hp-1(A,B)、h(B,Ap-1)和Hp-1(A,B)，若：① Hp-1(A,B)

4)從B中剔除外部點。計算hq-1(B,A)、h(A,Bq-1)和Hq-1(B,A)，若：① Hq-1(B,A)

上述部分匹配途徑無需事先人工設定任何參數(shù)。且由于NPHD 能檢測到最能引起兩個形狀不匹配的點，通過不斷檢測并剔除最能引起兩個形狀不匹配的點就可以減少外部點的干擾，同時NPHD 能夠敏感于剔除共同點的操作，確保不損失形狀的相似信息，因此能夠自動獲取最優(yōu)部分形狀 AL0和BK0。

3 算法實現(xiàn)

3.1 最小NPHD

在導彈慣性導航期間，由于艦艇編隊整體可能存在一致平移運動，并且彈上導航系統(tǒng)存在導航位置誤差，因此XOZ 平面上的兩個點集存在位置平移，又由于編隊整體可能的一致轉(zhuǎn)向運動，彈上導航系統(tǒng)存在導航姿態(tài)誤差，并且發(fā)射平臺的導航設備與彈上導航設備存在初始對準誤差，因而這兩個點集還存在位置旋轉(zhuǎn)。這兩個點集之間的平移和旋轉(zhuǎn)可以統(tǒng)一用剛體變換來描述。

NPHD 用來度量兩個固定位置點集之間的距離。對于存在剛體變換的兩個點集，所關心的是所有可能的匹配位置下的最小NPHD。剛體變換下的最小NPHD 定義為

和

式中：t為加在A中各點的平移量；θ為施加在A中各點的旋轉(zhuǎn)量；⊕為標準的閔可夫斯基(Minkowski)求和符號，也就是說A⊕t={a+t|a∈A}；Rθ為旋轉(zhuǎn)矩陣；最小NPHD 所對應的t和θ就是最佳匹配位置。

3.2 搜索最佳匹配位置

為了獲得各種可能的剛體變換下的最小NPHD和最佳匹配位置，提出二級匹配模型：粗匹配和精匹配。首先，是進行粗匹配。粗匹配過程又分為3步，第一步是獲得可能的平移；第二步是從這些可能平移上找到最可能是最佳匹配位置的剛體變換位置；第三步是從這些可能是最佳匹配位置的剛體變換位置中計算NPHD最小的位置。然后，進行精匹配。在粗匹配得到的最佳匹配位置附近尋找更優(yōu)的匹配位置，是對粗匹配結果的微調(diào)，且精匹配過程又可分2個步驟實現(xiàn)。下面詳細闡述上述5個實現(xiàn)步驟。

第一步：獲取粗匹配的可能平移。

某一次剔除外部點的操作中，設A中元素個數(shù)為M(M≤p)，B中元素的個數(shù)為N(N≤q)。首先，假設A中的某一點a在B中存在對應點。平移A 使a與B中的每一個點重合就可構成N個平移，這其中一定包含了a與其B中對應點重合的情況。如果A、B之間不存在旋轉(zhuǎn)，那么這個使對應點重合的平移一定是這N個平移中最接近最佳匹配位置的一個。盡管A中有M個點，但只需要其中一個在B中存在對應點的點進行N次平移就可以找到近似的最佳匹配位置。但通常無法保證這個任意選取的A中的點在B中一定存在對應點。如果所選擇的a 由于某種原因在B中沒有出現(xiàn)，也就是說它在B中不存在對應點，那么這N個平移都將偏離最佳的匹配位置較大的距離。為了確保所選擇的A中的點至少有一個在B中存在對應點，可以從A中選擇多個(M0個)點，將這些點分別平移到與B中的每個點重合，顯然會有M0?N個平移。M0的取值可根據(jù)火控雷達獲取目標信息時可能的海面干擾情況以及末制導雷達的探測概率大致確定。若火控雷達探測編隊時海面不存在沖淡干擾，且末制導雷達對目標的探測概率為1，可以取M0=1，否則需要增大M0。當M0=M時，可以肯定至少存在一個組對應點，除非末制導雷達根本沒有探測到任何真實的目標。

第二步：獲取粗匹配的可能剛體變換位置。

對于第一步獲取的M0?N個平移，每個平移位置上還需要考慮旋轉(zhuǎn)。每個平移都是由A中某點平移到與B中某點重合的結果。取該平移上的旋轉(zhuǎn)中心為其所對應的A中的點。假設A和B之間最大的可能旋轉(zhuǎn)變化為其中，dθ1是旋轉(zhuǎn)步長，i=?Nc1∶1∶Nc1為旋轉(zhuǎn)系數(shù)。平移與旋轉(zhuǎn)組合后構成M0?N?(2Nc1+1)個剛體變換位置。

仿照文獻[12]的方法，可從所有的剛體變換中找到那些是最佳匹配位置的可能性較大的位置，并存儲它們，隨后在這些存儲的位置上應用NPHD，從中找出最佳的匹配位置。對于某一個剛體變換位置，對A中的每一個點a 定義一個以該點為中心、半邊長為ρ(本文取3 km)的正方形鄰域，如果有B中的點位于此鄰域內(nèi)，就稱a在B中存在對應點。定義

式中，r為小于1的測量系數(shù)，可根據(jù)經(jīng)驗或試驗給出，本文取0.6。

如果某一個剛體變換位置下A中有對應點的元素個數(shù)大于Ms，那么這個剛體變換位置就添加到可能的最佳匹配位置數(shù)組中。對每一個位置進行以上操作，最后剩下的可能最佳匹配位置相對M0?N?(2N1c+1)要小得多。

在本文的仿真實驗中，對圖1中的3個編隊情形，通過該措施篩選出來的最佳匹配位置分別只占M0?N?(2N1c+1)個剛體變換位置的26.16%、27.47%和27.62%。由于計算Ms(僅包含比較運算)的耗時小于計算NPHD(包含乘法運算)的耗時，本文仿真實驗中，采用該措施后，針對圖1中3個編隊的預定目標選擇算法平均耗時降低了41.46%。

第三步：獲取最佳粗匹配位置。

對第二步獲取的每一個可能的最佳匹配位置計算 NPHD，進行部分匹配(剔除外部點)，并選擇NPHD最小的位置作為最佳粗匹配位置。

第四步：選取精匹配的可能匹配位置。

粗匹配過程剔除了部分外部點，且將模板中的點整體平移和旋轉(zhuǎn)到了很接近最佳匹配的位置。但為了進一步剔除外部點，并使各個對應點之間的距離更加接近，需要在最佳粗匹配位置附近搜索更優(yōu)的變換位置。如果說粗匹配過程是一個粗調(diào)過程，那么精匹配過程就是一個微調(diào)過程。取兩個坐標軸方向上的平移范圍為±(Nt?dx)和±(Nt?dz)，dx和dz為步長，i=?Nt∶1∶Nt為平移系數(shù)。

第五步：獲取最佳匹配位置。

對精匹配時選取的每一個可能的匹配位置計算NPHD，進行部分匹配(進一步剔除外部點)，并選擇NPHD最小的位置作為最佳匹配位置。

3.3 獲取對應點

獲取最佳匹配位置的過程就是不斷將A中的點移動到B中對應點附近的過程。因此，在最佳匹配位置下，對于A中的每一點，B中與之距離最近的點最可能是其對應點，反之亦然。

實現(xiàn)預定目標選擇，實際上就是進行對應點的配對，為了提高所選擇結果的正確概率，本文采用雙向最近鄰準則來獲取對應點，即對于A中的某點a，在最佳匹配位置下，可得到B中距離a最近的點為b，若同時A中距離b最近的點為a，那么a和b是對應點，否則不然。

這種雙向最近鄰準則可以處理A中的預定目標在B中沒有出現(xiàn)的情況。如果從火控雷達探測到的編隊中選擇的預定目標a1沒有被末制導雷達探測到，盡管B中存在距離a1最近的點，但該點在A中與之最近的那個點卻并非a1，因此a1不會出現(xiàn)在對應點結果中。

4 仿真試驗

4.1 仿真設置

為了考察本文預定目標選擇方法的抗干擾能力，并與以往的基于編隊相互位置關系的預定目標選擇方法進行比較，在Matlab 下進行了仿真實驗。

由于探測概率小于1、虛警概率大于0都是和沖淡干擾一樣引起兩個點集元素數(shù)目的不一致，因而在仿真實驗中假設探測概率為1，虛警概率為0，僅對沖淡干擾的數(shù)目進行了調(diào)整，這不影響實驗的可信性。

設XOZ坐標系下真實的編隊隊形如圖1所示，各編隊中“a1”為預定目標，且讓預定目標a1的坐標都統(tǒng)一為(100 km,0)。編隊1的其余4個目標等方位間距分布在半徑為R=5 km的圓周上，θ=35 °。編隊2 構成人字形編隊，編隊中相鄰目標的間距為5 km。編隊3 構成菱形編隊，編隊中相鄰目標的間距也為5 km，a1和a3距離也為5 km。用阿拉伯數(shù)字對每個編隊目標編號。這些編隊位置數(shù)據(jù)稱為原始數(shù)據(jù)，每次仿真實驗的火控數(shù)據(jù)A和末制導雷達數(shù)據(jù)B都以這些原始數(shù)據(jù)為基礎產(chǎn)生。

A是在原始數(shù)據(jù)的基礎上增加了m個干擾(每個干擾產(chǎn)生在隨機的一個目標附近，方位隨機均勻分布，且干擾離此隨機目標平均距離為1.2 km，高斯均方差為0.2 km)。此外，A 還相對原始數(shù)據(jù)平移了(1.2 km，1.3 km)，旋轉(zhuǎn)了1°，并通過疊加火控雷達在X和Z方向上的高斯定位誤差(均方差分別為0.2 km、0.6 km)來模擬形狀的扭曲。

B是在原始數(shù)據(jù)的基礎上受到了嚴重的沖淡干擾，n個目標(編號隨機等概率)按照90°的方位間隔各自釋放4個沖淡干擾(實際方位為正態(tài)分布隨機數(shù)，均值為瞄準方位，均方差為5°)，沖淡干擾的發(fā)射距離為高斯分布，均值為1.2 km，均方差為0.2 km，且各個沖淡發(fā)射互不相關。此外B相對原始數(shù)據(jù)在X和Z方向上的平移量是不相關的零均值高斯形式，均方差分別為5 km、4.6 km，以此來模擬自控段的導航誤差。另外，且B相對A 旋轉(zhuǎn)了4°?？紤]到末制導雷達在X和Z方向上有高斯定位誤差，且編隊的不一致運動也會造成形狀扭曲，一并通過疊加高斯誤差(均方差分別為0.02 km、0.5 km)來模擬形狀的扭曲。

對m、n的多個取值組合各進行了200次蒙特卡洛實驗，并統(tǒng)計預定目標選擇概率。

4.2 處理過程示例

本文所提出的預定目標選擇方法對編隊1的某一次實驗所用的仿真數(shù)據(jù)及其處理過程的數(shù)據(jù)狀態(tài)如圖2所示(非零阿拉伯數(shù)字代表了該位置目標在原始仿真數(shù)據(jù)中的編號，“0”表示干擾，m=2，n=2)。

圖2 試驗產(chǎn)生仿真數(shù)據(jù)及其處理過程的數(shù)據(jù)狀態(tài)

圖2中，c)為粗匹配的結果，可見通過粗匹配剔除了部分干擾。圖2d)為精匹配結果，可見經(jīng)過精匹配進一步剔除了一些干擾。圖2e)為雙向最近鄰準則選擇到的對應點。返回的最后對應點中，盡管目標4的對應點錯誤地選擇為一個干擾，這個錯誤選擇的后果也不至于完全使導彈攻擊任務失敗。因為這個干擾離目標4 很近，將此干擾的位置作為后續(xù)制導的測量仍可以引導導彈飛向目標位置附近，可以通過后續(xù)的一些手段來重新捕獲目標4。

4.3 抗干擾能力

表1給出了本文方法和基于編隊相互位置關系方法的抗干擾能力。干擾不存在時，兩種方法都具有很高的預定目標選擇概率，但干擾存在時，本文方法明顯優(yōu)于基于編隊相互位置關系的方法。此外，編隊隊形對算法性能存在影響，構成隊形的艦艇數(shù)目越多，則干擾對預定目標選擇概率的影響越小。由于編隊3的數(shù)據(jù)點最少，因而其預定目標選擇平均概率低于另外兩個編隊。

表1 不同干擾程度下的預定目標選擇概率

5 結論

本文用基于Hausdorff距離的點集匹配理論處理反艦導彈對艦艇編隊中預定目標的選擇問題，即用火控雷達提供編隊信息作為模板，從末制導雷達獲得的編隊信息中尋找對應點。提出了一種基于Hausdorff距離的部分匹配新途徑，能在自適應剔除干擾的影響的同時保留形狀的相似部分。

仿真試驗表明本文提出的方法具有較強的對抗沖淡干擾的能力，且抗干擾能力優(yōu)于以往的基于編隊相互位置關系的方法。

值得注意的是，當火控雷達得到的編隊目標數(shù)據(jù)存在干擾時，就可能選擇到一個干擾作為預定目標，這將使本文算法失去意義。在仿真試驗中，假設了裝定的預定目標全是真實目標。如何在干擾環(huán)境下從火控數(shù)據(jù)中選擇出預定目標，涉及到火力分配和射前識別干擾等因素，這是需要進一步深化研究的課題。

[1]盧毅,姜永華.反艦導彈目標選擇的一種新方法[J].航空學報,2010,31(4):778-784.

[2]沈建鋒.艦艇隊形識別目標選擇算法[J].火力與指揮控制,2010,35(9):98-100.

[3]潘哲.一種反艦導彈目標選擇混合算法[J].戰(zhàn)術導彈技術,2010(3):48-52.

[4]盧毅,姜永華,劉興明,等.一種基于Hausdorff距離的反艦導彈預定目標選擇方法[J].數(shù)據(jù)采集與處理,2011,26(2):146-151.

[5]HUTTENLOCHER D P,KLANDERMAN G A,RUCKLIDGE W J.Comparing images using the Hausdorff distance[J].IEEE Trans.on Pattern Analysis and Machine,1993,15(9):850-863.

[6]TAN H C,ZHANG Y J.Computing Eigenface from Edge Images for Face Recognition Based on Hausdorff Distance[C]//Proceedings of IEEE International Conference on Image and Graphics.2007:639-644.

[7]PAUMARD J,AUBOURG E.Adjusting astronomical images using a censored Hausdorff distance[C]//Proceedings of IEEE International Conference on Image Processing.1997:232-235.

[8]HAN I,YUN I D,LEE S U.Model-based object recognition using the Hausdorff distance with explicit pairing[C]//Proceedings of IEEE International Conference on Image Processing.1999:83-87.

[9]RUCKLIDGE W J.Locating objects using the Hausdorff distance.In:Proceedings of IEEE International Conference on Computer Vision.1995:457-464.

[10]KWON O K,SIM D G,PARK R H.New Hausdorff distances based on robust statistics for comparing images[C]//Proceedings of IEEE International Conference on Image Processing.1996:21-24.

[11]HUTTENLOCHER D P,LILIEN R H,OLSON C F.View-based recognition using an eigenspace approximation to the Hausdorff measure[J].IEEE Transactions on Pattern Analysis and Machine.1999,21(9):951-955.

[12]ZHANG Z,HUANG S,SHI Z.A fast strategy for image matching using Hausdorff distance[C]//Proceedings of IEEE International Conference on Robotics,Intelligent Systems and Signal Processing.2003:915-919.