CN105761276B - Based on the iteration RANSAC GM-PHD multi-object tracking methods that adaptively newborn target strength is estimated - Google Patents

Abstract

A GM‑PHD multi-target tracking method based on iterative RANSAC adaptive nascent target strength estimation, including I‑RANSAC nascent target detection module and PHD filtering module. Wherein: the I-RANSAC new target detection module includes: an effective measurement generation submodule, a hypothesis generation submodule, and a hypothesis testing submodule, wherein: the effective measurement generation submodule is connected with the current measurement and the current state estimation to transmit the current For the effective measurement of "sliding window", the hypothesis generation sub-module is connected with the effective measurement sub-module to transmit the track hypothesis generated by random sampling from the effective measurement, and the hypothesis verification sub-module is connected with the hypothesis generation sub-module to transmit the current hypothesis The empirical results of the track, ie, the position information of the identified nascent target. The method of the invention has the advantages of being effective and robust, and can be widely used in multi-target tracking fields such as radar, robot, and video surveillance.

Description

GM-PHD multi-target tracking based on iterative RANSAC adaptive nascent target strength estimation tracking method

technical field

The invention relates to a video multi-target tracking method, in particular to a dynamic video multi-target tracking method based on Gaussian mixture probability hypothesis density (GM-PHD) filtering.

Background technique

Multi-target tracking (MTT) technology has been widely used in different fields such as intelligent monitoring, robot automatic navigation, and biology. The purpose of MTT is to estimate the number and state of multiple targets from a measurement set containing clutter. Due to the existence of clutter in the measurement and the uncertainty of detection, it is still a difficult problem to accurately track multiple targets with varying numbers. The traditional multi-target tracking application "measurement-track" data association technology aims to decouple the multi-target tracking problem into multiple single-target tracking problems. The multiple hypothesis method (MHT) proposed by Reid et al. and the joint probabilistic data association method (JPDA) proposed by Bar-Shalom et al. are the two most representative and effective association methods. Due to the combined nature of the method, the common disadvantage of data association methods is the huge amount of calculation, which limits the practical application of this type of algorithm.

In recent years, random finite set (RFS) based multi-object tracking methods have achieved great breakthroughs and received extensive attention. Based on the RFS theoretical framework method, uncertain measurements and multi-target states are represented as random sets, and then the multi-target tracking problem is expressed as a multidimensional Bayesian filter, thereby avoiding the data association of "measurement-track". Among them, the probability hypothesis density (PHD) filter proposed by Mahler and the PHD implementation method proposed by later scholars are the most representative. PHD uses the first-order statistic (probability hypothesis density, or PHD) of the posterior probability density of multi-target random sets to approximately replace the multi-target posterior probability density, and simplifies the integral operation in the multidimensional Bayesian filtering recursive formula, making the multidimensional The implementation of Bayesian filtering becomes possible. But the PHD filter has the problem of inaccurate target number estimation. In order to solve this problem, Mahler proposed the Cardinalized Probability Hypothesis Density (CPHD) filter. CPHD obtains an accurate estimate of the number of targets by simultaneously propagating the intensity function and the cardinality distribution of a random set of states. Although the PHD and CPHD filters can deal with the problems of newborn, hatching, and death of multiple targets, there is still a shortcoming that the standard PHD and CPHD filters assume that the intensity function of the newborn target is known. However, the strength function of nascent targets is not easy to obtain in general. Therefore, this assumption restricts the wide application of PHD filters.

Through literature search to prior art, it is found that "Adaptive target birth" published by B.RISTIC et al. Intensity for PHD and CPHD filters (the nascent target adaptive intensity function in PHD and CPHD filters)" proposes an adaptive nascent target intensity method based on the particle PHD filter. In this method, new target intensity functions are designed by measuring each frame, and the measurement space is divided into a measurable subspace p and an unmeasurable subspace v. For p, the new target intensity is constructed by the likelihood function, but for v, Known prior information is required, and the construction problem of the nascent target intensity function is not fundamentally solved. Michael Beard et al proposed a Gaussian mixture PHD filter when the intensity distribution of the newborn target is uniform, but still assumes that the intensity distribution of the newborn target is known. Based on the literature, Ouyang Cheng et al. proposed a normalization factor correction method to improve the track normalization imbalance problem of the original algorithm, but this method still needs to know some prior information, and the method still remains after filtering. Contains a lot of clutter, weakening the main advantage of the PHD filter to remove clutter. Wang et al. proposed to use the Probability Likelihood Ratio Test (SPRT) method of all measurements to detect newborn targets, and then construct the newborn target strength function. However, due to its combinatorial optimization using all measurements, it inevitably brings a huge computational burden.

