Hungarian Matching Algorithm

What is the Hungarian Matching Algorithm?

The Hungarian Matching Algorithm is a bipartite matching algorithm that solves the assignment problem in polynomial time. The assignment problem assumes there are $n$ tasks that must be assigned to $n$ agents, with no duplicate assignments, in such a way that the total cost of the assignments is minimized.

 

Problem Definition

Given an $n \times n$ cost matrix $C$, where $C[i][j]$ represents the cost of assigning task $j$ to worker $i$, the Hungarian Matching algorithm follows these steps:

1. Find row minimums and subtract: Identify the smallest value in each row and subtract it from all elements in that row.
2. Find column minimums and subtract: After step 1, repeat the process for each column by subtracting the smallest value from all elements in the column.
3. Cover all zeros with the minimum number of lines: Cover all zeros in the matrix using the fewest possible horizontal or vertical lines. If the number of lines equals the number of rows, a perfect matching exists. If fewer than $n$ lines are used, further adjustments are necessary.
4. Adjust the matrix: Identify the smallest uncovered value and subtract it from all uncovered elements. Simultaneously, add this value to all elements covered by both a row and a column.
5. Repeat the covering step: Repeat steps 3 and 4 iteratively until the number of lines equals $n$.
6. Make the assignment: Select a set of independent zeros in the matrix such that no two zeros are in the same row or column.

 

Proof of the Validity of the Hungarian Matching Algorithm

The validity of the Hungarian Matching Algorithm can be proven using complementary slackness conditions from linear programming.

 

The primal problem for this assignment is to assign $n$ workers to $n$ tasks. This can be formulated as:

$$ \min \sum_{i,j} C[i][j] \cdot x[i][j] $$

where $C[i][j]$ is the cost of assigning task $j$ to worker $i$, and $x[i][j]$ is an indicator function.

 

The constraints are defined as:
$$
\begin{align}
&1. \sum_j x[i][j] = 1 \text{ for all } i, \
&2. \sum_i x[i][j] = 1 \text{ for all } j, \
&3. x[i][j] \in {0,1} \text{ for all } i,j.
\end{align}
$$

 

The dual problem is to find a set of prices for each worker and task such that the total price is maximized, while ensuring that no assignment costs more than the sum of the prices for the corresponding worker and task. Let $u[i]$ be the price for worker $i$ and $v[j]$ be the price for task $j$.

 

The dual problem can be written as:

$$ \max \sum_i u[i] + \sum_j v[j] $$

subject to the constraint:

$$ u[i] + v[j] \leq C[i][j] \text{ for all } i, j $$

 

In the Hungarian matching algorithm, a feasible labeling is chosen such that:

$$ u[i] + v[j] \leq C[i][j] \text{ for all } i, j $$

For this assignment problem, the complementary slackness conditions are:

1. If $x[i][j] = 1$, then $u[i] + v[j] = C[i][j]$.
2. If $u[i] + v[j] < C[i][j]$, then $x[i][j] = 0$.

 

By ensuring feasible labeling, these complementary slackness conditions are satisfied, which means the Hungarian algorithm always returns the optimal solution.

 

 

Time Complexity of the Hungarian Matching Algorithm

The time complexity of the Hungarian matching algorithm is $O(n^3)$. This can be broken down into the following steps:

1. Row and column reductions: Each row and column reduction takes $O(n)$ time, so the total time for this step is $O(n^2)$.
2. Covering zeros with the minimum number of lines: Finding the minimum number of lines using bipartite matching algorithms takes $O(n^3)$ time.
3. Adjusting the matrix: Finding the minimum value in the matrix takes $O(n^2)$ time. Since this process is repeated until a perfect matching is found, it can be repeated up to $n$ times, leading to a total time complexity of $O(n^3)$.

 

Utilizing the Hungarian Matching Algorithm in DETR-based Object Detectors

In DETR, the model outputs a fixed set of $N$ predictions, including bounding boxes and class labels. However, the number of objects in an image may be less than or equal to $N$. To handle this, DETR-based detectors add a 'no object' class and treat the task as a bipartite matching problem.

 

The cost matrix is computed by combining the classification loss and bounding box regression loss. The Hungarian matching algorithm is then applied to the cost matrix to find the optimal matching between predictions and ground truth.

 

After matching is determined, the losses for the matched pairs and unmatched predictions are backpropagated to train the network.

 

By utilizing the Hungarian Matching Algorithm, DETR can be optimized in an end-to-end manner without the need for non-maximum suppression (NMS).