{'fraction_non_alphanumeric': 0.052158273381294966, 'fraction_numerical': 0.010116906474820143, 'mean_word_length': 4.13546276698095, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Neural Enhanced Belief Propagation for Data Association in Multiobject Tracking

Situation-aware technologies enabled by multiobject tracking (MOT) methods will create new services and applications in fields such as autonomous navigation and applied ocean sciences. Belief propagation (BP) is a state-of-the-art method for Bayesian MOT but fully relies on a statistical model and preprocessed sensor measurements. In this paper, we establish a hybrid method for model-based and data-driven MOT. The proposed neural enhanced belief propagation (NEBP) approach complements BP by information learned from raw sensor data with the goal to improve data association and to reject false alarm measurements. We evaluate the performance of our NEBP approach for MOT on the nuScenes autonomous driving dataset and demonstrate that it can outperform state-of-the-art reference methods.


I. INTRODUCTION
Multi-object tracking (MOT) [1] is a key aspect in a variety of applications including autonomous navigation and applied ocean sciences. In particular, in autonomous navigation systems accurate MOT enables tasks such as motion forecasting [2] and path planning [3]. The main challenge in MOT is data association uncertainty, i.e., the unknown association between measurements and objects. MOT is further complicated by the fact that the number of objects is unknown.
Most MOT methods adopt a detect-then-track approach where an object detector [4]- [13] is applied to the raw sensor data. The resulting object detections are then used as measurements for MOT. Many existing MOT methods follow a global nearest neighbor [1] approach where a Hungarian [14] or a greedy matching algorithm is used to perform "hard" data association. These types of methods rely on heuristics for track initialization and termination. To improve the reliability of hard data association, often discriminative features are extracted and incorporated by the matching algorithm [7], [15]- [22]. Another line of work formulates and solves MOT in the Bayesian estimation framework [1], [23]- [29]. This type of methods rely on statistical models for object birth, object motion, and sensor measurements [1], [23]- [29]. The statistical model makes it possible to perform a more robust probabilistic "soft" data association. In addition, heuristics for track initialization and termination can be avoided by modeling the existence of objects by binary random variables.
BP [30] can solve high-dimensional Bayesian estimation problems by "passing messages" on the edges of a factor graph [30] that represents the underlying statistical model. By exploiting the structure of the graph, BP-based MOT methods [23]- [25], [31], [32] are highly scalable. This makes it possible to generate and maintain a very large number of potential object tracks and, in turn, outperform existing MOT approaches [24], [25]. However, BP fully relies on a statistical model. When the factor graph does not accurately represent the true data generating process, MOT performance is reduced due to model mismatch. In addition, with the detectthen-track approach employed by BP-based MOT, important object-related information might be discarded by the object detector. We aim to overcome these limitations by introducing information learned from raw sensor data to BP-based MOT.
NEBP [33] is a hybrid method that combines the benefits of model-based and data-driven inference and addresses potential limitations of BP such as model mismatch and overconfident beliefs [33], [34]. NEBP has been successfully applied to decoding [33] and cooperative localization [34] tasks. In NEBP, a graph neural network (GNN) that matches the topology of the factor graph is introduced. The trained GNN enhances potentially inaccurate BP messages to ultimately improve object declaration and estimation accuracy.
In this paper, we propose NEBP for MOT. Here, BP messages calculated as input for probabilistic data association are combined with the output of the GNN. The GNN uses measurements (i.e., object detections) and shape features learned from raw sensor data as an input. For false alarm rejection, the GNN identifies which measurements are likely false alarms. If a measurement has been identified as a potential false alarm, the false alarm distribution in the statistical model of BP is locally increased. This reduces the probability that the measurement is associated with an existing object track or initializes a new object track. Object shape association computes improved association probabilities by also comparing shape features extracted for existing object tracks with shape features extracted for measurements. The resulting NEBP method for MOT can improve object declaration and estimation performance compared to BP for MOT as well as outperform further state-of-the-art methods.
The main contributions of this paper can be summarized as follows.
driving dataset [35] and demonstrate state-of-the-art object tracking performance. Our approach recognizes that in modern MOT problems with high-resolution sensors [32], [36]- [38], it is challenging to capture object shapes and the corresponding data generating process by a statistical model. Consequently, the influence of object shapes on data generation is best learned directly from data.

II. BACKGROUND
In what follows, we will briefly review factor graphs and graph neural networks (GNNs).

A. Factor Graphs
A factor graph [30] is a bipartite undirected graph G f = (V f , E f ) that consists of a set of edges E f and a set of vertices or nodes V f = Q ∪ F . A variable node q ∈ Q represents a random variable x q and a factor node s ∈ F represents a factor f s x (s) . Here, each factor argument x (s) comprises certain random variables x q (each x q can appear in several x (s) ). Factor nodes and variable nodes are typically depicted by circles and boxes, respectively. The joint probability density function (PDF) represented by the factor graph reads p(x) ∝ s∈F f s x (s) where ∝ indicates equality up to a constant factor.
Belief propagation (BP) [30], also known as the sumproduct algorithm can compute marginal PDFs p(x q ), q ∈ Q efficiently. BP performs local operations called "messages" on the edges of the factor graph. There are two types of messages: (i) messages passed from variable nodes to factor nodes given by and (ii) messages passed from factor nodes to variable nodes defined as Here, N Q (·) ⊆ Q and N F (·) ⊆ F denote the set of neighboring variable and factor nodes, respectively. After message passing is completed, one can subsequently obtain marginal PDFs p(x q ) as the product of all incoming messages from the neighboring factors, i.e., p(x q ) ∝ s∈NF (q) φ fs→xq (x q ). In factor graph with loops, BP is applied in an iterative manner. It can then only provide approximations of marginal posterior pdfs p(x q ).

B. Graph Neural Networks
Graph Neural Networks (GNNs) [39] extend neural networks to graph-structured data. We consider message passing neural networks (MPNNs) [40] which are a variant of GNNs that generalizes graph convolutional networks [41] and provides a message passing mechanism similar to BP. A MPNN is defined on a graph G = (V, E) where E induces the sets of neighbors N (i) = {j ∈ V (i, j) ∈ E}.
Each node i ∈ V is associated with a vector h i called node embedding. At message passing iteration l ∈ {1, . . . , L}, the following operations are performed for each node i ∈ V in parallel. First, messages are exchanged with neighboring nodes j ∈ N (i). In particular, the GNN message sent from node i ∈ V to its neighboring node j ∈ N (i) is given by In addition, the node embedding h (l) i is updated by incorporating the sum of received messages m Here, g i (·), i ∈ V and g i→j (·), (i, j) ∈ E denote the node and edge networks, respectively. Furthermore, a i and a i→j denote node and edge attributes.

III. REVIEW OF BP-BASED MULTI-OBJECT TRACKING
The proposed NEBP approach is based on BP-based MOT introduced in [25]. The statistical model used by BP-based MOT is reviewed next.

A. Object States
At each time frame k, an object detector g det (·) extracts J k measurements z k [z T k,1 · · · z T k,J k ] T from raw sensor data Z k , i.e., z k = g det (Z k ). All measurements extracted up to time frame k are denoted as z 1:k [z T 1 · · · z T k ] T . Since the number objects is unknown, potential object (PO) states are introduced. The number of PO states N k is the maximum possible number of objects that have generated a measurement up to time frame k. At time frame k, the existence of a PO n ∈ {1, · · · , N k } is modeled by a binary random existence variable r k,n ∈ {0, 1}, i.e., PO n exists if and only if r k,n = 1. The state of PO n is modeled by the random vector x k,n . The augmented PO state vector is denoted by y k,n [x T k,n r k,n ] T and the joint PO state vector by y k [y T k,1 · · · y T k,N k ] T . There are two types of POs: , · · · , I k } represent objects that have generated a measurement for the first time at a previous time frame k ′ < k.
New POs become legacy POs when the measurements of the next time frame are considered. Thus, the number of legacy POs at time frame k is I k = I k−1 +J k−1 = N k−1 and the total number of POs is N k = I k + J k . We further denote the joint new PO state by y k [y T k,1 · · · y T k,J k ] T and the joint legacy PO state by y k [y T k,1 · · · y T k,

B. Measurement Model
The origin of measurements z k,j , j ∈ {1, · · · , J k } is unknown. A measurement can originate from a PO or can be a false alarm. Furthermore, a PO may also not generate any measurements (missed detection). With the assumption that a PO can generate at most one measurement and a measurement is originated from at most one PO, we model data association uncertainty as follows [25]. The PO-measurement association at time frame k can be described by an "object-oriented" DA vector a k = [a k,1 · · · a k,I k ] T . Here, the association variable a k,i = j ∈ {1, · · · , J k } indicates that legacy PO i generated measurement j and a k,i = 0 indicated that legacy PO i did not generate any measurement at time k. Following [42], we also introduce the "measurement-oriented" DA vector , · · · , I k } if measurement j was generated by legacy PO i, or b k,j = 0 if measurement j was not generated by any legacy PO. Note that there is a one-to-one mapping between a k and b k and vice versa. Introducing b k in addition to a k makes it possible to develop scalable MOT [25]. Finally, we establish the notation If legacy PO i exists, it generates a measurement (i.e. a k,i = j ∈ {1, · · · , J k }) with probability p d . Furthermore, the probability that it also exists at the next time frame k + 1 is p s . The number of false alarms is modeled by a Poisson distribution with mean µ fa and false alarm measurements are independent and identically distributed according to f fa (z k,j ). Before the measurements {z k,j } J k j=1 are observed, the number of new POs is unknown. The number of newly detected objects is Poisson distributed with mean µ n , while the states of newly detected objects are a priori independent and identically distributed according to f n (x k,j ). Following the assumptions presented in [25, Sec. VIII-A], the joint posterior PDF f (y 1:k , a 1:k , b 1:k |z 1:k ) can be derived [25, Sec. VIII-G]. The factorization of this joint posterior pdf is visualized by the factor graph shown in Fig. 1a. Note that legacy POs are connected to object-oriented association variables and new POs are connected to measurement-oriented association variables.

