Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (1): 271-277.DOI: 10.11772/j.issn.1001-9081.2019061057

• Frontier & interdisciplinary applications • Previous Articles     Next Articles

Multi-extended target tracking algorithm based on improved K-means++ clustering

YU Haofang1, SUN Lifan1,2, FU Zhumu1   

  1. 1. Information Engineering College, Henan University of Science and Technology, Luoyang Henan 471023, China;
    2. School of Communication and Information Engineering, University of Electronic Science and Technology of China, Chengdu Sichuan 611731, China
  • Received:2019-06-21 Revised:2019-09-03 Online:2020-01-10 Published:2019-09-29
  • Contact: 孙力帆
  • Supported by:
    This work is partially supported by the National "the 13th Five-year" Equipment Pre-Research Foundation of China (61403120207), the National Defense Basic Scientific Research Program of China (JCKY2018419C001), the Aeronautical Science Foundation of China (20185142003), the National Natural Science Foundation of China (U1504619, 61671139), the Scientific Technology Program of Henan Province (182102110397, 192102210064, 172002310636), the Support Plan for the Science and Technology Innovative Teams in University of Henan Province (18IRTSTHN011).

基于改进K-means++聚类的多扩展目标跟踪算法

俞皓芳1, 孙力帆1,2, 付主木1   

  1. 1. 河南科技大学 信息工程学院, 河南 洛阳 471203;
    2. 电子科技大学 通信与信息工程学院, 成都 611731
  • 作者简介:俞皓芳(1995-),女,浙江诸暨人,硕士研究生,主要研究方向:多目标跟踪、扩展目标跟踪;孙力帆(1982-),男,河南洛阳人,副教授,博士,主要研究方向:多扩展目标跟踪、多传感器信息融合;付主木(1974-),男,湖北仙桃人,教授,博士,主要研究方向:不确定信息处理、机器视觉。
  • 基金资助:
    国家"十三五"装备预研共用技术和领域基金资助项目(61403120207);国家国防基础研究计划项目(JCKY2018419C001);航空科学基金资助项目(20185142003);国家自然科学基金资助项目(U1504619,61671139);河南省科技攻关计划项目(182102110397,192102210064,172102310636);河南省高校科技创新团队支持计划项目(18IRTSTHN011)。

Abstract: In order to solve the problem of low partition accuracy of measurement set and high computational complexity, a Gaussian-mixture hypothesis density intensity multi-extended target tracking algorithm based on improved K-means++ clustering algorithm was proposed. Firstly, the traversal range of K value was narrowed according to the situations that the targets may change at the next moment. Secondly, the predicted states of targets were used to select the initial clustering centers, providing a basis for the correct partition of measurement set to improve the accuracy of clustering algorithm. Finally, the proposed improved K-means++ clustering algorithm was applied to the Gaussian-mixture probability hypothesis filter to jointly estimate the number and states of multiple targets. The simulation results show that the average tracking time of the proposed algorithm is reduced by 59.16% and 53.25% respectively, compared with that of multi-extended target tracking algorithms based on distance partition and K-means++. Meanwhile, the Optimal Sub-Pattern Assignment (OSPA) of the proposed algorithm is much lower than that of above two algorithms. In summary, the algorithm can greatly reduce the computational complexity and achieve better tracking performance than existing measurement set partition methods.

Key words: multi-target tracking, extended target, probability hypothesis density, Gaussian mixture, K-means++ clustering

摘要: 针对多扩展目标跟踪过程中量测集划分准确度低和计算量大的问题,提出一种基于改进K-means++聚类划分的高斯混合假设密度强度多扩展目标跟踪算法。首先,根据下一时刻目标可能变化的情况缩小K值的遍历范围;其次,利用目标预测状态选择初始聚类中心点,为正确划分量测集提供依据,从而提高聚类算法的精度;最后,将所提改进K-means++聚类划分方法应用到高斯混合概率假设滤波器中,联合估计多目标的个数和状态。仿真实验结果表明:与基于距离划分和基于K-means++的多扩展目标跟踪算法相比,该算法在平均跟踪时间上分别减小了59.16%和53.25%,同时其最优子模式指派度量(OSPA)远小于以上两种算法。综上,该算法能在大幅度降低计算复杂度的同时取得比现有量测集划分方法更为优异的跟踪性能。

关键词: 多目标跟踪, 扩展目标, 概率假设密度, 高斯混合, K-means++聚类

CLC Number: