基于Hough變換和聚類的艦艇編隊隊形識別算法

張翼飛，董受全，畢開波（海軍大連艦艇學(xué)院導(dǎo)彈系，遼寧大連116018）

?

基于Hough變換和聚類的艦艇編隊隊形識別算法

張翼飛，董受全，畢開波
（海軍大連艦艇學(xué)院導(dǎo)彈系，遼寧大連116018）

摘要：編隊隊形識別技術(shù)是反艦導(dǎo)彈武器系統(tǒng)目標(biāo)識別領(lǐng)域中的一項重要研究內(nèi)容，具有隊形識別能力的反艦導(dǎo)彈可以有效增強(qiáng)對密集型艦艇編隊當(dāng)中重要目標(biāo)的選擇能力，進(jìn)而直接提升導(dǎo)彈的命中概率和作戰(zhàn)效能?；贖ough變換技術(shù)研究了一種艦艇編隊隊形識別算法，在無探測噪聲影響時具有很好的識別率。當(dāng)目標(biāo)信息受污染較嚴(yán)重時，進(jìn)一步采用了改進(jìn)的K均值聚類算法對Hough變換后得到的積累矩陣局部峰值進(jìn)行聚類處理，根據(jù)峰值聚類的結(jié)果準(zhǔn)確提取出待識別隊形的參數(shù)，從而有效抑制了探測噪聲帶來的不利影響。仿真結(jié)果表明，采用該算法可以正確識別出艦艇編隊隊形，在目標(biāo)信息受污染較嚴(yán)重時也具有較好的識別效果，具有較好的魯棒性。對該算法復(fù)雜度及目標(biāo)指示誤差對算法精度的影響進(jìn)行了分析。

關(guān)鍵詞：飛行器控制、導(dǎo)航技術(shù)；隊形識別；Hough變換；改進(jìn)K均值聚類；峰值聚類

0 引言

對日趨先進(jìn)的反艦導(dǎo)彈的威脅，世界各國都傾向于組成由多種艦艇混合編成的作戰(zhàn)艦艇編隊，實(shí)現(xiàn)艦艇間的優(yōu)勢互補(bǔ)，形成綜合的作戰(zhàn)體系。不同的艦艇編隊，有著不同的戰(zhàn)斗使命，各個目標(biāo)的戰(zhàn)術(shù)價值各不相同，如航母編隊中戰(zhàn)術(shù)價值大的目標(biāo)是航母，護(hù)航運(yùn)輸編隊中戰(zhàn)術(shù)價值大的目標(biāo)是滿載的運(yùn)輸船。而在戰(zhàn)時，我方編隊的火力受實(shí)際情況的限制，并不能對敵方編隊內(nèi)的所有目標(biāo)進(jìn)行打擊，這就要求盡可能地提高導(dǎo)彈武器系統(tǒng)的作戰(zhàn)效能。在現(xiàn)代海戰(zhàn)，尤其是在低強(qiáng)度的海上局部戰(zhàn)爭中，只要能重創(chuàng)或擊沉敵水面艦艇編隊中戰(zhàn)術(shù)價值大的目標(biāo)，即可有效阻止敵實(shí)現(xiàn)其戰(zhàn)術(shù)意圖，甚至起到威懾作用，使敵放棄使用武力或武力干涉。具有編隊識別能力的反艦導(dǎo)彈，可從敵方艦艇編隊中選擇高戰(zhàn)術(shù)價值目標(biāo)進(jìn)行精確打擊，只需為數(shù)不多的導(dǎo)彈即可達(dá)成戰(zhàn)術(shù)目的，從而提高反艦導(dǎo)彈武器系統(tǒng)的戰(zhàn)斗效能與效費(fèi)比。因此，研究適用于反艦導(dǎo)彈的艦艇編隊隊形識別算法具有非常重要的軍事意義和應(yīng)用價值［1］。

