The Hungarian Algorithm and Its Applications in Computer Vision

Contents

Multi-object tracking (MOT) is a task in which an algorithm must detect and track multiple objects in a video. Most known algorithms are based on using simple detectors (e.g. YOLO) designed for processing individual images. The overall method involves separately using a detector on consecutive video frames and then matching the corresponding bounding boxes across different frames that belong to the same objects. The core part that makes MOT algorithms different is how they perform matching between video frames. They can take into account several factors to perform matching: bounding box positions; occlusions (when bounding boxes of several objects intersect with each other); object’s motion; physical object similarity; In some cases, for every pair of bounding boxes on consecutive frames A and B, these characteristics are combined into a single number that describes the likelihood that a pair of bounding boxes detected in frames A and B belongs to the same object. Example of multi-object tracking (MOT): the algorithm tracks of two balls. These values are calculated for all pairs of bounding boxes in frames A and B. Then, the MOT algorithm attempts to identify the best possible matching between all bounding boxes. More concretely, given n detected bounding boxes in both frames A and B, the goal is to create a mapping between every bounding box from A to B in a way that every bounding box is used only once. Hungarian algorithm Formulation Idea Example 1. Row & column reduction 2. Adjustment step 3. Solution retrieval Applications Conclusion Resources

Hungarian algorithm

The Hungarian algorithm is usually studied in algorithms and data structure courses. Nevertheless, it also has applications in matching systems, and, in particular, is frequently used to solve the tracklet matching problem mentioned above.

We are going to study the workflow of the Hungarian algorithm in simpler settings. Once we have understood how it is used, we will be able to apply it to MOT problems as well easily.

The algorithm is called Hungarian because it is “was largely based on the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry” — Hungarian Algorithm | Wikipedia

Formulation

There exist many examples to demonstrate the Hungarian algorithm. I like the one with workers and tasks. Here is the formulation:

There are n workers available, and n tasks need to be completed by them. There is information about the salary every worker receives for every task. As for the company director, the problem consists of optimally assigning tasks to workers given the following conditions:

every worker gets assigned only one task;
all tasks get completed;
the money spent on salaries should be minimized.

We are going to solve this problem by using the following 4 x 4 cost matrix as an example:

Cost matrix containing information about the cost of every task done by every worker. The goal is to assign every task to each worker, so that all tasks are completed with the minimal overall cost.

Geometrically, given the matrix above, the objective consists of choosing n matrix elements in a manner that there are no repeating elements in any row or column, and the total sum of chosen elements is minimal.

Idea

The Hungarian method involves transforming the initial cost matrix into a new form that facilitates the solution search. For this, we will use several matrix transformations. Even though the matrix will be modified, the problem will always remain equivalent, meaning that the solution will still be the same.

To keep things simple, we are not going to prove here mathematically why this or that matrix transformation maintains the problem invariant. Instead, we will provide some logical thoughts to explain why the solution remains the same.

Example

1. Row & column reduction

The first step consists of identifying a minimum element in every row of the matrix and subtracting it from each row. The idea here is to get at least one zero in every row. In practice, having more zeros simplifies the problem.

Suppose that some number m is subtracted from a given row. While the objective value (the total minimized salary) changes during the transformation (it decreases by m), the relative cost between the assignments for the same worker remains unchanged. Therefore, the ranking of solutions remained unchanged.

The analogous procedure is then performed on columns: a minimum element in every column is subtracted from that column.

First two steps: 1. subtract the minimal element from every row; 2. subtract the minimal element from every column.

After the first two transformations, we obtain a matrix with some zeros representing potential assignments.

The next step consists of drawing the minimal number of horizontal and vertical lines in a way that they pass through all zeros in the matrix. In the image below, we can draw k = 3 lines in total to cover all zeros.

All zeros can be covered using only k = 3 lines.

If the number of drawn lines equals the dimension n of the matrix, then we have found a solution. The only step left in such a case is to choose n zeros such that no zero is on the same horizontal or vertical line as another zero.

Since, in our example, n ≠ k, (the matrix dimension n = 4; the number of drawn lines k = 3), it means we must perform an adjustment step.

