Hungarian Algorithm

匈牙利算法是一种精确的优化方法，可找到成本最低的一对一匹配，为两个集合中较小集合的每个元素配对。它会优化所有选定配对的总成本。在计算机视觉中，它用于将检测结果与跟踪对象配对，或将预测结果与训练目标配对。

Harold W. Kuhn 于 1955 年在《指派问题的匈牙利方法》中提出了该算法。匈牙利方法和 Kuhn–Munkres 算法是同一类算法的不同名称。该算法以匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 命名，他们的研究为这一方法奠定了基础。

匈牙利算法的工作原理#

输入是一个成本矩阵：每一行表示一个集合中的元素，每一列表示另一个集合中的元素，每个条目表示将这两个元素配对的成本。对于方阵，解会在每行和每列中恰好选取一个条目。贪心策略会选定单个看似划算的配对；匈牙利匹配则会找到全局总成本最低的方案。

在经典的矩阵约简过程中，从每一行减去该行的最小值，再从每一列减去该列的最小值。由于每个完整指派都会恰好使用每一行和每一列一次，这些约简不会改变最优完整指派。用尽可能少的水平线和垂直线覆盖所有零值。如果一个 n x n 矩阵需要 n 条线，则选择 n 个零值，且这些零值不能共用行或列。否则，从未覆盖的条目中减去最小的未覆盖值，并在覆盖线的交点处加上该值，然后重复覆盖测试。使用原始矩阵计算指派的成本。

高效的匈牙利算法实现对方阵的运行时间为 O(n³)，而可能的完整指派有 n! 种。

计算机视觉中的应用#

多目标跟踪。原始 SORT 设计将匈牙利指派与卡尔曼滤波器结合使用，由卡尔曼滤波器预测每条轨迹的位置。交并比用于衡量预测边界框与检测到的边界框之间的重叠程度。SORT 的参考实现使用 LAPJV 或 SciPy 求解指派，拒绝重叠度低的关联，并为未匹配的检测结果创建身份标识。

目标检测训练。DETR使用匈牙利匹配，将无序预测与标注对象配对。它的Transformer会生成预测槽位，匹配过程则结合分类成本和边界框位置成本。只要槽位足够，每个目标都会获得一个预测，使损失函数不受标注顺序影响；未匹配的槽位则学习“无目标”类别。Ultralytics 在 RT-DETR 中采用了这种指派方案：其中的匈牙利匹配器结合分类成本、L1 坐标距离和广义 IoU 成本。其线性指派后端使用经过修改的 Jonker–Volgenant 求解器来选择训练配对。

Python 中的匈牙利匹配#

munkres Python 包实现了匈牙利方法。使用 pip install munkres 安装，然后求解其示例成本矩阵：

from munkres import Munkres

costs = [
    [5, 9, 1],
    [10, 3, 2],
    [8, 7, 4],
]
solver = Munkres()
assignments = solver.compute(costs)
# Read costs from the original matrix.
minimum_cost = sum(costs[row][col] for row, col in assignments)
print(f"Minimum total cost: {minimum_cost}")

输出为 Minimum total cost: 12，这是在每行和每列中各选取一个条目时所能达到的最小总和。

相关方法和未匹配对象#

指派问题是要解决的任务；匈牙利算法是其中一种求解方法。非极大值抑制会移除图像中的竞争检测结果。目标重识别为关联提供外观信息，通常通过嵌入向量并使用余弦相似度进行比较。这类分数可以用作匹配成本。

集合大小不同时会产生矩形矩阵。跟踪还需要拒绝规则或具有明确未匹配成本的虚拟条目，以处理漏检和新出现的对象。错误关联会导致身份切换：一条轨迹的 ID 转移到另一个对象。

SciPy 的线性指派求解器使用经过修改的 Jonker–Volgenant 算法求解同一优化问题。对于 r x c 的矩形矩阵，只要存在可行的完整指派，求解器就会返回恰好 min(r, c) 个配对。