基于序列霍夫变换的概率假设密度滤波算法

刘文德，曹明基,2，聂东虎，韦佳利，李东奇，吴鑫宇，戴佳瑞

基于序列霍夫变换的概率假设密度滤波算法

刘文德1，曹明基1,2，聂东虎1，韦佳利3，李东奇1，吴鑫宇1，戴佳瑞1

（1. 哈尔滨工程大学 水声技术重点实验室/海洋信息获取与安全工信部重点实验室（哈尔滨工程大学）/水声工程学院，哈尔滨 150001；2. 中国电子科技集团公司 第54研究所，石家庄 050081；3. 中国船舶工业系统研究院，北京 100094）

针对经典的自适应新生强度概率假设密度滤波算法在高杂波密度环境下存在计算复杂度较高的问题，提出一种基于序列霍夫（Hough）变换的概率假设密度滤波算法：将传统航迹起始中的Hough变换引入随机有限集，解决标准Hough变换的航迹簇拥问题，提高Hough变换的准确度；并将序列Hough变换与概率假设密度（PHD）相结合，通过序列Hough变换得到目标新生位置信息，将其作为PHD的新生目标强度进行迭代更新。实验结果表明，该算法对新生目标反应更为迅速，在高杂波环境下消耗时间更短，适合实际工程应用。

随机有限集；多目标跟踪；序列霍夫（Hough）变换

0 引言

随机有限集（random finite set，RFS）框架下的目标跟踪算法，是将多目标状态与量测建模为RFS，通过多目标贝叶斯递归完成对多目标状态的估计。文献[1]提出使用RFS理论解决多目标跟踪算法数据关联组合计算复杂度高的问题，但由于无穷维多目标状态空间的多重积分问题[2]，难以在工程中应用；文献[3]提出了概率假设密度（probability hypothesis density，PHD）滤波算法，利用后验强度来近似计算多目标概率密度，可以显著降低计算复杂度。文献[4]提出了高斯混合PHD（Gaussian mixture PHD，GM-PHD）滤波算法，在线性高斯模式下，给PHD算法提供了一种闭合实现方法。文献[5]提出序贯蒙特卡罗PHD（sequential Monte Carlo PHD，SMC-PHD）算法解决非线性非高斯场景下的跟踪问题。

针对未知新生目标位置的问题，文献[6-7]提出了一种自适应目标新生强度滤波算法（PHD filter with the measurement-driven birth intensity，PHDF-M），通过改进的PHD公式区分存活目标和新生目标，并根据量测信息判断新生目标的位置。文献[8]通过高斯混合实现方案改进了自适应新生目标强度PHD算法。文献[9]将启发式逻辑法引入PHD滤波中，通过速度、加速度多参数联合实现杂波的快速筛选。文献[10]针对高斯混合势平衡多目标多伯努利滤波器的缺陷，引入航迹标签提供航迹信息，通过可能的新生目标的位置和多普勒量测得到新生目标的初始状态信息。文献[11]通过剪枝步骤中保留高斯分量来解决未知新生目标位置的问题。在传统的航迹起始算法中，文献[12]使用修正的霍夫（Hough）方法很大程度上缩短了航迹起始的时间。文献[13]将传统航迹起始算法与随机有限集相结合，解决了新生目标位置未知时的跟踪问题。

本文针对未知目标新生信息的实际问题，提出一种基于序列Hough变换的PHD滤波算法，以期解决PHD滤波算法对新生目标响应速度慢、在高杂波环境中计算时间过长的问题。

1 基于序列Hough变换的PHD滤波算法

1.1 序列Hough变换及航迹簇拥现象

标准Hough变换主要用于提取图像中的直线[14-15]。在目标跟踪中，目标新生之后的一段时间内一般不会做明显的机动运动，因此可将Hough变换应用于检测目标的起始航迹中。

定义转换矩阵

转换矩阵与数据矩阵相乘得到矩阵，即

1.2 基于序列Hough变换的PHD滤波

使用粒子群方式实现基于序列Hough变换的PHD滤波器（PHD filter with sequential Hough transform，PHDF-SHT）。通过序列Hough变换得到了一系列极值点，这些点包含与航迹的有关参数，但在PHD滤波的2种实现方式中，需要目标的起始状态，而非航迹，因此在序列Hough变换后，还需要对量测数据与得到的航迹参数进行匹配。在PHD滤波器中，假设新生目标随机有限集的强度为高斯混合模型

2 实验与结果分析

2.1 未知新生目标信息场景仿真

为检验基于序列Hough变换PHD算法的有效性，将PHDF-M、PHDF-SHT、经典PHD这3种滤波算法进行对比。传感器位于原点，探测距离为2000 m，以正北方向为0°，顺时针为正，逆时针为负，探测范围为[-90°,90°]。有12个匀速直线运动目标，目标新生状态及运动信息如表1所示。

