Search

CN-121995322-A - Multi-target tracking method and system

CN121995322ACN 121995322 ACN121995322 ACN 121995322ACN-121995322-A

Abstract

The invention discloses a multi-target tracking method and a multi-target tracking system. The method comprises a state prediction step for predicting the current time target state and covariance based on the last time target state estimation, a factor graph construction step for establishing a two-factor graph model comprising two types of nodes representing targets and measurements and edges therebetween, wherein the edges represent associated probability weights, a message iteration step for executing multiple rounds of message transmission on the two-factor graph, and applying damping factors to outgoing messages in at least one round Weighted smoothing, and/or applying a scaling factor to incoming messages And performing confidence correction, namely calculating the edge association probability between the target and the measurement according to the iteration result, and updating the target state and covariance according to the edge association probability. The method solves the problems of excessive calculation complexity, easy track aggregation and excessive confidence in estimation caused by factor graph loops of the traditional method under the crossing scene of the dense clutter and the target, and improves tracking precision and stability.

Inventors

  • LIU ZHENYU
  • ZHOU RONG

Assignees

  • 清华大学深圳国际研究生院

Dates

Publication Date
20260508
Application Date
20260331

Claims (10)

  1. 1. A multi-target tracking method is characterized by comprising a state prediction step, a factor graph construction step, a message iteration step and a probability calculation and state updating step, wherein the state prediction step comprises predicting a target state predicted value and a prediction covariance at the current moment based on target state estimation at the previous moment, the factor graph construction step comprises building a two-factor graph model, the two-factor graph model comprises a first class node representing a target, a second class node representing measurement and an edge connecting the first class node and the second class node, the edge is used for representing the association probability weight between the target and the measurement, the message iteration step comprises performing multi-round message transmission between the first class node and the second class node on the two-factor graph model, wherein in at least one round of message transmission, a damping factor is applied to outgoing messages, and/or a scaling factor is applied to incoming messages, the confidence correction is carried out, and the probability calculation and state updating step comprises calculating the edge association probability between the target and the measurement according to the convergence result of the message iteration step and updating the target state estimation and the estimation covariance at the current moment based on the edge association probability.
  2. 2. The method of claim 1, further comprising, prior to the factor graph construction step, a wave gate screening step comprising calculating a statistical distance between the measured and target predicted values and screening valid correlation pairs according to a predetermined threshold, wherein edges in the two-factor graph model are established based only on the valid correlation pairs.
  3. 3. The method of claim 1, wherein the message iterating step includes a first message calculating step including calculating, for messages sent from the first class node to the second class node, based on initial association weights of targets and measurements and messages incoming from other second class nodes and introducing the scaling factor in the calculation, a first message updating step including weighting and fusing the messages obtained in the first message calculating step with corresponding history messages of a previous iteration using the damping factor to generate final messages sent to the second class node, a second message calculating step including calculating, for messages sent from the second class node to the first class node, messages incoming from the first class node based on initial association weights of targets and measurements and other first class nodes and introducing the scaling factor in the calculation, and a second message updating step including weighting and fusing the messages obtained in the second message calculating step with corresponding history messages of a previous iteration using the damping factor to generate final messages sent to the first class node.
  4. 4. A method according to claim 3, wherein the calculation in the first message calculation step follows the mathematical relationship: Wherein For the target in the p-th round of iteration Send to measurement Is used for the transmission of the intermediate message, For the initial association weight(s), For the last round of other measurements To the target Is used for the message of (a), Is the scaling factor.
  5. 5. A method according to claim 3, wherein the calculation in the second message calculation step follows the mathematical relationship: Wherein For measurement in the p-th iteration To the target Is used for the transmission of the intermediate message, For the initial association weight(s), Other targets for the current wheel Send to measurement Is used for the message of (a), For the scaling factor, the constraint that "a measurement is derived from at most one target" is embodied.
  6. 6. The method of claim 1, wherein in the probability calculation and state updating steps, the probability distribution is modified by introducing the scaling factor when calculating the edge correlation probability, and the calculation follows the following mathematical relationship: Wherein Is the object of And measuring Is associated with the probability of the edge of the (c) sheet, For the initial association weight(s), For all measurements after iteration convergence To the target Is used for the message of (a), Is the scaling factor.
  7. 7. The method of claim 1, wherein the state prediction step and the probability calculation and state update step are implemented based on a kalman filter framework.
  8. 8. The method of claim 1, wherein the damping factor has a value in the range of [0, 1], and the scaling factor has a value in the range of (0, 1].
  9. 9. The method of claim 1, wherein the message iteration step is terminated under the condition that a maximum value of a difference between message matrices generated by two successive iterations is less than a preset convergence threshold, or that a number of iterations reaches a preset maximum number of iterations.
  10. 10. A signal processing system for multi-target tracking, comprising a memory for storing a computer program, and a processor for executing the computer program in the memory for implementing the multi-target tracking method according to any one of claims 1 to 9.

