CN107169989B

CN107169989B - Multi-target tracking method based on data association and track evaluation

Info

Publication number: CN107169989B
Application number: CN201710249226.9A
Authority: CN
Inventors: 许正; 朱松豪; 孙成建; 荆晓远; 岳东
Original assignee: Nanjing University of Posts and Telecommunications
Current assignee: Nanjing University of Posts and Telecommunications
Priority date: 2017-04-17
Filing date: 2017-04-17
Publication date: 2020-04-24
Anticipated expiration: 2037-04-17
Also published as: CN107169989A

Abstract

The invention discloses a multi-target tracking method based on data association and track evaluationd∈DThe observation is carried out with straight line fitting to obtain an initial track set of the targetTSimultaneously using the space-time relationship for eachd∈DEstablishing a conditional random field model by observing, and giving a labeling mode; secondly, a fitting model, a prior model and a mutual exclusion model are established, on the basis of the CRF model, the fitting model, the prior model and the mutual exclusion model are utilized to construct an objective function, and a gradient descent method are utilizedα‑expansionSolving the approximate minimum energy of the objective function by an algorithm; finally, the initial trajectory set is aligned based on the minimum energyTAnd carrying out segmentation and combination, addition and deletion, growth and contraction to obtain the optimal tracking track of the target. The multi-target tracking algorithm based on data association and track evaluation can obtain stable and continuous tracking tracks under the conditions of crowded scenes, frequent target identity switching and long-time target shielding.

Description

Multi-target tracking method based on data association and track evaluation

Technical Field

The invention relates to a multi-target tracking algorithm, in particular to a multi-target tracking method based on data association and track evaluation, and belongs to the technical field of image processing.

Background

The multi-target tracking technology is a very hot topic in the field of computer vision. In recent years, detection-based tracking methods are largely classified into two categories:

(1) recursive state estimation methods, i.e. the future state of a moving object depends only on past and current observed states.

(2) Non-recursive tracking methods, i.e. predicting the trajectory of all objects from the information in a series of image frames. However, most work is currently focused on data correlation, i.e., associating each observation with a particular original target.

Therefore, most current methods are primarily aimed at finding an approximate, or locally optimal, solution to the problem. Kalman filtering is widely used due to its simplicity, but it is only applicable to linear models as well as gaussian noise distribution models. The monte carlo method can overcome the limitation of kalman filtering, and is more and more used for estimating the target position, but the number of particles is explosively increased along with the increase of the number of targets, so that the multi-modal maintenance becomes more and more difficult. Such a recursive state estimation method has a major drawback that it is difficult to repair once false detection occurs. Non-recursive tracking methods focus primarily on data correlation, i.e., associating each observation with a particular original target. The tracking method based on the network flow uses the minimum cost flow to find a relatively simple objective function in the minimum polynomial and determine the global optimal solution of the minimum polynomial. When the target is blocked for a long time, the determination of the target identity is not facilitated.

Disclosure of Invention

The invention aims to solve the technical problem of providing a multi-target tracking method based on data association and track evaluation aiming at the defects involved in the background technology of the multi-target tracking problem.

A multi-target tracking method based on data association and track evaluation comprises the following steps:

step A), performing linear fitting on each observation belonging to the same class as the observation of the corresponding class D by using a RANSAC algorithm to obtain an initial trajectory set T of a target, establishing a CRF (model reference number) model for each observation belonging to the same class as the observation of the corresponding class D by using a space-time relationship, and giving a label mode, wherein D is an observation set;

step B), establishing a fitting model, a prior model and a mutual exclusion model, constructing an objective function by using the fitting model, the prior model and the mutual exclusion model on the basis of the CRF model, and solving the approximate minimum energy of the objective function by using a gradient descent method and an α -expansion algorithm;

and step C), based on the minimum energy, carrying out segmentation and combination, addition and deletion, growth and contraction on the initial track set T to obtain the optimal tracking track of the target.

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the specific steps of performing straight line fitting on each observation of the D e D by using the RANSAC algorithm in the step A) are as follows:

