# An Efficient Implementation of Track-Oriented Multiple Hypothesis Tracker Using Graphical Model Approaches

Authors: Jinping Sun; Qing Li; Xuwang Zhang; Wei Sun
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

The multiple hypothesis tracker (MHT) is currently the preferred method for addressing data association problem in multitarget tracking (MTT) application. MHT seeks the most likely global hypothesis by enumerating all possible associations over time, which is equal to calculating maximum a posteriori (MAP) estimate over the report data. Despite being a well-studied method, MHT remains challenging mostly because of the computational complexity of data association. In this paper, we describe an efficient method for solving the data association problem using graphical model approaches. The proposed method uses the graph representation to model the global hypothesis formation and subsequently applies an efficient message passing algorithm to obtain the MAP solution. Specifically, the graph representation of data association problem is formulated as a maximum weight independent set problem (MWISP), which translates the best global hypothesis formation into finding the maximum weight independent set on the graph. Then, a max-product belief propagation (MPBP) inference algorithm is applied to seek the most likely global hypotheses with the purpose of avoiding a brute force hypothesis enumeration procedure. The simulation results show that the proposed MPBP-MHT method can achieve better tracking performance than other algorithms in challenging tracking situations.


---

## Body

## 1. Introduction

Multitarget tracking (MTT) is a crucial component for surveillance systems which aimed to obtain the sequential estimation of the number of targets and their states (positions, velocities, etc.). The main task of MTT is to partition the received observations into tracks that correspond to correct targets, and this procedure is also known as the data association. The usual constraint is that each target at each scan gives rise to at most one observation. However, it is not known which observation originates from which target, and there are as well false observations that are not originated by targets. To address the data association problem, several methods, including global nearest neighbor (GNN), joint probabilistic data association (JPDA), and multiple hypothesis tracking (MHT), were proposed. Among these methods, MHT is widely regarded as the most prominent method for structuring the data association problem in MTT systems. MHT is a deferred decision logic method that allows a firm decision to be postponed until more report data are available. Basically, there are two types of MHT framework. The first, known as hypothesis-oriented MHT (HOMHT), is proposed by Reid in [1]. HOMHT directly maintains and propagates global hypotheses, and the complexity of treating global hypotheses makes it difficult to be implemented. The alternative framework, which is more favored currently, is track-oriented MHT (TOMHT). Rather than maintaining global hypotheses formed previously, TOMHT reforms global hypotheses using newly updated tracks on each scan and typically maintains a set of potential tracks using the track tree structure [2].Even though TOMHT appears to be the most-preferred tracking algorithm, it inherently suffers from the combinational explosion that exists in the hypothesis formation step. To improve the efficiency of generating hypotheses, a multidimensional assignment (MDA) method was proposed and the computational feasibility has been greatly enhanced by the use of Lagrangian relaxation [3].In addition, graphical models, which have received a lot of attention in recent years, were also introduced to tackle the data association problem. Graphical models are powerful tools to model the joint probability distribution of multiple random variables, in which message passing algorithms can be used to solve the inference problem efficiently. Several graph approaches that emerge in the tracking literature were reviewed in [4]. A factor graph aided multiple hypothesis tracking approach was proposed to solve the association probability using the sum-product algorithm [5]. A graph-theoretic interpretation was introduced in [6] and specifically, the data association problem was formulated as the maximum weight independent set problem (MWISP), which is a well-studied combinatorial optimization problem and known to be NP-hard. To construct suboptimal solutions for the MWISP, a greedy randomized adaptive search procedure (GRASP) was developed and applied to MHT framework [7]. Despite the fact that GRASP based approach is not likely to find the optimal solution, however, this approach provides a compact and efficient representation of multiple hypotheses in MHT framework.In this paper, we utilize an efficient TOMHT implementation, referred to as MPBP-MHT, to solve the data association problem by exploiting the graphical models and message passing algorithms. In our approach, hypothesis generation can be represented using a graph structure with nodes representing tracks and edges defining compatibility restrictions, and in this way finding the best hypothesis is transformed into seeking the maximum weight independent set on the graph, which is a maximum a posteriori (MAP) problem. Because finding the maximum weighted independent set is known to be NP-hard for an arbitrary graph and the nature equivalence between MWISP and MAP assignment, as a result, approximate algorithms are introduced to efficiently address this problem. Max-product belief propagation (MPBP), as an efficient inference algorithm, is generally used for finding the MAP assignment in a joint probability distribution represented by a graphical model [8]. Therefore, this paper combines the MWISP formulation and the MPBP inference algorithm with the purpose of generating the best hypothesis efficiently. The effectiveness of the proposed approach is tested over challenging tracking cases and a comparison with GRASP-MHT algorithm is made to demonstrate the efficiency of MPBP-MHT approach.The rest of this paper is organized as follows: Section2 briefly reviews the standard TOMHT framework and several techniques to maintain track hypotheses. Section 3 gives the definition of MWISP and also basic concepts of the graphical models. In particular, we introduce a case of graphical models named Markov Random Field (MRF). Additionally, we also review an efficient inference algorithm called max-product belief propagation, which is used in graphical models for calculating MAP assignment. Section 4 outlines the MWISP formulation of data association problem and presents in detail the MPBP algorithm applied in the proposed MPBP-MHT method. Section 5 shows the empirical results of several algorithms about tracking performance over challenging situations, followed by concluding comments in Section 6.


## 2. Track-Oriented Multiple Hypothesis Tracker

The proposed method is based on the TOMHT framework, which takes advantage of the track tree structure to manage and maintain hypotheses sets. Figure1 shows the basic elements of a typical TOMHT system. Hypotheses are reformed from tracks at each scan and the tracks that survive pruning are predicted to the next scan where the process continues. An overview of the core components of TOMHT framework given in Sections 2.1 and 2.2 provides some efficient strategies for limiting the number of hypotheses.Figure 1
Basic elements of TOMHT algorithm.


### 2.1. Background

