# Draft:Multiple-Object Tracking using JPDAF

• Comment: needs specialist, i think DGG ( talk ) 05:48, 4 July 2021 (UTC)

Authors:

1. Sneha Nayak

This work is inspired by[1] and[2]

Multiple-object tracking is one of the most important topics in any machine-vision related application wherein the environment is cluttered with multiple objects/obstacles. Various techniques are used to solve the problem of multi-object tracking. In this article, the Joint Probabilistic Data Association Filter is used to solve the problem of multiple-object tracking. JPDAF is one step above PDAF where the minimum mean square error of each target state is estimated. The particle filter method also is known as the Sequential Monte Carlo[3] method is considered for the tracking application. Particle filter is generally used for non-gaussian and non-linear dynamic processes. It is used to estimate the internal states for partially observable and noisy systems. In the case of multiple-object tracking problems, generally, the environment is cluttered with objects very closely spaced out. This creates noise in the system. Alongside this, since the system is dynamic, it is considered as partially observable. This proves as the correct use case for a partially observable system and hence, particle filter suits best. The traditional JPDAF[4] uses the Extended Kalman Filter (EKF) with the data association for state estimation of multiple objects. The Monte Carlo version of JPDAF is a particle filter combined with the Joint Probabilistic Data Association method.

## Background

Unlike single-object tracking applications, multiple-object tracking is more challenging. In presence of multiple objects, the targets and observations (data associations) need to be matched from frame to frame in video sequences. This becomes more tedious when it comes to objects which have the same appearance. on To solve the problem of multiple-objects being tracked in a scene, Kalman filtering[5] is used. It solves the problem to a great extend but fails to the point when the system becomes non-linear in nature. The state estimation for many real-time systems has severe non-linearity and the posterior probability density function of the states cannot be represented as a Gaussian density function, hence, the Kalman filter fails at this point.

Particle filters are used for non-gaussian and non-linear dynamic processes. The number of filters used depends on the number of objects to be tracked. Here, each state is represented by a set of samples or particles. Using particle filtering, we can represent multi-model state densities which increases the robustness of the state-estimation process. With an increasing number of objects to be tracked, the number of filters increases, and a combined state space comes into the picture which increases the complexity of the algorithm.

## Overview

### JPDAF

The main idea behind any multi-object tracking module is to estimate the position of each target. We do receive measurements of the system as a whole, but the main problem lies in associating those measurements with the target. The way this can be done is though data association, which allows for associating these data measurements to its target. This way the problem of multi-tracking can be overcome by using this state estimation algorithm with filtering techniques like Kaman filter and particle filtering as opposed to applying state estimation procedure to a combined state space model.

For the case of more than one target in the cluttered environment we use Joint probabilistic data association (JPDA),[6] which is an elegant method of associating the detected measurements in each time frame with existing targets using a joint probabilistic score. A Bayesian estimate of the match between features detected in the sensor data and targets is computed.[7]JPDAF deals with a fixed number of targets and defines a way of combining all valid data-association hypotheses such that, at each time step, only one global update is needed during the correction step without requiring the memory of previous associations. The data association algorithm also helps to recover from full or partial occlusions. Gating Techniques can be used to remove spurious sensor measurements in order to reduce the number of association. This can be done by checking the proximity of the target estimates and actual observations.

### Extended Kalman Filter with JPDAF

[1]The traditional JPDAF uses Extended Kalman Filtering(EKF) joint with the data association to estimate the states of multiple objects.[6]In order to improve the real-time processing and accuracy of target tracking, based on a probabilistic data association algorithm, a data association algorithm using distance weighting was proposed, which can enhance the association probability of measurement originated from target, and then using a Kalman filter to estimate the target state more accurately. Thus, the tracking performance of the algorithm when tracking non-maneuvering targets in a densely cluttered environment improved, and also does better when two targets are parallel to each other, or at a small-angle crossing in a densely cluttered environment.[6]

While Kalman filters have been shown to provide highly efficient state estimates, they are only optimal for uni-modal Gaussian distributions over the state to be estimated. The performance of the algorithm degrades as the non-linearity become more severe. More recently, particle filters have been introduced to estimate non-Gaussian, non-linear dynamic processes.

## Monte Carlo Version of JPDAF

In the recent years, particle filtering techniques with JPDAF algorithm have seemed to gain popularity primarily because of their ability to work with non-linear , non-gaussian, multi-modal states densities The key idea of particle filters is to represent the state by sets of samples (or particles). This has shown to increase the robustness of the underlying state estimation process.