文獻(xiàn)［2 - 3］研究了基于模板匹配技術(shù)的隊形識別方法，但這些方法需要將待識別隊形與各種隊形模板一一進(jìn)行匹配，當(dāng)隊形模板數(shù)量較多時，匹配計算量較大，在目標(biāo)信息不完整和含有雜波情況下，匹配精度不高。為此，本文提出利用圖像處理領(lǐng)域中用于識別圖像幾何形狀的一種有效算法—Hough變換算法來研究艦艇編隊隊形識別方法。常見的艦艇編隊隊形大都是由各種線形或環(huán)形隊列組成。圖1所示為美軍遠(yuǎn)征打擊大隊的雙縱隊隊形，主要由兩個雙線形縱隊組成。圖2所示為日本海軍八八艦隊的防空隊形，防御圈最外部的5艘艦艇構(gòu)成了圓環(huán)形隊列，圓環(huán)內(nèi)部則由兩個“人”字型線形隊列構(gòu)成。因此，只要能從目標(biāo)偵測信息中識別出基本的線形或環(huán)形形狀，就可以判斷出艦艇編隊的隊形構(gòu)成。

圖1 美遠(yuǎn)征打擊大隊雙縱隊隊形示意圖Fig.1 Double column formation of American expedition units

圖2 日本海軍八八艦隊防空隊形示意圖Fig. 2 Air defense formation of Japanese eight-eight fleet

1 Hough變換算法

Hough變換算法于1962年由Paul Hough提出，它所實(shí)現(xiàn)的是一種從圖像空間到參數(shù)空間的映射關(guān)系。Hough變換的基本原理是利用點(diǎn)與線的對偶性，將原始量測空間中給定的曲線通過曲線表達(dá)形式變?yōu)閰?shù)空間的一個點(diǎn)。這樣就把原始圖像中給定曲線的檢測問題轉(zhuǎn)化為尋找參數(shù)空間中的峰值問題，也即把檢測整體特性轉(zhuǎn)化為檢測局部特性，可以檢測直線、圓、橢圓、圓弧等基本形狀［4 -5］。

Hough變換算法與傳統(tǒng)的模板匹配類隊形識別算法在隊形識別的原理和方法上完全不同，它具有如下一些明顯優(yōu)點(diǎn)：1）利用圖像識別方法可以從整體上一次性檢測和識別出編隊隊形，不需要根據(jù)隊形模板庫進(jìn)行一一匹配，計算簡單，計算量相對較?。?）根據(jù)局部度量來計算全部描述參數(shù)，對于區(qū)域邊界被噪聲干擾或被其他目標(biāo)遮蓋而引起邊界發(fā)生某些間斷的情況，仍具有較好的識別效果，具有一定的容錯性和魯棒性。

利用Hough變換識別形狀的方法如下（以檢測直線為例），對于直角坐標(biāo)空間中過某一點(diǎn)（x，y）的任意一條直線，其極坐標(biāo)方程可表示為如下形式［6］：

式中：ρ為從極坐標(biāo)原點(diǎn)到該空間內(nèi)直線所引的垂線長度（可正可負(fù)）；θ為此垂線與橫軸所成的夾角。如果把直角坐標(biāo)空間看作原始量測空間，極坐標(biāo)空間看作參數(shù)空間，這樣，量測空間中的任意一點(diǎn)（xi，yi）將對應(yīng)參數(shù)空間中的一條正弦曲線。量測空間中位于同一直線上的點(diǎn)確定了參數(shù)空間的多條正弦曲線，且這些正弦曲線交于同一點(diǎn)（θ0，ρ0），此交點(diǎn)即確定了原量測空間中直線的參數(shù)。圖3給出了檢測直線的標(biāo)準(zhǔn)變換示意圖。將圖3（a）中位于同一直線上的4個點(diǎn)按（1）式進(jìn)行標(biāo)準(zhǔn)Hough變換后，就可得到如圖3（b）所示的映射圖。這樣，如果把量測空間上各點(diǎn)的能量分布到相應(yīng)的Hough參數(shù)空間的正弦曲線上并進(jìn)行疊加，在這些正弦曲線的交點(diǎn)上將會出現(xiàn)一個峰值。因此，判斷量測空間中的各點(diǎn)是否在一條直線上，就等價于在θ-ρ平面內(nèi)找到一簇正弦曲線的交點(diǎn)。

圖3 標(biāo)準(zhǔn)Hough變換檢測直線示意圖Fig. 3 Normal Hough transform for line detection