In the TOMHT approach, tracks are updated using all newly received observations within the gate. Each track is defined by a sequence of observations with the restriction that at most one observation is included at each scan. Letzikkik=1mk denote the set of observations received at scan k, where mk is the total number of observations and zikk represents the ikth observation in scan k. Then the jkth track is denoted as Tjkk=zik1,…,zikk. For instance, in Figure 2, track 2 can be represented as z1k-2,z3k-1,z2k. Dummy observation in scan k is denoted as z0k with the purpose of introducing tracks with missed detection. Tracks are defined as compatible if they do not share common observations; that is, one observation can be associated with at most one track. For the convenience of clustering and solving the MWISP, an incompatibility list (ICL) for each track is maintained, which contains all existing tracks with which a given track is incompatible.Figure 2
Formation of hypotheses from tracks in track trees.TOMHT uses a track tree structure to store all possible track hypotheses. A track tree represents all possible track hypotheses of the corresponding target. A family of tracks is composed of multiple tracks corresponding to the same target, i.e., a set of tracks all emanating from a single root observation. Figure2 shows the growth of track trees with scan time and the process of global hypotheses generation. When new scans arrive, the track trees are extended to include new observations. As the track tree is formed by a set of tracks that share a common root node, all these tracks are incompatible. A global hypothesis is the subset of all possible tracks that are compatible. As a result, a global hypothesis can only include no more than one track from each track tree (see, e.g., Figure 2).In order to evaluate a certain track hypothesis, a track score, which is used to describe the validity of a track, is associated with each track. A track score is generally defined as the log likelihood ratio of the probability of the track being generated from true target returns to the probability of all observations being false alarms [9]. A recursive formula for the track score L(k) at scan k is(1)Lk=Lk-1+ΔLk,where the track score increment ΔL(k) is (2)ΔLk=ln⁡1-PDif  no  update  on  scankΔLukif  track  update  on  scank.As the detection probability PD is less than unity, it is obvious that ln⁡1-PD<0. Therefore, the track score suffers from a decrease when the track is not updated. When an observation is used to update the track on scan k, however, the track score increases by the amount ΔLuk. The magnitude of the increment ΔLu is the sum of kinematic and signal-related terms [10]. Assuming the tracker to be a Kalman filter with Gaussian innovations, the explicit form of the increment ΔLu, in the case where the only signal-related datum is that a detection or a miss occurred, is given by (3)ΔLu=ln⁡PD2πM/2λfaS-d22,where the time index k has been dropped and the following notations are used:M: observation dimensionλfa: false target densityS: observation residual covariance matrixd2: normalized statistical distance for the observation defined in terms of observation residual vector z~ and covariance matrix S.(4)d2=z~TS-1z~.Having defined a score for each track, one can determine the score of a global hypothesis and prunes a track once its track score falls below a given threshold.


### 2.2. Efficient Mechanisms for Implementation

Due to the fact that the global hypothesis is made by a combination of multiple tracks, the TOMHT may suffer from a heavy computational burden as there is a potential combination explosion in the number of hypotheses with the growth of track trees. As a result, several mechanisms are needed to suppress the number of hypotheses in real-time systems.One crucial technique for limiting the growth of track trees is to apply then-scan pruning strategy. Upon finding the best global hypothesis, then-scan pruning strategy prunes all tracks belonging to a track tree with depth more than n and tracks that fail to share a common root observation with any track included in the best global hypothesis. Another important strategy to reduce the complexity is clustering, which successfully divides a large problem into independent small problems. A cluster is composed of several track trees that share one or more common observations. By clustering, the global hypothesis formulation step can be realized in individual clusters, which in turn greatly reduce the size of track hypotheses and computing complexity. Other standard techniques used in TOMHT framework, including gating, Shiryayev sequential probability ratio test (SSPRT), hypothesis pruning, and track merging, could be referred to [11, 12].


## 2.1. Background

In the TOMHT approach, tracks are updated using all newly received observations within the gate. Each track is defined by a sequence of observations with the restriction that at most one observation is included at each scan. Letzikkik=1mk denote the set of observations received at scan k, where mk is the total number of observations and zikk represents the ikth observation in scan k. Then the jkth track is denoted as Tjkk=zik1,…,zikk. For instance, in Figure 2, track 2 can be represented as z1k-2,z3k-1,z2k. Dummy observation in scan k is denoted as z0k with the purpose of introducing tracks with missed detection. Tracks are defined as compatible if they do not share common observations; that is, one observation can be associated with at most one track. For the convenience of clustering and solving the MWISP, an incompatibility list (ICL) for each track is maintained, which contains all existing tracks with which a given track is incompatible.Figure 2
Formation of hypotheses from tracks in track trees.TOMHT uses a track tree structure to store all possible track hypotheses. A track tree represents all possible track hypotheses of the corresponding target. A family of tracks is composed of multiple tracks corresponding to the same target, i.e., a set of tracks all emanating from a single root observation. Figure2 shows the growth of track trees with scan time and the process of global hypotheses generation. When new scans arrive, the track trees are extended to include new observations. As the track tree is formed by a set of tracks that share a common root node, all these tracks are incompatible. A global hypothesis is the subset of all possible tracks that are compatible. As a result, a global hypothesis can only include no more than one track from each track tree (see, e.g., Figure 2).In order to evaluate a certain track hypothesis, a track score, which is used to describe the validity of a track, is associated with each track. A track score is generally defined as the log likelihood ratio of the probability of the track being generated from true target returns to the probability of all observations being false alarms [9]. A recursive formula for the track score L(k) at scan k is(1)Lk=Lk-1+ΔLk,where the track score increment ΔL(k) is (2)ΔLk=ln⁡1-PDif  no  update  on  scankΔLukif  track  update  on  scank.As the detection probability PD is less than unity, it is obvious that ln⁡1-PD<0. Therefore, the track score suffers from a decrease when the track is not updated. When an observation is used to update the track on scan k, however, the track score increases by the amount ΔLuk. The magnitude of the increment ΔLu is the sum of kinematic and signal-related terms [10]. Assuming the tracker to be a Kalman filter with Gaussian innovations, the explicit form of the increment ΔLu, in the case where the only signal-related datum is that a detection or a miss occurred, is given by (3)ΔLu=ln⁡PD2πM/2λfaS-d22,where the time index k has been dropped and the following notations are used:M: observation dimensionλfa: false target densityS: observation residual covariance matrixd2: normalized statistical distance for the observation defined in terms of observation residual vector z~ and covariance matrix S.(4)d2=z~TS-1z~.Having defined a score for each track, one can determine the score of a global hypothesis and prunes a track once its track score falls below a given threshold.


## 2.2. Efficient Mechanisms for Implementation

Due to the fact that the global hypothesis is made by a combination of multiple tracks, the TOMHT may suffer from a heavy computational burden as there is a potential combination explosion in the number of hypotheses with the growth of track trees. As a result, several mechanisms are needed to suppress the number of hypotheses in real-time systems.One crucial technique for limiting the growth of track trees is to apply then-scan pruning strategy. Upon finding the best global hypothesis, then-scan pruning strategy prunes all tracks belonging to a track tree with depth more than n and tracks that fail to share a common root observation with any track included in the best global hypothesis. Another important strategy to reduce the complexity is clustering, which successfully divides a large problem into independent small problems. A cluster is composed of several track trees that share one or more common observations. By clustering, the global hypothesis formulation step can be realized in individual clusters, which in turn greatly reduce the size of track hypotheses and computing complexity. Other standard techniques used in TOMHT framework, including gating, Shiryayev sequential probability ratio test (SSPRT), hypothesis pruning, and track merging, could be referred to [11, 12].


## 3. Mathematical Preliminaries

Graphical models provide a common structure on which generic inference algorithms can operate. In this section, firstly we give a brief review of MWISP, which will be used to construct the graphical model in the proposed method. Then we give some basic concepts of graphical models. Particularly, we are interested in a special graphical model, namely, the Markov Random Field (MRF), as it is the prototype on which we develop our graphical model for tracking applications. Furthermore, we review the standard message passing algorithm for inference problems in graphical models. Specifically, we introduce in detail the max-product belief propagation (MPBP) inference which can be used in the loopy graph situations.


