随着信息技术的发展，基于视觉的运动目标的检测与跟踪已逐渐渗透到人们生活的方方面面，其重要性日益突出，吸引着越来越多的国内外学者和研究机构参与在这个领域的研究。目前，基于视觉的运动目标检测与跟踪已广泛应用于视频监控、虚拟现实、人机交互、行星探测、行为理解等领域。

SORT是一种快速在线多目标跟踪（MOT）算法，基于TBD（Traking-by-Detection）策略，这些特征决定了SORT的实用性，多目标跟踪方法的重点是为在线和实时应用有效的关联对象。

SORT算法仅使用基本算法，例如卡尔曼滤波和匈牙利算法作为跟踪组件。本文将使您对目标跟踪任务和SORT算法的工作流程有一个初步的了解。

卡尔曼滤波算法

卡尔曼滤波理论是卡尔曼博士在1960年访问美国宇航局时首次提出的，它震惊了美国宇航局，并为著名的“阿波罗”计划做出了贡献，使人类首次登上月球。

卡尔曼滤波是基于时域描述的线性动态系统。其模型是一个马尔可夫链，该马尔可夫链基于一个受高斯噪声干扰的线性算子。

系统的状态可以由向量表示，其元素为实数。随着离散时间的增加，线性运算符将作用于当前状态，生成新状态，并带来一些噪声，并且还将添加一些已知的控制信息。同时，另一个受噪声干扰的线性算子将产生这些隐藏状态的可见输出。

假设我们想要实时获得机器人在空间中的位置，我们需要一个机器人运动模型。如果我们不知道机器人的确切运动模型，我们可以简单地假设它是一个匀速运动模型。

对于运动模型，我们可以通过一组状态变量来表示：

其中

我们只记录位置和速度，根据我们的模型和期望得到的数据，我们可以将任何数据变量放入系统状态。

根据轨道在k-1时刻的状态x，我们预测k时刻的状态x为:

令F为状态转移矩阵，则

卡尔曼滤波假设所有变量的值都服从正态分布，那么系统各变量之间的不确定性可以用协方差来表示。系统状态的协方差记为P_k，因为我们有以下公式:

综合上述运动模型，我们可以得到状态变量和误差的更新公式:

我们将这个预测误差矩阵记录为Q，它代表预测中的高斯噪声。误差的简单叠加就可以得到一个完整的预测转换方程：

我们还需要一个传感器来提供系统状态的观测数据，并通过实测值来细化前一阶段模型的预测值。传感器可以测量的变量由其功能决定。

假设我们有一个可以直接获取机器人位置状态量p的传感器，p = [x，y，z]。传感器测量的范围和单位可能与系统状态变量的范围和单位不一致，因此我们需要进行以下转换：

其中H是变换矩阵。由于高斯噪声的影响，传感器的读数会在一定范围内波动。我们将传感器测量值的不确定度的方差记为R，传感器实际返回的值记为z_k。

卡尔曼增益是赋予测量值和当前状态估计值的相对权重，可以“调整”以获得特定的性能。

简化后，我们可以获得三个更新的公式，一起形成了卡尔曼滤波的五个核心公式：

我们估计了当时的位置值，以及更新后的系统方差，将作为下一次迭代使用。

匈牙利法

匈牙利方法是一种能够在多项式时间内解决分配问题的组合优化算法。它是由Harold Kuhn在1955年提出的。由于该算法严重依赖于两位匈牙利数学家Denes Konig和Jeno Egervary，因此它被命名为“匈牙利方法”。

1957年，James Munkres对该方法进行了重新检验，证明该方法是严格多项式，故又称Kuhn-Munkres算法或Munkres分配算法。原匈牙利算法的时间复杂度为O(n^4)，但Edmonds和Karp、Tomizawa分别发现，经过一定的修改后，算法的时间复杂度可以达到O(n^3)。Ford和Fulkerson将该方法扩展到解决一般的交通问题。

让我们引入0-1变量：

我们使用cij来表示第i个人完成第j个作业所需的资源数量，称为值系数。因此，指派问题的数学模型为:

第一个表达式表示通过完成所有n个任务消耗的资源总数应该最少；第二个意味着第i个人只能完成一项任务，第三个意味着第j个工作只能由一个人完成。最后一个表达式表示决策变量只能取0或1。

任务分配问题可以用0-1整数规划问题来解决，也可以用更简单的匈牙利方法来解决:

对于大小为n×n的值系数矩阵步骤1：对于每一行的所有元素，减去该行的最小元素。步骤2：对于每列中的所有元素，减去列中的最小元素。步骤3：在适当的行或列上绘制直线，以使这些直线覆盖所有零元素，并且同时使用的直线数最少。步骤4：最佳检测1.如果直线的最小数量为n，则意味着存在大小为n的独立零元素组，即可以进行最佳分配并结束。

2.如果直线数小于n，则表示尚无法实现最佳分配。在这种情况下，请转到步骤5。步骤5：确定该行未覆盖的所有元素中的最小值，从该行未覆盖的每一行中减去该最小值，然后将此元素添加到该行覆盖，然后返回到步骤3。

在多目标跟踪问题中，可以简单地理解为在前后两帧中找到多个目标的最优匹配解的算法。卡尔曼滤波可以看作是一个运动模型，用于预测目标的运动轨迹，并利用具有较高置信度的跟踪结果来修正预测结果。

简单的在线和实时跟踪

SORT采用线速度模型和卡尔曼滤波进行位置预测，首先进行位置预测，然后进行匹配。在没有合适的匹配检测帧的情况下，运动模型的结果可以用来预测目标的位置。

首先，我们使用经过Single Shot Multibox Detection （SSD）框架进行对象检测，该对象检测将捕获的图像作为输入并生成边界框作为输出。

我们使用线性分配将每个box配给跟踪器。我们使用跟踪器边界框和检测边界框的交集相交（IOU）作为度量。我们使用匈牙利算法来解决IOU分配问题的最大化。

根据线性分配结果，我们分别保留两个列表，分别用于未匹配检测和未匹配跟踪器。当一个对象进入一个帧并首先被检测到，它没有与任何现有的轨道匹配，因此这种特殊的检测被称为未匹配检测。

另外，任何重叠小于阈值的匹配都表示存在未跟踪的对象。当对象离开帧时，先前建立的轨道不再具有与之关联的检测。在这种情况下，该轨道称为未匹配轨道。因此，将匹配中关联的跟踪器和检测分别添加到未匹配跟踪器和未匹配检测的列表中。

然后利用卡尔曼滤波器对目标进行跟踪。卡尔曼滤波有以下重要的特点：

• 预测目标的未来位置
• 根据新的测量值对预测进行校正
• 减少由不正确检测引起的噪声
• 促进多个对象与其轨迹的关联过程

虽然目标在两帧之间的运动量可能不大，但是由于探测器本身的检测结果不准确，目标帧的偏移量可能很大，这仍然可能会导致IOU太小。