张翼飞，董受全，毕开波（海军大连舰艇学院导弹系，辽宁大连116018）



基于Hough变换和聚类的舰艇编队队形识别算法

张翼飞，董受全，毕开波
（海军大连舰艇学院导弹系，辽宁大连116018）

摘要：编队队形识别技术是反舰导弹武器系统目标识别领域中的一项重要研究内容，具有队形识别能力的反舰导弹可以有效增强对密集型舰艇编队当中重要目标的选择能力，进而直接提升导弹的命中概率和作战效能。基于Hough变换技术研究了一种舰艇编队队形识别算法，在无探测噪声影响时具有很好的识别率。当目标信息受污染较严重时，进一步采用了改进的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