小波聚类在多目标定位中的应用

王 崛，刘文杰

(装甲兵工程学院 信息工程系，北京 100072)

随着现代战争中侦察监视装备的大量应用，基于多传感器的多目标侦察［1-2］技术应运而生，这种方法有效地改善了侦察系统的性能，将各传感器的信息资源进行了整合。但要想从大量的、复杂的、变化的数据中挖掘出目标并跟踪并非易事，这涉及到噪声的抑制，目标的分割，跟踪目标的轨迹等一系列问题。一种有效的方法是:应用聚类算法解决目标的分割以及目标的跟踪等问题。目前，已经提出的聚类方法主要有基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等［3］。其中基于划分方法的Kmeans 算法［3-4］在聚类算法中占有重要地位。该算法具有简便易实现、复杂度较低等优点，但其在应用上也明显存在缺陷，如对于大数据集的聚类执行效率低，不能发现任意形状的簇，受孤立点的影响较大，需要预先指定聚类数目等等。尤其是在解决多个运动目标的识别方面，这些缺陷都会使聚类的效果变差。

为克服传统聚类方法在解决实际问题上的缺陷，本文提出了一种基于小波技术［5］的聚类算法，简称小波聚类［6-8］，并将其应用到多传感器的多目标定位当中。小波聚类是一种多分辨率的聚类算法，它首先通过在数据空间上强加一个多维网格［9-10］结构来汇总数据，每个网格单元汇总了一组映射到该单元中的点的信息。这种汇总信息适合于在内存中进行多分辨率小波分析使用，以及随后的聚类分析。在进行小波分析时，原始数据将被变换为在不同的分辨率层次上对象间的相对距离，这使得数据的自然聚类变得更加容易区别，然后通过在新的空间中寻找高密度区域，可以确定聚类。

1 小波变换的边缘检测

小波变换是一种信号处理技术，小波变换的模极大值点对应于信号的突变点，通过检测这些模极大值点可以检测到信号的突变，利用这个原理可以进行图像边缘的检测，应用到本文就可以检测出簇，即聚类。

假设将原始数据转化为数字图像数据形式后的数据为D，具有N×N 像素点。此时，只需要在log2m+1 个尺度上对D 进行分解。选择适当的二维平滑函数θ(x，y)，定义小波构造出离散滤波器。在尺度2j上，可以采用二维离散小波变换的快速算法进行计算每一个点(n，m)的离散二进小波变换W1.d2jf(n，m)，W2.d2j(n，m)。点(n，m)的模值为

假设在J 个尺度上进行分解，在尺度s=2j(1≤j≤J)上，对可能的边缘Pj={Pj(n，m)}，1≤n，m≤N 进行连接处理，即将模值相近和相角相近的相邻奇异点进行连接，同时去掉长度小于给定阈值的短连接，这样就得到尺度s =2j(1≤j≤J)上的边缘Ej={Ej(n，m)}。其中，若(n，m)为边缘点，则Ej(n，m)=1;否则，Ej(n，m)=0。

在不同尺度上得到的边缘定位精度与抗噪性是互补的。在大尺度上，边缘比较稳定，对噪声不敏感，但是边缘的定位精度较差;在小的尺度上，边缘细节信息比较丰富，边缘定位精度较高，但对噪声比较敏感。在多尺度边缘提取中，结合大、小尺度的优势，对各尺度上的边缘图像进行综合，可以得到精确的像素边缘，也就是说可以以不同尺度从细尺度到粗尺度来聚类，选择怎样的聚类尺度可由实际情况决定。

2 小波聚类算法

小波聚类算法中主要思想是首先对输入数据进行基于网格的划分构造类似数字图像的数据，通过小波变换进行边缘检测，检测出簇边界，如图1 所示。在不同的分辨率和尺度上产生可以产生不同的簇，可根据实际情况选择分辨率和尺度。小波聚类算法的主要步骤为:

输入:多维数据对象

输出:聚类对象