### 3.1. Maximum Weight Independent Set Problem

MWISP is a well-studied combinatorial optimization problem. LetG=V,E be an undirected graph with a vertex set V and an edge set E. The edge i,j is included in the graph only if two nodes i and j are connected to each other. The independent set on the graph is defined as a subset of V that has no edge between any two nodes. A binary vector x, the length of which equals the cardinality of V, that is, V, is defined to represent an independent set of the graph G. xi takes value 1 if node i belongs to the independent set and 0 otherwise. Define wi as the weight on node i; then MWISP is to find an independent set of V that the sum of corresponding weights is largest; that is, (5)maxx∑i∈Vwixi,s.t.xi+xj≤1,∀i,j∈E.


### 3.2. Graphical Models

The core component of graphical models is the representation of a probability distribution using a graph as a data structure. A graphical model is denoted as a graphG=V,E with a probability distribution px, in which nodes represent the variables x=xi∣i∈V, and edges represent the probabilistic interaction between the neighboring variables. Basically there are two types of graphical representation of distributions. One is the Bayesian network which utilizes a directed graph; and the other is the Markov Random Field (MRF) using an undirected graph. As the graph model used in the MPBP-MHT approach is the undirected graph, in this paper we focus on the MRF. A graph is called an MRF if every variable xi is independent of nonneighboring variables in the graph given the value of its neighbors. For instance, in Figure 3, the lack of an edge between nodes x1 and x3 means they are conditionally independent under a given x2.Figure 3
A graph fragment showing the updating rule of the message sent from node 2 to node 1.A clique of a graph is a subset of this graph in which all the nodes are fully connected. A pairwise Markov network is an undirected graphical model that only takes the edges as cliques, which means that the potentials are over single variables or pairs of variables. More precisely, letx denote the values of all unobserved variables in the graph and we assume that each unobserved node xi is associated with an observation zi. Then the probability distribution px∣z of a pairwise MRF is expressed in terms of the product of potentials on edges and nodes (6)px∣z=1Z∏i,jψijxi,xj∏iϕixi,zi,where Z is the normalization constant, ϕixi,zi is the node potential at the node i, and ψijxi,xj is the edge potential between the nodes i and j.


### 3.3. Belief Propagation

The task of inference is to determine the underlying state of the random variables in the graphical model. A key problem in designing algorithms for inference is finding an efficient way to reason about the large number of possible assignments to the variables in the model. One fundamental inference problem is to find the most likely configuration of the probability distribution, which is known as the MAP assignment. Many NP-hard combinatorial optimization problems (e.g., MWISP) can be posed as finding the MAP inference problem in pairwise Markov random fields with binary variables. There are many ways to solve the MAP inference problem. The belief propagation (BP) algorithm, specifically the max-product belief propagation (MPBP) algorithm, is an efficient way to solve MAP inference problems in graphical models.MPBP is an approximate inference algorithm that is simple to code and scales very well with problem size. By taking advantage of the statistical independence in the graph structure, MPBP algorithm can break the global inference problem into localized operations, which is generally faster than manipulating the joint distribution explicitly. The MPBP algorithm operates by a message passing mechanism which is implemented by iteratively passing messages along edges of the graph that summarize each variable’s beliefs. After receiving messages from its neighbors, the node updates its belief and propagates it to the rest of the graph. An assignment can then be decided from the beliefs by choosing the most likely state according to each node’s belief. The MPBP algorithm makes direct use of the graph structure in constructing and passing messages, making it simple to implement and run quickly. As a result, the review will primarily focus on the MPBP algorithm, which approximates the MAP inference problem, as it will be used in the proposed approach.The update equations for MPBP algorithm can be derived from the probability distribution. The messages are updated as follows: each node sends messages to its neighbors and receives messages from them and the messages are updated according to the received messages from neighbors at the previous iteration(7)mi→jxj=maxxi⁡ψijxi,xjϕixi,zi∏xk∈Nxi∖xjmk→ixi,where mi→jxj represents the message passed from node xi to node xj and Nxi is the set of all the neighbors of node xi.At any iteration, once a node has received all messages from its neighbor nodes, the belief at nodexi can be computed by(8)bixi=ϕixi,zi∏xk∈Nximk→ixi,and the output of (8) should be normalized. Initially, the messages are initialized with constant functions. As the observed nodes are localized and do not receive messages, generally we denote ϕixi,zi as ϕixi for notation simplicity.


## 3.1. Maximum Weight Independent Set Problem

MWISP is a well-studied combinatorial optimization problem. LetG=V,E be an undirected graph with a vertex set V and an edge set E. The edge i,j is included in the graph only if two nodes i and j are connected to each other. The independent set on the graph is defined as a subset of V that has no edge between any two nodes. A binary vector x, the length of which equals the cardinality of V, that is, V, is defined to represent an independent set of the graph G. xi takes value 1 if node i belongs to the independent set and 0 otherwise. Define wi as the weight on node i; then MWISP is to find an independent set of V that the sum of corresponding weights is largest; that is, (5)maxx∑i∈Vwixi,s.t.xi+xj≤1,∀i,j∈E.


## 3.2. Graphical Models

The core component of graphical models is the representation of a probability distribution using a graph as a data structure. A graphical model is denoted as a graphG=V,E with a probability distribution px, in which nodes represent the variables x=xi∣i∈V, and edges represent the probabilistic interaction between the neighboring variables. Basically there are two types of graphical representation of distributions. One is the Bayesian network which utilizes a directed graph; and the other is the Markov Random Field (MRF) using an undirected graph. As the graph model used in the MPBP-MHT approach is the undirected graph, in this paper we focus on the MRF. A graph is called an MRF if every variable xi is independent of nonneighboring variables in the graph given the value of its neighbors. For instance, in Figure 3, the lack of an edge between nodes x1 and x3 means they are conditionally independent under a given x2.Figure 3
A graph fragment showing the updating rule of the message sent from node 2 to node 1.A clique of a graph is a subset of this graph in which all the nodes are fully connected. A pairwise Markov network is an undirected graphical model that only takes the edges as cliques, which means that the potentials are over single variables or pairs of variables. More precisely, letx denote the values of all unobserved variables in the graph and we assume that each unobserved node xi is associated with an observation zi. Then the probability distribution px∣z of a pairwise MRF is expressed in terms of the product of potentials on edges and nodes (6)px∣z=1Z∏i,jψijxi,xj∏iϕixi,zi,where Z is the normalization constant, ϕixi,zi is the node potential at the node i, and ψijxi,xj is the edge potential between the nodes i and j.


## 3.3. Belief Propagation