表1 未知新生强度场景的目标运动参数

目标的匀速直线运动的状态转移方程为

在PHD中，已知新生目标随机有限集强度为

图1与图2分别给出了PHDF-M、PHDF-SHT、经典PHD 3种算法目标数估计均值和目标数估计均方根误差的结果对比。由于PHD算法中新生目标是目标真实起始位置，因此对目标数量的估计十分准确，对新生目标的响应也十分迅速。相同条件下，缺少目标先验位置信息的PHDF-M与PHDF-SHT算法对目标数的估计略差。PHDF-M算法只利用当前时间传感器接收的量测信息，对新生目标的响应时间过长，在21、31、51 s几个有目标新生的时间节点，无法做到快速定位目标进行跟踪；但随着环境中目标新生消亡不再变化后，对目标数的估计逐渐准确。PHDF-SHT算法充分利用一段时间内的所有量测信息，能够做到对新生目标响应迅速，并且对目标数的估计误差较小。

图1 目标数估计均值

图2 目标数估计均方根误差

图3给出了不同算法的最优次模式分配（optimal sub-patten assignment，OSPA）距离对比。整个跟踪阶段PHD算法由于具有目标位置的先验信息，在3种算法中跟踪精度最高。0～20 s目标数目较少时，PHDF-M算法具有较好的跟踪精度；但随着目标数目的突变与增加，PHDF-M算法对新生目标响应速度不够，导致跟踪精度很差。PHDF-SHT算法新增目标后，能够快速确认新生目标，使跟踪精度较PHDF-M算法有较大提升。在跟踪后期，目标数目稳定后，PHDF-SHT算法的跟踪精度与PHD算法相近，验证了所提算法跟踪精度的有效性。图4给出了PHDF-M、PHDF-SHT、经典PHD 3种算法在不同杂波率下的计算时间比较。

图3 OSPA距离比较

图4 不同杂波率下的运行时间比较

由图可知：PHD算法只处理新生目标位置和预测位置附近的量测，在强杂波环境中处理速度较快；PHDF-M算法将各时刻的量测暂时当作新生目标，在新生目标预测阶段，需要对每个量测进行处理，在杂波率逐渐增大时，计算时间远大于其他2种方法；提出的PHDF-SHT算法能够在高强度杂波环境下快速估计出新生目标信息，筛选掉无用的量测信息，在更新阶段不引入杂波，运算速度相比PHDF-M算法大幅提高。

2.2 算法适用范围仿真分析

图5 目标初始直线运动时间及杂波率对算法的影响

从图5中可以看出，当目标直线运动时间一定时，环境中杂波数目越少，误差越小，估计结果更加准确。随着目标运动时间的增加，3条曲线逐渐收敛。当目标直线运动时间到达20 s时，杂波率为30与10的情况下误差均小于1。综上所述，PHDF-SHT算法在目标直线运动时间短、杂波率大时，跟踪误差较大。当目标处于较长的直线运动时间和较少的杂波环境中时，算法跟踪更加准确。

3 结束语

本文针对未知新生目标的多目标跟踪问题，提出基于序列Hough变换的概率假设密度滤波算法，引入序列Hough变换，解决标准Hough变换的航迹簇拥现象，提高Hough变换的准确度。并将序列Hough变换与PHD相结合，通过序列Hough变换得到目标新生位置信息，将其作为PHD的新生目标强度进行迭代更新。仿真实验结果表明，PHDF-SHT算法相较PHDF-M算法对新生目标的响应更快，OSPA距离更低，在杂波率高时运算速度更快。另外，PHDF-SHT算法适用于目标新生阶段做直线运动时间长的场景，杂波率越低，误差越小。

[1] FOURATI H, INIEWSKI K. Multisensor data fusion: from algorithms and architectural design to applications [EB/OL]. (2017-01-31)[2022-01-01]. https://doi.org/10.1201/b18851.

[2] RONALD M. "Statistics 102" for multisource-multitarget detection and tracking[EB/OL].(2013-03-29)[2022-01-01]. https://doi.org/10.1109/JSTSP.2013.2253084.

[3] Mahler R P S. Multitarget Bayes filtering via first-order multitarget moments[J]. IEEE Transactions on Aerospace and Electronic Systems, 2003, 39(4): 1152-1178.

[4] Vo B N, Ma W K. The Gaussian mixture probability hypothesis density filter[EB/OL]. (2005-08-16)[2022-03-10]. https://doi.org/10.1109/TSP.2006.881190.

[5] Vo B N, Singh S, Doucet A.Sequential Monte Carlo methods for multitarget filtering with random finite sets[EB/OL]. (2005-12-19)[2022-03-10]. https://doi.org/10.1109/TAES.2005.1561884.

