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

張翼飛，董受全，畢開波（海軍大連艦艇學院導彈系，遼寧大連116018）

?

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

張翼飛，董受全，畢開波
（海軍大連艦艇學院導彈系，遼寧大連116018）

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

關鍵詞：飛行器控制、導航技術；隊形識別；Hough變換；改進K均值聚類；峰值聚類

0 引言

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

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

圖1 美遠征打擊大隊雙縱隊隊形示意圖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提出，它所實現的是一種從圖像空間到參數空間的映射關系。Hough變換的基本原理是利用點與線的對偶性，將原始量測空間中給定的曲線通過曲線表達形式變為參數空間的一個點。這樣就把原始圖像中給定曲線的檢測問題轉化為尋找參數空間中的峰值問題，也即把檢測整體特性轉化為檢測局部特性，可以檢測直線、圓、橢圓、圓弧等基本形狀［4 -5］。

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

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

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

圖3 標準Hough變換檢測直線示意圖Fig. 3 Normal Hough transform for line detection

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

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

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

2 改進K-均值聚類算法

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

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

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

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

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

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

式中：F（D，L）稱為距離比值函數。當距離比值函數達到最小值時，空間聚類結果為最優。距離比值函數根據（5）式計算：

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

3 算法流程

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

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

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

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

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

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

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

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

步驟5：根據局部峰值的個數n確定聚類數的最大值kmax，再根據（4）式和（5）式確定最佳聚類個數k*和初始聚類中心（j =1，2，…，k）.令初始迭代次數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：根據（3）式更新k個聚類中心，Cj（t +表示第j類的對象數目，根據（2）式計算出此時的準則函數值E1.

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

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

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

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

4 仿真實驗結果

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

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

圖5 標準Hough變換識別編隊隊形示意圖Fig. 5 Normal Hough transform for formation recognition

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

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

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

從表1的實驗結果可以看出，隊形識別的正確率隨著Δθ和Δρ的變化差異較大。Δθ取0. 3 rad，Δρ取1時，識別正確率最高。Δθ和Δρ的取值過大或過小，識別正確率都將降低。這是因為：Δθ和Δρ取值越小，參數空間劃分越細，局部峰值點越多；Δθ 和Δρ取值越大，參數空間劃分越粗，局部峰值點越少。局部峰值點太多或太少，都對聚類結果不利，降低了隊形識別的正確率。

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

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

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

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

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

5 算法分析

5. 1 算法復雜度分析

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

關于Hough變換算法：設探測得到的數據點有n個，將θ在［0，π）區間內按Δθ間隔進行離散可得到約M個采樣值，將ρ按量化間隔Δρ進行量化分區可得到Q個采樣值，則參數空間積累矩陣A的維數即空間復雜度為M×Q，標準Hough變換的計算量為n×M×Q，即時間復雜度為O（N2）.

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

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

5. 2 目標位置散布誤差影響

算法的精度除受算法本身設計因素的影響外，受目標位置散布圓概率誤差和初始目標指示誤差的影響最大。目標位置散布圓概率誤差和初始目標指示誤差越大，相當于探測噪聲越大，則經Hough變換后的峰值簇擁現象越嚴重，嚴重時采用K-均值聚類算法對峰值點進行聚類后可能會得到多個聚類中心，出現錯誤的識別結果。

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

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

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

6 結論

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

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

參考文獻（References）

［1］ 沈建鋒.艦艇隊形識別目標選擇算法［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］ 喬冰，肖濱.基于模板匹配的戰斗艦艇隊形自動識別研究［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］.國防科技大學學報，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，Feng 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］.兵工學報，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值優化問題研究［J］.系統工程理論與實踐，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］ 祁亞芳，楊明.一種改進的隨機Hough變換檢測圓的方法［J］.數學的實踐與認識，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

文獻標志碼：A

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

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

收稿日期：2015-08-06

基金項目：海軍裝備部軍內科研項目（2012年）

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