Object Tracking Overview

Object tracking is the process of:

1. Taking an initial set of object detections (such as an input set of bounding box coordinates)
2. Creating a unique ID for each of the initial detections
3. And then tracking each of the objects as they move around frames in a video, maintaining the assignment of unique IDs

As Object tracking keeps track of the object in the frame and can identify the same object reappearing in the frame Vs new objects, it’s ideal to implement use cases like Unique people counter, Queue Management, Unattended baggage detection.

An object tracking algorithm should do the below:

• Object detection and calculation of the bounding boxes of the object (i.e., when the object is initially detected)
• Be able to handle when the tracked object “disappears” or moves outside the boundaries of the video frame
• Be robust to occlusion
• Be able to pick up objects it has “lost” in-between frames

Centroid Tracking Algorithm

Centroid tracking relies on the Euclidean distance between

(1) existing object’s centroids (i.e., objects the centroid tracker has already seen before)

(2) new object centroids between subsequent frames in a video.

The below flow chart explains the steps of the Centroid tracking algorithm.

Capture a Frame

This step captures a frame for inference from video input framework like V4L2 or UVC.

Use Object detector

For the centroid algorithm to Work, we need an object detector to detect objects in each Frame. In this case, Object detector is YoloV3

The object detector will detect objects as usual and calculate the bounding boxes of each object.

Find the Centroid

The centroid of a bounding box is as below

Compute the Euclidean distances

We then compute the Euclidean distances between each pair of original/existing centroids in our database with the new detected Centroids.

Euclidean Distance between 2 points in 2D space can be represented by the below formula

Where p1,p2, and q1,q2 are coordinates of 2 centroids.

Check and associate the centroids as per the distance.

The primary assumption of the centroid tracking algorithm is that a given object may move in between subsequent frames, but the distance between the centroids for frames t and t+1 will be smaller than all other distances between objects.

For example, say we have 2 Objects already detected in the previous frame (ID=0 and ID=1)as below

In the next frame, we detect 3 objects represented by red color (A,B,C) and old objects by yellow color (ID=0 and ID=1).

To associate ID=0, we check distances d1 , d5 , d4 .

And as d1 is minimal and below the threshold, we can associate ID=0 to A .

Similarly to associate ID=1, we check the distances d2 , d3, d6, and as d2 is the least distance between existing ID=1 and B.So we can associate B as ID=1 in this new frame.

Now as we cant relate C to any existing Object, so we have to register C as a new object ID=3 and insert it into our database.

Deregister disappeared Objects.

we will deregister old objects when they cannot be matched to any existing objects for a total of N subsequent frames.

Ie in the above picture for ID=0 if d1, d5, d4 are all above the threshold for N subsequent frames, then we will deregister ID=0.

But this can be customized based on the use case.

Results

Using the same centroid tracking Algorithm and running the algorithm along with Caffe Yolo on some video files we get below output

Please see the video

https://youtube.com/shorts/pkuj9VKbzX8

LIMITATIONS AND DRAWBACKS

There are two primary drawbacks of the Centroid tracking algorithm.

1. it requires that the object detection step be run on every frame of the input video.
2. The centroids must lie close together between subsequent frames. For Eg If two or more objects overlap each other to the point where their centroids intersect and instead have the minimum distance to the other respective object, the algorithm may (unknowingly) swap the object ID as we relying strictly on the Euclidean distances between centroids and no additional information.

LICENSE :

The algorithm does not have a license associated with it. Reference source in C++ has a BSD 3 Clause license.