[1]To enhance the performance of the JPDAF against the severe nonlinearity of dynamical and sensor models, recently, strategies have been proposed to combine the JPDAF with particle techniques known as Monte Carlo JPDAF, to accommodate general non-linear and non-gaussian models. Soft gating techniques are also used to reduce computational costs and reduce the number of associations, which have proven to be beneficial in online tracking problems.

This Monte Carlo version of the JPDAF algorithm employs the particle filter approach to estimate the posterior density of the states given the measurements of each of the targets, given by P(xkt | y1:t), where k = 1,2,...N represents the target number and t represents the state of the target at a time t.

If we consider the target to have a non-linear dynamic state, the state space model can be represented as:

${\displaystyle x_{t+1}=f(x_{t})+v_{t}}$

(1)

${\displaystyle y_{t}=g(x_{t})+w_{t}}$

(2)

where vt and wt are white noise with a covariance, f and g are non-linear functions of the target and sensor model. The JPDAF recursively updates the P(xkt | y1:t) for each target.

## Mulitple Target Tracking

### Sequential Monte Carlo

Particle filtering also is known as the Sequential Monet Carlo technique is used to detect and track the object of interest. The common particle filter is used to estimate the posterior density function of the state. The posterior state distribution (filtering distribution) given by ${\displaystyle p(x_{k}|Z_{k})}$ is calculated at each step for tracking the object of interest. According to the Bayesian sequential estimation, the posterior state distribution can be calculated in two steps:

prediction step

${\displaystyle p(x_{k}|Z_{k-1})=\int p(x_{k}|x_{k-1})p(x_{k-1}|Z_{k-1})\,dx_{k-1}}$

(1)

which follows from marginalisation

and, filtering step

${\displaystyle p(x_{k}|Z_{k})\varpropto p(z_{k}|x_{k})p(x_{k}|Z_{k-1})}$

(2)

is used to obtain the filtering distribution using Baye's rule. This is a recursive step and requires the specifications of a dynamic model whose state evolution is described by ${\displaystyle p(x_{k}|x_{k-1})}$ and the state likelihood with current observations is ${\displaystyle p(z_{k}|x_{k})}$. A Maximum a Posteriori (MAP) is estimated as ${\displaystyle argmax_{xk}p(x_{k}|Z_{k})}$ and the minimum Mean Square Error (MMSE) is estimated as ${\displaystyle \int x_{k}p(x_{k}|Z_{k})\,dx_{k}}$.

Particle filtering is basically a sampling method. We start with a weighted set of samples ${\displaystyle \{x_{k-1}^{(i)},w_{k-1}^{(i)}\}_{i=1}^{N}}$ which is approximately distributed according to ${\displaystyle p(x_{k-1}|Z_{k-1})}$. The new samples are derived from a proposal distribution. These new samples may be dependent on the previous states and the new measurements. The new particle set ${\displaystyle \{x_{k}^{(i)},w_{k}^{(i)}\}_{i=1}^{N}}$ which is derived is then approximately distributed as ${\displaystyle p(x_{k}|Z_{k})}$. Th performance of the particle filter is dependent on the above distribution.

### Data Association using JPDA

In video sequences, when we try to track an object of interest, associating the data from one frame to another becomes of utmost importance. In the case of multiple-object tracking, it is important to relate the measurements to the correct object. There are several methods to associate the data between measurements and targets. In some cases, the number of targets is constant. The observations come from multiple targets or a clutter which is considered as a false alarm as their properties are different from the targets. Sometimes, it is assumed that one target will have one measurement, and sometimes, multiple measurements from one target. The JPDA estimates the states by assuming over all the association hypothesis weighted by the probabilities from the likelihood. A known number of targets is assumed which is ${\displaystyle \tau }$.

${\displaystyle t=\{1,...,\tau \}}$ designates one among the ${\displaystyle \tau }$ targets.

The measurements taken at time step ${\displaystyle k}$ is given by,

${\displaystyle z_{k}=\{Z_{k}^{j}\}_{j=0}^{mk}}$

(3)

where,

${\displaystyle m_{k}=}$ number of measurements

${\displaystyle z_{0}=}$ artificial measurement to handle false alarms

Considering the estimation to be Markovian, we use the Baye's theorem to calculate the joint association probabilities as,

${\displaystyle P(\theta |Z_{k})={\frac {1}{c}}p(z_{k}|\theta ,X_{k})P(\theta |X_{k})}$

(4)

where,

${\displaystyle c=}$ normalization constant

${\displaystyle X_{k}=\{x_{1},...,x_{k}\}}$

${\displaystyle \theta =}$ joint association event

Since we calculate the probabilities using Baye's rule, we consider the measurements to be independent of each other. Approximation of the sequence of target states ${\displaystyle P(\theta |X_{k})}$ with conditioned ${\displaystyle \theta }$ is given by,

