匈牙利算法是多目标追踪算法中最基础的数据关联方法。

基本思路

在追踪问题当中，我们的目标是将“当前时刻的检测目标”和“过去（上一时刻）已经存在的目标轨迹”进行一一对应。经过过去学者的研究，将这个问题转换为一个分配问题，从而可以用匈牙利算法进行求解。

数学表达

分配问题

对于 $( n \times n )$ 的代价矩阵 $( C )$，需要求得最小的总代价：
$$
\min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}
$$
并且满足以下约束条件：

  • 每个人只能完成一个任务且必须做一个任务：
    $$
    \sum_{i=1}^n x_{ij} = 1 \quad \forall j = 1, 2, \ldots, n
    $$

  • 每个任务只能由一个人完成且必须完成：
    $$
    \sum_{j=1}^n x_{ij} = 1 \quad \forall i = 1, 2, \ldots, n
    $$

  • $( x_{ij} )$ 是二进制变量：
    $$
    x_{ij} \in {0, 1} \quad \forall i, j = 1, 2, \ldots, n
    $$

$c_{ij}$ 表示第 i 个任务由第 j 个人完成的代价

$x_{ij}$表示第 i 个任务是否由第 j 个人完成

匈牙利算法伪代码

输入: 检测框列表 $D$, 轨迹列表 $T$, IoU 阈值 $\theta$

输出: 匹配列表 $M$

1. 构建代价矩阵:

$cost matrix$ $\leftarrow$ 计算检测框与轨迹之间的代价矩阵

2. 矩阵预处理:

对于每一行 $i$：
$$cost_matrix[i, :] \leftarrow cost_matrix[i, :] - \min(cost_matrix[i, :])$$

对于每一列 $j$：
$$cost_matrix[:, j] \leftarrow cost_matrix[:, j] - \min(cost_matrix[:, j])$$

3. 寻找零元素并标记:

$marked_{zeros} \leftarrow$ 使用最少数量的线覆盖所有零元素

4. 调整矩阵:

当覆盖线的数量不等于矩阵的行数或列数时：
调整矩阵，重新寻找零元素并标记
找到步骤 3 中未被一行覆盖的最小元素（称为 k）。从所有未覆盖的元素中减去 k，然后将 k 添加到覆盖两次的元素中。

5. 提取匹配:

$M \leftarrow$ 从标记的零元素中提取匹配对

返回结果:

返回 $M$

代码实现

调用库函数的实现

1
2
3
from scipy.optimize import linear_sum_assignment
cost =np.array([[4,1,3],[2,0,5],[3,2,2]])
row_ind,col_ind=linear_sum_assignment(cost)

SORT的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import lap
import numpy as np

def linear_assignment(cost_matrix, extend_cost=True):
if extend_cost:
# 这里可以根据需要扩展代价矩阵
# 例如，如果cost_matrix不是方阵，可以添加无穷大的填充值
# 但lap.lapjv通常可以直接处理非方阵，所以这里简化处理
pass
row_ind, col_ind, cost = lap.lapjv(cost_matrix)
return cost, row_ind, col_ind

# 示例代价矩阵
cost_matrix = np.array([[4, 1, 3], [2, 0, 5], [3, 2, 2]])

# 调用函数
cost, row_ind, col_ind = linear_assignment(cost_matrix)

print("最小代价:", cost)
print("行分配:", row_ind)
print("列分配:", col_ind)