SVM在多目标跟踪中的回波分类及并行化研究

侯立斐，郑晓薇，于梦玲

（辽宁师范大学 计算机与信息技术学院，辽宁 大连 116081）

多目标跟踪是为了维持对多个目标当前状态的估计，及对探测器所接收到的回波信息进行处理的过程[1]，核心部分是数据关联。数据关联是用来解决传感器在空间覆盖区域中的重复跟踪问题。联合概率数据关联算法JPDA（Joint Probabilistic Data Association）[2]是公认有效的多目标跟踪的经典数据关联方法。但目标跟踪门的交叉区域若存在过多的干扰杂波，会影响数据关联的精度，导致跟踪系统概率数据关联算法的滤波值发散，最终影响跟踪性能。为解决此问题，人们不断提出了一些新方法。

MC-JPDA算法[3]和 MCMCDA算法[4]，基本思想都是用蒙特卡洛循环来收敛关联概率，极端情况下的收敛需要迭代过多。参考文献[5]提出利用模糊C-均值聚类算法实现数据关联，能对多目标进行有效关联，但是密集杂波环境下的跟踪效果差；参考文献[6]研究了基于支持向量机的航迹关联算法，实现了多传感器信息融合的航迹关联，却未优化回波的数据关联。本文采用支持向量机技术对有效回波进行分类，提高了跟踪效率。

1 利用支持向量机分类有效回波

在多目标跟踪中，跟踪门是跟踪空间中的一块子空间，系统正确接收回波的概率确定其大小，跟踪门的形成既是维持跟踪或保持目标轨迹的先决条件，也是限制不可能决策数目的关键环节。跟踪门规则是最直接和最有效的减少JPDAF框架中有效假设数量的方法[7]，但是实际情况中的回波点和杂波点存在于多个跟踪门交叉区域的情形却很常见。

在蒙特卡洛联合数据关联算法基础上，引入了支持向量机（SVM）分类技术，利用其在小样本分类[8]中的优势，对跟踪门交叉区域的回波进行分类，计算出一组判断矩阵 （有效回波对应目标，杂波对应为空），用它为JPDA滤波器有效回波矩阵和关联事件矩阵进行更新，然后计算交叉区域回波点的预测权值和预测似然，得出更精确的交叉区域回波的关联概率。SVM类型采用分类模型υ-SVC，使用多项式（r*u′v+coef0）degree 作为核函数。

2 SVM-MC-JPDAF的算法核心及并行化

2.1 SVM-MC-JPDAF核心算法

（2）利用“跟踪门规则”，对前景区的回波进行处理，得出有效回波矩阵，以及所有可能的互联事件假设：

（3）对于 k=1…K，n=1…N，利用“SVM 分类有效回波”，输出{ωt1，ωt2，…，ωtm（test）}，更新[Ωt]j，k

（4）对于 k=1…K，n=1…N，计算并正常化预测权值

（5）对于 k=1…K，i=1…N0，j=1…Mi，计算预测似然的蒙特卡罗近似值：

（6）对于 i=1…N0，在第 i个观测上，利用所有目标与回波合理的联合关联假设集构造Λ˜ti。

（7）对于 i=1…N0，λ˜ti∈Λ˜ti计算联合关联的后验概率

（8）对于 k=1…K，i=1…N0，j=1…Mi，计算边缘关联后验概率：

（9）对于 k=1…K，n=1…N，计算目标似然：

（10）对于 k=1…K，n=1…N，计算并正常化回波点权值

2.2 算法的并行化

由于SVM-MC-JPDAF算法增加了SVM对有效回波的分类过程，算法的执行时间有所增加。而且算法采用了蒙特卡洛迭代的方法收敛概率，不同观测条件下算法对蒙特卡洛迭代的次数要求不同。而过多的算法迭代次数会加重算法的执行负担。对此，采用并行计算的方式，将JPDA核心算法的输入输出外移，去除迭代相互间的依赖关系，构建子程序模块，并利用Matlab并行工具箱对算法进行分布式并行计算。

在 4 台联网的 Intel（R）Core（TM）i3-530@2.93 GHz双核处理器的计算机上，构造8节点的Matlab集群。软件环境为Matlab_R2010B，在 Matlab安装时选择组件：并行计算工具箱软件 （Parallel Computing Toolbox）和Matlab分布式计算服务软件 （Distributed ComputingServer software）。利用 Matlab的作业管理器（JobManager）对并行作业进行分割，然后在集群环境中分配任务，实现算法的分布式计算。

