目标跟踪中的匈牙利算法

• 从数学角度来看，线性分配问题（也称为匈牙利算法或指派问题）是一个经典的优化问题，其目的是在两个集合之间找到最佳匹配，使得总成本最小。我们可以将其形式化为一个二分图的最小权匹配问题。
  

数学配景

假设我们有两个集合 ( A ) 和 ( B )，此中 ( A ) 有 ( m ) 个元素，( B ) 有 ( n ) 个元素。我们有一个 ( m \times n ) 的成本矩阵 ( C )，此中 ( C[i, j] ) 表示将 ( A ) 中的第 ( i ) 个元素分配给 ( B ) 中的第 ( j ) 个元素的成本。
目标是找到一个匹配                                    (                         M                         ⊆                         A                         ×                         B                         )                              (M \subseteq A \times B )                  (M⊆A×B)，使得总成本
                                              ∑                                       (                               i                               ,                               j                               )                               ∈                               M                                            C                         [                         i                         ,                         j                         ]                              \sum_{(i, j) \in M} C[i, j]                  ∑(i,j)∈M​C[i,j]
最小，而且每个元素最多匹配一次。
算法解释

1. 空成本矩阵的处置惩罚

假如成本矩阵为空（即没有元素），则直接返回空匹配和未匹配的索引。

1. if cost_matrix.size == 0:
2.     return np.empty((0, 2), dtype=int), tuple(range(cost_matrix.shape[0])), tuple(range(cost_matrix.shape[1]))

复制代码

2. 利用 LAPJV 算法

假如选择利用 LAPJV 算法（来自 lap 库），则执行以下步骤：

1. _, x, y = lap.lapjv(cost_matrix, extend_cost=True, cost_limit=thresh)

复制代码

• lap.lapjv 函数返回三个数组：
  
  
  
  • 第一个数组（未利用）是总成本。
    
  • x 数组表示每个 ( A ) 中元素的匹配结果，假如未匹配则为 -1。
    
  • y 数组表示每个 ( B ) 中元素的匹配结果，假如未匹配则为 -1。
    
  
  

1. matches = [[ix, mx] for ix, mx in enumerate(x) if mx >= 0]
2. unmatched_a = np.where(x < 0)[0]
3. unmatched_b = np.where(y < 0)[0]

复制代码

• matches 是一个列表，包罗所有有用的匹配对。
  
• unmatched_a 和 unmatched_b 分别是未匹配的 ( A ) 和 ( B ) 中的索引。
  

3. 利用 SciPy 的线性和分配算法

假如选择利用 SciPy 的 linear_sum_assignment 算法，则执行以下步骤：

1. x, y = scipy.optimize.linear_sum_assignment(cost_matrix)

复制代码

• scipy.optimize.linear_sum_assignment 返回两个数组：
  
  
  
  • x 表示 ( A ) 中元素的匹配索引。
    
  • y 表示 ( B ) 中元素的匹配索引。
    
  
  

1. matches = np.asarray([[x[i], y[i]] for i in range(len(x)) if cost_matrix[x[i], y[i]] <= thresh])

复制代码

• 这行代码筛选出所有匹配成本不凌驾阈值的匹配对。
  

1. if len(matches) == 0:
2.     unmatched_a = list(np.arange(cost_matrix.shape[0]))
3.     unmatched_b = list(np.arange(cost_matrix.shape[1]))
4. else:
5.     unmatched_a = list(set(np.arange(cost_matrix.shape[0])) - set(matches[:, 0]))
6.     unmatched_b = list(set(np.arange(cost_matrix.shape[1])) - set(matches[:, 1]))

复制代码

• 假如没有有用匹配，所有元素都未匹配。
  
• 否则，计算未匹配的 ( A ) 和 ( B ) 中的索引。
  

线性分配问题通过最小化总成本来找到两个集合之间的最佳匹配。上述函数实现了这个过程，并提供了两种差异的算法选择（LAPJV 和 SciPy 的线性和分配算法）。通过筛选出有用的匹配对和未匹配的元素索引，函数可以有用地处置惩罚目标跟踪等应用中的匹配问题。