1)量化数据空间，然后分配对象到网格单元，并构造数据对象到网格单元的映射表;

2)对量化后的网格数据单元应用多尺度小波变换，检测出簇的边缘，并标号;

3)给每个单元分配簇标号;

4)根据映射表将数据对象分配到簇;

5)计算聚类中心点。

图1 小波分析聚类分类演示图

进行小波聚类的第1 步就是给待聚类的数据空间强加一个多维网格结构汇总数据。假设A =Al，A2，…，Ad为有限规则集。S=A1×A2×…Ad为d维数字空间或特征空间。输入数据集为d维点{P1，P2，…，PN}的集合，其中Pi=〈Pi1，Pi2，…，Pid〉，1≤i≤N。把所有维Ai分割为m 个间隔，间隔的大小由分辨率决定，则空间S 可以分成多个长度等同连续而又不相交的单元，则称这些单元为数据单元。每个单元的形式为〈C1，C2，…，Cd〉，其中Ci=［Li，Hi)是Ai分区间的右开区间，如果Li≤Pki≤Hi，1≤i≤d，则点Pk=〈Pk1，Pk2，…，Pkd〉包含在该单元中。每个单元有一个关联它的统计参数记为c. param，本文中这个参数为数据单元格内数据点数。从数字图像处理的角度看，经过这种划分后，就将待聚类数据转化为了类似于图像数据的形式。

接下来进行多尺度的小波分解，在每个尺度上检测边缘信息，其基本步骤为:

1)求出每一个尺度s=2j(1≤j≤J)上可能的边缘Cj={Cj(n，m)};

2)对CJ={CJ(n，m)}进行连接处理，得到尺度2J上的边缘EJ={EJ(n.m)}，并令j=J;

3)针对尺度2j的边缘点(n，m)，把Cj-1在以点(n，m)为中心的3 ×3 像素区域内所有可能的边缘点均标成尺度2j-1上的候选边缘点;

4)对尺度2j-1上的所有候选边缘点进行连接处理，得到尺度Ej-1上的边缘Ej-1，并令j=j-1;

5)重复步骤3)与4)，直到j=1，边缘E1就是综合得到的簇边界;

最后对小波变换检测出的簇进行标号，给簇内每个单元分配簇标号，根据之前建立的单元格与数据对象之间的映射表，确定对象所属的聚类。采用算术平均法计算聚类中心，即

其中:n 为簇内点的个数;Xi为簇内点坐标。

3 仿真实验及分析

Matlab 是一套功能非常强大的商业数学软件，从信号处理、语音处理、数据采集、数值运算、图像处理到电子仿真，金融分析等等，几乎在各个工业领域，它都已经得到了广泛应用，同时也取得了巨大的成功。但是，由于Matlab 是用一种脚本语言，他的解释是逐行执行的，程序中所有的变量都是用MxArray 来实现的，所以为了保证通用性，它的执行效率非常低，常常看到:在开发一些复杂的算法时，通常会发现程序执行得特别慢，虽然Mathworks 公司已经在竭力提高m 脚本文件(script files)的运算速度，但目前为止效果仍然不能和实现同样功能的可执行程序相比。

基于上述考虑，本文将利用Matlab 提供的C/C ++编译器，将m 文件编译成可执行的应用程序，使用的编译环境是MS VC++ 6.0 和Matlab6.5。针对静态多目标和动态多目标侦察2 种不同的情况，本文进行2 次测试，2 组测试数据分别为:

第1 组:静态目标，有10 000个数据点，目标数目为100，并给出100 个目标中心点坐标，该数据样本具有不规则的簇分布，且含有噪声点;

第2 组:动态目标，有两批数据点，假设时间(t -t +Δt)时，有10 000个数据点，目标数目为100，并给出100 个目标中心点坐标;(t+Δt，t+2Δt)时，有1000个数据点，目标数目为100，并给出100 个目标中心点坐标。该数据样本具有不规则的簇分布，且含有噪声点;