[6] Ristic B, Clark D, Vo B N,et al.Adaptive targetbirth intensity for PHD and CPHD filters[EB/OL].(2012-04-05) [2022-03-10]. https://udrc.eng.ed.ac.uk/sites/udrc.eng.ed.ac.uk/files/publications/O02_IEEE_TrAES.pdf.

[7] Ristic B, Clark D, Vo B N. Improved SMC implementation of the PHD filter[C]//201013th International Conference on Information Fusion.Edinburgh, UK:[s.n.], 2010: 1-8. DOI: 10.1109/ICIF.2010.5711922.

[8] 欧阳成, 华云, 高尚伟.改进的自适应新生目标强度PHD滤波[J]. 系统工程与电子技术,2013, 35 (12): 2452-2458.

[9] 李坦坦, 雷明. 基于启发式逻辑的概率假设密度滤波高效航迹起始方法[J]. 上海交通大学学报, 2018, 52 (1): 63-69.

[10] 魏立兴, 孙合敏, 吴卫华,等.自适应单点航迹起始的带标签GM-CBMeMBer滤波器[J]. 电光与控制, 2018, 25(9): 78-83, 87.

[11] Zhang H, Wang J, Ye B, et al. A GM-PHD filter for new appearing targets tracking[C]//Edinburgh, 20136th International Congress on Image and Signal Processing (CISP).Hangzhou, China:[s.n.], 2013:1153-1159. DOI: 10.1109/CISP. 2013. 6745230.

[12] CHEN J, Leung H, Lo T, et al.A modified probabilistic data association filter in a real clutter environment[J].IEEE Transactions on Aerospace and Electronic Systems,1996, 32 (1): 300-313.

[13] 曹明基. 先验信息缺失场景下的多目标跟踪算法研究[D]. 哈尔滨:哈尔滨工程大学, 2022.

[14] Zhang X, Burkhardt H.Grouping edge points into line segments by sequential Hough transformation[EB/OL]. (2000-01-01) [2022-03-10]. http://dx.doi.org/10.1109/ICPR.2000.903634.

[15] Duda R O, Hart P E. Use of the Hough transformation to detect lines and curves in pictures[EB/OL].(1972-01-01) [2022-03-10]. https://dl.acm.org/doi/pdf/10.1145/361237.361242.

Probability hypothesis density filtering algorithm based on sequential Hough transform

LIU Wende1, CAO Mingji1,2, NIE Donghu1, WEI Jiali3, LI Dongqi1, WU Xinyu1, DAI Jiarui1

（1. Acoustic Science and Technology Laboratory/Key Laboratory of Marine Information Acquisition and Security of Ministry of Industry and Information Technology(Harbin Engineering University)/College of Underwater Acoustic Engineering, Harbin Engineering University, Harbin 150001, China; 2. The 54th Research Institute of China Electronics Technology Group Corporation, Shijiazhuang 050081, China;3. Systems Engineering Research Institute, China State Shipbuilding Corporation, Beijing 100094, China）

Aiming at the problem of high computational complexity in high clutter density environment for the classical adaptive newborn intensity probability hypothesis density filtering algorithm, the paper proposed a probability hypothesis density filtering algorithm based on sequential Hough transform: the Hough transform in traditional track initiation was introduced into random finite set for solving the clustering problem of standard Hough transform and improving the accuracy of Hough transform; in addition, by combining the sequential Hough transform with the probability hypothesis density (PHD), the target newborn position information was obtained by the sequence Hough transform, which was used as the PHD newborn target intensity for iterative update. Experimental result showed that the proposed algorithm could respond more quickly to new targets and consume less time in high clutter environment, which would be suitable for practical engineering application.

random finite set; multi-target tracking; sequence Hough transform

P228

A

2095-4999(2023)01-0102-05

刘文德，曹明基，聂东虎，等. 基于序列霍夫变换的概率假设密度滤波算法[J]. 导航定位学报, 2023, 11(1): 102-106.（LIU Wende, CAO Mingji, NIE Donghu, et al. Probability hypothesis density filtering algorithm based on sequential Hough transform[J]. Journal of Navigation and Positioning, 2023, 11(1): 102-106.）DOI:10.16547/j.cnki.10-1096.20230115.

2022-04-18

国家自然科学基金资助项目（11974090，U1806201）；国防基础科研项目（JCKY2021604B013，JCKY2019604B001）；国防科技173计划技术领域基金项目；重点实验室基金项目（6142109180305）；中央高校基本科研业务费专项资金资助项目（3072021CFJ0510）。

刘文德（2001—），男，天津人，研究方向为水下目标探测。

聂东虎（1978—），男，辽宁锦州人，博士，副教授，研究方向为水下目标探测与识别。