• 匹配过程的计算涉及到解决一个优化问题，即找到两个集合之间的最佳匹配，使得总成本最小。这个问题可以用匈牙利算法（Hungarian Algorithm）或其他线性分配算法来解决。下面详细解释这些算法是怎样计算匹配的。
  

1. 匈牙利算法（Hungarian Algorithm）

匈牙利算法是一个经典的解决线性分配问题的算法，具有多项式时间复杂度。它的根本思想是通过渐渐修改成本矩阵，找到一个零成本的完善匹配。具体步骤如下：
1.1 构造初始零矩阵

• 从每一行中减去该行的最小值，使得每一行至少有一个零。
  
• 从每一列中减去该列的最小值，使得每一列至少有一个零。
  

1.2 覆盖零

• 尽可能少地画横线和竖线覆盖所有的零。
  
• 假如所需的线条数量等于行（或列）的数量，则找到最优匹配。
  

1.3 调解矩阵

• 假如线条数量少于行（或列）的数量，找出未被覆盖的最小元素，将其从所有未覆盖元素中减去，并将其加到所有被两条线覆盖的元素上，重复步骤1.2。
  

2. LAPJV 算法

LAPJV（Jonker-Volgenant Algorithm）是匈牙利算法的一个高效变种，适用于稀疏矩阵。它通过扩展成本矩阵和利用增广路径技术来找到最优匹配。
2.1 初始化

• 初始化标号（labels）和匹配。
  
• 标号表示当前的成本调解，匹配表示当前的部门匹配。
  

2.2 构造增广路径

• 从未匹配的行开始，探求增广路径。
  
• 增广路径是从未匹配的行到未匹配的列的一条路径，通过调解标号来找到更低成本的匹配。
  

2.3 更新匹配

• 利用增广路径更新匹配。
  
• 重复构造增广路径和更新匹配，直到找到最优匹配。
  

3. SciPy 的线性和分配算法

SciPy 的 linear_sum_assignment 函数实现了匈牙利算法。它通过以下步骤来计算匹配：
3.1 构造初始零矩阵

• 从每一行中减去该行的最小值。
  
• 从每一列中减去该列的最小值。
  

3.2 覆盖零

• 利用最少的线条覆盖所有的零。
  

3.3 调解矩阵

• 找到未覆盖的最小元素，调解矩阵。
  
• 重复覆盖零和调解矩阵，直到找到最优匹配。
  

示例

假设我们有如下成本矩阵：
                                         C                            =                                       [                                                                                     4                                                                                             1                                                                                             3                                                                                                                   2                                                                                             0                                                                                             5                                                                                                                   3                                                                                             2                                                                                             2                                                                                 ]                                            C = \begin{bmatrix} 4 & 1 & 3 \\ 2 & 0 & 5 \\ 3 & 2 & 2 \end{bmatrix}                     C=               ​423​102​352​               ​
利用匈牙利算法计算匹配

• 构造初始零矩阵：
  
  
  
  • 行减去最小值：                                                  [                                                                                            3                                                                                                    0                                                                                                    2                                                                                                                            2                                                                                                    0                                                                                                    5                                                                                                                            1                                                                                                    0                                                                                                    0                                                                                        ]                                          \begin{bmatrix} 3 & 0 & 2 \\ 2 & 0 & 5 \\ 1 & 0 & 0 \end{bmatrix}                                            ​321​000​250​                 ​
    
  • 列减去最小值：                                                  [                                                                                            3                                                                                                    0                                                                                                    2                                                                                                                            1                                                                                                    0                                                                                                    5                                                                                                                            0                                                                                                    0                                                                                                    0                                                                                        ]                                          \begin{bmatrix} 3 & 0 & 2 \\ 1 & 0 & 5 \\ 0 & 0 & 0 \end{bmatrix}                                            ​310​000​250​                 ​
    
  
  
• 覆盖零：
  
  
  
  • 利用最少的线条覆盖所有的零。
    
  
  
• 调解矩阵：
  
  
  
  • 找到未覆盖的最小元素，调解矩阵。
    
  
  
• 找到匹配：
  
  
  
  • 通过增广路径找到最优匹配。
    
  
  