3 仿真实验及性能分析

将本文算法与普通JPDAF和MC-JPDAF算法作对比，实验数据通过Matlab下的仿真实验得到。在二维平面内设定目标初始状态：目标一（15 km，-0.5 km/s，0 km，0.1 km/s）；目标二（10 km，-0.2 km/s，0 km，0.5 km/s）；目标三（1 km，0.3 km/s，1 km，0.2 km/s）。 采样间隔 1 s，跟踪目标100个时间步。在目标每个时刻的观测点周围仿真出对应杂波，数量服从参数λ的泊松分布，它们在以目标观测预测值为中心的椭球区域内服从均匀分布，噪声协方差都为[0.01 0.01]。其中，正确检测概率PD=0.99，正确回波落入跟踪门中的概率PG=0.99。

（1）对比三种算法平均失跟率，蒙特卡洛迭代次数均设为10次。由图1可得，低杂波环境中，三种算法失跟率都很低，当单位面积的杂波增加时，MC-JPDAF和SVM-MC-JPDAF算法的优势明显；但杂波若进一步增加，由于SVM-MC-JPDAF对采样进行了更细致的分类，失跟率明显低于MC-JPDAF算法。

图1 算法的失跟率对比

（2）通过100次实验，统计三种算法跟踪的均方根误差值（RMSE）。图2是三种算法在100次实验后分别对目标跟踪的RMSE值平均值、最大值和最小值。通过数据可以得出，JPDAF、MC-JPDAF、SVM-MC-JPDAF 算法的跟踪精度依次递增。另外，SVM-MC-JPDAF算法在RMSE值的波动性也明显要小于另外两种算法。

（3）SVM-MC-JPDAF算法的并行加速比。表1给出的是SVM-MC-JPDAF算法进行不同次数的蒙特卡洛迭代运算的串并行时间对比，实验数据是在单位面积10个杂波、跟踪3个目标、100个时间步的情况下得到的。

图2 100次实验结果的RMSE统计对比

表1 SVM－MC－JPDAF串并行执行时间对比

如表1所示，当蒙特卡洛迭代次数较少时，并行执行时间甚至长于串行执行，这是由于网络的数据通信以及Matlab任务调度所致。当蒙特卡洛次数增大到10次及以上时，可以看出并行执行时间已经优于串行执行时间，此后随着蒙特卡洛迭代次数的增加，并行算法的加速比也不断提高。

本文提出SVM-MC-JPDAF算法利用支持向量机对跟踪门交叉区域分类有效回波。通过仿真实验的数据对比，SVM-MC-JPDAF算法在杂波数量密集增加的情况下，与JPDAF以及MC-JPDAF算法相比，无论在目标失跟率上还是RMSE值上均要优秀，而且SVM-MC-JPDAF算法的并行化也有效地控制了算法执行时间。在今后的研究中，本算法的并行化可以做进一步优化。另外，支持向量机也可利用相应分布的模糊支持向量机对采样进行分类，可以在更多的概率分布情况下考虑样本的更多维信息。

[1]SHALOM BY，FORTMANN TE.Trackinganddata association[M].New York： Academic Press， 1988.

[2]FORTMANN TE，SHALOM Y B.Sonartrackingof multiple targets using joint probabilistic data association[J].IEEE JournalofOceanic Engineering （S0364-9059），1983， 8（3）： 173-184.

[3]VERMAAK J， GODSILL S J， PEREZ P.Monte Carlo filtering for multi-target tracking and data association[J].IEEE Transactions on Aerospace and Electronic Systems，2005， 41（1）： 309-332.

[4]OH S， RUSSELL S， SASTRY S.Markov chain Monte Carlo data association for multi-target tracking[J].IEEE Transactions on Automatic Control， 2009， 54（3）：481-497.

[5]杨雷，胡炜薇.多目标聚类融合跟踪中的特征信息利用[J].弹箭与制导学报，2007，27（2）：328-331.

[6]廖德勇.支持向量机在多目标跟踪中的应用研究[D].南京：南京航空航天大学，2006.

[7]徐勋华，王继成.支撑向量机的多类分类方法[J].微电子学与计算机，2004，21（10）：149-152.

[8]REZAII T Y，TINATI M A.Improved joint probabilistic data association filter for multi-target tracking in wireless sensor networks[J].Journal of Applied Sciences， 2009，9（5）： 924-930.