step A.1.1), randomly selecting an observation subset D_kTargets i and j in the epsilon D;

step A.1.2), if the inter-frame interval between the targets i and j is equal to or less than 4 frames and the inter-frame distance is less than 30cm, connecting the targets into a straight line, otherwise, not connecting the targets;

as a further optimization scheme of the multi-target tracking method based on data association and trajectory evaluation, the specific steps of establishing a CRF model and a labeling mode of data association by utilizing a space-time relationship in the step A) are as follows:

step A.2.1), each observation D e D is regarded as a vertex V;

step A.2.2), mutually exclusive sides epsilon of different observation spaces in the same frame of image_XAre connected with each other;

step A.2.3), smoothing the observation time epsilon with the distance between two adjacent frames of images smaller than a preset threshold value tau_SAre connected with each other;

step a.2.4), for any observation with D e D, giving the label set L of the initial trajectories of all targets {1, 2.

Step A.2.5), the effective track Tl is given^*For any valid label/_d∈L，

Step A.2.6), if a certain observation target d belongs to the foreground, then l_dE.g.., 1,2,. N }; if false alarm is given, l_d＝φ。

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the steps of establishing a fitting model, a prior model and a mutual exclusion model in the step B) are as follows:

step B.1.1), calculating the target i and the track T thereof_iIf the Euclidean distance between the target i and the track T is smaller than a preset threshold value tau, the target i and the track T are connected_iConnecting the target i with other tracks if the target i is not connected with the other tracks;

step B.1.2), setting the linear velocity of the target i to be less than 1.2m/s, the angular velocity to be less than 10rad/s and the track durability to be F_i＝e_i-s_i+1, the linear velocity, the angular velocity and the track persistence form a prior model;

and B.1.3), overlapping the tracks of the target i and the target j to form a mutual exclusion model.

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the objective function in the step B) is as follows:

β, gamma and delta are preset weight threshold values;

E_d(l_dt) represents the energy of the trajectory fitting model,

representing spatial mutually exclusive edges epsilon_XThe energy of (a); e_S(l_d,l_d') represents the time smoothing edge ε_SThe energy of (a); e_tr(T_i) The energy of the prior model of the trajectory is represented,

representing the energy of the trajectory mutual exclusion model.

As a further optimization scheme of the multi-target tracking method based on data association and trajectory evaluation, the specific steps of solving the objective function by using the α -expansion algorithm and the gradient descent method in the step B) are as follows:

step B.2.1), inputting an initial track set T and an observation set D;

step B.2.2), outputting the observed set D with the label set l and the effective track T_l ^*，

Step B.2.3), if the iterative solution times of the objective function are less than 10 times, executing the step B.2.4); otherwise, stopping iteration to obtain the final label set l and the effective track T_l ^*；

Step B.2.4), optimizing a label set l by adopting an α -expansion algorithm, and sequentially and completely removing a label to check whether the energy is further reduced or not until the energy of the target function is increased;

step B.2.5), refitting the track set T by adopting a gradient descent method;

step B.2.6), the trajectory space T is redetermined, and the step B.2.3) is switched to.

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the specific steps of segmenting and merging the initial track set T based on the minimum energy in the step C) are as follows:

step C.1.1), segmenting track segments which continuously exceed 10 frames and have no targets into 2 or 3 track segments, if the energy of the target function is reduced, stripping the false detection target from the track set T, otherwise, maintaining the track segments before segmentation;

step C.1.2), merging 2 or 3 track segments with the inter-frame interval not more than 10 frames into a new track, if the energy of the target function is reduced, adding the target after shielding into a merged track set T, otherwise, maintaining the track segments before merging.

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the specific steps of adding and deleting the initial track set T based on the minimum energy in the step C) are as follows:

step C.2.1), adding a new track segment to the track set T, if the energy of the target function is reduced, adding a newly appeared target to the track set T, otherwise, maintaining the track segment which is not added;