Contents of the invention

Aiming at the deficiencies in the above-mentioned prior art, the present invention provides a GM-PHD multi-target tracking method based on iterative random sampling consistency (RANSAC) algorithm for adaptive newborn target strength estimation. The present invention proposes an iterative RANSAC (I-RANSAC) algorithm that can estimate the position of the newborn target from the measurement set. Based on the estimated position information of the newborn target, the intensity function of the newborn target is constructed, thereby solving the need of the original PHD filter. Insufficiency of the target strength function is known. The present invention provides an adaptive GM-PHD multi-target tracking framework based on the proposed I-RANSAC algorithm, which solves the problem that the original GM-PHD multi-target tracking method needs to know the newborn target strength function, and has the advantages of simple implementation and robustness Strong advantage.

The present invention is achieved through the following technical solutions:

The present invention includes: an I-RANSAC newborn target detection module and a PHD filter module, wherein: the I-RANSAC newborn target detection module is connected with the measurement data in the "sliding window" and the current state estimation to transmit possible newborns in the current sliding window The position information of the target, the so-called "sliding window" refers to a continuous measurement set with a fixed number of frames, which moves forward with time, that is, when a new frame measurement arrives, the frame measurement Add the last frame of the "sliding window" set, and discard the first frame measurement in the "sliding window" set, so as to keep the number of frames measured in the "sliding window" set fixed. Rather, a "sliding window" is a queue of measurements that moves forward over time. The PHD filtering module is connected with the I-RANSAC new target detection module and the current measurement to transmit the state estimation random set and target number estimation random set of all targets.

The I-RANSAC new target detection module includes: an effective measurement generation submodule, a hypothesis generation submodule, and a hypothesis verification submodule, wherein: the effective measurement generation submodule is connected with the current measurement and the current state estimation to transmit the current "slip" The effective measurement of the "window", the hypothesis generation sub-module is connected with the effective measurement sub-module to transmit the track hypothesis generated by random sampling from the effective measurement, and the hypothesis verification sub-module is connected with the hypothesis generation sub-module to transmit the current hypothetical track The empirical result of , that is, the location information of the identified nascent target.

The PHD filter module includes: newborn target strength function construction submodule, prediction submodule, update submodule, Gaussian pruning submodule and state extraction submodule, wherein: newborn target strength function construction submodule and I-RANSAC newborn target detection The hypothesis testing sub-module in the module is connected to transmit the nascent target strength function, the prediction sub-module is connected to the nascent target strength function construction sub-module, and the prediction Gaussian element parameters of the target state random set PHD are transmitted, and the update sub-module is respectively connected to the prediction sub-module and the measurement Transmit the updated Gaussian element parameters of the target state random set PHD, the Gaussian element pruning submodule is connected with the update submodule, and transmit the Gaussian element parameters of the updated Gaussian element merged and deleted target state random set PHD, and the state extraction submodule It is connected with the Gaussian element pruning sub-module to transmit the target state estimation random set and the target number estimation random set.

Compared with the prior art, the beneficial effects of the present invention are: the I-RANSAC-based nascent target detection module provides the nascent target strength information for the PHD filter; solves the problem that the PHD filter needs to know the nascent target strength function, and ensures Robustness and reliability of PHD filters. The method is simple, effective, easy to implement, and has good robustness, and can be widely used in military and civilian multi-target tracking fields.

Description of drawings

Fig. 1 is a block diagram of an adaptive GM-PHD multi-target tracking system based on I-RANSAC in an embodiment of the present invention;

Fig. 2 is a tracking scene and a target track diagram in an embodiment of the present invention;

FIG. 3 is a measurement diagram including clutter in the x direction and y direction of each frame in the embodiment of the present invention;

Fig. 4 is the position estimation result of time in the x and y directions in the embodiment of the present invention;

Fig. 5 provides the result of estimating the same multi-target scene by the standard GM-PHD filter for an embodiment of the present invention;

Fig. 6 provides the comparison result of the real number of targets of 100 Monte Carlo averages, the standard GM-PHD filter and the number of targets estimated by the method of the present invention in the embodiment of the present invention;

Fig. 7 is the comparison diagram of the OSPA distance estimated by the standard GM-PHD filter of 100 Monte Carlo averages and the method of the present invention in the embodiment of the present invention;

Detailed ways

The embodiments of the present invention are described in detail below in conjunction with the accompanying drawings: this embodiment is implemented on the premise of the technical solution of the present invention, and detailed implementation methods and specific operating procedures are provided, but the protection scope of the present invention is not limited to the following the described embodiment.

