DETR Models - 匈牙利匹配

@misc{detr-models,
  author = {仇镜溪},
  title = {DETR Models - 匈牙利匹配},
  howpublished = {仇镜溪},
  year = {2025},
  url = {https://jingxiqiu.com/zh/blog/detr-models/}
}

仇镜溪. (2025). DETR Models - 匈牙利匹配. In 仇镜溪.

仇镜溪. “DETR Models - 匈牙利匹配.” 仇镜溪, 2025.

仇镜溪. 2025. “DETR Models - 匈牙利匹配.” In 仇镜溪. Preprint.

这篇文章将解释DETR系列模型所使用的匈牙利匹配机制。区别于之前的Anchor系匹配机制，匈牙利匹配不需要NMS来去重。
本文将介绍：

1. 匈牙利匹配的机制/过程

2. 为什么“只靠 cost”就能得到匹配

3. 之前是怎么做的

4. 为什么换成匈牙利

5. 还有哪些可替代/可优化的匹配方案

匈牙利匹配#

匈牙利算法主要解决两个问题：

1. 求二分图的最大匹配数
2. 求二分图的最小点覆盖数

最大匹配问题#

在DETR匹配中，它会将一个图里的M个GT(ground truth)和N个预测(queries)看成两侧的二分图。匈牙利匹配的作用在于将M个GT和N个预测做匹配，得到一个O2O一一对应的结果（可以视作 线性指派问题 Linear Assignment Problem, LAP）。

我们首先定义一个代价函数，我们希望以最小的代价（类似最短路径）来得到匹配结果

在DETR中，这个代价函数为：

$$C[i,j]=\lambda_{cls}\cdot(−logp_j(y_i))+\lambda_{\ell_{1}}\cdot ||b^j−bi||_1+\lambda_{giou}\cdot(1−GIoU(\hat{b_j},b_i))$$

其中可以看到:

$\lambda_{cls}\cdot(−logp_j(y_i))$	是i预测对应j类型的概率
$\lambda_{\ell_{1}}\cdot
$\lambda_{giou}\cdot(1−GIoU(\hat{b_j},b_i))$	是第i个预测对应j锚框的GIoU损失

在匈牙利匹配中，我们希望选一组索引$\pi$使得总损失最小。

$$\min_{bijection \pi} \sum^M_{i=1}C[i,π(i)]$$

在 M×N 的代价矩阵上，用匈牙利算法找出总代价最小的双射（更准确：把 M 个真值匹到 N 个预测中的 M 个，保证一对一且全局最优）。时间复杂度约 O(max(M,N)^3)，N=100 时很快。

为什么换成匈牙利、匈牙利匹配造成的问题#

在DETR之前，主流检测器主要采用一对多(O2M)或者启发式分配，比如Anchor系，Anchor-free系，动态分配。

这些方法的好处是正样本密度大，因此模型训练收敛快，但问题是会产生重复框，需要依靠NMS去除。

而DETR做的是集合预测(Set Prediction),只允许每个目标出现一次，因此采用一对一的全局最优分配，推理时可以去掉NMS这一步。

但是同时带来的问题是，在训练时正样本密度较低，导致训练收敛慢。后续DINO/DEIM通过引入[对比去噪训练（CDN）与密集辅助分支（One-to-Many辅助监督）]等方法进行改善。

https://reimuyk.github.io/2021-04-01-konig-theorem/

https://zhuanlan.zhihu.com/p/96229700

https://zhuanlan.zhihu.com/p/1941526646839570865