Hough變換在檢驗(yàn)已知形狀的目標(biāo)方面具有受曲線間斷影響小和不受圖形旋轉(zhuǎn)的影響等優(yōu)點(diǎn)，即使目標(biāo)信息有稍許缺損或污染也能被識別。但在目標(biāo)信息缺損或污染較嚴(yán)重時，其識別正確率將明顯降低。如圖4（a）所示，在對排成一條直線的4個目標(biāo)進(jìn)行探測定位時，由于噪聲和電子干擾等因素的影響，存在一定距離和方位探測誤差，這將導(dǎo)致直線隊形變形為近似于直線的折線，從而影響到隊形的正確識別。

在坐標(biāo)空間中，折線可視為該折線上數(shù)條通過兩點(diǎn)之間的連線的聚類，圖4（a）中的折線ABCD可視為直線AB、BC、CD、AD等多條直線的聚類。而由點(diǎn)線對偶性可知，作為多條直線的聚類，這些折線最終可對應(yīng)到參數(shù)空間中相應(yīng)的正弦曲線的交點(diǎn)的聚類，即折線ABCD對應(yīng)于圖4（b）參數(shù)空間中的聚類區(qū)abcd.因此，只要在參數(shù)空間中將某一區(qū)域里的各個曲線交點(diǎn)正確聚類，檢測出聚類后聚焦點(diǎn)的參數(shù)，就仍然可以在噪聲干擾條件下識別得到正確的圖形信息。根據(jù)這一思路，本文采用K-均值聚類算法來處理曲線交點(diǎn)的聚類問題［7 -8］。

圖4 噪聲條件下Hough變換檢測直線示意圖Fig. 4 Hough transform for line detection with noises

2 改進(jìn)K-均值聚類算法

根據(jù)圖4所示檢測直線的仿真結(jié)果可知，在受嚴(yán)重探測噪聲干擾等情形下，即使是采用具有一定容錯性和魯棒性的Hough變換算法來檢測直線，變換后的參數(shù)空間可能還會出現(xiàn)多個峰值（實(shí)際應(yīng)為1個峰值）。但這多個峰值出現(xiàn)的位置彼此靠近，因而可以采用峰值聚類的方法提取出多個峰值的聚類中心。該中心就是實(shí)際的直線AD經(jīng)Hough變換后的參數(shù)空間交點(diǎn)，根據(jù)該交點(diǎn)參數(shù)就可以檢測出正確的直線形狀。

K-均值算法是聚類分析中基于劃分方法的一種經(jīng)典算法，它通過不斷的迭代過程來進(jìn)行聚類。當(dāng)算法收斂到一個結(jié)束條件時就終止迭代過程，輸出聚類結(jié)果。由于其算法思想簡便，又容易實(shí)現(xiàn)，因此K-均值算法己成為一種目前最常用的聚類算法之一［9 -10］。

聚類的原理如下：將數(shù)據(jù)點(diǎn)到類中心的某種距離之和作為優(yōu)化的目標(biāo)函數(shù)，通常采用歐氏距離作為相似度度量方法，通過一系列的迭代運(yùn)算使得目標(biāo)函數(shù)值最小，從而得到對應(yīng)初始聚類中心向量的最優(yōu)分類。假設(shè)X =（x1，x2，…，xn）是具有n個數(shù)據(jù)對象的集合，xi=（xi1，xi2，…，xim），i = 1，2，…，n是具有m維變量的數(shù)據(jù)對象，目標(biāo)是將數(shù)據(jù)集合X劃分為k類：W1，W2，…，Wk. K-均值聚類算法采用誤差平方和準(zhǔn)則函數(shù)作為目標(biāo)函數(shù)，利用（2）式和（3）式所定義的準(zhǔn)則函數(shù)和類中心更新公式進(jìn)行迭代聚類：

式中：xp為簇Wj所含的任一樣本對象；cj（j = 1，2，…，k）是類Wj中樣本的平均值（聚類中心）；nj表示類Wj中的數(shù)據(jù)樣本數(shù)目；目標(biāo)函數(shù)E是關(guān)于樣本和聚類中心的函數(shù)，E的值取決于k個聚類中心，迭代過程中應(yīng)尋求使E值最小的聚類結(jié)果。

傳統(tǒng)K-均值聚類算法存在兩個明顯的缺陷：一是聚類的數(shù)目即k值需要由用戶預(yù)先給出，不能自行確定；二是初始聚類中心的取值對算法的影響很大，初始聚類中心點(diǎn)選取不當(dāng)很容易造成聚類結(jié)果陷入局部最優(yōu)解，甚至導(dǎo)致錯誤的聚類結(jié)果。因此，本文對傳統(tǒng)K-均值聚類算法進(jìn)行了改進(jìn)，使得改進(jìn)后的算法可以自動給出最佳聚類數(shù)k，并通過合理確定初始聚類中心來提高聚類的準(zhǔn)確性。

