Tracking multiple moving objects with KalmanFilter in OpenCV/C++ - How to assign tracks individually to detected objects

Question

I am working on realtime movement detection and object tracking in OpenCV/C++ and am currently stuck at the tracking part.

Matlab-Example of what I want to do: http://www.mathworks.de/de/help/vision/examples/motion-based-multiple-object-tracking.html (I'm troubled with the tracking part and how to transfer it to C++/OpenCV)

My motion part works with OpenCVs BackgroundSubtractor MOG2 which makes it possible to find contours and filter smaller contours out.

For tracking I am currently trying to use the KalmanFilter (with a similar implementation to this) which right now is getting called in every frame if a moving object was found and draws a line on it's path. My Detection & Tracking part looks something like this:

BackgroundSubtractorMOG2 bg;
bg.operator()(frame, threshold);
bg.getBackgroundImage(background);
...  //morphological operations to remove noise etc.
findContours(threshold, ...);
...  //filtering to reject contours which are too smalle/too big

for(int i = 0; i < contours.size(); i++){
approxPolyDP(...);
boundRect = boundingRect(...);
x = boundRect.x + boundRect.width/2;
y = boundRect.y + boundRect.height/2;}

kalmanFilter.track(x,y);
kalmanFilter.draw(frame);

Current Problem: I have a scene with 0 moving objects, then 1 object moves in, gets detected through contours and gets tracked. Then a 2nd object moves in sight, gets detected and makes the tracker jump to it instead of following the first or marking both individually (which I want).

The current tracker takes x & y coordinates of the found object. Like this, once another object gets detected, the tracker still assumes it is the same object but with other coordinates than anticipated.

As one can see, there's no function to assign "tracks" to a certain object which is probably the biggest problem. I read about the hungarian algorithm but am not quite sure on how to implement it within my functions.

What would be a good method to make the tracking work for multiple objects?

My idea was that if I had each object uniquely identified I could check if the ID is still the same and if not let the tracker know that it's a new object to track separately from the other. Not sure if this is necessary or even useful though and if so, how to do it.

Solution 1

try something like this:

for each contour:
    if its already tracked with ID 'A': kalmanFilter_with_id_A.track(x,y);
    else createNewKalmanFilterWithID A

you need some mechanism to decide whether it is already tracked. In simple tracking you just decide by measuring distances to contours in last frame and if its close enough, it's the old object. This is quite erroneous so you might want to have a look at better tracking methods, e.g. probabilistic tracking.

so simple mode:

for each contour 'currentFrameC':
    for each contour 'lastFrameC'
        if distance(currentFrameC, lastFrameC) is smallest and < threshold
            currentFrameC is the same object as lastFrameC so give it the same ID
    if no shortest contour with dist < thres was found, create a new object with a new ID and create a new KalmanFilter with this same ID for that object

call kalmanFilter with ID for each found contour ID

Solution 2

As Micka suggested you need to have your own algorithm to differentiate the tracked_object from a new_detection. Simplest solution is to compare the distance between centroids.

Other apporaches include,

1. Bounding Box overlap Ratio
2. Hungarian Algorithm

(I have provided links to the code and articles at the end.)

---

BoundingBoxOverlapRatio method:

Steps

• Frame_1: Identify blobs -> Draw boundingRectangles for each blob bbox_frame1_obj1, bbox_frame1_obj2...

• Frame_2: Identify blobs -> Draw boundingRectangles bbox_frame2_obj1

  -> compare overlap of bbox_frame2_obj1 with bbox_frame1_obj1,bbox_frame1_obj2 etc..

The amount of overlap indicates the likelihood of being the same object, based on which object positions can be updated.

But this method is suitable for scenarios which include slow moving objects like pedestrian detection, or else there might not be overlap at all.

---

Hungarian Algorithm

This 5 to 6 step algorithm serves as a simple yet robust solution for this kind of assignment problem.

It works like below.

Create a matrix with Rows as prev_position of objects and Columns as new_detections

If we have 3 objects in memory and the new frame has 4 blobs, it leads to a 3x4 matrix with each element being the distance between objects and detections.

Element(1,1) -> distance between centroid of obj_1 and detected detection_1

Element(1,2) -> distance between centroid of obj_1 and detected detection_2...

Example matrix(units in pixels):

5    15   30   20

20   30   3    40

12   4    15   50

The situation here is simple and straight forward leading to the conclusion of

obj_1 -> detection_1   (5px between obj_1 and detection_1)
obj_2 -> detection_3   (3px between obj_2 and detection_3)
obj_3 -> detection_2   (4px between obj_3 and detection_2)

So detection_4 must be a new object and a new track and id has to assigned.

Thereafter obj_4 has to be tracked along with and next matrix has 4 rows…

But with more number of objects the task gets more comples. And the Hungarian Algorithm helps is solving more complex and huge matrices for the optimal assignment of detections to objects.

---

Below are some useful resources for multi-object tracking and hungarian algorithm.

1. Matlab documentation

   • Pedestrian detector - Provides a neat step-by-step approach to handle multi-object tracking.

2. C++ implementation of MATLABs Multi-Object tracker (Includes Hungarian Algorithm)

   • Youtube

   • Github

3. BoundingBoxOverlapRatio method:

   • Matlab documentation.C++ implementation should be straight forward.

4. Hungarian algorithm:

   • Explanation and code
   • Simple explanation and steps to solve

Comments

[Appuru]

Yeah, my thinking was pretty much the same so far I suppose, I just wasn't sure on how to go with the ID-part. Guess I'll have to write another class specifying the tracking targets to get IDs assigned to it. And yes, the tracking might have to get refined afterwards but for now it's all I need. I'll accept your answer as it's probably still the closest to what I want. Thanks for the help.