Description

Multi-target tracking method and system Technical Field The invention relates to the technical field of signal processing and target tracking, in particular to a method for tracking a target state by utilizing cyclic belief propagation and joint probability data association under a dense mixed wave and multi-target crossing scene. Background The multi-target tracking technology is widely applied to the fields of radar monitoring, automatic driving, air traffic control and the like, and has the core task of jointly estimating the number of targets and the motion states (such as position, speed and the like) of the targets changing along with time from sensor measurement data comprising noise, clutter and false alarms. In a multi-target tracking process, the most critical and challenging link is data correlation, i.e., where the measurement source is uncertain, which measurement originates from which target, or whether it originates from clutter background. Due to sensor resolution limitations and environmental interference, there is often a high degree of ambiguity in the correspondence between the measurement and the target, and erroneous correlations will directly lead to filter divergence and track loss. For data correlation problems, the global nearest neighbor algorithm is a typical "hard decision" based approach that finds a globally optimal single correlation hypothesis by minimizing the total distance or maximizing the likelihood function. Although the global nearest neighbor algorithm is relatively simple to calculate, it is extremely fragile when dense clutter or objects are close to each other, and is prone to false correlations. In contrast, joint probability data correlation algorithms employ a Bayesian inference-based "soft correlation" strategy that does not make decisions other than that, but rather calculates the edge correlation probability that each measurement originates from each target, and updates the target state with a weighted sum of all possible correlation hypotheses. In order to reduce the computational complexity while ensuring accuracy, factor graph-based belief propagation algorithms (also known as sum-product algorithms) are introduced into the data correlation field. The belief propagation algorithm models the data association problem as a graph model that contains variable nodes (representing association states) and factor nodes (representing constraints), and approximates the computation of edge association probabilities by iteratively passing probability "messages" between the nodes. Compared with the traditional method of combination enumeration, the belief propagation algorithm utilizes the conditional independence of the statistical model to greatly reduce the calculation complexity and greatly improve the expandability of the algorithm. Although joint probability data correlation algorithms build the basis for multi-target tracking, the prior art has significant and insurmountable drawbacks in the face of large-scale dense target scenarios. First, the computational complexity of conventional algorithms grows exponentially. As indicated by the related research, the posterior probability of the core-joint correlation event of the algorithm is accurately calculated, which is equivalent to the product-sum formula of a calculation matrix in mathematical essence, and belongs to the extremely difficult counting problem in the calculation complexity theory. As the number of targets and the number of measured sensors in the field of view increases, the number of feasible joint association hypotheses expands dramatically, resulting in a computational load that rapidly exceeds the processing capacity of the real-time system and fails to meet the application requirements in high-density complex environments. Second, joint probability data correlation algorithms suffer from the inherent "track condensation" phenomenon when processing spatially adjacent objects. When two or more targets are very close in space (e.g., parallel motion or cross), the minimum mean square error based estimation criteria will weight average the common measurements of neighboring targets such that the state estimates tend to the geometric center of the measurement cluster rather than the respective true positions, resulting in originally separate tracks attracting each other and eventually merging, resulting in loss of target identity. Finally, while factor graph-based belief propagation algorithms can reduce computational complexity, standard algorithms have limitations in processing data to correlate specific graph structures. Since the factor graph of data correlation typically comprises a closed loop structure, directly applying a standard belief propagation algorithm results in information being fed back in a loop, producing an "echo" effect. The positive feedback effect causes the edge probability distribution calculated by the algorithm to show non-physical 'excessive confidence', namely, the estim