多目标跟踪-DeepSort分析（二）HungarianOper模块代码分析

HungarianOper

https://blog.csdn.net/qq_25945437/article/details/70835157
https://blog.csdn.net/Kerrwy/article/details/81018202

在得到了上一帧的多个Bbox与这一帧的多个Bbox的IOU矩阵，需要找到最大IOU组合的索引对，論文使用匈牙利算法来進行匹配。在class HungarianOper—匈牙利指派模块中，核心功能

static Eigen::Matrix<float, -1, 2> Solve(const DYNAMICM &cost_matrix)

是通過调用class Munkres 这个类來實現的（Ubuntu下輸入法有問題了，有时候是繁體字。。。）。Munkres算法是帶權重的一種指派算法。

Munkres算法流程如下：

前提：要求传进来的矩阵m是方阵，即行和列相等。if 行数！=列数，就resize 。

void solve(Matrix<Data> &m)

this->matrix = m;
if (rows != columns)
    {
      matrix.resize(size, size, matrix.mmax());
    }

而且，如果存在无穷大的值，替换成矩阵的最大值。

replace_infinites(matrix);

以上是准备工作，下面進入munkres指派流程（请结合流程图和我的笔记看,同样没有学会在csdn画矩阵划线,所以就直接贴图了）：


首先，對行進行規約，具體做法爲，在每行中找出最小值，然後每行都減掉這個最小值。
第二，進行列規約，前提是經過行規約後，該列的最小值不等於0，具體做法同行規約。
尋找最小值及規約代碼如下：

for (size_t j = 1; j < inner_size && min > 0; j++)
  {
        min = XYZMIN(min,over_columns ? matrix(j, i) : matrix(i, j));
  }

if (min > 0)
{
 for (size_t j = 0; j < inner_size; j++)
  {
     if (over_columns)
     {
       matrix(j, i) -= min;
     }
    else
     {
        matrix(i, j) -= min;
     }
  }

第三，進行試指派。

首先,画盖零线,通俗的理解为:用最少的横线来覆盖矩阵中所有被標記为0的元素.

在矩阵中,找到没有被盖零线覆盖的值.

inline bool find_uncovered_in_matrix();

if (find_uncovered_in_matrix(0, saverow, savecol))
    {
      mask_matrix(saverow, savecol) = PRIME; // prime it.
    }

判定盖零线的数量covercount是否==矩陣的rows ||==矩陣的cols。如果等於，則指派成功.(这里,可以理解为:判定i行i列是否只有一个0元素,如果是,则说明指派成功.)
否則進行下一步:调整。

主0搜索

if (find_uncovered_in_matrix(0, saverow, savecol))
    {
    // 把它标记为prime
      mask_matrix(saverow, savecol) = PRIME; 
    }

Increment Set of Starred Zeros

1. Construct the ``alternating sequence’’ of primed and starred zeros:
   伪代码:

   Z0 : Unpaired Z' from Step 4.2
       Z1 : The Z* in the column of Z0
       Z[2N] : The Z' in the row of Z[2N-1], if such a zero exists
       Z[2N+1] : The Z* in the column of Z[2N]
       The sequence eventually terminates with an unpaired Z' = Z[2N] for some N.

2. Unstar each starred zero of the sequence.
   if (mask_matrix(i->first, i->second) == STAR) mask_matrix(i->first, i->second) = NORMAL;

3.Star each primed zero of the sequence

if (mask_matrix(i->first, i->second) == PRIME)
        mask_matrix(i->first, i->second) = STAR;

4. Erase all primes, uncover all columns and rows,

for (size_t row = 0; row < mask_matrix.rows(); row++)
    {
      for (size_t col = 0; col < mask_matrix.columns(); col++)
      {
        if (mask_matrix(row, col) == PRIME)
        {
          mask_matrix(row, col) = NORMAL;
        }
      }
    }

最后返回结果,类型为matrix矩阵.