and C.2.2), deleting one or two frames of track segments from the initial track set T, if the energy of the target function is reduced, keeping the track set T after deletion, otherwise, keeping the track segments before deletion.

As a further optimization scheme of the multi-target tracking method based on data association and track evaluation, the specific steps of growing and shrinking the initial track set T based on the minimum energy in the step C) are as follows:

step C.3.1), passing t₀Start frame s of a track segment of a frame_iForward moving, end frame e_iMoving backwards, if the energy of the target function is reduced, keeping the track set T after growth, otherwise, maintaining the track segment before growth;

step C.3.2), passing t₀Start frame s of a track segment of a frame_iBackward moving, end frame e_iMoving forward, if the energy of the objective function is reduced, keeping the track set T after contraction, otherwise, maintaining the track segment before contraction.

Compared with the prior art, the invention adopting the technical scheme has the following technical effects:

1. the CRF model is established from the angles of time and space respectively to realize multi-target tracking, which provides a premise and a basis for realizing a multi-target tracking technology;

2. the data association and the track evaluation are fused to establish an objective function, the objective function is solved by utilizing an α -expansion algorithm and a gradient descent method, approximate minimum energy and an initial motion state of each target are obtained, and compared with a pure continuous minimum energy method, the method can effectively process the false alarm and the missing alarm of the targets and the identity switching of the targets;

3. the tracked target track obtained by adopting the method of expanding the track assumed space is more continuous and smooth, and the fragment track formed by the target in the long-time shielding process is restrained. The final tracking result also shows that the method provided by the invention has better tracking effect.

Drawings

FIG. 1 is a schematic of the tracking flow of the present invention;

FIG. 2 is a CRF model employed in the present invention;

FIG. 3 is a schematic diagram of a model of the present invention when different objects are occluded;

FIG. 4 is a schematic diagram of the α -expansion algorithm employed by the present invention;

FIG. 5 is a schematic diagram of the expansion process of the trajectory hypothesis space of the present invention;

FIG. 6 is a diagram illustrating the effect of the weight occupied by each portion of energy on tracking performance in the present invention;

fig. 7 is a partial trace result obtained by the present invention.

Detailed Description

The technical scheme of the invention is further explained in detail by combining the attached drawings:

as shown in FIG. 1, the invention aims to provide a multi-target tracking algorithm based on data association and track evaluation, which is implemented by the steps of firstly, utilizing a RANSAC algorithm to perform linear fitting on each observation of the D e D to obtain an initial track set T of a target, simultaneously utilizing a space-time relationship to establish a CRF model for each observation of the D e D and giving a label mode, secondly, establishing a fitting model, a prior model and a mutual exclusion model, constructing a target function on the basis of the CRF model by utilizing the fitting model, the prior model and the mutual exclusion model, solving the approximate minimum energy of the target function by utilizing a gradient descent method and an α -expansion algorithm, and finally, segmenting and combining, adding and deleting, increasing and contracting the initial track set T based on the minimum energy to obtain the optimal tracking track of the target.

And A, performing straight line fitting on each observation belonging to the same class as the observation of the D by utilizing a RANSAC algorithm to obtain an initial trajectory set T of a target, establishing a CRF model for each observation belonging to the same class as the observation of the D by utilizing a space-time relationship, and giving a label mode.

The straight line fitting process of the RANSAC algorithm to each observation of D ∈ D is as follows:

(1) randomly selecting a subset of observations D_kTargets i and j in the epsilon D;

(2) if the inter-frame interval between the targets i and j is equal to or less than 4 frames and the inter-frame distance is less than 30cm, connecting the targets into a straight line, otherwise, not connecting the targets;

the CRF model is constructed by the following steps:

(1) each observation D e D is regarded as a vertex V;

(2) the mutually exclusive sides epsilon of different observation spaces in the same frame image_XAre connected with each other;

(3) the time smoothing edge epsilon for observing that the distance between two adjacent frames of images is less than a specific threshold value tau_SAre connected with each other;

through the above steps, a complete CRF model is obtained, as shown in fig. 2.