C. Object Declaration and State Estimation
In the Bayesian setting, declaration of object existence and object state estimation are based on the marginal existence probabilities p(r k,n = 1|z 1:k ) and the conditional PDFs f (x k,n |r k,n = 1, z 1:k ). In particular, declaration of object existence is performed by comparing p(r k,n = 1|z 1:k ) to a threshold T dec . In addition, for objects n that are declared to exist, an estimate of x k,n is provided by the minimum meansquare error (MMSE) estimator Note that declaration of object existence is based on the existence probability p(r k,n = 1|z 1:k ) = f (x k,n , r k,n = 1| z 1:k )dx k,n . In addition, object state estimation makes use of f (x k,n |r k,n = 1, z 1:k ) = f (y k,n |z 1:k ) p(r k,n = 1|z 1:k ) .
Thus, both tasks rely on the calculation of marginal posterior PDFs f (y k,n |z 1:k ) f (x k,n , r k,n |z 1:k ). By applying BP following [25, Sec. VIII-IX], accurate approximations (a.k.a. "beliefs")f (y k,n ) ≈ f (y k,n |z 1:k ) of marginal posterior PDFs can be calculated efficiently. For future reference we introduce the notationr k,n = p(r k,n = 1|z 1:k ).
Note that since we introduce a new PO for each measurement, the number of POs grows with time k. Therefore, legacy and new POs whose approximate existence probabilities are below a threshold T pru are pruned, i.e., removed from the state space.