As shown in Figure 1, this embodiment includes: I-RANSAC newborn target detection module and PHD filter module, wherein: I-RANSAC newborn target detection module includes: effective measurement generation submodule, hypothesis generation submodule, hypothesis testing submodule , where: the effective measurement generation sub-module is connected with the current measurement and the current state estimation to transmit the effective measurement of the current "sliding window", assuming that the generation sub-module is connected with the effective measurement sub-module and transmits the effective measurement through random sampling As for the generated track hypothesis, the hypothesis checking sub-module is connected with the hypothesis generating sub-module to transmit the empirical results of the current hypothetical track, that is, the position information of the confirmed newborn target.

The valid metrics generation sub-module implements valid metrics for detecting nascent objects.

The hypothesis generation sub-module implements various possible nascent target hypotheses.

The hypothesis testing sub-module realizes the testing of nascent target hypotheses to confirm possible nascent targets.

The PHD filtering module includes: new target strength function construction sub-module, prediction sub-module, update sub-module, Gaussian pruning sub-module and state extraction sub-module. Among them: the nascent target strength function construction sub-module is connected to the hypothesis testing sub-module in the I-RANSAC nascent target detection module to transmit the nascent target strength function, and the prediction sub-module is connected to the nascent target strength function construction sub-module to transmit the prediction of the target state random set PHD Gaussian element parameters, the update sub-module is connected with the prediction sub-module and the measurement, and the updated Gaussian element parameters of the target state random set PHD are transmitted, and the Gaussian element pruning sub-module is connected with the update sub-module, and the updated Gaussian elements are merged and deleted Gaussian element parameters of the final target state random set PHD, the state extraction sub-module is connected with the Gaussian element pruning sub-module to transmit target state estimation random set and target number estimation random set.

The nascent target intensity function sub-module realizes the construction of the intensity function of the nascent target.

The prediction sub-module realizes the prediction of the Gaussian meta-parameters of the PHD of the target state random set.

The updating sub-module realizes updating the Gaussian meta-parameters of the random set PHD of the target prediction state.

The Gaussian element pruning sub-module implements merging Gaussian elements with very close distances and removing Gaussian elements with extremely small weights, so as to reduce the amount of calculation and clutter.

The expected value corresponding to the Gaussian element whose weight value is greater than the threshold (generally 0.5) extracted by the state extraction sub-module is the state random set, and the Gaussian element number is the target number random set.

The specific working process of the efficiency measurement generation sub-module in this embodiment is as follows:

1) Input a new frame measurement, put it at the end of the "sliding window" queue, remove the first frame measurement of the "sliding window" queue, and realize the movement of the "sliding window" queue.

2) Let the current state estimate be x _k , calculate the measurement residual d _k (i)=z _k (i)-H _k F _k x _k of the corresponding frame in the "sliding window", where H _k and F _k are respectively The measurement matrix and state transition matrix of the system; and the norm of the residuals: where S _k is the covariance matrix of the residual vector. If the g _k (i) distance is smaller than the set threshold, the corresponding measurement is considered to be associated with the existing track, and the measurement is removed. In this way, an effective measurement set is obtained.

In this embodiment, it is assumed that the specific working process of generating sub-modules is as follows: a subset containing one sample is randomly selected from the first two frames of the effective measurement set, and its model is calculated by the least squares method based on these two sample points M; The set after removing the two samples drawn from the effective measurement set is called the remainder of the original measurement set. The samples whose error between the co-set and the model M are less than a certain threshold are called interior points, and they form a set called a consistent set. Model M is the current hypothetical model.

The specific working process of the hypothesis testing sub-module in this embodiment is: if the cardinality of the consistent set is greater than a given threshold, it is considered that the correct model parameters have been obtained, and the model is recalculated by the least squares method using the samples in the consistent set, the new The model is a nascent target model; after a new target is determined, the effective measurement set is replaced by the residual set, and the above hypothesis generation and hypothesis testing processes are repeated to confirm multiple new targets.

The target model in this example is:

1) The state equation of the target is a nonlinear asymptotic turn (CT) model:

x _k ＝F(ω)x _k-1 +Gv _k-1 (3)

Among them, ω is the turning rate, when the target is described by the coordinates of the center of mass of the target and its speed, the state x _k can be expressed as:

x _k = (loc _{x, k} , loc _{y, k} , vel _{x, k} , vel _{y, k} , ω) ^T (4)

F(ω) is the state transition matrix,

The state noise v _k is zero-mean Gaussian noise with Q as the covariance, and σ _v is the standard deviation of the system noise.

2) The system observation model is z _k =Hx _k +w _k , where the observation matrix H is:

The observation noise w _k is zero-mean Gaussian noise with a covariance of σ _w is the standard deviation of observation noise.

Some parameters of the PHD filter module in this embodiment are set as follows: the survival probability P _S of each target is set to be 0.99, and the target detection probability P _D is set to be 0.99. The standard deviation of state noise σ _v =2m/s ² , and the standard deviation of observation noise σ _w =8. The sampling time interval is taken as T=1s. The clutter follows a uniform distribution in the tracking area [0, 20000]×[0, 20000], and the number of clutter at each moment obeys a Poisson distribution with a parameter of λ _c =10 ^-7 m ^-2 (that is, the average frame has 40 clutter).

The specific working process of the newborn target intensity function sub-module in this embodiment is as follows:

Assuming that m newborn targets are detected by the I-RANSAC newborn target detection module at time k, the position of each newborn target is used as the mean value of the position, the given value is used as the mean value of the speed, and the given larger positive definite numerical matrix is used as the variance The array constructs a multidimensional Gaussian distribution function as the intensity function of each new target, and its weight is 0.03.

The specific working process of the prediction sub-module in this embodiment is as follows:

Assume that the Gaussian meta-parameters describing PHD at time k are Among them, J _k is the number of Gaussian elements at time k, is the mean value of the i-th Gaussian element at time k, is its weight, is the corresponding covariance.

1) Predict the newly generated targets, assuming that the number of newly generated targets at time k+1 is J _{γ, k+1} , then for j=1,..., J _{γ, k+1} , we have in Respectively, the weight, state expectation (mean) and covariance of the new target Gaussian element;

2) For the prediction of hatching targets, if the number of hatching targets is J _{β, k+1} , then for j=1,..., J _{β, k+1} , l=1,..., J _k have in is the weight of the incubation target Gaussian meta-model, are the state transition matrix and state noise covariance in (5) and (6), respectively.

3) Predict and calculate the continuation target, set its survival probability as p _S , then for j=1,..., J _k , update the weight, mean and covariance according to the following formula:

The specific working process of updating the sub-module in this embodiment is as follows:

1) The measurement random set obtained by the moving target detection module is denoted as Z _k+1 , and the observation matrix H and measurement noise covariance R of formula (7) are used to update the weights, mean and covariance. p _D is the detection probability as described in the above embodiment, then update the undetected target with formula (8)～(10): for j=1,..., J _k+1|k , wherein J _{k+1| k} ＝J _{γ, k+1} +lJ _{β, k+1} +J _k+1 , there are:

2) Update the detected target, that is, use the centroid coordinates of the moving target detection module as the measurement random set to update and calculate, for each z∈Z _k+1 , calculate:

Suppose the probability of clutter RFS of Poisson distribution is κ _k (z), for j=1,..., J _k+1|k :

Implementation Effect

The tracking scene in this embodiment is a two-dimensional multi-target scene, and there are 8 targets in the monitoring area. The newly generated targets obey the Poisson distribution. In order to compare with the original PHD filter, the starting positions of 5 targets are known, and the appearance of new targets obeys the Poisson distribution, and the intensity is: where ω _γ =0.03, The starting positions and times of the remaining three targets are unknown.

Figure 2 shows the target track in the simulation scene.

FIG. 3 is a measurement diagram including clutter in the x direction and y direction of each frame.

Fig. 4 is the result of time position estimation in the x and y directions by the method of the present invention. It can be seen from FIG. 4 that the method of the present invention can not only accurately estimate 5 newborn targets with known starting positions, but also accurately estimate 3 newborn targets with unknown starting positions.

Figure 5 presents the results of estimating the same multi-object scene by the standard GM-PHD filter. Wherein the parameter setting of the PHD filtering part is exactly the same as the method of the present invention. It can be seen that the GM-PHD filter can only accurately estimate 5 nascent targets with known initial positions, but cannot estimate 3 nascent targets with unknown initial positions. This is due to the fact that the GM-PHD filter does not have the capability of new targets with unknown starting positions.

Fig. 6 shows the comparison result of the real number of targets estimated by the 100 Monte Carlo averages, the standard GM-PHD filter and the method of the present invention, wherein the red solid line represents the real target number, and the blue dotted line represents the estimated number of the present invention. The number of targets in , and the dotted line with dots in black indicates the number of targets estimated by the standard GM-PHD filter. It can be clearly seen that the standard GM-PHD filter estimate gives wrong target number estimates in the time period after the newborn targets appear, but the method of the present invention gives correct target number estimates throughout the whole process.