The CRF model labeling method comprises the following specific steps:

(1) for any observation with D e D, the label set L of all assumed trajectories is given {1, 2.

(2) Given a set of labels l for an active track, for any active label l_d∈L，

(3) If a certain observation target belongs to the foreground, l_dE.g.., 1,2,. N }; if false alarm is given, l_d＝φ。

And step B, establishing a fitting model, a prior model and a mutual exclusion model, constructing an objective function by using the fitting model, the prior model and the mutual exclusion model on the basis of the CRF model, and solving the approximate minimum energy of the objective function by using a gradient descent method and an α -expansion algorithm.

The target function definition of the multi-target tracking is specifically as follows:

β, gamma and delta are preset weight threshold values, the tracking effect can be changed by adjusting the weight before the energy function, and for convenience of calculation, the value of β is fixed to be 1. E_d(l_dAnd T) represents the energy of the trajectory fitting,

representing the energy generated when two observation labels in the same frame image are the same; e_S(l_d,l_d') indicates that two adjacent frames belong to the same bar ε_SThe energy of (1) at different times; e_tr(T_i) The energy of the trajectory a-priori is represented,

representing the energy of the mutually exclusive trajectory.

For convenience of representation, v { E } in the formula_d(l_d,T)}＝E_d(l_d,T)，ε{E_S(l_d,l_d’),

1. Fitting model

E_d(l_dT) represents the energy of the trajectory fit that a certain observed object D ∈ D belongs to, and the metric is the shortest distance between the observation and its trajectory. In addition, the term can also indicate whether the observation target belongs to false alarm. The trajectory fitting cost in defining the t-th frame image is as follows:

wherein w_g ^tRepresenting confidence values of observed objects, p_g ^tRepresents the position of the observation and Dis () represents the distance function, i.e. the minimum distance of the observation target from its trajectory. When the label of a certain detection result is l ═ phi, it indicates that the background is mistakenly targeted.

In order to optimize equation (3) based on a gradient algorithm, the present invention adopts a differentiable euclidean distance function, and in order to prevent the differential denominator from being zero, a small fine tuning parameter epsilon is added to the distance function to be 0.1, and the function is defined as follows:

2. prior model

The trajectory prior energy function of the target i consists of the following aspects:

E_tr(T_i)＝E_lin(T_i)+E_ang(T_i)+E_per(T_i)+λ_reg(4)

wherein E_lin(T_i) Representing linear velocity energy of target i, E_ang(T_i) Representing the angular velocity energy of the object i, E_per(T_i) Representing the persistent energy, λ, of the target i track_regThe energy of the model is modified for the trajectory in order to prevent overfitting during the iteration. Each of the above formulas may be minute.

The dynamic model used by the invention is established on the basis of the slow change of the angular velocity and the linear velocity of the target. Let x ═ x (t), y ═ y (t) be the coordinates of the reference plane curve, x '(t), y' (t) be the first derivative, x "(t), y" (t) be the second derivative.

The pedestrian is assumed to move at a uniform speed of about 1.2 m/s. If there is a deviation from this speed, a second penalty is imposed. Therefore, the expression of the linear velocity model of the target i is as follows:

the expression of the angular velocity model of target i is as follows:

and e is equal to 0.1, and further obtaining an angular dynamic trajectory model of the target i through the deformation:

the invention corrects the persistence of the track through the following sigmoid function, and the expression is as follows:

wherein

Indicating the distance between the start of the ith track and the nearest tracking area boundary,

indicating the distance between the end point of the ith trace and the nearest tracking area boundary. The parameter u is 1/s and s is 35cm in the test. The measure is beneficial to the track recovery after the target is shielded, and the phenomenon that the tracking track is suddenly interrupted due to shielding is effectively avoided.

3. Mutual exclusion model

The trajectories between different objects should not overlap spatially in all image frames. If the target i and j tracks in the same physical space overlap, a certain penalty is imposed on the track pair, as shown in fig. 3. For each pair of effective tracks T_i，

Then a corresponding binary cost is incurred

When two targets are close, the corresponding penalty cost approaches infinity.

Wherein X (T)_i,T_j) The overlap in time of the traces i and j is indicated, and s-35 cm indicates the width of the detection box.