最佳聚類數(shù)k的值采用（4）式來計算

式中：F（D，L）稱為距離比值函數(shù)。當(dāng)距離比值函數(shù)達(dá)到最小值時，空間聚類結(jié)果為最優(yōu)。距離比值函數(shù)根據(jù)（5）式計算：

式中：k為所要聚類的個數(shù)，k的上限值為kmax≤n （n為全部樣本的總數(shù)）［11］；cj為簇Wj所含樣本的均值；ci為除簇Wj外其他簇所含樣本的均值。因此，D定義為類內(nèi)距離，為所有聚類簇內(nèi)部距離的總和（每個簇的內(nèi)部距離為該簇內(nèi)所有樣本到其中心的距離之和）；L定義為類間距離，為每個聚類中心（簇內(nèi)樣本的均值）到其他聚類中心的距離之和。由（4）式和（5）式可知，只有類內(nèi)距離和類間距離的比值最小時的k值，才是所求的最佳聚類數(shù)k*.將此時所確定的k個類內(nèi)距離最小的聚類簇所含樣本的均值（j =1，2，…，k）作為K-均值聚類算法的初始聚類中心。

3 算法流程

以檢測多條直線組成的編隊隊形為例，基于Hough變換和K-均值聚類算法進(jìn)行隊形識別的具體計算流程如下：

輸入：所有量測空間中直線隊形上的數(shù)據(jù)點(diǎn)（xi，yi），xi和yi代表量測的位置信息。

首先采用Hough變換算法將各條直線轉(zhuǎn)換為極坐標(biāo)中的曲線，利用量化間隔Δθ和Δρ對參數(shù)空間進(jìn)行量化分區(qū)，采用累積投票的方式尋找參數(shù)空間中的各局部峰值，具體計算步驟如步驟1～步驟4所示。

步驟1：根據(jù)（1）式，按照一定的量化間隔Δθ將自變量參數(shù)θ離散化，離散取值為θk，k = 1，2，3，…，h.對于量測空間中的每個數(shù)據(jù)點(diǎn)（xi，yi）和每一個離散化的θk，計算ρik= xicos θk+ yisin θk，將所有ρik保存到矩陣ρ中。

步驟2：給定因變量量化間隔Δρ，對所有ρik進(jìn)行量化分區(qū)，離散取值為ρm，m = 1，2，3，…，l，得到矩陣ρ＇imk.

步驟3：按照劃分間隔Δθ和Δρ建立參數(shù)空間積累矩陣P，并置矩陣中的每一個元素為0.

步驟4：對于矩陣ρ＇中的所有元素ρ＇（i，m，k），考察在其相鄰的長和寬分別為Δρ和Δθ的區(qū)域內(nèi)是否存在曲線的交點(diǎn)。若有，則令A(yù)（m，k）= A（m，k）+1，交點(diǎn)越多，則A（m，k）累加值越大。從而在積累矩陣P中得到局部峰值A(chǔ)（ρpeak1，θpeak1），A（ρpeak2，θpeak2），…，A（ρpeakn，θpeakn）.

由于受探測噪聲干擾，得到的各局部峰值并不是實(shí)際的參數(shù)空間交點(diǎn)，因而需要再采用K-均值聚類算法對局部峰值點(diǎn)進(jìn)行聚類，得到真正的交點(diǎn)，從而確定直線參數(shù)。聚類時需要先確定聚類的個數(shù)，再利用迭代法確定最優(yōu)聚類中心，具體計算步驟如步驟5～步驟9所示。

步驟5：根據(jù)局部峰值的個數(shù)n確定聚類數(shù)的最大值kmax，再根據(jù)（4）式和（5）式確定最佳聚類個數(shù)k*和初始聚類中心（j =1，2，…，k）.令初始迭代次數(shù)t =1，將聚類中心記作Cj（t）（j =1，2，…，k），表示第t次迭代時第j類的中心。

步驟6：對于局部峰值集合中的每個對象Ai，計算其與各個聚類中心的歐氏距離d（Ai，Cj（t）），若滿足d（Ai，Cj（t））= min｛d（Ai，Cj（t））|j =1，2，…，k｝，則將對象Ai賦給聚類Wj：Ai→Wj.