最终匹配结果可能是 ((0, 1), (1, 0), (2, 2))，总成本为 (1 + 2 + 2 = 5)。

• 匹配过程的核心是通过调解成本矩阵，使得在零成本上找到一个完善匹配。匈牙利算法和 LAPJV 算法都通过差异的路径和技术来实现这一目标。SciPy 的 linear_sum_assignment
  函数实现了匈牙利算法，提供了一个高效的解决方案。
  

在目标跟踪问题中，目标框之间的匹配通常是通过计算每个目标框之间的相似度或距离来实现的。以下是一个常见的匹配过程，结合了匈牙利算法或其他线性分配算法来找到最佳匹配。
1. 定义成本矩阵

起首，我们须要定义一个成本矩阵                                    C                              C                  C，此中每个元素                                    C                         [                         i                         ,                         j                         ]                              C[i, j]                  C[i,j] 表示第                                    i                              i                  i 个目标框和第                                    j                              j                  j 个目标框之间的匹配成本。匹配成本可以基于多种度量方式，例如欧氏距离、IoU（Intersection over Union）、马氏距离等。
1.1 欧氏距离

假如目标框的位置用中央点表示，可以计算中央点之间的欧氏距离：
                                    C                         [                         i                         ,                         j                         ]                         =                                              (                                           x                                  i                                          −                                           x                                  j                                                      )                                  2                                          +                               (                                           y                                  i                                          −                                           y                                  j                                                      )                                  2                                                            C[i, j] = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}                  C[i,j]=(xi​−xj​)2+(yi​−yj​)2            ​
1.2 IoU（Intersection over Union）

IoU 是目标跟踪中常用的度量方式，表示两个边界框的交集与并集之比：
                                    C                         [                         i                         ,                         j                         ]                         =                         1                         −                         IoU                         (                                   B                            i                                  ,                                   B                            j                                  )                              C[i, j] = 1 - \text{IoU}(B_i, B_j)                  C[i,j]=1−IoU(Bi​,Bj​)
此中，                                             B                            i                                       B_i                  Bi​ 和                                              B                            j                                       B_j                  Bj​ 分别是第                                    i                              i                  i个和第                                    j                              j                  j 个目标框。
2. 构造成本矩阵

假设我们有两个集合：上一帧的目标框集合                                    A                              A                  A 和当前帧的目标框集合                                    B                              B                  B。我们构造一个成本矩阵                                    C                              C                  C，此中                                   C                         [                         i                         ,                         j                         ]                              C[i, j]                  C[i,j] 表示                                    A                              A                  A中的第                                    i                              i                  i 个目标框和                                    B                              B                  B 中的第                                    j                              j                  j 个目标框之间的匹配成本。
3. 计算匹配

利用匈牙利算法或其他线性分配算法来计算最佳匹配。下面是一个利用 scipy.optimize.linear_sum_assignment 函数的示例：

1. import numpy as np
2. from scipy.optimize import linear_sum_assignment
4. # 假设 cost_matrix 是预先计算好的成本矩阵
5. cost_matrix = np.array([
6.     [4, 1, 3],
7.     [2, 0, 5],
8.     [3, 2, 2]
9. ])
11. # 使用匈牙利算法计算最佳匹配
12. row_ind, col_ind = linear_sum_assignment(cost_matrix)
14. # row_ind 和 col_ind 分别表示最佳匹配的行索引和列索引
15. matches = list(zip(row_ind, col_ind))
16. print("匹配结果:", matches)

复制代码

4. 处置惩罚未匹配的目标框

在现实应用中，可能会有一些目标框没有找到匹配。我们须要处置惩罚这些未匹配的目标框：

1. # 找到未匹配的目标框
2. unmatched_a = list(set(range(cost_matrix.shape[0])) - set(row_ind))
3. unmatched_b = list(set(range(cost_matrix.shape[1])) - set(col_ind))
5. print("未匹配的A中的目标框索引:", unmatched_a)
6. print("未匹配的B中的目标框索引:", unmatched_b)

复制代码

5. 更新目标状态

根据匹配结果更新目标状态。例如，可以更新目标的轨迹、位置等信息。
示例总结

