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

?

基于Hough變換和聚類的艦艇編隊(duì)隊(duì)形識(shí)別算法

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

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

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

0 引言

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

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

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

圖2 日本海軍八八艦隊(duì)防空隊(duì)形示意圖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)與線的對(duì)偶性，將原始量測(cè)空間中給定的曲線通過曲線表達(dá)形式變?yōu)閰?shù)空間的一個(gè)點(diǎn)。這樣就把原始圖像中給定曲線的檢測(cè)問題轉(zhuǎn)化為尋找參數(shù)空間中的峰值問題，也即把檢測(cè)整體特性轉(zhuǎn)化為檢測(cè)局部特性，可以檢測(cè)直線、圓、橢圓、圓弧等基本形狀［4 -5］。

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

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

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

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

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

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

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

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

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

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

聚類的原理如下：將數(shù)據(jù)點(diǎn)到類中心的某種距離之和作為優(yōu)化的目標(biāo)函數(shù)，通常采用歐氏距離作為相似度度量方法，通過一系列的迭代運(yùn)算使得目標(biāo)函數(shù)值最小，從而得到對(duì)應(yīng)初始聚類中心向量的最優(yōu)分類。假設(shè)X =（x1，x2，…，xn）是具有n個(gè)數(shù)據(jù)對(duì)象的集合，xi=（xi1，xi2，…，xim），i = 1，2，…，n是具有m維變量的數(shù)據(jù)對(duì)象，目標(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所含的任一樣本對(duì)象；cj（j = 1，2，…，k）是類Wj中樣本的平均值（聚類中心）；nj表示類Wj中的數(shù)據(jù)樣本數(shù)目；目標(biāo)函數(shù)E是關(guān)于樣本和聚類中心的函數(shù)，E的值取決于k個(gè)聚類中心，迭代過程中應(yīng)尋求使E值最小的聚類結(jié)果。

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

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

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

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

3 算法流程

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

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

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

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

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

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

步驟4：對(duì)于矩陣ρ＇中的所有元素ρ＇（i，m，k），考察在其相鄰的長(zhǎng)和寬分別為Δρ和Δθ的區(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）.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 算法分析

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

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

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

［1］ 沈建鋒.艦艇隊(duì)形識(shí)別目標(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)斗艦艇隊(duì)形自動(dòng)識(shí)別研究［J］.計(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變換的線型群體隊(duì)形識(shí)別方法［J］.國防科技大學(xué)學(xué)報(bào)，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é)報(bào)，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變換檢測(cè)圓的方法［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，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

中圖分類號(hào)：TP391

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

文章編號(hào)：1000-1093（2016）04-0648-08

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

收稿日期：2015-08-06

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

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