多目标跟踪中的目标匹配算法

多目标跟踪算法

自动驾驶领域中的目标跟踪算法通常都是多目标跟踪算法，即 MOT（Multiple Object Tracking）。因为在这种场景中，要跟踪的目标往往不止一个。也有些文献会把这类问题称为 MTT（Multiple Target Tracking）。

MOT 问题中，并不是所有目标都会在第一帧出现，也并不是所有目标都会出现在每一帧。如何对出现的目标进行初始化，可以作为跟踪算法的一种分类方式。常见初始化方式大致分为两类：Tracking-by-Detection（TBD，也常写作 Detection-Based Tracking）和 Detection-Free Tracking。主要区别在于初始化和更新目标时，是依赖检测器输出，还是依赖人工或第一帧给定的目标初始化。

Detection-Free Tracking 通常需要在第一帧或某个起始帧手动初始化目标，后续不依赖每一帧检测器持续发现新目标。它更适合目标集合相对确定的场景。自动驾驶这类开放道路场景中，目标会不断进入和离开视野，因此当前主流 MOT 框架大多采用 Tracking-by-Detection 思路。

此外，MOT 的处理模式也分为两类：Online 和 Offline。Online Tracking 对视频帧进行逐帧处理，当前帧仅利用过去信息；Offline Tracking 会利用前后视频帧的信息对当前帧进行目标跟踪。由于 Offline 方法需要未来帧信息，所以通常不适合实时在线部署，但可以用于离线处理已经录制好的视频。

MOT 算法就先简单介绍一下，后面再深入。主要是因为我也刚开始学……

目标匹配算法

当前主流 MOT 框架大多是 Tracking-by-Detection 框架。这种框架依赖数据关联算法，也就是目标之间的匹配结果。

良好的匹配结果能保证目标 ID 的连续性，由此可见目标匹配是 MOT 中的重要环节。

目标匹配算法以二分图匹配为主。

假设帧中只有一辆车，那么一直进行目标检测是 OK 的，下图黄色车辆 ID 会一直为 1。

不过当帧中出现第二辆车，这种方法就寄了。

匈牙利算法

利用增广路寻找最大匹配的算法，就叫做匈牙利算法，可以认为是一类算法。

最大匹配指的是一个图所有匹配中，所含匹配边数最多的匹配。在线性分配问题（Linear Assignment Problem, LAP）中，我们通常会构造一个代价矩阵，然后寻找总代价最小的一组匹配。

作者注：LAP 问题的解法除了 Hungarian algorithm，还有 Jonker-Volgenant 算法，在实践中后者表现得更快，相关函数和算法简写为 lapjv。

简单描述一下：每个点从另一个集合里挑对象，没冲突的话就先安排上；要是冲突了，就用增广路径重新匹配。重复上述思路，直到无法继续增广，或者已经得到所需的可行匹配。

二分图

二分图又称作二部图，是图论中的一种特殊模型。设 \text{G} = (\text{V}, \text{E}) 是一个无向图，如果顶点集合 \text{V} 可分割为两个互不相交的子集 \text{A} 和 \text{B}，并且图中的每条边所关联的两个顶点 \text{i} 和 \text{j} 分别属于这两个不同的顶点集，即 \text{i} \in \text{A}、\text{j} \in \text{B}，则称图 \text{G} 为一个二分图。下图就是一个典型的二分图：

下图乍一看不是一个二分图，其实也是一个二分图。转换一下，就会发现它仍然可以划分为两个互不相交的点集：

增广路和交替路

交替路：从一个未匹配点出发，依次经过非匹配边 -> 匹配边 -> 非匹配边形成的路径。
增广路：从一个未匹配点出发，走交替路，如果途经另一个未匹配点（出发点不算），则这条交替路称为增广路。

增广路的性质：