假设我们有以下成本矩阵：
                                         C                            =                                       [                                                                                     4                                                                                             1                                                                                             3                                                                                                                   2                                                                                             0                                                                                             5                                                                                                                   3                                                                                             2                                                                                             2                                                                                 ]                                            C = \begin{bmatrix} 4 & 1 & 3 \\ 2 & 0 & 5 \\ 3 & 2 & 2 \end{bmatrix}                     C=               ​423​102​352​               ​
通过 linear_sum_assignment 函数，我们可以计算出最佳匹配：

1. row_ind, col_ind = linear_sum_assignment(cost_matrix)
2. matches = list(zip(row_ind, col_ind))

复制代码

匹配结果可能是 ((0, 1), (1, 0), (2, 2))。
通过定义成本矩阵并利用匈牙利算法或其他线性分配算法，我们可以在目标跟踪中找到最佳的目标框匹配。匹配过程包括计算成本矩阵、利用优化算法计算最佳匹配、处置惩罚未匹配的目标框以及更新目标状态。这些步骤可以帮助我们在视频帧之间有用地跟踪目标。

• 目标检测中的非极大值抑制（Non-Maximum Suppression, NMS）和匈牙利算法解决的匹配问题是两个差异的概念，尽管它们都涉及到目标框的处置惩罚，但它们的应用场景和目的差异。
  

非极大值抑制（NMS）

NMS 是一种后处置惩罚技术，用于在目标检测中消除多余的检测框。目标检测算法通常会在同一目标上产生多个重叠的检测框，NMS 通过以下步骤来保留最好的检测框并去除冗余的框：

• 排序：根据检测框的置信度得分对所有检测框举行排序，从高到低。
  
• 选择最高得分框：选择得分最高的检测框，并将其加入最终的检测结果中。
  
• 移除重叠框：计算其他检测框与当前选择框的 IoU（Intersection over Union），假如 IoU 凌驾预设的阈值，则将这些重叠的检测框移除。
  
• 重复：重复步骤 2 和 3，直到没有剩余的检测框。
  

NMS 的目的是减少冗余检测框，保留最有可能的目标框。
匈牙利算法

匈牙利算法用于解决线性分配问题，目的是在两个集合之间找到最佳匹配，使得总的匹配成本最小。它通常用于目标跟踪中的目标框匹配，具体步骤如前面所述，包括构造成本矩阵、利用匈牙利算法计算最佳匹配以及处置惩罚未匹配的目标框。
NMS 和匈牙利算法的区别

• 目的：
  
  
  
  • NMS：用于消除冗余检测框，保留最有可能的目标框。
    
  • 匈牙利算法：用于在两个集合之间找到最佳匹配，使得总的匹配成本最小。
    
  
  
• 应用场景：
  
  
  
  • NMS：主要用于目标检测的后处置惩罚阶段。
    
  • 匈牙利算法：主要用于目标跟踪中的目标框匹配。
    
  
  
• 处置惩罚方式：
  
  
  
  • NMS：基于检测框的置信度得分和 IoU 举行排序和移除。
    
  • 匈牙利算法：基于成本矩阵和优化算法找到最佳匹配。
    
  
  

示例

假设我们在目标检测中得到了以下检测框和对应的置信度得分：

• 框 1：得分 0.9
  
• 框 2：得分 0.8
  
• 框 3：得分 0.7
  

这些检测框有一定的重叠度。NMS 的工作流程如下：

• 排序：框 1、框 2、框 3。
  
• 选择最高得分框：选择框 1。
  
• 移除重叠框：计算框 1 与框 2、框 3 的 IoU，假如 IoU 凌驾阈值，将这些框移除。
  
• 重复：选择下一个最高得分框（框 2），重复步骤 3，直到没有剩余的检测框。
  

最终，NMS 将保留最有可能的目标框，减少冗余。
非极大值抑制（NMS）和匈牙利算法解决的匹配问题是差异的技术，尽管它们都涉及到目标框的处置惩罚。NMS 主要用于目标检测的后处置惩罚阶段，以消除冗余检测框，而匈牙利算法主要用于目标跟踪中的目标框匹配，以找到最佳匹配。两者在目的、应用场景和处置惩罚方式上都有显著区别。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。