The task of inference is to determine the underlying state of the random variables in the graphical model. A key problem in designing algorithms for inference is finding an efficient way to reason about the large number of possible assignments to the variables in the model. One fundamental inference problem is to find the most likely configuration of the probability distribution, which is known as the MAP assignment. Many NP-hard combinatorial optimization problems (e.g., MWISP) can be posed as finding the MAP inference problem in pairwise Markov random fields with binary variables. There are many ways to solve the MAP inference problem. The belief propagation (BP) algorithm, specifically the max-product belief propagation (MPBP) algorithm, is an efficient way to solve MAP inference problems in graphical models.MPBP is an approximate inference algorithm that is simple to code and scales very well with problem size. By taking advantage of the statistical independence in the graph structure, MPBP algorithm can break the global inference problem into localized operations, which is generally faster than manipulating the joint distribution explicitly. The MPBP algorithm operates by a message passing mechanism which is implemented by iteratively passing messages along edges of the graph that summarize each variable’s beliefs. After receiving messages from its neighbors, the node updates its belief and propagates it to the rest of the graph. An assignment can then be decided from the beliefs by choosing the most likely state according to each node’s belief. The MPBP algorithm makes direct use of the graph structure in constructing and passing messages, making it simple to implement and run quickly. As a result, the review will primarily focus on the MPBP algorithm, which approximates the MAP inference problem, as it will be used in the proposed approach.The update equations for MPBP algorithm can be derived from the probability distribution. The messages are updated as follows: each node sends messages to its neighbors and receives messages from them and the messages are updated according to the received messages from neighbors at the previous iteration(7)mi→jxj=maxxi⁡ψijxi,xjϕixi,zi∏xk∈Nxi∖xjmk→ixi,where mi→jxj represents the message passed from node xi to node xj and Nxi is the set of all the neighbors of node xi.At any iteration, once a node has received all messages from its neighbor nodes, the belief at nodexi can be computed by(8)bixi=ϕixi,zi∏xk∈Nximk→ixi,and the output of (8) should be normalized. Initially, the messages are initialized with constant functions. As the observed nodes are localized and do not receive messages, generally we denote ϕixi,zi as ϕixi for notation simplicity.


## 4. Efficient Multitarget Tracking Using Graphical Models

The main reason for constructing graphical model representation for data association is to utilize efficient inference algorithms, specifically, the max-product belief propagation algorithm, to seek the best global hypothesis. In this section, we first present the approach we take to construct graphical models for data association problem in MTT applications. Then we describe the detailed formulation of the proposed MPBP-MHT method. Specific process of defining potential functions and running message passing algorithms is also given.


### 4.1. Graphical Model Representation

TOMHT seeks and generates the best global hypothesis by enumerating all possible associations over time which, as we can see, is equal to seeking maximum a posteriori (MAP) assignment over the report data. LetT and z denote the set of all tracks and observations up to the present scan, respectively. A binary vector h, the length of which equals the cardinality of T, that is, T, is used to denote the global hypothesis where hi=1 if the ith track is included in the global hypothesis and hi=0 otherwise. In this way, the process of finding the best hypothesis h∗ is equivalent to computing the MAP solution of the posterior probability distribution ph∣z(9)h∗=argmaxh⁡ph∣z.The specific logarithmic formula of ph∣z is given by Kurien in [13](10)log⁡ph∣z=C+∑i=1Thisi,where C is a constant and si is the track score of the ith track.Therefore, the process of computing the MAP solution ofph∣z can be formulated as an integer linear program which is subject to the restriction that no common observation is shared by tracks included in the same global hypothesis(11)h∗=argmaxh⁡h·s=argmaxh⁡∑i=1Thisi.Due to the equivalence of the integer linear program problem in (11) and MWISP described in (5), the graph representation for data association can be constructed by utilizing the graphical model in MWISP so that efficient inference algorithms can be used to calculate the MAP assignment in MTT application.In individual clusters, we construct the graphGk=Vk,Ek at scan k. Every node represents a possible track and is associated with a hypothesis variable hi. The variable hi=1 if the track is included in the global hypothesis and hi=0 corresponds to absence. The weight of a node is defined as the track score and in our approach we only use the tracks that have positive track scores. An edge is added between nodes if the corresponding tracks are incompatible. Therefore, the process of seeking the best global hypothesis can be translated to finding the maximum weight independent set on the graph.Taking the track trees in Figure2 as an example, it is clear that 5 track hypotheses are formulated up to scan k. All tracks that share one or more common observations are connected to each other with edges in the corresponding graph in Figure 4. Assuming the track score of track 1 to track 5 is one to five, respectively (the score is labeled within the cycles), in this case the best global hypothesis with the largest sum of weights consists of tracks 2, 3, and 4.Figure 4
Graphical model for data association problem in Figure2.


### 4.2. MPBP-MHT Algorithm for Data Associations

Once a graphical model is constructed, the specific form of the potential functions and the update equations for the max-product belief propagation algorithm can be calculated. As the joint probability distribution is consistent with a pairwise MRF, it can be factored into a product of potential functions and thus the probability distributionph∣z of hypothesis variable h given an observation set z is(12)ph∣z=1Z∏i,j∈Eψijhi,hj∏iϕihi,where the edge potentials ψijhi,hj between nodes i and j are(13)ψijhi,hj=0ifhi=1,hj=11otherwise.Assume si is the track score of the ith track; then the potential function ϕihi at node i is(14)ϕihi=esiifhi=11otherwise.It is clear that ifh is an independent set, then ph∣z=1/Zexp⁡∑ihisi; otherwise, ph∣z equals zero. If h∗=argmaxh⁡ph∣z, then the MAP assignment corresponds to a maximum weight independent set in the graph. It is clear that finding the MWIS is equivalent to finding the MAP assignment on the corresponding graphical model. Therefore, the max-product belief propagation algorithm can be used as an iterative strategy for finding the MWIS solution on the graph.The main idea of max-product belief propagation is to convert messages between nodes iteratively, which aims to maximize the joint probability by finding the most likely assignment to all of the variables. In each iteration, each node sends messages to its neighbors and the belief can be updated by exploiting the incoming messages at each node. This procedure is repeated until convergence.Definemi→jn=mi→jn0,mi→jn1T as the messages passed from the node i to its neighbor node j in the nth iteration. Initialize the iteration by setting n=0 and mi→j0=mi→j00,mi→j01T, where(15)mi→j0r=exp⁡siifr=01otherwise.For n≥1, in each iteration, the message in a node is updated according to the messages from its neighbors recursively, where the updating rule is (16)mi→jn=maxhi⁡ψijhi,hjϕihi∏k∈Ni∖jmk→in-1.Specifically, by combining (13), (14), and (16), the updating rule can be rewritten as(17)mi→jn0=max⁡∏k∈Ni∖jmk→in-10,exp⁡si∏k∈Ni∖jmk→in-11,mi→jn1=∏k∈Ni∖jmk→in-10.Each node i maintains a belief bin=bin0,bin1, which is computed as follows:(18)bin=ϕihi∏k∈Nimk→in,where in the same way the specific form is (19)bin0=∏k∈Nimk→in0,bin1=exp⁡si∏k∈Nimk→in1.At the end of the nth iteration, the maximum weight independent set hn is estimated as(20)hin=1bin1>bin0.The track hypothesis will be included in the MWIS if its belief satisfiesbin1>bin0. The iteration process will repeat until hn converges or the number of iterations exceeds a given threshold.The specific pseudocode of the MPBP-MHT algorithm is shown in Algorithm1. The hypothesis generation step is executed in independent cluster. Input parameters include the current graph G and scan index k is omitted for simplicity.Algorithm 1:MPBP-MHT algorithm. Note. For computational stability, it is often recommended that messages should be normalized in each iteration.
Input: graph G, including a cluster of family, track score and track ICL.
Output: best global hypothesis
(1)initialization: set mi→j0=mi→j00,mi→j01T with (15).
(2)iteration: At iteration n for all nodes i∈V
(a) Calculate new message mi→jn which is sent by the node i to all its neighbors with (17).
(b) Calculate the belief at each node with (19).
(c) Decision: for each node i∈V, compare bin1 and bin0; if bin1>bin0, set hin=1.
(3)ifhn converges, finish the iteration and output h∗; else set n=n+1 and go to step (2)In the practical tracking application, the graphical models corresponding to the track trees can be singly connected graphs (i.e., there is only one path between any two given nodes and in this case the graph structure resembles a tree) or graphs with cycles. For a tree-structured graph, the max-product belief propagation algorithm is guaranteed to converge in a finite number of iterations and the assignment based on the messages at convergence is guaranteed to give the optimal assignment values corresponding to the MAP solution [14]. As for a graph with cycles, its performance has not been well studied and the algorithm may not converge. Nevertheless, max-product algorithms often show remarkable performances even on graphs with cycles. Recently several good empirical performances have been obtained by running the max-product algorithm on loopy graphs [15–18] and progress has been made to understand the mechanism behind its empirical success. For loopy graph with a single loop, [19] demonstrated that the algorithm converges to the correct marginal or MAP probabilities. For arbitrary graphs, [20] proved that the assignment based on a fixed point is a neighborhood maximum of the posterior probability.