步驟7：根據(jù)（3）式更新k個聚類中心，Cj（t +表示第j類的對象數(shù)目，根據(jù)（2）式計算出此時的準(zhǔn)則函數(shù)值E1.

步驟8：計算新的分配方式，假設(shè)Ai在類Wj中，而‖Ai- Cp（t +1）‖＜‖Ai- Cj（t +1）‖，則將對象Ai賦給聚類Wp：Ai→Wp，然后再根據(jù)（2）式計算出此時的準(zhǔn)則函數(shù)值E2.

步驟9：若| E2- E1|＜ε，則迭代停止，否則，轉(zhuǎn)步驟7.

輸出：聚類算法結(jié)束，輸出k個聚類中心A1（ρpeak1，θpeak1），A2（ρpeak2，θpeak2），…，Ak（ρpeakk，θpeakk）和迭代次數(shù)t，各個聚類中心的值代表了提取出來的直線參數(shù)，直線檢測完畢。

以上算法主要是針對直線檢測設(shè)計的。如果要識別圓形、橢圓等形狀，則需要對算法進(jìn)行改進(jìn)，以適應(yīng)不同形狀圖像檢測的要求。如檢測圓形的Hough變換算法需要用到3個參量，比直線的Hough變換多一個參數(shù)，因此算法形式更加復(fù)雜，但基本的處理過程與直線檢測一致。

4 仿真實(shí)驗(yàn)結(jié)果

以兩條直線組成的V字形艦艇編隊隊形識別為例，首先采用標(biāo)準(zhǔn)Hough變換算法得到參數(shù)空間的映射圖，如圖5（a）所示。從圖5（a）中可以很清楚地看到參數(shù)空間的曲線相交于兩點(diǎn)，把計算得到的積累矩陣局部峰值A(chǔ)（ρpeak，θpeak）在三維空間進(jìn)行繪制得到如圖5（b）所示的效果圖。

當(dāng)存在探測噪聲干擾時，艦艇編隊各探測點(diǎn)的位置將偏離直線，經(jīng)Hough變換后得到的參數(shù)空間映射圖如圖6（a）所示。從圖6（a）中可以看出，由于有噪聲影響參數(shù)空間中的曲線相交情況比較復(fù)雜，在多個點(diǎn)處均有相交。噪聲影響下的積累矩陣局部峰值圖如圖6（b）所示。從圖6（b）中可以看出，在噪聲干擾下，局部峰值圖出現(xiàn)峰值簇?fù)憩F(xiàn)象，不易判斷出真實(shí)峰值點(diǎn)的個數(shù)和位置。

圖5 標(biāo)準(zhǔn)Hough變換識別編隊隊形示意圖Fig. 5 Normal Hough transform for formation recognition

對于峰值簇?fù)砬闆r，采用K-均值聚類算法來提取局部峰值，聚類效果圖如圖7（a）所示。從圖7（a）中可以看出，盡管峰值點(diǎn)出現(xiàn)情況比較雜亂，但經(jīng)過迭代聚類后，最終把交點(diǎn)聚為兩類，確定了聚類中心的參數(shù)，從而提取出兩處局部峰值。根據(jù)峰值聚類的結(jié)果對艦艇編隊隊形進(jìn)行識別，最終的隊形識別結(jié)果如圖7（b）所示，可以看出即使存在探測噪聲影響，該算法仍然具有較高的識別率。

隊形識別算法中，對峰值點(diǎn)個數(shù)及聚類結(jié)果影響較大的是劃分間隔Δθ和Δρ的取值，通過仿真實(shí)驗(yàn)對其影響進(jìn)行了驗(yàn)證。實(shí)驗(yàn)中共構(gòu)造了100組如圖7（b）所示的不同形狀的V字形編隊。V字形編隊的隊列角β在15°～60°范圍內(nèi)變化，間隔5°取值，兩條直線上均勻分布8～12個目標(biāo)點(diǎn)，各目標(biāo)位置均疊加均值為0、均方差為0. 3的正態(tài)分布探測噪聲。Δθ在0. 1～0. 4 rad范圍內(nèi)變化，Δρ在0. 5～3范圍內(nèi)變化，仿真得到的Δθ和Δρ變化對隊形識別正確率的影響如表1所示。隊形識別正確的評判標(biāo)準(zhǔn)為峰值點(diǎn)聚類數(shù)為2，且聚類后獲得的直線斜率和截距參數(shù)與理想?yún)?shù)的偏差不大于30%.

