Tracking Multiple Interacting Targets via MCMC-MRF
Posted on
Abstract
Proposal: a MCMC based particle filter that effectively deals with interacting targets, i.e., targets that are influenced by the proximity and/or behavior of other targets.
Main contributions:
- show how a MRF motion prior, built on the fly at each time step, can substantially improve tracking when targets interact: incorporating an MRF to model interactions is equivalent to adding an additional interaction factor to the importance weights in a joint particle filter.
- show how this can be done efficiently using MCMC sampling
Introduction
Objective: obtain a record of the trajectories of targets over time, and to maintain correct, unique identification of each target throughout
classical multi-target tracking literature (till 2004): performing a data-association step after a detection step:
- multiple hypothesis tracker
- joint probabilistic data association filter (JPDAF)
In contrast to traditional methods, the approach relies on the use of a more capable motion model, one that is able to adequately describe target behavior throughout an interaction event. The basic assumption on which all established data-association methods rely is that targets maintain their behavior before and after the targets visually merge.
The approach is based on the well known particle filter, a multi-hypothesis tracker that uses a set of weighted particles to approximate a density function corresponding to the probability of the location of the target given observations over time.
The standard particle filter weights particles based on a likelihood score, and then propagates these weighted particles according to a motion model.
Replace the traditional importance sampling step in the particle filter with an MCMC sampling step. This approach has the appealing property that the filter behaves as a set of individual particle filters when the targets are not interacting, but effectively deals with complicated interactions when targets approach each other.
Bayesian Multi-target Tracking
Recursively update the posterior distribution $P(X_t\mid Z^t)$ over the joint state of the all $n$ targets ${X_{it}\mid i=1,\ldots,n}$ given all observations $Z^t = {Z_1,\ldots,Z_t}$ up to and including time $t$, according to
\begin{equation} P(X_t\mid Z^t) = kP(Z_t\mid X_t)\int_{X_{t-1}}P(X_t\mid X_{t-1})P(X_{t-1}\mid Z^{t-1})dX_{t-1}\label{eq:update} \end{equation}
$k$ should be $P(Z_t\mid Z^{t-1})$, doesn’t it relate to $t$?
The likelihood $P(Z_t\mid X_t)$ expresses the measurement model, while $P(X_t\mid X_{t-1})$ is the motion model.
In all that follows, assume that $P(Z_t\mid X_t) = \prod_{i=1}^nP(Z_{it}\mid X_{it})$.
Independent Particle Filters
When identical targets do not interact, we can approximate the exact Bayes filter by running multiple single-target particle filters, i.e., factoring the motion model $P(X_t\mid X_{t-1})$ as $\prod_iP(X_{it}\mid X_{i,t-1})$.
The particle filter used the predictive density on the state $X_{it}$ as the proposal distribution, then the incremental importance weight reduced to $P(Z_{it}\mid X_{it})$. (See Particle Filtering and Smoothing for more details.)
Specifically, assume that the posterior at the previous time step is approximated by a set of weighted particles
\[P(X_{it}\mid Z^{t-1})\approx \{X_{i,t-1}^{(r)},\pi_{i,t-1}^{(r)}\}_{r=1}^N\,.\]Then, for the current time-step, we draw $N$ samples $X_{it}^{(s)}$ from a proposal distribution
\[X_{it}^{(s)} \sim q(X_{it}) = \sum_r \pi_{i,t-1}^{(r)}P(X_{it}\mid X_{i,t-1}^{(r)})\]which is a mixture of motion models $P(X_{it}\mid X_{i,t-1}^{(r)})$. Here it seems to estimate the predictive density by using information from all chains, but the procedure of SMC filtering samples each particle by using the proposal density with known form.
Then we weight each sample so obtained by its likelihood given the measurement $Z_{it}$, i.e,
\[\pi_{i,t}^{(s)} = P(Z_{it}\mid X_{it}^{(s)})\]This results in a weighted particle approximation $\{X_{it}^{(s)},\pi_{it}^{(s)}\}_{s=1}^N$ for the posterior $P(X_{it}\mid Z^t)$ over the target’s state $X_{it}$ at time $t$.
While independent filters is computationally tractable, the result is prone to frequent failures. Each particle filter samples in a small space, and the resulting “joint” filter’s complexity is linear in the number of targets, $n$.
MRF Motion Model
To address tracker failures resulting from interactions is to introduce a more capable model motion model, based on MRF. Model the interaction between targets using a graph-based MRF constructed on the fly for each individual time-step.
An MRF is a graph $(V,E)$ with undirected edges between nodes where the joint probability is factored as a product of local potential functions at each node, and interactions are defined on neighborhood cliques.
Assume the following pairwise MRF form, where the $\psi(X_{it},X_{jt})$ are pairwise interaction potentials:
\begin{equation} P(X_t\mid X_{t-1})\propto \prod_i P(X_{it}\mid X_{i(t-1)})\prod_{ij\in E}\psi(X_{it}, X_{jt})\label{eq:mrf} \end{equation}
Express $\psi(X_{it},X_{jt})$ by means of the Gibbs distribution:
\[\psi(X_{it},X_{jt}) \propto \exp(-g(X_{it},X_{jt}))\]where $g(X_{it},X_{jt})$ is a penalty function. For example, it can depends only on the number of pixels overlap between the target boxes of two targets. It is maximal when two targets coincide and gradually falls off as targets move apart.
The Joint MRF Particle Filter
Consider the full joint state of all $n$ targets, the Monte Carlo approximation to the Bayes filter is
\begin{equation} P(X_t\mid Z^t) \approx kP(Z_t\mid X_t) \sum_r \pi_{t-1}^{r} P(X_t\mid X_{t-1}^{(r)})\label{eq:jpf} \end{equation}
The approximation is based on \eqref{eq:update}.
Plug the MRF motion model \eqref{eq:mrf} into the joint particle filter equation \eqref{eq:jpf}, and note that the interaction potential does not depend on the previous target state $X_{t-1}$, and hence the target distribution for the joint MRF filter factors is
\[P(X_t\mid Z^t)\approx kP(Z_t\mid X_t)\prod_{ij\in E}\psi(X_{it},X_{jt}) \sum_r\pi_{t-1}^{(r)} \prod_i P(X_{it}\mid X_{i(t-1)}^{(r)})\,,\]which means that we can simply treat the interaction term as an additional factor in the importance weight. In other words, sample from the joint proposal distribution function
\[X_t^{(s)} \sim q(X_t) = \sum_{r}\pi_{t-1}^{(r)}\prod_iP(X_{it}\mid X_{i(t-1)}^{(r)})\]and weight the samples according to the following factored likelihood expression:
\[\pi_t^{(s)} = \prod_{i=1}^n P(Z_{it}\mid X_{it}^{(s)}) \prod_{ij\in E}\psi(X_{it}^{(s)},X_{jt}^{(s)})\]However, the joint particle filter approximation is not well suited for multi-target tracking. Each particle contains the joint position of all $n$ targets, $X_t^{(s)}=\{X_{1t}^{(s)},\ldots,X_{nt}^{(s)}\}$, and the filter suffers from exponential complexity in the number of tracked targets $n$.
The MCMC-Based MRF Particle Filter
Generate a sequence of samples from $P(X_t\mid Z^t)$.
Proposal step:
- Randomly select a joint sample $X_{t-1}^{(r)}$ from the set of unweighted samples from the previous time step.
- Randomly select a target $i$ from $n$ targets.
- Use the previous state of this $i$-th target $X_{i(t-1)}^{(r)}$, sample from conditionally dependent motion model $P(X_{it}’\mid X_{i(t-1)}^{(r)})$ to obtain $X_{it}’$.
The acceptance ratio is
\[a = \min\left(1,\frac{P(Z_{it}\mid X_{it}')\prod_{j\in E_i}\psi(X_{it}',X_{jt}')}{P(Z_{it}\mid X_{it})\prod_{j\in E_i}\psi(X_{it},X_{jt})}\right)\]Since the proposal distribution $Q(X_t’\mid X_t)$ equals to $P(X_t’\mid Z^{t-1})$, which is approximated by $\sum_{r}\pi_{t-1}^{(r)}P(X_{t}\mid X_{(t-1)}^{(r)})$.
How to deal with the appearance and disappearance?