muSSP：高效的多目标跟踪最小费用流求解器

项目介绍

muSSP（Minimum-update Successive Shortest Path）是一个精确且高效的最小费用流（MCF）求解器，专门用于多目标跟踪（MOT）中的全局数据关联问题。MCF在MOT中广泛用于解决数据关联问题，但现有的MCF求解器大多是通用算法的直接应用或轻微修改，效率并不理想。基于连续最短路径（SSP）算法，muSSP识别了MOT中MCF问题的几个特殊性，并通过利用这些特殊性大幅节省了计算资源。在五个MOT基准测试中，muSSP相比同类方法实现了数百到数千倍的效率提升。muSSP保持了与SSP相同的在最坏情况下的复杂度和空间效率，但其计算效率的提升有望使更复杂的跟踪框架成为可能，从而提高跟踪精度。

项目技术分析

最小费用流在MOT中的作用

• 选择一组总成本最小的s-t路径：每条路径代表一个轨迹。
• 网络的特殊性：
  1. 有向无环图，具有单一源节点s和单一汇节点t。
  2. 单位容量图。
  3. 每个检测对应一对节点（前节点和后节点），并通过单个弧连接。
  4. 每个前节点从s连接，每个后节点连接到t。

连续最短路径（SSP）算法

• 顺序实例化残差图上的最短s-t路径，并在其上增广流量，直到路径饱和。

最小更新连续最短路径（muSSP）算法

• 动态维护残差图的最短路径树，同时避免与寻找最短s-t路径无关的计算。

项目及技术应用场景

muSSP特别适用于需要高效处理大规模数据关联问题的多目标跟踪场景。例如：

• 智能监控系统：在实时监控中，快速准确地跟踪多个目标。
• 自动驾驶：在复杂环境中，高效地跟踪和预测多个移动目标。
• 机器人导航：在动态环境中，实时跟踪和避障。

项目特点

高效性

• 数百到数千倍的效率提升：在多个MOT基准测试中，muSSP显著优于同类方法。
• 保持最坏情况下的复杂度和空间效率：与SSP相同，但计算效率更高。

灵活性

• 支持自定义图结构：用户可以根据自己的需求重建图结构。
• 易于集成：代码遵循DIMACS CNF格式，便于集成到现有系统中。

理论支持

• 基于严格的理论基础：muSSP的四个策略均不违反最终解的最优性，详细证明可在相关论文中找到。

如何使用muSSP？

运行提供的示例图

(1). cd 到文件路径（例如：'your path to/SrcCode/muSSP/'）
(2). 在当前位置打开终端
(3). 在终端中运行命令：'./muSSP ../input_MOT_seq07_followme.txt'

重建自定义图

(1) 在文件头部添加节点和弧的基本信息
(2) 设置源节点和汇节点。在我们的测试中，使用1和n
(3) 添加表示进入/退出和检测转换成本的弧
(4) 添加表示将两个对象链接为一个轨迹的成本的弧

参考文献

如果您发现代码对您的研究有用，请引用我们的论文：

@inproceedings{wang2019mussp,
  title={muSSP: Efficient Min-cost Flow Algorithm for Multi-object Tracking},
  author={Wang, Congchao and Wang, Yizhi and Wang, Yinxue and Wu, Chiung-Ting and Yu, Guoqiang},
  booktitle={Advances in Neural Information Processing Systems},
  pages={423--432},
  year={2019}
}

更新日志

2021年1月13日

• 添加了Apache-2.0许可证。

2020年6月12日

1. 整合了Nuzhny007的代码优化，修复了内存泄漏问题。
2. 更改了运行muSSP/dSSP/SSP的命令（移除了“-i”）。
3. 修复了在C++14标准下由'abs'函数引起的错误。
4. 更新了代码以支持C++14标准，并使用g++/gcc v9.3.0进行了测试。

---

通过以上介绍，相信您已经对muSSP有了全面的了解。如果您正在寻找一个高效、灵活且理论基础扎实的多目标跟踪解决方案，muSSP无疑是您的最佳选择。立即尝试，体验其带来的效率提升吧！