圖6 噪聲影響下Hough變換識別編隊隊形示意圖Fig. 6 Hough transform for formation recognition with noises

從表1的實(shí)驗(yàn)結(jié)果可以看出，隊形識別的正確率隨著Δθ和Δρ的變化差異較大。Δθ取0. 3 rad，Δρ取1時，識別正確率最高。Δθ和Δρ的取值過大或過小，識別正確率都將降低。這是因?yàn)椋害う群挺う讶≈翟叫?，參?shù)空間劃分越細(xì)，局部峰值點(diǎn)越多；Δθ 和Δρ取值越大，參數(shù)空間劃分越粗，局部峰值點(diǎn)越少。局部峰值點(diǎn)太多或太少，都對聚類結(jié)果不利，降低了隊形識別的正確率。

圖7 采用K-均值聚類后編隊隊形識別結(jié)果示意圖Fig. 7 Formation recognition result after K-means clustering

表1 Δθ和Δρ對識別正確率的影響Tab. 1 The effects of Δθ and Δρ on the recognition results

Δθ=0. 3 rad和Δρ=1時，本文所采用的改進(jìn)聚類算法與普通聚類算法的對比結(jié)果如表2所示。普通聚類算法人工給定聚類個數(shù)并隨機(jī)確定初始聚類中心，改進(jìn)算法采用（4）式和（5）式來確定聚類個數(shù)和初始聚類中心。構(gòu)造的實(shí)驗(yàn)隊形包括了單橫隊、雙縱隊、V形隊和三角隊等4種隊形，分別由一條、兩條或三條直線構(gòu)成。每種隊形均構(gòu)造了100個待識別的模板，并疊加了適量的探測噪聲，同樣以聚類后獲得的直線參數(shù)與理想?yún)?shù)的偏差不大于30%作為識別結(jié)果是否正確的標(biāo)準(zhǔn)。

表2 改進(jìn)與普通聚類算法效果對比Tab. 2 The effects of f1and f2on the recognition results

從表2的實(shí)驗(yàn)結(jié)果可以看出，本文所采用的改進(jìn)聚類算法盡管在識別時間上比普通聚類算法略有增加，但在識別正確率上比普通算法要高得多。因此，本文采用的算法具有更優(yōu)越的聚類性能。

5 算法分析

5. 1 算法復(fù)雜度分析

本文所設(shè)計算法的復(fù)雜度主要受Hough變換計算復(fù)雜度和K-均值聚類計算復(fù)雜度兩方面的影響。

關(guān)于Hough變換算法：設(shè)探測得到的數(shù)據(jù)點(diǎn)有n個，將θ在［0，π）區(qū)間內(nèi)按Δθ間隔進(jìn)行離散可得到約M個采樣值，將ρ按量化間隔Δρ進(jìn)行量化分區(qū)可得到Q個采樣值，則參數(shù)空間積累矩陣A的維數(shù)即空間復(fù)雜度為M×Q，標(biāo)準(zhǔn)Hough變換的計算量為n×M×Q，即時間復(fù)雜度為O（N2）.

關(guān)于K-均值聚類算法：設(shè)聚類空間對象數(shù)目為n，聚類個數(shù)為k，聚類過程中的迭代次數(shù)為t，最優(yōu)解的上界k≤n，則K-均值聚類算法的計算量為n×k×t×n.

算法總的計算量為上述兩部分計算量之和，總體來看計算量并不大。經(jīng)過仿真測試，在Intel Core i7四核3. 5 GHz處理器的計算上采用Matlab 9. 0軟件編寫仿真程序，經(jīng)運(yùn)行后檢驗(yàn)，算法平均運(yùn)行時間不超過100 ms，表明該算法具有很好的實(shí)時性。

5. 2 目標(biāo)位置散布誤差影響