\text{P} 的路径长度必定为奇数，第一条边和最后一条边都不属于 \text{M}，因为两个端点分属两个集合，且均未匹配。
\text{P} 经过取反操作可以得到一个更大的匹配 \text{M'}。
\text{M} 为 \text{G} 的最大匹配，当且仅当不存在相对于 \text{M} 的增广路径。

算法流程

趣写算法系列之--匈牙利算法_匈牙利算法基本原理-CSDN 博客这篇博客写得非常好，没有公式，只用了几张图片，非常方便理解。

配对流程以下面这个二分图为例。图中蓝色连线不是已匹配的边，而是一种初始可选连接状态，所以蓝色连线是非匹配边。

开始匹配，先给 A 匹配，A 和 a 会进行匹配，用红线将两者连起来，这条边变成了匹配边。但是接下来，B 也想和 a 匹配，这就产生了冲突。交替路和增广路可以用来解决这个冲突。

找一条交替路，也就是依次经过非匹配边（蓝线）、匹配边（红线）。那么我们从 B 出发找交替路：

（非匹配边）   （匹配边）   （非匹配边）
B ----------- a ----------- A ----------- c

B 和 c 都是未匹配的点，而且它们又是这条交替路的起点和终点。那么这条交替路就是增广路。现在进行一个取反操作，将上面这条增广路的匹配边变成非匹配边，非匹配边变成匹配边：

（匹配边）     （非匹配边） （匹配边）
B ----------- a ----------- A ----------- c

就得到了下图，A 和 c 匹配，B 和 a 匹配：

增广路最重要的特点是起点和终点都是非匹配点，这会导致非匹配边比匹配边多一条。取反之后，匹配边数量就会增加 1。取反的过程说白了，就是把原本匹配上的两个人拆散，给第三个人腾位置。

接下来对 C 进行匹配。C 要和 c 匹配，又产生了冲突，把上述过程再进行一次：

（非）   （匹）   （非）   （匹）   （非）
C ---- c ---- A ---- a ---- B ---- b

取反得到：

（匹）   （非）   （匹）   （非）   （匹）
C ---- c ---- A ---- a ---- B ---- b

得到下图，A、B、C 三个节点全部匹配完成，且找到了最大匹配。

KM（Kuhn-Munkres）算法

相比普通二分图最大匹配，KM 算法处理的是带权二分图匹配。更准确地说，KM 算法是用于求解二分图最大权完美匹配的经典算法。

在很多中文资料中，KM 算法、匈牙利算法、线性分配问题的 Hungarian method 经常会被放在一起讲。

这里可以先粗略理解为：普通二分图匹配更关心能不能匹配、最多匹配多少条边；带权匹配则进一步关心匹配质量，希望总代价最小或总收益最大。

如果一个图的某个匹配中，所有顶点都是匹配点，那么它就是一个完美匹配。完美匹配一定是最大匹配，但并非每个图都存在完美匹配。

这类方法会建立一个图，其中有前一帧和当前帧的 Node，然后计算两帧 Node 之间的距离或代价。距离越小，代表两帧 Node 之间越可能匹配。如果用的是相似度分数，则方向相反，通常是分数越大越可能匹配。下图以 Camera 和 LiDAR 融合为例：

距离矩阵

用一个距离矩阵为例：

每行减去最小值，第一行减 9，第二行减 5，第三行减 3：

每列减最小值，第一列减 1，第二列减 6，第三列减 0：

以最少数量的线，划掉所有 0：

若线数大于等于矩阵行列数，进入 Step 5；否则，找到未被覆盖元素中的最小值。未覆盖元素减去这个最小值，交叉覆盖处加上这个最小值，其他已覆盖元素不变。

上图可以看出，剩下的 [3, 7; 5, 2] 全部减了 2，同时线条交叉的部分加了 2。再划线：

当线数等于矩阵行列数时，就可以寻找一组最优分配。常见做法是优先选择只有一个 0 的行或列，也可以通过回溯等策略得到一组合法的最优匹配。

最终匹配为：

WorkerA <-> Job2
WorkerB <-> Job3
WorkerC <-> Job1

距离的计算

欧氏距离，即 Bounding Box 的中心点距离。这种方法简单直观，但不能很好处理目标形状发生变化，或目标与其他目标重叠的情况。

IoU，交并比。这种方法会让我们要解决的问题从寻找最小 Distance，变为寻找最大 IoU。

Appearance Cost

DeepSORT 会使用 Bounding Box 内的外观信息。通常做法是用 CNN 提取目标外观 embedding，然后根据 embedding 之间的距离或相似度计算 appearance cost。相比 SORT 算法，DeepSORT 额外引入了 BBox 内的外观信息，因此在遮挡和目标交叉场景中更稳一些，但计算成本也更高。

Corner Case

若前帧出现了 3 个目标，后帧出现了 4 个目标，也就是从 N x N 问题变成了 N x M 问题。

解决办法之一是将矩形矩阵扩展为方阵。很多算法库可以直接处理矩形分配问题；如果手动扩展，可以增加 dummy 行或 dummy 列。dummy 的代价应按业务含义设置为未匹配代价，不一定简单取整个矩阵最大值。

最大值和最小值

如果使用 IoU，想进行最大 IoU 匹配；或者有相似性 cost，想进行最大相似性匹配，可以把相似度最大化问题转成代价最小化问题。

常见做法包括：

如果分数范围是 [0, 1]，可以使用 cost = 1 - IoU。
如果使用一般相似度分数，可以使用 cost = max_score - score。

Hungarian VS Kuhn-Munkres

两者的关系困扰我非常久，疑问包括：【Hungarian 算法到底是不是带权的？】【很多 MOT 用到了 Hungarian 算法，咋还带权重啊？】，【Hungarian 算法和 KM 算法的区别就是带不带权重？】

为了解决这个困惑，我决定先去看看 Hungarian 算法的论文和历史。

算法之所以叫 Hungarian，是因为这套算法建立在 1930s 的两位匈牙利数学家（Dénes 的二分图和 Jenő 的加权匹配）建立的图论定理之上。Hungarian 算法最初是为了解决 LAP 问题。

很多跟踪算法，都说自己使用的是 Hungarian 算法而非 KM 算法。

ByteTrack 的论文原文：

Then, we adopt Hungarian Algorithm [31] to finish the matching based on the similarity.

引用文献是：

H. W. Kuhn. The Hungarian Method for the Assignment Problem. Naval Research Logistics Quarterly, 1955.

The Hungarian method for the assignment problem 论文摘要第一行说的就是：

assuming that numerical scores are available for the performance of each of n persons on each of n jobs ... assignment so that the sum of the scores obtained is as large as possible

意为假设每个人执行每个任务都有一个数值评分，然后任务分配要尽可能最大化总数值评分。说明 1955 年的提出的 Hungarian 算法本身就是带权重的分配问题。

两年后 James Munkres 对 Kuhn 提出的 Hungarian 算法提出了改进，看了这么多文章，大家都知道 Munkres 做了改进，但是具体改进了什么，CSDN 的作者们守口如瓶。

Algorithms for the Assignment and Transportation Problems 这篇短短 7 页的论文做出的改进如下：

给出了严格的算法流程，Step 1 到 Step 3
做了完整的算法终止性证明，算法终止性是最坏情况下需要做多少次计算（必须有限）
做了完整时间复杂度计算，当年朴素实现 \text O(\text n^4)

这也是为什么我把 Hungarian 算法和 KM 算法的介绍放在了前面。因为两者的讲述模式已经说明了问题： Hungarian 算法只是提出了一种纯数学上的证明，但是 KM 算法则是将它进一步算法化，给出了严格的计算流程，目的就是让一个会线性代数的人，能够根据 KM 的流程， Step-by-Step 求出最终匹配结果。

我们捋一下历史：

1930s 两位匈牙利数学家建立二分图匹配和加权匹配理论
1955年 Kuhn 发表了 Hungarian 算法论文，用于解决 LAP 问题
1957年 Munkres 对 Kuhn 的论文提出了改进，被称作 Kuhn-Munkres 算法

所以，【Hungarian 算法到底是不是带权的？】【很多 MOT 用到了 Hungarian 算法，咋还带权重啊？】，【Hungarian 算法和 KM 算法的区别就是带不带权重？】这类问题的答案基本明了。

在图论语境中，Hungarian 算法本质上是基于增广路径的二分图最大匹配算法，是无权重的匹配问题。如果你是搞数学的，搞 ACM 的，这么说没错，但是这个和 1955 年的那篇 Hungarian method 不是同一个算法问题 ，人家一开始就是带权的。但是并非没有历史关系，二者都源于 Hungarian method。

在工程和 MOT 语境中，Hungarian 算法也经常指求解线性分配问题的最小代价匹配方法。如果你是 CV/MOT 领域的，这么说没错，LAP 在这个领域的算法都是™带权的。