## 4.1. Graphical Model Representation

TOMHT seeks and generates the best global hypothesis by enumerating all possible associations over time which, as we can see, is equal to seeking maximum a posteriori (MAP) assignment over the report data. LetT and z denote the set of all tracks and observations up to the present scan, respectively. A binary vector h, the length of which equals the cardinality of T, that is, T, is used to denote the global hypothesis where hi=1 if the ith track is included in the global hypothesis and hi=0 otherwise. In this way, the process of finding the best hypothesis h∗ is equivalent to computing the MAP solution of the posterior probability distribution ph∣z(9)h∗=argmaxh⁡ph∣z.The specific logarithmic formula of ph∣z is given by Kurien in [13](10)log⁡ph∣z=C+∑i=1Thisi,where C is a constant and si is the track score of the ith track.Therefore, the process of computing the MAP solution ofph∣z can be formulated as an integer linear program which is subject to the restriction that no common observation is shared by tracks included in the same global hypothesis(11)h∗=argmaxh⁡h·s=argmaxh⁡∑i=1Thisi.Due to the equivalence of the integer linear program problem in (11) and MWISP described in (5), the graph representation for data association can be constructed by utilizing the graphical model in MWISP so that efficient inference algorithms can be used to calculate the MAP assignment in MTT application.In individual clusters, we construct the graphGk=Vk,Ek at scan k. Every node represents a possible track and is associated with a hypothesis variable hi. The variable hi=1 if the track is included in the global hypothesis and hi=0 corresponds to absence. The weight of a node is defined as the track score and in our approach we only use the tracks that have positive track scores. An edge is added between nodes if the corresponding tracks are incompatible. Therefore, the process of seeking the best global hypothesis can be translated to finding the maximum weight independent set on the graph.Taking the track trees in Figure2 as an example, it is clear that 5 track hypotheses are formulated up to scan k. All tracks that share one or more common observations are connected to each other with edges in the corresponding graph in Figure 4. Assuming the track score of track 1 to track 5 is one to five, respectively (the score is labeled within the cycles), in this case the best global hypothesis with the largest sum of weights consists of tracks 2, 3, and 4.Figure 4
Graphical model for data association problem in Figure2.


## 4.2. MPBP-MHT Algorithm for Data Associations

Once a graphical model is constructed, the specific form of the potential functions and the update equations for the max-product belief propagation algorithm can be calculated. As the joint probability distribution is consistent with a pairwise MRF, it can be factored into a product of potential functions and thus the probability distributionph∣z of hypothesis variable h given an observation set z is(12)ph∣z=1Z∏i,j∈Eψijhi,hj∏iϕihi,where the edge potentials ψijhi,hj between nodes i and j are(13)ψijhi,hj=0ifhi=1,hj=11otherwise.Assume si is the track score of the ith track; then the potential function ϕihi at node i is(14)ϕihi=esiifhi=11otherwise.It is clear that ifh is an independent set, then ph∣z=1/Zexp⁡∑ihisi; otherwise, ph∣z equals zero. If h∗=argmaxh⁡ph∣z, then the MAP assignment corresponds to a maximum weight independent set in the graph. It is clear that finding the MWIS is equivalent to finding the MAP assignment on the corresponding graphical model. Therefore, the max-product belief propagation algorithm can be used as an iterative strategy for finding the MWIS solution on the graph.The main idea of max-product belief propagation is to convert messages between nodes iteratively, which aims to maximize the joint probability by finding the most likely assignment to all of the variables. In each iteration, each node sends messages to its neighbors and the belief can be updated by exploiting the incoming messages at each node. This procedure is repeated until convergence.Definemi→jn=mi→jn0,mi→jn1T as the messages passed from the node i to its neighbor node j in the nth iteration. Initialize the iteration by setting n=0 and mi→j0=mi→j00,mi→j01T, where(15)mi→j0r=exp⁡siifr=01otherwise.For n≥1, in each iteration, the message in a node is updated according to the messages from its neighbors recursively, where the updating rule is (16)mi→jn=maxhi⁡ψijhi,hjϕihi∏k∈Ni∖jmk→in-1.Specifically, by combining (13), (14), and (16), the updating rule can be rewritten as(17)mi→jn0=max⁡∏k∈Ni∖jmk→in-10,exp⁡si∏k∈Ni∖jmk→in-11,mi→jn1=∏k∈Ni∖jmk→in-10.Each node i maintains a belief bin=bin0,bin1, which is computed as follows:(18)bin=ϕihi∏k∈Nimk→in,where in the same way the specific form is (19)bin0=∏k∈Nimk→in0,bin1=exp⁡si∏k∈Nimk→in1.At the end of the nth iteration, the maximum weight independent set hn is estimated as(20)hin=1bin1>bin0.The track hypothesis will be included in the MWIS if its belief satisfiesbin1>bin0. The iteration process will repeat until hn converges or the number of iterations exceeds a given threshold.The specific pseudocode of the MPBP-MHT algorithm is shown in Algorithm1. The hypothesis generation step is executed in independent cluster. Input parameters include the current graph G and scan index k is omitted for simplicity.Algorithm 1:MPBP-MHT algorithm. Note. For computational stability, it is often recommended that messages should be normalized in each iteration.
Input: graph G, including a cluster of family, track score and track ICL.
Output: best global hypothesis
(1)initialization: set mi→j0=mi→j00,mi→j01T with (15).
(2)iteration: At iteration n for all nodes i∈V
(a) Calculate new message mi→jn which is sent by the node i to all its neighbors with (17).
(b) Calculate the belief at each node with (19).
(c) Decision: for each node i∈V, compare bin1 and bin0; if bin1>bin0, set hin=1.
(3)ifhn converges, finish the iteration and output h∗; else set n=n+1 and go to step (2)In the practical tracking application, the graphical models corresponding to the track trees can be singly connected graphs (i.e., there is only one path between any two given nodes and in this case the graph structure resembles a tree) or graphs with cycles. For a tree-structured graph, the max-product belief propagation algorithm is guaranteed to converge in a finite number of iterations and the assignment based on the messages at convergence is guaranteed to give the optimal assignment values corresponding to the MAP solution [14]. As for a graph with cycles, its performance has not been well studied and the algorithm may not converge. Nevertheless, max-product algorithms often show remarkable performances even on graphs with cycles. Recently several good empirical performances have been obtained by running the max-product algorithm on loopy graphs [15–18] and progress has been made to understand the mechanism behind its empirical success. For loopy graph with a single loop, [19] demonstrated that the algorithm converges to the correct marginal or MAP probabilities. For arbitrary graphs, [20] proved that the assignment based on a fixed point is a neighborhood maximum of the posterior probability.


