介绍

多目标跟踪（MOT）是一项任务，其中算法必须检测和跟踪视频中的多个对象。大多数已知的算法都是基于使用简单的检测器（例如 YOLO）设计用于处理单个图像。整体方法涉及在连续视频帧上分别使用检测器，然后匹配属于同一对象的不同帧之间的对应边界框。使MOT算法不同的核心部分是它们如何在视频帧之间执行匹配。它们可以思考几个因素来执行匹配：

· 边界框位置;

· 遮挡（当多个物体的边界框相互交叉时）;

· 物体的运动；

· 物理对象类似性;

在某些情况下，对于相邻帧上的每一对边界框 A 和 B，这些特征被合并为一个单一数字，描述了在帧 A 和 B 中检测到的一对边界框属于同一对象的可能性。

多目标跟踪（MOT）的示例：该算法跟踪两个球。

这些数值是针对帧A和B中所有边界框对计算的。然后，MOT算法尝试识别所有边界框之间的最佳匹配。更具体地说，给定帧A和B中各有n个检测到的边界框，目标是以一种方式创建从A到B的每个边界框之间的映射，使得每个边界框仅使用一次。

匈牙利算法

匈牙利算法一般在算法和数据结构课程中学习。不过，它也在匹配系统中应用，并且特别常常用于解决上述提到的轨迹匹配问题。

我们将在更简单的设置中研究匈牙利算法的工作流程。一旦我们理解了它的使用方法，我们也将能够轻松地将其应用于MOT问题。

这个算法被称为匈牙利算法，由于它“在很大程度上基于两位匈牙利数学家Dénes Kőnig和Jenő Egerváry的早期作品”——匈牙利算法 | 维基百科

这个算法被称为匈牙利算法，由于它“在很大程度上基于两位匈牙利数学家Dénes Kőnig和Jenő Egerváry的早期作品”——匈牙利算法 | 维基百科

配方

有许多例子可以证明匈牙利算法。我喜爱其中一个关于工人和任务的例子。以下是表述：

有n名工人可用，需要他们完成n项任务。有关每名工人完成每项任务所获得的工资信息。对于公司董事来说，问题在于在以下条件下将任务最佳地分配给工人：

· 每个工人只分配一个任务；

· 所有任务都完成了。

· 工资支出应该尽量减少。

我们将通过使用以下4 x 4成本矩阵作为示例来解决这个问题：

包含每个工人完成每项任务成本信息的成本矩阵。目标是将每项任务分配给每个工人，以便以最小的总成本完成所有任务。

在几何上，思考到上面的矩阵，目标是以一种方式选择n个矩阵元素，使得任何行或列中都没有重复元素，并且所选元素的总和是最小的。

在几何上，给定上面的矩阵，目标是以一种方式选择 n 个矩阵元素，使得任何行或列中都没有重复元素，并且所选元素的总和是最小的。

想法

匈牙利方法涉及将初始成本矩阵转换为一种新形式，以便于解决方案的搜索。为此，我们将使用几种矩阵转换。尽管矩阵将被修改，但问题始终保持等效，这意味着解决方案仍将保持不变。

为了简化问题，我们不会在这里数学上证明为什么这个或那个矩阵变换会保持问题不变。相反，我们将提供一些逻辑思考来解释为什么解决方案保持不变。

为了简化问题，我们不会在这里数学上证明为什么这个或那个矩阵变换会保持问题不变。相反，我们将提供一些逻辑思考来解释为什么解决方案保持不变。

例子

行和列的简化

第一步包括识别矩阵每一行中的最小元素，并从每一行中减去它。这里的想法是让每一行至少有一个零。实际上，有更多的零可以简化问题。

假设从给定行中减去某个数字m。在转换过程中，目标值（总最小化工资）发生变化（减少m），但同一工人的任务之间的相对成本保持不变。因此，解决方案的排名保持不变。

假设从给定行中减去某个数字m。在转换过程中，目标值（总最小化薪水）会发生变化（减少m），但对于同一工人的分配之间的相对成本保持不变。因此，解决方案的排名保持不变。

类似的过程然后在列上执行：从每一列中减去最小元素。

前两个步骤：1. 从每一行中减去最小元素；2. 从每一列中减去最小元素。

经过前两次转换后，我们得到了一个矩阵，其中一些零表明潜在的分配。

下一步包括以最少数量的水平和垂直线穿过矩阵中的所有零。在下面的图像中，我们总共可以画出 k = 3 条线来覆盖所有零。

所有的零可以只用 k = 3 条线覆盖。

如果所画线的数量等于矩阵的维数n，则我们已经找到了一个解决方案。在这种情况下剩下的唯一步骤是选择n个零，使得没有一个零位于与另一个零一样的水平线或垂直线上。

在我们的例子中，由于n ≠ k（矩阵维数n = 4；绘制的线条数k = 3），这意味着我们必须执行一个调整步骤。

调整步骤

