Hungarian algorithm for tracking a lot of moving objects
I want to talk about the well-known, but not much covered in the literature approach to tracking a lot of moving objects. The complexity of this task lies in the fact that the algorithms for detecting and highlighting objects often fail, and the objects themselves can be blocked by other objects and background elements. In the general case, the solution to the tracking problem contains three main stages:
- selection of segments;
- establishment of correspondence between the selected segments and tracked objects;
- clarification or prediction of the position of objects of interest.
In this case, a segment is called a connected region of the image, distinguished by the sign of movement. As part of this note, we will be interested in the 2nd and 3rd of the listed stages.
General statement of the problem
We assume that in the current frame one or more segments are selected based on the motion. To do this, you can use background subtraction, optical flux, methods based on a mixture of Gaussian distributions, etc. As a result, instead of the initial grayscale image, we get a binary image, as shown in the figure below.
Due to the presence of noise and various atmospheric distortions, the results of the extraction contain errors that can be easily eliminated using methods of mathematical morphology. First, a morphological discovery should be applied, which will remove small segments and point noise. You can then apply morphological closure to restore the shape of the objects. As a result, we get a cleared image (see the figure), which is subsequently subjected to markup and parameterization. The list of found segments and their parameters are the initial data for the tracking algorithm.
So, as a result of the operation of the object extraction algorithm, a list of segments found on a given frame can be obtained, however, in order to solve the problem of tracking objects, it is necessary to match each of these segments with the object known in the previous frame or make a decision about discovering a new object. Sometimes erroneously detected segments are sufficiently stable in time and exist at close points in space for several frames. On the other hand, sometimes correctly detected segments disappear briefly. Therefore, there must be a mechanism that, firstly, decides to detect a new object, secondly, filters out false segments that are unstable in time, thirdly, establishes the correspondence between previously known objects and new segments, fourthly,
To give the tracking algorithm stability to temporary closure of the object by background sections, a personal trajectory filter is introduced for each object, the main task of which is to predict the coordinates of the object in the next frame based on the analysis of the object's trajectory. Typically, a Kalman filter is used as such a filter.
When the object is temporarily closed by background sections or other objects, the trajectory parameters are not refined, and the trajectory filter operates in the coordinate prediction mode.
If there are many tracking objects in the sequence of images, there is a chance of entanglement of objects in situations of intersection of their motion paths. After crossing the trajectories, objects should receive the same identifiers as they had before the intersection. An example of the correct assignment of identifiers is shown in the figure.
Tracking objects based on the Hungarian algorithm
As the first step of the tracking algorithm, it is necessary to establish a correspondence between the segments found in the current frame and the tracked objects. To this end , a quantitative measure of similarity is calculated between each i- th object and each j- th segment. As such a measure, one can use the Euclidean distance between the predicted coordinates of the object
and the center of the segment 
, i.e.
It should be noted that new objects may appear on the image, and objects tracked for some time may leave the frame or be temporarily obscured by obstacles. We will consider three types of situations:
a) a correspondence is found between the object and the segment;
b) for this object no match was found among the segments;
c) for this segment, no match was found among the objects.
Euclidean distance can be considered as the cost of making a decision (a) on the correspondence between the ith object and the jth segment. We introduce the value of E t specifying the cost of the solution (b), and the value of E s specifying the cost of the solution (c).
As a result, we come to the solution of the following problem: it is necessary to establish a correspondence between segments and objects or make a decision on the impossibility of such a comparison in such a way that the total cost of all decisions is minimal. This task is known as the assignment problem; the Hungarian algorithm is used to solve it .
To apply the Hungarian algorithm, it is necessary to compose a square matrix of cost of size N M = N t + N s , where N t is the number of tracked objects, and N s is the number of segments found. The cost matrix has the following form:
where D max is a sufficiently large number such that D max >> E ij . Tracked objects are counted along the rows of the matrix, and segments found on the columns.
As a result of the Hungarian algorithm obtain a list of pairs of (t, s) k , k, t, s = 1..N M .
If t <= N t and s <= N s , between t -th object and the s -th segment set line [the situation (a)].
If t <= N t and s> N s, then the corresponding segment was not found for the t-th object [situation (b)].
If t> N t and s <= N s , then no suitable object was found for the s-th segment [situation (c)].
Each of these situations leads to the need to perform various actions. In the first case, you should update the list of object parameters based on the parameters of the corresponding segment. In the second case, updating is not possible, however, the absence of an appropriate segment can be explained by temporary obstruction of the object. Therefore, in this case, we should proceed to forecasting the parameters of the object based on previous observations. To refine and predict the coordinates of objects, the Kalman filter is used. Finally, in the third case, the segment corresponds to the newly appeared object.
During observation, objects can leave the frame. In this case, stop monitoring them. The criterion for determining such situations is the inability for a sufficiently long time to establish a correspondence between this object and any of the segments selected in the current frame.
Of course, the scheme described above is quite simple. In more complex scenarios, object obscurations should be handled by merging and splitting tracks. However, this is a completely different story ...