IV. NEBP-BASED MULTI-OBJECT TRACKING
To further improve the performance of BP-based MOT, we augment the factor graph in Fig. 1a by a GNN. The GNN uses features extracted from previous estimates, measurements, and raw sensor information as an input. Since we limit the following discussion to a single time frame, we will omit the time index k.

A. Feature Extraction
First, we discuss how features are learned from raw sensor data for legacy POs and measurements. We consider motion and shape features. The motion features for legacy PO i and measurement j are computed as h ai,motion = g motion,1 (x − i ,r − i ) and h bj ,motion = g motion,2 (z j ), respectively. Here, g motion,1 (·) as well as g motion,2 (·) are neural networks. In addition,x − i and r − i are the approximate MMSE state estimate and existence probability of legacy PO i at the previous time frame. Similarly, the shape features, denoted by h ai,shape and h bj ,shape , are extracted from raw sensor data Z − and Z at previous and current time, respectively, i.e., h ai,shape = g shape,1 (Z − ,x − i ) and h bj ,shape = g shape,2 (Z, z j ). Here, g shape,1 (·) as well as g shape,2 (·) are again neural networks. We will discuss one particular instance of shape feature extraction in Sec. V-A.

B. The Proposed Message Passing Algorithm
For neural enhanced DA, we introduce a GNN that matches the topology of the DA section of the factor graph in Fig. 1a. The resulting GNN is shown in Fig. 1b. In addition to the output of the detector, the GNN also uses raw sensor information as an input. The goal is to use this additional information to reject false alarm measurements and obtain improved DA probabilities by enhancing BP messages with the output of the GNN. NEBP for MOT consists of the following steps: 1) Conventional BP: First, conventional BP-based MOT is run until convergence. This results in the BP messages φ ai = [φ ai (0) · · · φ ai (J)] T ∈ R J+1 , φ bj = [φ bj (0) · · · φ bj (I)] T ∈ R I+1 , φ Ψi,j →bj ∈ R, and φ Ψi,j →ai ∈ R (cf. [25, Sec. IX-A1-IX-A3]).
2) GNN Messages: Next, GNN message passing is executed iteratively. In particular, at iteration l ∈ {1, . . . , L} the following operations are performed: Here, g e (·) is the edge neural network and g n (·) is the node neural network. The edge neural network g e (·) provides messages passed along the edges of the GNN. The node embeddings are initialized as the concatenation of respective motion and shape features, i.e., h bj →ai ∈ R are computed based on the two additional neural networks g r (·) and g a (·). As discussed next, these correction factors provided by the GNN are used to implement false alarm rejection and object shape association, respectively.
Note that φ ai (j), j ∈ {1, . . . , J} represents the likelihood that the legacy PO i is associated to measurement j [25]. Consequently, the ReLU γ i (j) > 0 term in (3) provided by the GNN implements object shape association, i.e., the likelihood that the legacy PO i is associated to the measurement j is increased if the shape features extracted for legacy POs resembles the shape features extracted for measurements.
Next, neural enhanced versionsφ bj of the messages φ bj are obtained by computing and settingφ bj (i) = φ bj (i), i ∈ {1, · · · , I}. We recall that The scalar β j ∈ (0, 1) in (3) and (4) provided by the GNN implements false alarm rejection. In particular, β j < 1 is equal to the local increase of the false alarm distribution given bỹ f fa (z j ) = 1 βj f fa (z j ). This local increase of the false alarm distribution makes it less likely that the measurement z j is associated to a legacy PO and reduces the existence probability of the new PO introduced for the measurement z j .