## 5. Experimental Results

In this section, we conduct an empirical evaluation of the proposed MBPB-MHT algorithm over a challenging situation using simulated data. We present the setup and scenarios under which we operate our experiments. The performance of the proposed approach was evaluated with several performance metrics. To further demonstrate its superiority, comparisons were made with GRASP-MHT algorithm in correlation quality, overall cardinality, and state estimation.


### 5.1. Target Motion and Measurement Models

The acceleration model with a white Gaussian noise is considered and the linear Kalman filter is used in our experiments. Targets move in a 2D surveillance area. The true state of a target at scank is xk=xk,yk,x˙k,y˙kT. xtk and ytk are, respectively, the positions of this target in the X-Y coordinate system, while x˙tk and y˙tk are, respectively, the velocities of this target. The movement of each target is modeled as the following target motion model: (21)xk=Fxk-1+vk,where the state transition matrix F is expressed as (22)F=10T0010T00100001,and the sampling periodT = 2 s. The covariance matrix of the white Gaussian noise vk is (23)Q=T330T2200T330T22T220T00T220Tq,where the process noise intensity q=100m2/s3. The measurement model is given as (24)zk=Hxk+wk,where(25)H=10000100,and the zero-mean Gaussian measurement noise wk has a covariance matrix R=diagσx2,σy2, where σx2=σy2=50m2.


### 5.2. Simulation Scenarios

We employ two scenarios for verifying the performance of the proposed method. All the estimation results were based on 100 Monte Carlo runs and the depth of TOMHT equals 5. The tracking performance is then compared with the GRASP-MHT algorithm in the same scenario, respectively. In the GRASP-MHT algorithm, the maximum number of tuples is set to 30 and the number of randomized iterations for each tuple is set to 3. All other parameters were shared with MPBP-MHT algorithm.


#### 5.2.1. Scenario A

In the scenario A, the number of scans is set to 80. At the beginning, two closely spaced targets are moving parallelly with a separation of 30 m and a speed of 30 m/s over a period of 30 s. In the later 50 s, there is an intersect at 32 s and after that two targets are moving separately. Figure5(a) shows the real tracks of the two targets, and Figure 5(b) shows the real observations with clutters. The observation errors of azimuth and range are 0.002 rad and 20 m, respectively. The standard deviation of the process noise is 10 m. The target detection probability is 0.9 and the false alarm density is set as 10-8/m2.Figure 5
Target trajectories and the real observations with clutters in scenario A. (a) Target trajectories; (b) real observations.
(a)
(b)


#### 5.2.2. Scenario B

The scenario B consists of ten closely spaced targets and the targets are moving in formation with a separation of 900 m and a speed of 300 m/s over a period of 120 s. The start and stop positions are marked with∘ and ×, respectively. Each target performs three turns with an acceleration of 3g at 22 s, 42 s, and 72 s, where g is the gravitational acceleration and each turn lasts for 8 s with a course change of 45ο. The target detection probability is set as 0.9 and the false alarm density is 10-8/m2. Figure 6(a) shows the true target trajectories in the scenario B used for performance evaluation and Figure 6(b) provides the true observations with clutter. The number of clutter is Poisson distributed and their locations in the observation space are uniformly distributed.Figure 6
Target trajectories and the real observations with clutters in scenario B. (a) Target trajectories; (b) real observations.
(a)
(b)


### 5.3. Results and Evaluation

In this part, we provide the empirical results in the simulation. In order to obtain a quantitative assessment of the performance of two algorithms, a set of performance metrics, including miscorrelation rate, correct correlation rate, average time for hypothesis per scan, and the optimal subpattern assignment distance, are introduced and the detailed description could be found in [21].(a)
Miscorrelation rate of true tracks (RMC): we use the miscorrelation rate to measure the data association quality. The miscorrelation rate is defined as the ratio of average number of miscorrelation over the average track life.(b)
Correct correlation rate of true tracks (RCC): the correct correlation rate is also used for evaluating the correctness of data association. It is defined as the ratio of total number of correctly associated observations in true tracks to the total number of target-originated observations.(c)
Average time for hypothesis per scan (TH): this metric is defined to evaluate the computational complexity of different trackers with unity being second.(d)
The optimal subpattern assignment (OSPA) distance: this metric is introduced to measure the quality of cardinality and state estimation. The OSPA distance between the two setsX=x1,…,xn and Y=y1,…,ym is calculated by(26)dospacX,Y=1nminπ∈∏nmax1≤i≤n⁡dcxi,y^πip+cpn-mpn≥mdospacY,Xn≤m,where∏n denotes the set of all possible permutations of 1,2,…,n and dcx,y=min⁡c,dx,y is the truncated Euclidean distance between the vectors x and y. The cut-off distance c is set as 5000 and the order parameter p is fixed at 2.


#### 5.3.1. Scenario A

The performance of the two algorithms in scenario A is shown in Table1 and Figures 7 and 8. At first glance, we can observe from Figure 7 that the estimated trajectories produced by MPBP-MHT are smoother than trajectories by GRASP-MHT and have less track confusion. Additionally, from Table 1, it can be seen that the correct correlation rate RCC of MPBP-MHT is larger than that of GRASP-MHT and the miscorrelation rate RMC of MPBP-MHT is smaller than that of GRASP-MHT, which means that the correctness of data association in MPBP-MHT is better than GRASP-MHT. The quantitative difference of TH between the two algorithms is merely 0.001 s, which indicates that both algorithms can operate efficiently. Finally, the overall tracking performance is compared in terms of the OSPA distance. The OSPA distance is used to evaluate both cardinality and state estimation. It can be seen that although the OSPA distance of MPBP-MHT in some frames is larger than that of GRASP-MHT, in general, the tracking performance of MPBP-MHT outperforms GRASP-MHT in terms of the OSPA distance with great priority.Table 1
Simulation results of the scenario A.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.01
0.85
0.002
GRASP-MHT
0.24
0.67
0.001Figure 7
Estimated trajectories in scenario A. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 8
OSPA distance of the scene A.