算法的精度除受算法本身設(shè)計因素的影響外，受目標(biāo)位置散布圓概率誤差和初始目標(biāo)指示誤差的影響最大。目標(biāo)位置散布圓概率誤差和初始目標(biāo)指示誤差越大，相當(dāng)于探測噪聲越大，則經(jīng)Hough變換后的峰值簇?fù)憩F(xiàn)象越嚴(yán)重，嚴(yán)重時采用K-均值聚類算法對峰值點(diǎn)進(jìn)行聚類后可能會得到多個聚類中心，出現(xiàn)錯誤的識別結(jié)果。

以圖8所示的V字形編隊為例，考慮隊形識別精確度的影響因素除了目標(biāo)位置散布圓概率誤差r0、初始目標(biāo)指示誤差δr和編隊隊形長度L外，還有編隊隊形寬度d，即還應(yīng)考慮隊列角β的影響。根據(jù)仿真計算結(jié)果：當(dāng)r0/ tanβ＜0. 2L時，算法基本可以判斷出正確的編隊隊形；當(dāng)r0/ tanβ＞0. 2L時，算法多數(shù)情況下會出現(xiàn)錯誤的識別結(jié)果。假設(shè)編隊隊形長度L =20 km，隊列角β=30°，根據(jù)上述分析，若要得到正確的編隊隊形識別結(jié)果，則目標(biāo)位置散布圓概率誤差r0應(yīng)小于2 km.由于通常取r0=3δr，因此初始的目標(biāo)指示位置誤差δr應(yīng)小于0. 7 km.

圖8 目標(biāo)指示誤差對編隊隊形識別精度的影響分析示意圖Fig. 8 Effect of target indication errors on recognition precision of formation

需要說明的是，這里的初始誤差δr指的是單個目標(biāo)相對于整體隊形的位置偏差，而不能簡單等同于探測器遠(yuǎn)程定位的誤差。對于艦艇編隊隊形識別而言，整體探測誤差可以大于單艦艇的定位誤差，因?yàn)檎w探測誤差對于每艘艦艇通常都是一樣的，并不影響編隊整體隊形形狀。只有對編隊中幾艘艦艇的定位誤差遠(yuǎn)大于對其他艦艇的定位誤差時，才有可能產(chǎn)生錯誤的識別結(jié)果。

6 結(jié)論

本文采用Hough變換技術(shù)來為反艦導(dǎo)彈武器系統(tǒng)設(shè)計艦艇編隊隊形識別算法。當(dāng)沒有探測噪聲影響時，采用標(biāo)準(zhǔn)Hough變換算法即可以準(zhǔn)確判斷出編隊隊形形狀；當(dāng)存在一定探測噪聲的影響時，可以采用K-均值聚類算法對積累矩陣局部峰值進(jìn)行聚類處理，根據(jù)峰值聚類的結(jié)果提取圖形參數(shù)后也能較好地判斷出編隊隊形的正確形狀。仿真結(jié)果表明，本文所設(shè)計的算法具有較好的適應(yīng)性和魯棒性，在目標(biāo)信息受污染較嚴(yán)重時，也具有較高的識別率。

基于Hough變換和聚類的艦艇編隊隊形識別算法不僅可用于識別線性隊形，對Hough變換公式進(jìn)行改進(jìn)后還可用于識別圓形等形狀的隊形。但進(jìn)行圓形狀的Hough變換時，參數(shù)空間的變換參數(shù)將增加為3個，相應(yīng)的K-均值算法也轉(zhuǎn)為三維空間的聚類，算法更加復(fù)雜。因此，在具體的工程應(yīng)用過程中，還應(yīng)注意算法的實(shí)時性，特別是在檢測圓、橢圓等形狀的圖形時，由于計算量劇增，更應(yīng)注意優(yōu)化算法，確保算法的實(shí)時性［12］。

參考文獻(xiàn)（References）

［1］ 沈建鋒.艦艇隊形識別目標(biāo)選擇算法［J］.火力與指揮控制，2010，35（9）：98 -100. SHEN Jian-feng. A target selection algorithm using naval ships formation identification［J］. Fire Control & Command Control，2010，35（9）：98 -100.（in Chinese）

［2］ 喬冰，肖濱.基于模板匹配的戰(zhàn)斗艦艇隊形自動識別研究［J］.計算機(jī)仿真，2006，23（9）：4 -6. QIAO Bing，XIAO Bin. Identification of combat warship formation based on template matching［J］. Computer Simulation，2006，23（9）：4 -6.（in Chinese）