C. The Loss Function
For supervised learning, it is assumed that ground truth object tracks are available in the training set. Ground truth object tracks consist of a sequence of object positions and object identities (IDs). During the training of the GNN, the parameters of all neural networks are updated through backpropagation, which computes the gradient of the loss function. The loss function has the form L = L r + L a . Here, the two contributions L r and L a establish false alarm rejection and object shape association, respectively.
False alarm rejection, introduces the binary cross-entropy loss [43,Chapter 4.3] where β gt j ∈ {0, 1} is the pseudo ground truth label for each measurement and ǫ ∈ R + is a tuning parameter. β gt j is 1 if the distance between the measurement and any ground truth position is not larger than T dist and 0 otherwise.
The tuning parameter ǫ ∈ R + is motivated as follows. Since missing an object is typically more severe than producing a false alarm, object detectors often output many detections and produce more false alarm measurements than true measurements. The tuning parameter ǫ ∈ R + addresses this imbalance problem which is well studied in the context of learning-based binary classification [44].
Sinceφ ai (j) in (3) represents the likelihood that the legacy PO i is associated to the measurement j, ideally ReLU γ i (j) is large if PO i is associated to the measurement j, and is equal to zero if they are not associated. Thus, object shape association introduces the following binary cross-entropy loss where σ(x) = 1/(1 + e −x ) is the sigmoid function and γ gt i = [γ gt i (1) · · · γ gt i (J)] T ∈ {0, 1} J is the pseudo ground truth association vector of legacy PO i ∈ {1, . . . , I}. In each pseudo ground truth association vector γ gt i , at most one element is equal to one and all the other elements are equal to zero.
Note that in (6), we do not apply the ReLU to the γ i (j), since this would result in the gradients ∂L a /∂γ i (j) to be zero for negative values of γ i (j). It was observed that performing backpropagation by also making use of the gradients related to the negative values of γ i (j), leads to a more efficient training of the GNN. At each time frame, pseudo ground truth association vectors are constructed from measurements and ground truth object tracks based on the following rules: • Get Measurement IDs: Compute the Euclidean distance between all ground truth positions and measurements and run the Hungarian algorithm [1] to find the best association between ground truth positions and measurements. All measurements that have been associated with a ground truth position and have a distance to that ground truth position that is smaller than T dist inherit the ID of the ground truth position. All other measurements do not have an ID.
• Update Legacy PO IDs: Legacy POs inherit the ID from the previous time frame. If a legacy PO with ID has a distance not larger than T dist to a ground truth position with the same ID, it keeps its ID. The for a legacy PO i ∈ {1, . . . , I} that has the same ID as measurement j ∈ {1, . . . , J}, the entry γ gt i (j) is set to one. All other entries γ gt i (j), i ∈ {1, . . . , I}, j ∈ {1, . . . , J} are set to zero.
• Introduce New PO IDs: For any measurement j ∈ {1, . . . , J} with an ID that does not share its ID with a legacy object, the corresponding new PO inherits the ground truth ID from the measurement. All other new POs do not have an ID.
V. EXPERIMENTAL RESULTS We present results in an urban autonomous driving scenario to validate our method. In particular, we use data provided by a LiDAR sensor mounted on the roof of an autonomous vehicle. This data is part of the nuScenes dataset [35].