#### 5.3.2. Scenario B

The performance of the two algorithms in scenario B is shown in Table2 and Figures 9 and 10. Figure 9 shows the estimated tracks obtained by MPBP-MHT and GRASP-MHT in scenario B, respectively. It can be seen that MPBP-MHT does better in tracking performance. The tracker using the MPBP-MHT algorithm gets cleaner tracks while the tracker using the GRASP-MHT algorithm exhibits obvious track switching.Table 2
Simulation results of the scene B.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.02
0.78
0.16
GRASP-MHT
0.17
0.69
0.04Figure 9
Estimated trajectories in scenario B. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 10
OSPA distance of the scene B.Table2 summarizes the tracking performance of the two algorithms in correlation quality and execution time. From the statistics, the MPBP-MHT algorithm obtains a larger RCC and a smaller RMC, which demonstrates that the MPBP-MHT algorithm outperforms the GRASP-MHT algorithm in the data association part. On timing results, both of the algorithms are efficient while the GRASP-MHT algorithm has a comparatively shorter execution time.Figure10 shows the average OSPA distance obtained over 100 Monte Carlo runs. It can be seen that the OSPA distance of GRASP-MHT fluctuates approximately between 1250 and 3000 whereas the OSPA distance of MPBP-MHT fluctuates between 250 and 2600. Although the curves of the two algorithms follow a similar pattern, the curve of MPBP-MHT is beneath the curve of GRASP-MHT most of time and stabilizes at a lower position. Therefore, we can conclude that the MPBP-MHT algorithm exhibits better overall estimation performance.


## 5.1. Target Motion and Measurement Models

The acceleration model with a white Gaussian noise is considered and the linear Kalman filter is used in our experiments. Targets move in a 2D surveillance area. The true state of a target at scank is xk=xk,yk,x˙k,y˙kT. xtk and ytk are, respectively, the positions of this target in the X-Y coordinate system, while x˙tk and y˙tk are, respectively, the velocities of this target. The movement of each target is modeled as the following target motion model: (21)xk=Fxk-1+vk,where the state transition matrix F is expressed as (22)F=10T0010T00100001,and the sampling periodT = 2 s. The covariance matrix of the white Gaussian noise vk is (23)Q=T330T2200T330T22T220T00T220Tq,where the process noise intensity q=100m2/s3. The measurement model is given as (24)zk=Hxk+wk,where(25)H=10000100,and the zero-mean Gaussian measurement noise wk has a covariance matrix R=diagσx2,σy2, where σx2=σy2=50m2.


## 5.2. Simulation Scenarios

We employ two scenarios for verifying the performance of the proposed method. All the estimation results were based on 100 Monte Carlo runs and the depth of TOMHT equals 5. The tracking performance is then compared with the GRASP-MHT algorithm in the same scenario, respectively. In the GRASP-MHT algorithm, the maximum number of tuples is set to 30 and the number of randomized iterations for each tuple is set to 3. All other parameters were shared with MPBP-MHT algorithm.


### 5.2.1. Scenario A

In the scenario A, the number of scans is set to 80. At the beginning, two closely spaced targets are moving parallelly with a separation of 30 m and a speed of 30 m/s over a period of 30 s. In the later 50 s, there is an intersect at 32 s and after that two targets are moving separately. Figure5(a) shows the real tracks of the two targets, and Figure 5(b) shows the real observations with clutters. The observation errors of azimuth and range are 0.002 rad and 20 m, respectively. The standard deviation of the process noise is 10 m. The target detection probability is 0.9 and the false alarm density is set as 10-8/m2.Figure 5
Target trajectories and the real observations with clutters in scenario A. (a) Target trajectories; (b) real observations.
(a)
(b)


### 5.2.2. Scenario B

The scenario B consists of ten closely spaced targets and the targets are moving in formation with a separation of 900 m and a speed of 300 m/s over a period of 120 s. The start and stop positions are marked with∘ and ×, respectively. Each target performs three turns with an acceleration of 3g at 22 s, 42 s, and 72 s, where g is the gravitational acceleration and each turn lasts for 8 s with a course change of 45ο. The target detection probability is set as 0.9 and the false alarm density is 10-8/m2. Figure 6(a) shows the true target trajectories in the scenario B used for performance evaluation and Figure 6(b) provides the true observations with clutter. The number of clutter is Poisson distributed and their locations in the observation space are uniformly distributed.Figure 6
Target trajectories and the real observations with clutters in scenario B. (a) Target trajectories; (b) real observations.
(a)
(b)


## 5.2.1. Scenario A

In the scenario A, the number of scans is set to 80. At the beginning, two closely spaced targets are moving parallelly with a separation of 30 m and a speed of 30 m/s over a period of 30 s. In the later 50 s, there is an intersect at 32 s and after that two targets are moving separately. Figure5(a) shows the real tracks of the two targets, and Figure 5(b) shows the real observations with clutters. The observation errors of azimuth and range are 0.002 rad and 20 m, respectively. The standard deviation of the process noise is 10 m. The target detection probability is 0.9 and the false alarm density is set as 10-8/m2.Figure 5
Target trajectories and the real observations with clutters in scenario A. (a) Target trajectories; (b) real observations.
(a)
(b)


## 5.2.2. Scenario B

The scenario B consists of ten closely spaced targets and the targets are moving in formation with a separation of 900 m and a speed of 300 m/s over a period of 120 s. The start and stop positions are marked with∘ and ×, respectively. Each target performs three turns with an acceleration of 3g at 22 s, 42 s, and 72 s, where g is the gravitational acceleration and each turn lasts for 8 s with a course change of 45ο. The target detection probability is set as 0.9 and the false alarm density is 10-8/m2. Figure 6(a) shows the true target trajectories in the scenario B used for performance evaluation and Figure 6(b) provides the true observations with clutter. The number of clutter is Poisson distributed and their locations in the observation space are uniformly distributed.Figure 6
Target trajectories and the real observations with clutters in scenario B. (a) Target trajectories; (b) real observations.
(a)
(b)


## 5.3. Results and Evaluation