［3］ 蔡益朝，張維明，賀玲，等.一種基于Hough變換的線型群體隊形識別方法［J］.國防科技大學(xué)學(xué)報，2006，28（2）：124 -130. CAI Yi-chao，ZHANG Wei-ming，HE Ling，et al. Formation recognition based on Hough transform［J］. Journal of National University of Defense Technology，2006，28（2）：124 - 130.（in Chinese）

［4］ Paulino A A，F(xiàn)eng J J，Jain A K. Latent fingerprint matching using descriptor-based Hough transform［J］. IEEE Transactions on Information Forensics and Security，2013，8（1）：31 -45.

［5］ Rodriguez L A F，Uribe J A，Bonilla J F V. Obstacle detection over rails using Hough transform［C］∥2012 XVII Symposium of Image，Signal Processing，and Artificial Vision（STSIVA）. Antioquia：IEEE，2012：317 -322.

［6］ HOUGH P V C. A method and means of recognizing complex patterns：US，3069645［P］. 1962-12-18.

［7］ Ebrahimpour R，Rasoolinezhad R，Hajiabolhasani Z，et al. Vanishing point detection in corridors：using Hough transform and K-means clustering［J］. IET Computer Vision，2012，6（1）：40 -51.

［8］ Zhou T H，Papanikolopoulos N. Enhancing the randomized Hough transform with k-means clustering to detect mutually-occluded ellipses［C］∥Proceedings of 19th Mediterranean Conference on Control & Automation. Corfu：IEEE，2011：1358 -1363.

［9］ Yu S，Tranchevent L C，Liu X H，et al. Optimized data fusion for kernel K-means clustering［J］. IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2012，34（5）：1031 -1039.

［10］ 鈕建偉，李志忠.基于形狀的三維頭面型聚類分析［J］.兵工學(xué)報，2009，30（8）：1084 -1088. NIU Jian-wei，LI Zhi-zhong. Shape-based 3D head data clustering［J］. Acta Armamentarii，2009，30（8）：1084 - 1088.（in Chinese）

［11］ 楊善林，李永森，胡笑旋，等. K-means算法中的k值優(yōu)化問題研究［J］.系統(tǒng)工程理論與實(shí)踐，2006，26（2）：97 -101. YANG Shan-lin，LI Yong-sen，HU Xiao-xuan，et al. Optimization study on k value of K-means algorithm［J］. Systems Engineering-Theory & Practice，2006，26（2）：97 - 101.（in Chinese）

［12］ 祁亞芳，楊明.一種改進(jìn)的隨機(jī)Hough變換檢測圓的方法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識，2014，44（17）：189 -195. QI Ya-fang，YANG Ming. An improved method of the randomized Hough transforms to detect the circle［J］. Mathematics in Practice and Theory，2014，44（17）：189 - 195.（in Chinese）

Warship Formation Recognition Algorithm Based on Hough Transform and Clustering

ZHANG Yi-fei，DONG Shou-quan，BI Kai-bo
（Deptment of Missile，Dalian Naval Academy，Dalian 116018，Liaoning，China）

Abstract：Formation recognition is an important research task in the area of target recognition for antiship missile weapon systems. Perfect formation recognition capability can improve the target selection of anti-ship missiles for compact warship formation，thus enhancing the hit probability and operational effectiveness of anti-ship missiles. The formation recognition algorithm is researched base on Hough transform，which has higher recognition rate without the influence of detection noise. If the target information is polluted badly，the improved K-means clustering algorithm is used to cluster the local peaks in an accumulation matrix. The shape parameters of formation to be recognized can be extracted from the clustering results so that the adverse influence due to detection noise is restrained effectively. Even though the target information is polluted badly，the algorithm has better recognition accuracy and robustness. The complexity of the algorithm and the effect of target designation error on the accuracy of the algorithm are analyzed. The simulation results show that the proposed algorithm has the perfect capability of formation recognition.

Key words：control and navigation technology of aerocraft；formation recognition；Hough transform；improved K-means clustering；peak clustering

中圖分類號：TP391

文獻(xiàn)標(biāo)志碼：A

文章編號：1000-1093（2016）04-0648-08

DOI：10. 3969/ j. issn. 1000-1093. 2016. 04. 011

收稿日期：2015-08-06

基金項目：海軍裝備部軍內(nèi)科研項目（2012年）

作者簡介：張翼飛（1976—），男，講師，博士后。E-mail：icyriver@163. com