A. System Model and Implementation Details
The nuScenes dataset consists of 1000 autonomous driving scenes and seven object classes. We use the official split of the dataset, where there are 700 scenes for training, 150 for validation, and 150 for testing. Each scene has a length of roughly 20 seconds and contains keyframes (frames with ground truth object annotations) sampled at 2Hz. Object detections extracted by the CenterPoint [7] detector are used as measurements, which are then preprocessed using nonmaximum suppression (NMS) [45]. Each measurement has a class index and the proposed MOT method is performed for each class individually.
We define the states of POs as x k,n ∈ R 4 which include their 2D position and 2D velocity. The measurements z k,j ∈ R 5 consist of the 2D position and velocity obtained as well as a score 0 < s k,j ≤ 1 from the object detector. The dynamics of objects are modeled by a constantvelocity model [46]. The region of interest (ROI) is given by [x e − 54, x e + 54] × [y e − 54, y e + 54], where (x e , y e ) is the 2D position of the autonomous vehicle. The prior PDF of false alarms f fa (·) and newly detected objects f n (·) are uniform over the ROI. All other parameters used in the system model are estimated from the training data. The thresholds for object declaration was set to T dec = 0.5 for legacy POs and to a class dependent value for new POs. The pruning threshold was set to T pru = 10 −3 .
The neural networks g e (·), g n (·), g a (·), g motion (·) g motion,1 (·) = g motion,2 (·) are multi-layer perceptrons (MLPs) with a single hidden layer and leaky ReLU activation function. Furthermore, g r (·) is a single-hidden-layer MLP with sigmoid activation at the output layer. Finally, g shape (·) g shape,1 (·) = g shape,2 (·) consists of two convolutional layers followed by a single-hidden-layer MLP. At each time frame, we use the  output Z of VoxelNet [4] to extract shape features as discussed in Section IV-A. The used VoxelNet has been pre-trained by the CenterPoint method [7]. Its parameters remain unchanged during the training of the proposed NEBP method. NEBP training is performed by employing the Adam optimizer [47]. The number of GNN iteration is L = 3. The batch size was set to 1, the learning rate to 10 −4 , and the number of training epochs to 8. The tuning parameter ǫ in (5) was set to 0.1 and the threshold T dist for the pseudo ground truth extraction discussed in Section IV-C was set to 2 meters.

