多目标跟踪问题中都会遇到多个目标在两帧之间的匹配问题，这种多对多的匹配问题一般会使用匈牙利算法解决。匈牙利算法，本身解决的是一个指派问题。
指派问题描述：
实际中，会遇到这样的问题，有 m 项不同的任务，需要 n 个人分别完成其中的1项，每个人完成任务的时间不一样。于是就有一个问题，如何分配任务使得花费时间最少。转换到多目标跟踪中即可描述为：待跟踪匹配目标为 m 个，当前帧检测到 n 个目标，已知 m 个目标和 n 个检测结果之间的距离，求最有匹配，使得距离误差累计最小。
如下表所示：
通俗来讲，就是 m*n 矩阵中，选取 min(m,n) 个元素，每行每列各有1个元素，使得和最小。如果是求和最小问题，那么这个矩阵就叫做花费矩阵（Cost Matrix）；如果要是使求和最大化，那么这个矩阵就叫做利益矩阵（Profit Matrix）。
代码实现：
from scipy.optimize import linear_sum_assignmentimport numpy as npcost = np.array([[0.64, 1.63, 3.95, 4.09, 4.48],[3.95, 4.48, 0.73, 0.23, 2.26],[0.42, 0.70, 4.24, 4.56, 4.35],[3.73, 3.84, 1.07, 1.95, 0.85],[4.37, 5.02, 1.60, 0.73, 3.48]])row_ind, col_ind = linear_sum_assignment(cost)print('row_ind:', row_ind) # 开销矩阵对应的行索引print('col_ind:', col_ind) # 对应行索引的最优指派的列索引print('cost:', cost[row_ind, col_ind]) # 提取每个行索引的最优指派列索引所在的元素，形成数组print('cost_sum:', cost[row_ind, col_ind].sum()) # 最小开销
结果：
row_ind: [0 1 2 3 4] col_ind: [0 2 1 4 3] cost: [0.64 0.73 0.7 0.85 0.73] cost_sum: 3.65
矩阵中，行为目标，列为当前检测到待匹配框，可以看到仅使用最小距离，匹配结果为：0->0，1->3，2->0，3->4，4->3，0号、2号目标匹配到同一结果0，1号、3号目标匹配到同一结果3，存在一对多的情况。
经过最小化花费，匈牙利算法结果为：0->0，1->2，2->1，3->4，4->3，达到全局最优。
PS：该函数在m != n时，同样适用！