到目前为止，我们已经画了几条线，并且我们可以将矩阵元素分类为三类：

· 未被揭示的元素；

· 覆盖的元素（仅一次）;

· 角元素（即水平和垂直方向都被覆盖两次的元素）。

调整步骤的想法包括识别未覆盖元素中的最小元素，并从所有未覆盖元素中减去它。同时，这个值被添加到所有角元素中。

在我们的示例中，最小的未覆盖元素是2。因此，我们从所有未覆盖的元素（红色）和所有角落元素（绿色）中减去2。

调整步骤涉及从每个被覆盖的元素（红色）中减去最小的被覆盖元素（2），并将其（2）加到所有角元素（绿色）中。

尽管调整步骤后问题不变量保持不变的缘由可能不明显，但可以通过数学证明，从所有未覆盖成本中减去一个数字与将其添加到所有已覆盖成本两次是相等的，这保持了最优解不变。

尽管调整步骤后问题不变量保持不变的缘由可能并不明显，但可以通过数学证明，从所有未覆盖成本中减去一个数与将其添加到所有已覆盖成本两次是相等的，从而保持最优解不变。

这次转换是调整步骤的单次迭代，导致我们得到另一个等价的矩阵形式。与以前一样，我们进行检查以找出是否可以仅使用行来覆盖所有零。

这一次，所有的零只需要用 k = n = 4 条线覆盖。这意味着不需要进一步的调整步骤，可以恢复最终解决方案。

正如我们所看到的，这一次我们的确 需要画 k = n = 4 条线来覆盖所有的零。这意味着我们最终可以找回我们的解决方案！

否则，如果我们画的线少于 k < 4 条，我们应该重复调整步骤，直到线的数量变为 k = 4。

否则，如果我们画的线少于 k < 4 条，我们应该重复调整步骤，直到线的数量变为 k = 4。

3. 解决方案检索

唯一剩下的步骤是在不同的垂直和水平线上找到n个零。如果手动操作，最好从零较少的线开始。

在找到矩阵中零的位置后，我们可以切换回原始矩阵，并选择与找到的零一样位置的初始元素。这将是最终的分配！

在最后一步，必须找到 n = 4 个水平和垂直线上不重复的零点。它们的位置与初始矩阵的成本值的位置完全对应。

匈牙利算法的复杂度为O(n³)，其中n为矩阵的维度。

匈牙利算法的复杂度是O(n³)，其中n是矩阵的维度。

我们刚刚看到的分配问题也可以通过线性规划方法来解决。

我们刚刚看到的分配问题也可以通过线性规划方法来解决。

应用程序

匈牙利算法最明显的应用之一是用于分配问题，即给定n个任务，目标是将它们与其他人或物体（例如机器）最优地关联起来，以完成这些任务。

计算机视觉中还有一个特定的应用。许多视频跟踪算法（MOT）基于标准图像检测算法（例如YOLO）以及将来自几个独立帧的检测结果合并成视频流的逻辑的组合。

让我们来看一个视频的两个连续图像帧的简化示例：

两个连续视频帧的示例。

我们基于YOLO运行物体跟踪的MOT算法。YOLO的预测结果如下所示，显示在灰色框中。

YOLO算法在每一帧中检测到树上的两个球。目标是理解两个帧上的检测是如何相关的。

该目标是在两个帧之间关联边界框，以跟踪物体。一种可能的方法是分析两个帧之间边界框之间距离的变化。合理地假设，如果两个边界框的位置在两个帧之间变化不大，则它们属于同一个物体。

这就是匈牙利算法发挥作用的地方。我们可以构建一个矩阵，表明两个帧中不同边界框坐标之间的成对距离（这将是成本函数）。我们可以找到一种映射，最小化边界框之间的总距离。

应用到包含边界框中心之间距离的矩阵的匈牙利算法的结果。

通过运行匈牙利算法，我们得到以下映射：(A₁, C₂), (B₁, A₂), (C₁, B₂)。

我们可以验证它们导致总成本为8 + 1 + 5 = 14，这是此矩阵的最小可能函数成本。因此，找到的映射是最优的。

在两个帧上映射边界框。

当然，现代MOT算法在匹配边界框时思考了其他因素，包括轨迹分析、物体速度和方向、以及物理类似性等。为简单起见，我们只思考了一个因素：边界框之间的距离。不过，在现实中，还思考了更多因素。

当然，现代的多目标跟踪算法在匹配边界框时思考了其他因素，包括轨迹分析、物体速度和方向以及物理类似性等。为简单起见，我们只思考了一个因素：边界框之间的距离。不过，在现实中，会思考更多因素。

结论

在本文中，我们已经看过了用于解决任务分配问题的匈牙利算法。通过对初始数据矩阵执行简单操作，匈牙利算法将其转换为其他格式，同时保持问题不变。

尽管匈牙利算法具有立方复杂度，但在匹配和计算机视觉问题中具有广泛的应用，其中对象的数量不是太大。