B. Performance Evaluation
We use the widely used CLEAR metrics [48] that include the number of false positives (FP), identity switches (IDS) and fragments (Frag). In addition, we also consider the average multi-object tracking accuracy (AMOTA) metric proposed in [15]. Note that the AMOTA is also the primary metric used for the nuScenes tracking challenge [35].
Evaluation of the AMOTA requires a score for each estimated object. It was observed that a high AMOTA performance is obtained by calculating the estimated object score as a combination of existence probability and measurement score. In particular, for legacy PO i the estimated object score is calculated as wherep ai (j) ∝ φ ai (j)κ i (j) are approximate marginal association probabilities [25]. Finally, for new PO j the estimated object score is given by s j =p(r j = 1) + s j .
For a fair comparison, we use state-of-the-art reference methods that all rely on the CenterPoint detector [7]. In particular, BP refers to the traditional BP-based MOT method [25] that uses object detections provided by the CenterPoint detector as measurements. Furthermore, the tracking method proposed in [7] uses a heuristic to create tracks and a greedy matching algorithm based on the Euclidean distance to associate CenterPoint object detections to tracks. Chiu et al. [17] follows a similar strategy but makes use of a hybrid distance that combines the Mahalanobis distance and the so-called deep feature distance. Finally, the method introduced by Zaech et al. [18] utilizes a network flow formulation and transforms the DA problem into a classification problem.
In Table I, it can be seen that the proposed NEBP approach outperforms all reference methods in terms of AMOTA performance. Furthermore, it can be observed, that BP and NEBP achieve a much lower IDS and Frag metric compared to the reference methods. This is because both BP and NEBP make use of a statistical model to determine the initialization and termination of tracks [25] which is more robust compared to the heuristic track management performed by other reference methods. The improved AMOTA performance of NEBP over BP comes at the cost of a slightly increased IDS and Frag.
TABLE II shows the AMOTA performance as well as number of FP for the bicycle and motorcycle class. To ensure a fair comparison, all the FP values are evaluated for the same percentage of true positives referred to as "recall". In particular, for each class, the recall that leads to the largest multi-object tracking accuracy [48] for NEBP was used.  For the considered two classes, NEBP yields the largest improvement in terms of AMOTA performance over BP. Compared to BP, the proposed NEBP method also has a reduced number of FP. In conclusion, false alarm rejection and object shape association introduced by the proposed NEBP method can make effective use of features learned from raw sensor data and substantially improve MOT performance.

VI. FINAL REMARKS
In this paper, we present a NEBP method for MOT that enhances probabilistic data association by features learned from raw sensor data. A GNN is introduced that matches the topology of the factor graph for model-based data association. In addition to the preprocessed measurements employed by BP, the GNN also makes use of object features learned from raw sensor data. For false alarm rejection, the GNN identifies which measurements are likely false alarms. For object shape association, the GNN computes improved association probabilities. The proposed method can improve the object declaration and state estimation performance of BP while preserving its low computational complexity. Performance evaluation based on the nuScenes autonomous driving dataset demonstrated state-of-the-art object tracking performance.