4. Edge of CRF model

Time smooth edge epsilon_SSupply numberAccording to the associated temporal smoothness. In two adjacent frames of images, if the distance between two observations is less than a certain threshold τ, the time smoothing edge ε is used_SConcatenate, as shown in FIG. 2, the expression is as follows:

where F denotes the number of frames of the video, this measure causes the same object to have the same reference number in two adjacent frames of images. The threshold τ is as large as possible in case sufficient target dynamics can be guaranteed.

In the same frame image, the space mutual exclusion edge epsilon_XIt can be ensured that the label of each observation target in the same frame image is unique, as shown in fig. 2.

Wherein

To observe

Coordinate (x) of_i,y_i) And s represents the width of the rectangular detection frame.

Connecting time neighborhoods (l)_d,l_d’)∈ε_S，l_dAnd l_d' indicates an observation in which two adjacent frames have the same reference numeral. The time smoothing edge epsilon_SThe energy of (c) is defined as follows:

where δ (.) represents the impulse sequence, when l_d≠l_dIn case of 'time', a certain penalty λ is generated_εs。

To prevent data misreading, the spatially exclusive edge (d, d') is ∈ ε_XEnsuring that the label of each target in the same frame image is unique and the space mutual exclusion edge epsilon_XThe energy of (c) is defined as follows:

where δ (.) denotes the impulse sequence. In the same frame image, if the labels between adjacent targets are the same, certain punishment is carried out.

As shown in FIG. 4, the invention adopts α -expansion algorithm and gradient descent method to solve the objective function, and the specific steps are as follows:

(1) inputting an initial track set T and an observed set D;

(2) outputting the observed set D with the set l of marks, the effective track T_l ^*，

(3) If the iterative solving times of the objective function are less than 10 times, turning to (4); otherwise, stopping iteration to obtain the final label set l and the effective track T_l ^*；

(4) The α -expansion algorithm is used to optimize the label set l, and the labels are removed all by all to check if the energy is further reduced until the energy of the objective function rises.

(5) Refitting the track set T by adopting a gradient descent method;

(6) re-determining the track space T, and turning to (3);

and C, segmenting and combining the initial track set T, adding and deleting, growing and shrinking the initial track set T based on the minimum energy to obtain the optimal tracking track of the target.

Relying only on initial trajectory assumptions may limit the optimal solution of energy to some extent. In order to make the optimization process more flexible, on the basis of the current solution, after each successive optimization iteration is finished, a certain expansion is performed on the search space of the trajectory hypothesis, as shown in fig. 5. The invention adopts the following 3 methods to expand the track hypothesis space:

method 1. segmentation and merging: dividing track segments which are continuously more than 10 frames and have no targets into 2 or 3 track segments, if the energy of the target function is reduced, stripping the false detection target from the track set T, otherwise, maintaining the track segments before division; merging 2 or 3 track segments with the inter-frame interval not more than 10 frames into a new track, if the energy of the objective function is reduced, adding the targets appearing after occlusion into a merged track set T, otherwise, maintaining the track segments before merging.

Method 2. add and delete: adding a new track segment to the track set T, if the energy of the target function is reduced, adding a newly appeared target to the track set T, otherwise, maintaining the track segment which is not added; deleting one or two frames of track segments from the initial track set T, if the energy of the target function is reduced, keeping the track set T after deletion, otherwise, keeping the track segments before deletion.

Method 3. will pass t₀Start frame s of a track segment of a frame_iForward moving, end frame e_iMoving backwards, if the energy of the target function is reduced, keeping the track set T after growth, otherwise, maintaining the track segment before growth; will pass t₀Start frame s of a track segment of a frame_iBackward moving, end frame e_iMoving forward, if the energy of the objective function is reduced, keeping the track set T after contraction, otherwise, maintaining the track segment before contraction.

As shown in fig. 6, in order to verify the influence of the changes of the weight thresholds β, γ, δ on the pedestrian tracking performance, the present invention performs fixed debugging on each parameter, the values of β, γ, δ in formula (1) are fixed in turn, another variable is changed, the influence on the MOTA performance is judged, for convenience of debugging, β is fixed to 1, when MOTA is equal to 0, the influence of the changes of the parameters on the MOTA index is small, and the adjustment coefficients β, γ, δ in the energy function are set to {1, 0.03, 0.8} respectively.

FIG. 7 shows the tracking results of a portion of the targets of the present invention on the TUD-Stadtmite and PETS2009 data sets. As can be seen from the tracking result, the tracking result of the TUD-standard (fig. 7 (top)) data set is ideal, and even if the pedestrians generate certain occlusion in the movement process, most of the pedestrians can be tracked and their trajectories can be determined. For the PETS S2L1 (in FIG. 7), although the occlusion between pedestrians causes the superposition of a small part of the track, since there are relatively few pedestrians and the occlusion is not obvious, the method can basically lock most of the target positions, and the accuracy is also ideal. Even in a crowded scene such as the PETS S2L2 (fig. 7 (bottom)), although there are a few identity switches and objects temporarily lost due to mutual occlusion of pedestrians, when the objects reappear, the objects can still be locked quickly.

It will be understood by those skilled in the art that, unless otherwise defined, all terms (including technical and scientific terms) used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. It will be further understood that terms, such as those defined in commonly used dictionaries, should be interpreted as having a meaning that is consistent with their meaning in the context of the prior art and will not be interpreted in an idealized or overly formal sense unless expressly so defined herein.

The above-mentioned embodiments, objects, technical solutions and advantages of the present invention are further described in detail, it should be understood that the above-mentioned embodiments are only illustrative of the present invention and are not intended to limit the present invention, and any modifications, equivalents, improvements and the like made within the spirit and principle of the present invention should be included in the protection scope of the present invention.

Claims

1. A multi-target tracking method based on data association and track evaluation is characterized by comprising the following steps:

the specific steps of using RANSAC algorithm to perform straight line fitting on each observation of D ∈ D are as follows:

the specific steps of establishing a CRF model and a labeling mode of data association by utilizing a space-time relationship are as follows:

step A.2.1), each observation D e D is regarded as a vertex V;