Fig. 7 shows a comparison chart of the OSPA distance estimated by the standard GM-PHD filter averaged 100 times and the method of the present invention. The OSPA distance is a measure of the "distance" between two random sets, which can be used to evaluate the performance of the tracking algorithm, and the smaller the value, the better the tracking performance of the algorithm.

Therefore, the method of the invention well solves the problem that the standard GM-PHD filter needs to know the initial intensity function of the target, and has strong practicability, effectiveness and robustness.

Claims (7)

1. a kind of GM-PHD multi-object tracking methods of the adaptive newborn target strength estimation based on iteration RANSAC, feature It is, the method is to be based on I-RANSAC new lives module of target detection and PHD filter modules；Wherein：I-RANSAC new life mesh Mark detection module in " sliding window " metric data and current state estimation be connected transmit be likely to occur in current sliding window it is new The location information of raw target, PHD filter modules are connected transmission all with I-RANSAC new lives module of target detection and current measure The state estimation random set and number of targets of target estimate random set；" sliding window " is a measurement moved forward with the time Queue；

The I-RANSAC new lives module of target detection includes：It effectively measures and generates submodule, assume to generate submodule, assume inspection Submodule is tested, wherein：Effectively measurement generation submodule is connected to transmit and currently " slide with currently measurement and current state estimation respectively Effective measurement of window ", it is assumed that generation submodule is connected with effective measurement generation submodule to be transmitted from effectively measuring by random Sampling and the flight path that generates are it is assumed that hypothesis testing submodule is connected the warp transmitted to currently assuming flight path with generation submodule is assumed It tests as a result, confirming the location information of newborn target；

The PHD filter modules include：Newborn target strength function structure submodule, prediction submodule, update submodule, Gauss Member trimming submodule and state extract submodule, wherein：Newborn target strength function structure submodule and I-RANSAC new life mesh Mark the newborn target strength function of the connected transmission of hypothesis testing submodule in detection module, prediction submodule and new life target strength Function builds submodule and is connected the prediction Gauss member parameter of transmission objectives state random set PHD, update submodule respectively with prediction Submodule trims submodule with the current updated Gauss member parameter for measuring the transmission objectives state random set PHD that is connected, Gauss member Block is connected with update submodule transmits the Gauss member of the dbjective state random set PHD after updated Gauss member is merged and deleted Parameter, state extract submodule and Gauss member trimming submodule be connected transmission objectives state estimation random set and number of targets estimate with Machine collection.

2. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that effective measure generates the end that submodule enters new input quantity measuring " sliding window " queue, together When remove " sliding window " queue first frame amount survey, realize " sliding window " queue movement, then according to current state estimation and " sliding window " The measurement of middle corresponding frame calculates residual error and its norm, according to the going or staying that the size of the norm determines to measure, to form effective amount Survey set.

3. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that the hypothesis generates submodule and respectively randomly selected from effective measure during two frame amount are surveyed before collection The subset for including a sample calculates its model M according to the two sample points by least square method, the vacation of model M, that is, current If model.

4. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that the hypothesis testing submodule is compared the radix unanimously collected with given threshold value, if one The radix of collection is caused to be more than given threshold value, then it is assumed that obtain correct model parameter, and using the sample unanimously concentrated by most Small square law recalculates model, which is a newborn object module；After determining a fresh target, replaced by complementary set It changes and effectively measures collection, repeat above-mentioned hypothesis generation and hypothesis testing process, you can confirm multiple newborn targets；Collection is measured from effective Before two frame amount survey in respectively randomly select the subset for including a sample, calculated by least square method according to the two sample points Go out its model M；It effectively measures the set after concentrating two samples for removing and extracting and is called the complementary set that commercial weight surveys collection；In complementary set with mould The sample that the error of type M is less than a certain given threshold is called interior point, and the set that they are constituted is called consistent collection；Model M, that is, current Hypothesized model.

5. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that the described newborn target strength function structure submodule then using each newborn target location as Location mean value using given value as speed mean value, and constructs one using given larger positive definite numerical matrix as variance matrix Intensity function of the Multi-dimensional Gaussian distribution function as each newborn target, and its weights is taken as 0.03.

6. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that the prediction submodule includes to hatch dbjective state mesh to newborn dbjective state random set PHD The Gauss member parameter of mark random set PHD and existing dbjective state random set PHD is predicted.

7. the GM-PHD multiple targets of the adaptive newborn target strength estimation according to claim 1 based on iteration RANSAC Tracking, characterized in that the state extracts submodule and refers to after update submodule and Gauss member trimming submodule The Gauss member of dbjective state random set PHD handle, extract Gauss member of its weights more than 0.5 as Target state estimator The number of random set, Gauss member of the weights more than 0.5 estimates random set as number of targets.