${\displaystyle P(\theta |X_{k})=P^{(}\tau -n)_{D}(1-P_{D})^{n}P_{FA}^{m_{k}-(\tau -n)}}$

(5)

here,

${\displaystyle P_{D}}$ denotes the probability of detection,

${\displaystyle n}$ is the number of ${\displaystyle z_{0}}$ assignments,

and ${\displaystyle P_{FA}}$ denotes the probability of the false alarm

For target ${\displaystyle t}$,let the ${\displaystyle j}$-the measurement be ${\displaystyle z_{k}^{j}}$ and the predicted measurement be ${\displaystyle {\hat {z}}_{t,k}^{j}}$. The innovation between these two at time step ${\displaystyle k}$ is given by,

${\displaystyle v_{t.k}^{j}=z_{k}^{j}-{\hat {z}}_{t,k}^{j}}$

(6)

and the corresponding innovation covariance matrix is defined as ${\displaystyle S_{t,k}^{j}}$. In this case, the normalized innovation is given by,

${\displaystyle d_{t,k}^{j}=(v_{t,k}^{j})^{T}(S_{t,k}^{j})^{-1}v_{t,k}^{j}}$

(7)

For ${\displaystyle M}$-dimenional Gaussion association likelihood for the ${\displaystyle j}$-th measurement to the target ${\displaystyle t}$ is given by,

${\displaystyle p(v_{t,k}^{j})={\frac {1}{(2\pi )^{\frac {M}{2}}|S_{t,k}^{j}|^{\frac {1}{2}}\exp {{\Bigl \{}{\frac {-(d_{t,k}^{j})^{2}}{2}}}{\Bigr \}}}}}$

(8)

The probability of an individual joint association event is given by,

${\displaystyle P(\theta |Z_{k})=P_{D}^{\tau -n}(1-P_{D})^{n}P_{FA}^{m_{k}-(\tau -n)}\prod _{\theta _{t}^{j}\in \theta }p(v_{t,k}^{j})}$

(9)

### The JPDAF Algorithm

To make sure the tracking is done efficiently, i.e. new filters are initialized for new objects to be tracked and the objects that disappeared from the scene are no more being tracked. The algorithm begins with a single filter consisting of uniformly distributed particles for the maximum number of targets ${\displaystyle \tau }$. The convergence of this filter is monitored, and a new filter is initialized with sampling particles prior to uniformly distributed at the region around the first tracker. The prior around tracker 1 is zero and this helps in reducing the likelihood of two filters tracking a single object. Again the variance of this new tracker is monitored for convergence and a new filter is initialized with a prior from the region not covered by the first two filters.

According to the total probability theorem, the existence probability of ${\displaystyle t}$ number of targets is given by,

${\displaystyle P(H_{t}|Z_{k})=\sum _{\theta \in \chi _{t}}P(\theta |Z_{k}),t=1,...,\tau }$

(10)

and, the joint probability of the specific targets is given by,

${\displaystyle P(H_{t_{1},t_{2},...,t_{\rho }}|Z_{k})=\sum _{\theta \in {\chi _{t_{1},t_{2},...,t_{\rho }}}}P(\theta |Z_{k})}$

(11)

These probabilities are used to keep track of the objects. Whenever the object disappears, the probabilities change as per the change in the number of objects. Thus, we can identify the object that disappeared. After identifying the disappeared object, we can stop the filter for the respective object and reinitialize a new filter for the new target object.

Algorithm

1) Initialisation.

Set ${\displaystyle k=0}$, generate ${\displaystyle N}$ samples ${\displaystyle \mathbf {x} _{t,0}^{(i)}}$ for all targets ${\displaystyle t=1,...,\tau }$ independently.

${\displaystyle x_{t,0}^{(i)}}$ is drawn from ${\displaystyle p(\mathbf {x} _{t,0})}$, with initial weights ${\displaystyle w_{t,0}^{(i)}=1/N}$, for ${\displaystyle i=1,...,N}$ particles and set ${\displaystyle k=1}$.

2) For ${\displaystyle i=1,...,N}$ predict new particles ${\displaystyle \mathbf {x} _{t,k}^{(i*)}=\mathbf {F} \mathbf {x} _{t,k-1}^{(i)}+\mathbf {v} _{t,k-1}^{(i)}}$.

3) For each particle compute the weights for all measurements ${\displaystyle (j=0,...,m_{k})}$ to target ${\displaystyle (t=1,...,\tau )}$ associations ${\displaystyle w_{t,k}^{(i)}=\sum _{\theta }P(\theta |\mathbf {Z} _{k})}$ and normalise the weights for each target: ${\displaystyle {\tilde {w}}_{t,k}^{(i)}={\frac {w_{t,k}^{(i)}}{\sum _{i=1}^{N}w_{t,k}^{(i)}}}}$

