摘要
我们提出了一种对不相交路径问题的扩展，该扩展引入了额外的提升边（lifted edges），以提供路径连通性的先验信息。我们将由此产生的优化问题称为提升不相交路径问题（lifted disjoint paths problem）。通过从整数多商品流问题和3-SAT问题进行归约，我们证明了该问题为NP难问题。为实现高效的全局优化，我们提出了一系列线性不等式约束，能够生成高质量的线性规划松弛（LP-relaxation）。此外，我们还设计了高效的割平面算法，用于分离所提出的线性不等式。 提升不相交路径问题为多目标跟踪提供了一个自然的建模框架，能够以简洁的数学形式表达长时程的时间交互关系。提升边有助于防止目标ID切换，并提升对同一人物的重新识别能力。所提出的提升不相交路径跟踪器能够基于输入检测结果实现近乎最优的匹配分配。因此，在多目标跟踪挑战赛（MOT Challenge）的三个主要基准测试中均取得领先，显著优于当前最先进的方法。