多目标跟踪是在给定的一段视频序列中定位感兴趣的多个运动目标,并形成目标运动的轨迹的过程。它是在对运动目标图像的分析和应用中产生的,并很快成为计算机视觉领域中视频分析的重要内容之一,其实质上是在捕获到的目标初始状态和通过特征提取得到的目标特征基础上,进行一种时空结合的目标状态估计。多目标跟踪在智能监控、行为分析等领域均有广泛的应用。目前主流的多目标跟踪算法都是在tracking-by-detection的框架下发展而来,这些算法的核心思想是将相邻帧之间的目标进行相似性度量和关联,因此在密集场景中处理目标长时间的遮挡和邻近表观相似目标时性能较差。本文提出的算法将多目标跟踪模型构建为一个全局高阶图,用高阶边来描述跨时域目标之间的相似性,并在高阶图中搜索二阶子图来完成各个目标的轨迹段的计算。高阶图是由各个代表轨迹段的顶点组成,高阶边描述的是同一个目标的集合,该集合是由目标之间的特征匹配值与阈值的关系来获得。目标之间通过跨时域后的高阶关系来计算表观和运动等特征,而不是仅仅考虑目标之间的二阶关系,这样可以使得目标的很多有效信息得以利用,有助于提高邻近表观相似目标的区分能力,对处理长期遮挡问题提供了解决方案。此外,将本算法视频序列进行分段迭代处理,提高计算速度,有利于满足实时性的要求。本文算法在UA-DETRAC中的100个具有挑战性的数据集上进行训练和测试,与目前主流的六个多目标跟踪算法进行大量的实验对比,并通过定性和定量分析得出相应的结论,证明本文算法的有效性和鲁棒性。