4) For each target, generate a new set ${\displaystyle \{x_{t,k}^{(i)}\}_{i=1}^{N}}$, by resampling with ${\displaystyle N}$ times from ${\displaystyle \{x_{t,k}^{(i*)}\}_{i=1}^{N}}$, where ${\displaystyle P(\mathbf {x} _{t,k}^{(i)}=\mathbf {x} _{t,k}^{(i*),t})={\tilde {w}}_{t,k}^{(i)}}$.

5) Increase ${\displaystyle k}$ and iterate to step 2.

## Results

The key results can be listed as follows:

• This JDPAF technique has also proven to work well with partial occlusions. An open research problem, however, is coping with full occlusions.
• JDPAF technique with Sequential Monte Carlo shows to be characterized with low computational complexity.
• JPDAF works well when the reference frame is static and stationary. But when the reference frame is dynamic and moving (in case of multi-robot teams, a reference robot would require to remain stationary), it doesn't seem to work well, which is an open research problem.
• In the case of local tracking for non-maneuvering objects with a near-constant velocity model,[1] the ability of the JPDAF algorithm in modifying the intrinsic error embedded in the data collected from the measurement sensor was justified.
• In the case of local tracking for maneuvering objects with a variable velocity model, 3 approaches were implemented to estimate the position of moving maneuvering targets. Near constant velocity model, the near-constant acceleration model, and the combined model were used to estimate the states of the targets. It was seen that the combined model performed the most efficiently with the JPDAF algorithm in tracking the targets.

## Application

The JPDAF Algorithm has a wide range of applications.

• Multiple-object tracking has a wide application in the field of self-driving vehicles.
• It also serves as an essential step in vision technology which includes object classification, traffic control, surveillance systems, and navigation systems.
• The extended application of using JPDAF for multiple-object can be with respect to tracking the position of robots in a given environment, with one static robot being the reference robot. In the case of mobile robots, one cannot completely depend on the odometry data from the robot's locomotion. Using this approach provides more accurate knowledge of the system.
• It can be used for multi-human tracking for surveillance.
• It can be used for re-routing air traffic.

## References

1. ^ a b c d Gorji A., Menhaj M.B., Shiry S. (2009) Multiple Target Tracking for Mobile Robots Using the JPDAF Algorithm. In: Koutsojannis C., Sirmakessis S. (eds) Tools and Applications with Artificial Intelligence. Studies in Computational Intelligence, vol 166. Springer, Berlin, Heidelberg.
2. ^ M. Jaward, L. Mihaylova, N. Canagarajah and D. Bull, "Multiple object tracking using particle filters," 2006 IEEE Aerospace Conference, Big Sky, MT, 2006, pp. 8 pp.-, doi: 10.1109/AERO.2006.1655926.
3. ^ Liu, Jun S., and Rong Chen. "Sequential Monte Carlo methods for dynamic systems." Journal of the American statistical association 93, no. 443 (1998): 1032-1044.
4. ^ D. H. Santosh and P. G. K. Mohan, "Multiple objects tracking using Extended Kalman Filter, GMM and Mean Shift Algorithm - A comparative study," 2014 IEEE International Conference on Advanced Communications, Control and Computing Technologies, Ramanathapuram, 2014, pp. 1484-1488, doi: 10.1109/ICACCCT.2014.7019350.
5. ^ Jong-Min Jeong, Tae-Sung Yoon and Jin-Bae Park, "Kalman filter based multiple objects detection-tracking algorithm robust to occlusion," 2014 Proceedings of the SICE Annual Conference (SICE), Sapporo, 2014, pp. 941-946, doi: 10.1109/SICE.2014.6935235.
6. ^ a b c Chen, Xiao; Li, Yaan; Li, Yuxing; Yu, Jing; Li, Xiaohua (2016). "A Novel Probabilistic Data Association for Target Tracking in a Cluttered Environment". Sensors. 16 (12): 2180. Bibcode:2016Senso..16.2180C. doi:10.3390/s16122180. PMC 5191159. PMID 27999347. Text was copied from this source, which is available under a Creative Commons Attribution 4.0 International License.
7. ^ Dirk, Schulz (February 1, 2003). "People Tracking with Mobile Robots Using Sample-Based Joint Probabilistic Data Association Filters". The International Journal of Robotics Reasearch. 22 (2): 99–116. doi:10.1177/0278364903022002002. S2CID 5668176.