2. Adjustment step

So far, we have drawn several lines, and we can classify the matrix elements into three categories:

Uncovered elements;
Covered elements (only once);
Corner elements (elements that are covered twice — horizontally and vertically).

The idea of the adjustment step consists of identifying the minimal element among uncovered elements and subtracting it from all uncovered elements. At the same time, this value gets added to all corner elements.

In our example, the minimal uncovered element is 2. As a result, we subtract 2 from all uncovered elements (in red) and 2 from all corner elements (in green).

Adjustment step involves subtracting the minimal covered element (2) from each covered elements (in red) and adding it (2) to all corner elements (in green).

Although it might not be obvious why the problem invariant remains maintained after the adjustment step, it can be mathematically proven that subtracting a number from all uncovered costs is equally compensated by its addition to all covered costs twice, which maintains the optimal solution the same.

This transformation was a single iteration of the adjustment step, which led us to another equivalent matrix form. As before, we perform the check to find out if we can cover all zeros using only n lines.

This time, all zeros can only be covered with k = n = 4 lines. This means that no further adjustment steps are needed, and the final solution can be retrieved.

As we can see, this time we indeed have to draw k = n = 4 lines to cover all zeros. It means that we can finally retrieve our solution!

Otherwise, if we could have drawn fewer than k < 4 lines, we should have repeated the adjustment step until the number of lines became k = 4.

3. Solution retrieval

The only step left is to find n zeros on different vertical and horizontal lines. If doing it manually, it is better to start with lines that have fewer zeroes.

After finding the positions of zeros in the matrix, we can switch back to the original matrix and choose the initial elements with the same positions as the found zeros. And that will be the final assignment!

During the final step, n = 4 non-repeating zeros on horizontal and vertical lines must be found. Their positions correspond exactly to the position of the cost values of the initial matrix.

The complexity of the Hungarian algorithm is O(n³), where n is the matrix dimension.

The assignment problem we have just seen can also be solved by linear programming methods.

Applications

One of the most obvious applications of the Hungarian algorithm consists of using it for assignment problems, where, given n tasks, the goal is to optimally associate them with other people or objects (e.g., machines) that will complete them.

There is also a particular application in computer vision. Many video tracking algorithms (MOT) are based on the combination of standard image detection algorithms (e.g., YOLO) and logic of merging detection results from several independent frames into a video flow.

Let us take a simplified example of two consecutive image frames of a video:

Example of two consecutive video frames.

We run a MOT algorithm for object tracking based on YOLO. The predictions of YOLO are shown below in gray boxes.

The YOLO algorithm detects two balls on a tree in every frame. The objective is to understand how detections on both frames are related to each other.

The objective is to associate bounding boxes between both frames to keep track of objects. One possible way to do this involves analyzing the change in distance between bounding boxes between the two frames. It is logical to assume that a pair of bounding boxes belongs to the same object if their position do not change a lot between the two frames.

Here is where the Hungarian algorithm comes into play. We can construct a matrix representing pairwise distances (which will be the cost functions) between the coordinates of different bounding boxes in both frames. We can find such a mapping that minimizes the total distance between bounding boxes.

The result of the Hungarian algorithm applied to the matrix containing distances between the centers of bounding boxes.

By running the Hungarian algorithm, we get the following mappings:
(A₁, C₂), (B₁, A₂), (C₁, B₂).

We can verify that they result in a total cost of 8 + 1 + 5 = 14 which is the minimal possible function cost for this matrix. Hence, the found mappings are optimal.

Certainly, modern MOT algorithms consider additional factors when matching bounding boxes, including trajectory analysis, object speed and direction, and physical similarity, among others. For simplicity, we only considered a single factor: the distance between the bounding boxes. However, in reality, more factors are taken into account.

Conclusion

In this article, we have looked at the Hungarian algorithm used to solve task assignment problems. By performing simple operations on the initial data matrix, the Hungarian algorithm transforms it to other formats while maintaining the problem invariant.

Despite its cubic complexity, the Hungarian algorithm has a wide range of applications in matching and computer vision problems where the number of objects is not too large.

Resources

All images unless otherwise noted are by the author.