Day 95(DL) — Hungarian Algorithm for object tracking

Photo by Yanny Mishchuk on Unsplash

The next block in the object tracking is the Hungarian Algorithm. It was developed by Harold Kuhn in 1955 and named after two Hungarian mathematicians whose work had a significant impact on the algorithm. The algorithm was later reviewed in 1957 by James Munkres, that why it is also called the ‘Kuhn-Munkres’ algorithm.

As we already know, the main objective of tracking is to trace the intended object(indicated by bounding boxes from detection) through time. The purpose of the algorithm is to identify unique objects by giving distinct ids and maintaining the same ids across the timeframes. For instance, we are monitoring bird migration(say 100 birds), when they fly a unique id assigned to each bird is maintained throughout the surveillance. The ‘id’ is the key to the entire process.

So how do the ids remain unaltered? With the assistance of comparison of objects between the frames. Since the objects are placed inside a bounding box, we could extract the features(via CNN) within the box and compare them against the previous frame. If there exists a strong interrelation of the object present in the current & the previous one, the same id gets allocated in the subsequent frame as well.

The comparison could be done in very many ways apart from the feature extraction, this includes shape score & IOU score. When incorporating IOU, the maximum overlapping values are considered, while making the rest of the values zero. In the case of occlusion, only visible portion features are extracted by the CNN for cross-validation.

Comparison and Assignment: During the comparison process, we have two lists at hand (1) The current detection output (2) Previous tracking information. Now we try to measure the match between these two lists and form a cross tab that gives the interlink. Either we can use the brute force approach for the comparison of the bb boxes across detection and tracking or the smartest hungarian algorithm.

Since the Hungarian algorithm outputs the minimum values, we need to multiply the IOU with -1 so that the largest IOU becomes the smallest, which will be chosen by the algorithm.

Unmatched Detection: Following the above bird example, there appears a newbie out of nowhere that is not a part of the flock. Since we do not have past information and for the very first time it gets detected, such introductions are referred to as Unmatched Detection. The other term is matched detection where the track is in place.

Unmatched Tracking: One of the birds in the herd wants to relax for a while, so it silently separates it out from the group and rests under the branch of an old tree. The tracking is already lost for this particular one and scenarios of these kinds are termed unmatched tracking.

Recommended Reading:

AI Enthusiast | Blogger✍

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store