摘要：本文将带你走进其中一个关键工具——匈牙利算法。它原本是为解决“工人任务分配”这类经典最优化问题而提出的，却在计算机视觉中焕发新生：通过构建代价矩阵，它能在多个候选目标之间找到最佳匹配，为 MOT 提供高效而稳定的解决方案。>>更多资讯可加入CV技术群获取了解哦

【导读】

本文将带你走进其中一个关键工具——匈牙利算法。它原本是为解决“工人任务分配”这类经典最优化问题而提出的，却在计算机视觉中焕发新生：通过构建代价矩阵，它能在多个候选目标之间找到最佳匹配，为 MOT 提供高效而稳定的解决方案。>>更多资讯可加入CV技术群获取了解哦

多目标跟踪（MOT, Multi-object tracking）是一项任务，要求算法能够在视频中检测并跟踪多个目标。大多数已知算法都是基于图像级的检测器（如 YOLO），它们最初是为单张图像处理设计的。整体方法通常是在连续视频帧上分别运行检测器，然后在不同帧之间匹配属于同一目标的边界框。

MOT 算法的核心区别在于：它们如何在视频帧之间执行匹配。

在匹配时可能会考虑以下因素：

在某些情况下，对于连续帧 A 和 B 上的每对边界框，这些特征会被组合为一个数值，表示它们属于同一目标的可能性。

计算完成后，MOT 算法会尝试找出所有边界框之间的最佳匹配。更具体地说，给定帧 A 和帧 B 上的 n 个检测框，目标是建立一个一一映射，使得每个边界框都只被使用一次。

匈牙利算法

匈牙利算法通常在算法与数据结构课程中学习。但它也有很多应用场景，尤其是在匹配问题中。在多目标跟踪中，它就常被用来解决“轨迹片段（tracklet）匹配”的问题。

名字“匈牙利”来源于该方法主要基于两位匈牙利数学家 Dénes Kőnig 和 Jenő Egerváry 的工作。

问题形式化

最常见的例子是“工人和任务”的问题：

有 n 个工人和 n 个任务；

每个工人完成每个任务所需的成本（工资）已知；

需要给每位工人分配一个任务，使得所有任务都完成，并且总成本最小化。

这类问题可以通过构建一个 n × n 的成本矩阵来描述。目标是从中选择 n 个元素，且每行每列都不重复，同时使总和最小。

基本思想

匈牙利算法的核心思想是通过一系列矩阵变换，把原始矩阵转化为更容易寻找解的形式。虽然矩阵在变换，但问题本质保持不变。

示例过程

行列归约（Row & Column Reduction）

从每一行中减去该行的最小值，使每行至少有一个 0。

再从每一列中减去该列的最小值，使每列也至少有一个 0。

这样可以生成带有若干“0”的新矩阵，代表潜在的最优分配。

接着，画出最少数量的水平和垂直直线来覆盖所有的 0。

如果所需直线数量 k = n，说明找到了解；

如果 k

调整步骤（Adjustment Step）

找出所有未覆盖元素中的最小值 m；

将 m 从所有未覆盖元素中减去，并加到所有交叉覆盖的元素上。

这样调整后，新的矩阵依然保持问题不变。重复这个过程，直到能用 n 条直线覆盖所有 0。

解决方案检索（Solution Retrieval）

从矩阵中选择 n 个互不在同一行或同一列的 0；

将它们映射回原始矩阵，即得到最优分配方案。

匈牙利算法的复杂度为 O(n³)。

应用

任务分配问题：为工人、机器、车辆等分配任务，成本最低。

计算机视觉中的多目标跟踪（MOT）：

在两帧图像中，目标检测器（如 YOLO）会生成多个边界框；

需要确定哪些框在前后帧中属于同一个目标；

可以通过构建“代价矩阵”（如边界框中心点的距离）来衡量匹配代价；

使用匈牙利算法找到最优匹配。

现代 MOT 算法还会考虑更多因素（速度、方向、外观相似度等），但核心思想依然可以简化为：构建代价矩阵 + 匈牙利算法求解。

如果你也想要使用模型进行训练或改进，Coovally——新一代AI开发平台，为研究者和产业开发者提供极简高效的AI训练与优化体验！Coovally支持计算机视觉全任务类型，包括目标检测、文字识别、实例分割并且即将推出关键点检测、多模态3D检测、目标追踪等全新任务类型。

千款模型+海量数据，开箱即用！

平台汇聚国内外开源社区超1000+热门模型，覆盖YOLO系列、Transformer、ResNet等主流视觉算法。同时集成300+公开数据集，涵盖图像分类、目标检测、语义分割等场景，一键下载即可投入训练，彻底告别“找模型、配环境、改代码”的繁琐流程！

在Coovally平台上，你可以一键训练类似的端到端模型训练流程，将目标跟踪与下游行业场景（如无人机监控、体育分析、安防）结合起来，形成完整的智能化解决方案。

平台链接：

Coovally平台还可以直接查看“实验日志”。在每一个实验详情页中，用户都可以实时查看训练日志、输出信息或报错内容，无需额外配置、无缝集成于工作流中！

不论是模型调参、错误排查，还是过程复现，这项新功能都将大幅提升你的实验效率。

结论

匈牙利算法是一种高效的最优化方法，适用于各种匹配与分配问题。尽管它的时间复杂度是 O(n³)，但在目标数量不是特别大的场景中（如 MOT），它依然表现出很强的实用性。

来源：小码科普君