In this part, we provide the empirical results in the simulation. In order to obtain a quantitative assessment of the performance of two algorithms, a set of performance metrics, including miscorrelation rate, correct correlation rate, average time for hypothesis per scan, and the optimal subpattern assignment distance, are introduced and the detailed description could be found in [21].(a)
Miscorrelation rate of true tracks (RMC): we use the miscorrelation rate to measure the data association quality. The miscorrelation rate is defined as the ratio of average number of miscorrelation over the average track life.(b)
Correct correlation rate of true tracks (RCC): the correct correlation rate is also used for evaluating the correctness of data association. It is defined as the ratio of total number of correctly associated observations in true tracks to the total number of target-originated observations.(c)
Average time for hypothesis per scan (TH): this metric is defined to evaluate the computational complexity of different trackers with unity being second.(d)
The optimal subpattern assignment (OSPA) distance: this metric is introduced to measure the quality of cardinality and state estimation. The OSPA distance between the two setsX=x1,…,xn and Y=y1,…,ym is calculated by(26)dospacX,Y=1nminπ∈∏nmax1≤i≤n⁡dcxi,y^πip+cpn-mpn≥mdospacY,Xn≤m,where∏n denotes the set of all possible permutations of 1,2,…,n and dcx,y=min⁡c,dx,y is the truncated Euclidean distance between the vectors x and y. The cut-off distance c is set as 5000 and the order parameter p is fixed at 2.


### 5.3.1. Scenario A

The performance of the two algorithms in scenario A is shown in Table1 and Figures 7 and 8. At first glance, we can observe from Figure 7 that the estimated trajectories produced by MPBP-MHT are smoother than trajectories by GRASP-MHT and have less track confusion. Additionally, from Table 1, it can be seen that the correct correlation rate RCC of MPBP-MHT is larger than that of GRASP-MHT and the miscorrelation rate RMC of MPBP-MHT is smaller than that of GRASP-MHT, which means that the correctness of data association in MPBP-MHT is better than GRASP-MHT. The quantitative difference of TH between the two algorithms is merely 0.001 s, which indicates that both algorithms can operate efficiently. Finally, the overall tracking performance is compared in terms of the OSPA distance. The OSPA distance is used to evaluate both cardinality and state estimation. It can be seen that although the OSPA distance of MPBP-MHT in some frames is larger than that of GRASP-MHT, in general, the tracking performance of MPBP-MHT outperforms GRASP-MHT in terms of the OSPA distance with great priority.Table 1
Simulation results of the scenario A.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.01
0.85
0.002
GRASP-MHT
0.24
0.67
0.001Figure 7
Estimated trajectories in scenario A. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 8
OSPA distance of the scene A.


### 5.3.2. Scenario B

The performance of the two algorithms in scenario B is shown in Table2 and Figures 9 and 10. Figure 9 shows the estimated tracks obtained by MPBP-MHT and GRASP-MHT in scenario B, respectively. It can be seen that MPBP-MHT does better in tracking performance. The tracker using the MPBP-MHT algorithm gets cleaner tracks while the tracker using the GRASP-MHT algorithm exhibits obvious track switching.Table 2
Simulation results of the scene B.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.02
0.78
0.16
GRASP-MHT
0.17
0.69
0.04Figure 9
Estimated trajectories in scenario B. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 10
OSPA distance of the scene B.Table2 summarizes the tracking performance of the two algorithms in correlation quality and execution time. From the statistics, the MPBP-MHT algorithm obtains a larger RCC and a smaller RMC, which demonstrates that the MPBP-MHT algorithm outperforms the GRASP-MHT algorithm in the data association part. On timing results, both of the algorithms are efficient while the GRASP-MHT algorithm has a comparatively shorter execution time.Figure10 shows the average OSPA distance obtained over 100 Monte Carlo runs. It can be seen that the OSPA distance of GRASP-MHT fluctuates approximately between 1250 and 3000 whereas the OSPA distance of MPBP-MHT fluctuates between 250 and 2600. Although the curves of the two algorithms follow a similar pattern, the curve of MPBP-MHT is beneath the curve of GRASP-MHT most of time and stabilizes at a lower position. Therefore, we can conclude that the MPBP-MHT algorithm exhibits better overall estimation performance.


## 5.3.1. Scenario A

The performance of the two algorithms in scenario A is shown in Table1 and Figures 7 and 8. At first glance, we can observe from Figure 7 that the estimated trajectories produced by MPBP-MHT are smoother than trajectories by GRASP-MHT and have less track confusion. Additionally, from Table 1, it can be seen that the correct correlation rate RCC of MPBP-MHT is larger than that of GRASP-MHT and the miscorrelation rate RMC of MPBP-MHT is smaller than that of GRASP-MHT, which means that the correctness of data association in MPBP-MHT is better than GRASP-MHT. The quantitative difference of TH between the two algorithms is merely 0.001 s, which indicates that both algorithms can operate efficiently. Finally, the overall tracking performance is compared in terms of the OSPA distance. The OSPA distance is used to evaluate both cardinality and state estimation. It can be seen that although the OSPA distance of MPBP-MHT in some frames is larger than that of GRASP-MHT, in general, the tracking performance of MPBP-MHT outperforms GRASP-MHT in terms of the OSPA distance with great priority.Table 1
Simulation results of the scenario A.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.01
0.85
0.002
GRASP-MHT
0.24
0.67
0.001Figure 7
Estimated trajectories in scenario A. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 8
OSPA distance of the scene A.


## 5.3.2. Scenario B

The performance of the two algorithms in scenario B is shown in Table2 and Figures 9 and 10. Figure 9 shows the estimated tracks obtained by MPBP-MHT and GRASP-MHT in scenario B, respectively. It can be seen that MPBP-MHT does better in tracking performance. The tracker using the MPBP-MHT algorithm gets cleaner tracks while the tracker using the GRASP-MHT algorithm exhibits obvious track switching.Table 2
Simulation results of the scene B.
Tracker
Performance metrics
R
M
C
R
C
C
T
E
s
MPBP-MHT
0.02
0.78
0.16
GRASP-MHT
0.17
0.69
0.04Figure 9
Estimated trajectories in scenario B. (a) MPBP-MHT; (b) GRASP-MHT.
(a)
(b)Figure 10
OSPA distance of the scene B.Table2 summarizes the tracking performance of the two algorithms in correlation quality and execution time. From the statistics, the MPBP-MHT algorithm obtains a larger RCC and a smaller RMC, which demonstrates that the MPBP-MHT algorithm outperforms the GRASP-MHT algorithm in the data association part. On timing results, both of the algorithms are efficient while the GRASP-MHT algorithm has a comparatively shorter execution time.Figure10 shows the average OSPA distance obtained over 100 Monte Carlo runs. It can be seen that the OSPA distance of GRASP-MHT fluctuates approximately between 1250 and 3000 whereas the OSPA distance of MPBP-MHT fluctuates between 250 and 2600. Although the curves of the two algorithms follow a similar pattern, the curve of MPBP-MHT is beneath the curve of GRASP-MHT most of time and stabilizes at a lower position. Therefore, we can conclude that the MPBP-MHT algorithm exhibits better overall estimation performance.


## 6. Conclusions

In this paper, we propose an efficient MPBP-MHT method that exploits graphical models and message passing algorithms to solve the data association problem in tracking application. Instead of seeking the best hypothesis by enumeration, we cast the hypothesis generation problem into the graphical model formalism using MWISP structure and the efficient MPBP algorithm is developed to find the MAP assignment. The effectiveness of the proposed algorithm is tested over challenging cases and a comparison with the GRASP-MHT algorithm is made to demonstrate the priority in association property of the MPBP-MHT algorithm.



---

*Source: 8061561-2017-09-11.xml*