仿真测试在联想y4 60 2.5GHz CPU 环境下进行。首先分别利用Kmeans 算法和Wavecluster 进行静态多目标定位，获取目标位置信息，选定的参数为:初始聚类数目K =100，分辨率resolution=1，数据维度Dimensions=2，采用的小波为二进小波。其结果如表1 所示。

表1 静态多目标定位结果

从表1 中可以看出，相比于传统的Kmeans 算法，Wavecluster 算法在处理簇分布不均匀、含有噪声的大规模数据集时，聚类结果更加精确和细致。

然后利用基于时间窗口的Kmeans 算法和Wavecluster算法进行动态多目标定位，获取目标位置信息，选定的参数为:初始聚类数目K =100，分辨率resolution =1，数据维度Dimensions=2，时间窗口W = Δt，采用的小波为二进小波。其结果如表2 所示。

表2 动态多目标定位结果

从表2 中可以看出，Wavecluster 算法在进行数据流聚类时，可以进行自动聚类，且具有较高的聚类精度;而传统的Kmeans 算法在处理数据流时需要指定时间窗口W，W 的选择直接影响着定位精度，而目前W 的选择并没有通用且有效的方法。

在Wavecluster 算法当中，参数resolution 表示分辨率，也即网格单元粒度，它的值与样本在各维度上的值有关。如果resolution 值较大，网格单元就会较大，那么得到的聚类的精度就较低。反之，得到的聚类的精度就较高，但是算法的计算复杂度会较大。通过表3 可以看到在不同resolution 下的聚类效果，测试数据为第1 组数据。

表3 在不同分辨率下的Wavecluster 定位结果

通过以上仿真测试可以看出，相比较Kmeans 聚类算法，Wavecluster 算法具有较大优势，主要有:一是可以自动确定聚类数目，二是可以有效去除噪声对聚类结果的影响并发现任意形状的簇，三是在处理数据流聚类问题时可以自动聚类。

4 结束语

本文提出了基于小波聚类的多目标分群算法，仿真试验结果证明了该方法的可行性和有效性。此方法先把原始数据进行量化，形成矩阵数据，然后在该矩阵数据形式中实施小波变换检测出簇的边缘，并为每个簇添加标签，然后通过算法提供的映射表确定原始数据集中的各数据点所属的聚类，最后计算定位中心。该聚类方法在性能和效率上比传统的聚类算法有较大的改进，对于多传感器的多目标侦察研究有着极大的借鉴意义，此外，由于该算法基于网格的特性，可以解决数据流据类的大数据量问题。但是该方法也存在一定的局限性，如分辨率的选择以及处理二维以上数据等问题，还需在今后的工作中进一步研究。

［1］张晶炜，刘永，熊伟.多传感器多目标跟踪算法性能分析［J］.现代雷达，2004，26(3):37-39.

［2］杨国盛，窦丽华.多传感器多目标定位与跟踪技术研究［J］.火力与指挥控制，2002，27(1):30-32.

［3］姜园，张朝阳.用于数据挖掘的聚类算法［J］.电子与信息学报，2005，27(4):655-661.

［4］徐义峰，陈春明，徐云青.一种改进的k-均值聚类算法［J］.计算机应用与软件，2008，25(3):275-277.

［5］何承伟.基于小波变换的目标机动检测［D］.太原:太原理工大学，2007.

［6］黄文佳.基于小波的肿瘤基因表达数据聚类分析模型［J］.上海大学学报，2011，17(5):625-630.

［7］李云，刘学诚. 小波聚类在算法在入侵检测中的应用［J］.计算机应用与软件，2010，27(6):103-125.

［8］毕玲.小波聚类算法的研究及应用［D］.大连:大连理工大学，2006.

［9］孙玉芬.基于网格方法的聚类算法研究［D］.武汉:华中科技大学，2006.

［10］张西芝，姬波，邱保志. 基于网格的多密度聚类算法［D］.郑州:郑州大学，2009.