K-Shortest Path ：Multiple Object Tracking using K-Shortest Paths Optimization论文笔记
Multiple Object Tracking using
K-Shortest Paths Optimization
Abstract ：当处理多目标问题时，在所有可能的轨迹中，连接这一步会带来困难的优化问题。这通常需要基于动态编程的采样或者贪婪寻找来完成，但其无法保证全局最优解。
在本文中，我们表明将该步骤重新定义为约束流优化导致了一个凸问题。 我们使用k-最短路径算法利用其特定的结构来解决它，这是非常快的。 这种新方法在正式和算法上比现有技术简单得多，让我们在两个非常不同的上下文中表现出出色的性能。In this paper, we show that reformulating that step as a constrained flow optimization results in a convex problem. We take advantage of its particular structure to solve it using the k-shortest paths algorithm, which is very fast.
ALGORITHM
首先，我们将多目标跟踪问题制定为整数规划问题（IP）。虽然在许多情况下这样的问题是NP-hard，但是我们表明，作为一个线性程序，它被放宽得到最优解，因此问题在多项式时间内是可解的。使其仅适用于小区域和短序列。
接下来证明，KSP与通用的线性规划相比更高效。
参数说明：
1.
在t时刻位于位置i，在t+1时刻移到位置j 的有向边。
2
从t时刻在位置i，移到t+1时刻在位置j，的预计的物体的数量。
3
t时刻，在位置i的预计的物体的数量。
4
5 k：location
代表 t时刻，在位置i的正确物体数量的随机变量。
表示位置i，时刻t，物体存在的边缘后验概率。
m是一个occupancy map，其为 每个时刻，每个位置occupancy variables的集合。
我们说，如果存在a set of flows 满足公式1-4，m是可行的。目标变成解决一下方程。
mi：0或者1。
Linear Programming Formulation
优化问题用flows提出。
K-Shortest Paths Formulation
有向边被分配为cost value。
ksp的最优解写为：
任何解决方案可以通过 k个节点不相交的路径的集合表示。
：第i次迭代中的最短路径。
：是计算到第L次迭代时，所有L个最短路径的集合。
我们通过在graph 中寻找单个最短路径，并计算其总的cost：
然后迭代地计算l个最短路径，对每个l，我们计算总的cost：
在每个新的迭代l+1中，总的cost cost（P(l+1)）与先前迭代cost（P(l)）比较。当k*+1迭代的cost大于k*迭代的cost时，路径的最优数量k*获得。
伪代码如下：
为了计算这些k个最短的路径，我们使用disjoint paths algorithm，可参考如下：
Suurballe’s algorithm：Suurballe算法是一种用于在非负向加权有向图中找到两个不相交路径的算法，使得两条路径连接同一对顶点并具有最小总长度。 Suurballe算法的主要思想是使用Dijkstra算法找到一条路径，修改图形边的权重，然后再次运行Dijkstra算法。 算法的输出通过组合这两个路径形成，通过路径丢弃沿相反方向穿过的边缘，并且使用剩余的边缘来形成返回的两条路径作为输出。 权重的修改类似于约翰逊算法中的权重修改，并保留权重的非负性，同时允许Dijkstra算法的第二个实例找到正确的第二个路径。
找到最小权重的两个不相交路径的问题可以看作是最小成本流问题的特殊情况，在这种情况下，有两个“流”单位，节点具有单位“容量”。 Suurballe的算法也可以被看作是一种最小成本流算法的特例，它可以沿着最短的增加路径反复推动最大可能的流量。 Suurballe算法发现的第一条路径是初始（零）流程的最短扩充路径，Suvoalle算法发现的第二条路径是沿着第一路径推动一个单位流之后剩下的剩余图形的最短增量路径。
https://en.wikipedia.org/wiki/Suurballe%27s_algorithm
path cost 是单调递增的。
Batch Processing and Complexity Reduction
为了实时，将序列分为100帧每批次。
跨批次实施时间一致性，将先前的优化好的批次的最后一帧，加到当前。然后我们强制流出该帧的每个位置，以总结到上一批中的位置的值，
为了限制运算时间和内存消耗，可通过裁剪detection graph。由于检测器估计的存在概率的大部分实际上等于零。我们可以使用这种稀疏性来减少优化中要考虑的节点数量。
对于每个位置k，和每个帧t，通过给定的时空领域来检查最大的检测概率。
如果其低于阈值，该位置被认为是不可达到具有任何合理的概率水平的对象。然后从模型中删除所有流出和流出这个位置的流。
Algorithm Output
Probabilistic Occupancy Map