Step A.2.5), effective track is given

For any valid label/_d∈L，

Step A.2.6), if a certain observation target d belongs to the foreground, then l_dE.g.., 1,2,. N }; if false alarm is given, l_d＝φ；

2. The multi-target tracking method based on data association and trajectory estimation as claimed in claim 1, wherein the step of establishing the fitting model, the prior model and the mutually exclusive model in step B) is as follows:

3. The multi-target tracking method based on data association and trajectory estimation as claimed in claim 2, wherein the objective function in step B) is as follows:

β, gamma and delta are preset weight threshold values;

E_d(l_dt) represents the energy of the trajectory fitting model,

representing the energy of the trajectory mutual exclusion model.

4. The multi-target tracking method based on data association and trajectory estimation as claimed in claim 3, wherein the specific steps of solving the objective function by using α -expansion algorithm and gradient descent method in the step B) are as follows:

step B.2.1), inputting an initial track set T and an observation set D;

step B.2.5), refitting the track set T by adopting a gradient descent method;

5. The multi-target tracking method based on data association and track evaluation as claimed in claim 4, wherein the specific steps of segmenting and merging the initial track set T based on the minimum energy in the step C) are as follows:

6. The multi-target tracking method based on data association and track evaluation as claimed in claim 5, wherein the specific steps of adding and deleting the initial track set T based on the minimum energy in the step C) are as follows:

7. The multi-target tracking method based on data association and track evaluation as claimed in claim 4, wherein the specific steps of growing and shrinking the initial track set T based on the minimum energy in the step C) are as follows: