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

基本思路

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

数学表达

分配问题

对于 \( n \times n \) 的代价矩阵 \( C \)，需要求得最小的总代价：

min⁡∑i=1n∑j=1ncijxij\min \sum_{i=1}^n \sum_{j=1}^n c_{ij} x_{ij}

并且满足以下约束条件：

  • 每个人只能完成一个任务且必须做一个任务：

∑i=1nxij=1∀j=1,2,…,n\sum_{i=1}^n x_{ij} = 1 \quad \forall j = 1, 2, \ldots, n

  • 每个任务只能由一个人完成且必须完成：

∑j=1nxij=1∀i=1,2,…,n\sum_{j=1}^n x_{ij} = 1 \quad \forall i = 1, 2, \ldots, n

  • \( x_{ij} \) 是二进制变量：

xij∈{0,1}∀i,j=1,2,…,nx_{ij} \in \{0, 1\} \quad \forall i, j = 1, 2, \ldots, n

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

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

匈牙利算法伪代码

输入: 检测框列表 DD, 轨迹列表 TT, IoU 阈值 θ\theta

输出: 匹配列表 MM

1. 构建代价矩阵:

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

2. 矩阵预处理:

对于每一行 ii：

cost_matrix[i,:]←cost_matrix[i,:]−min⁡(cost_matrix[i,:])cost\_matrix[i, :] \leftarrow cost\_matrix[i, :] - \min(cost\_matrix[i, :])

对于每一列 jj：

cost_matrix[:,j]←cost_matrix[:,j]−min⁡(cost_matrix[:,j])cost\_matrix[:, j] \leftarrow cost\_matrix[:, j] - \min(cost\_matrix[:, j])

3. 寻找零元素并标记:

marked_zeros←marked\_{zeros} \leftarrow 使用最少数量的线覆盖所有零元素

4. 调整矩阵:

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

5. 提取匹配:

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

返回结果:

返回 MM

代码实现

调用库函数的实现

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)