Hungarian Algorithm

An Assignment Problem-solving technique used for Object Tracking

How does a self-driving car keep track of the different obstacles on its way to avoid any collision? How does multi-object tracking keep track of the various objects?

Learn a step-by-step explanation of using the Hungarian Algorithm for object tracking.

Prerequisite to this article

An Introduction to Object Tracking

An Easy Explanation of Kalman Filter

The Hungarian matching algorithm is also called the Kuhn-Munkres algorithm or Bipartite Graph Matching.

In simplistic terms, you have an n by n matrix with the detections and tracks. You want to associate the detections to the right tracks with the maximum IOU(Intersection-over-Union) area or minimum Euclidean distance. This association problem can be optimally solved using the Hungarian algorithm.

The Hungarian algorithm allows you to select n elements from an n by n matrix so that there is exactly one element in each row and one in each column, and the sum of the related costs is either minimized or maximized.

How do you solve the cost optimization problem when the size of the matrix is large?

Hungarian algorithm solves the…