<jupyter_start><jupyter_text>Table of Contents0.1&nbsp;&nbsp;Probabilty theory:0.1.1&nbsp;&nbsp;Binominal distribution0.1.1.1&nbsp;&nbsp;Bernoulli Distribution0.1.1.2&nbsp;&nbsp;Poisson Distribution0.1.2&nbsp;&nbsp;Different types of target tracking0.1.3&nbsp;&nbsp;Multi object tracking algorithms taxonomy1&nbsp;&nbsp;Kalman Filter - TODO2&nbsp;&nbsp;Single object tracking3&nbsp;&nbsp;Motion model4&nbsp;&nbsp;Measurement model4.1&nbsp;&nbsp;Gaussian sum filtering5&nbsp;&nbsp;Module 3: Tracking a known number of objects5.1&nbsp;&nbsp;DA - data association5.1.1&nbsp;&nbsp;Creating cost matrix5.1.2&nbsp;&nbsp;Linear sum assignment optimization techniques:5.2&nbsp;&nbsp;GNN - Global Nearest Neighbours5.3&nbsp;&nbsp;JPDA - Joint Probability Data association5.4&nbsp;&nbsp;MHT - multi hypotheses tracker5.4.1&nbsp;&nbsp;Density operations:5.5&nbsp;&nbsp;Gaussian sum filtering6&nbsp;&nbsp;Multiple object tracking7&nbsp;&nbsp;RFS - random finite sets8&nbsp;&nbsp;8.1&nbsp;&nbsp;Bernoulli north model9&nbsp;&nbsp;MOT with conhugate prior. PMBM tracker.9.0.1&nbsp;&nbsp;Conjugacy9.0.2&nbsp;&nbsp;Bernoulli birth model9.0.3&nbsp;&nbsp;Multi Bernououlli (MB) birth model9.0.4&nbsp;&nbsp;Poisson birth model9.0.5&nbsp;&nbsp;The standart object deatj model9.0.6&nbsp;&nbsp;MBM CONJUGATE PRIOR9.0.7&nbsp;&nbsp;Hypotheses9.0.8&nbsp;&nbsp;algorithm9.0.9&nbsp;&nbsp;PMBM density9.1&nbsp;&nbsp;PMBM tracker9.2&nbsp;&nbsp;Part 6: Extended Object tracking9.2.0.1&nbsp;&nbsp;Sets of trajectories9.2.0.2&nbsp;&nbsp;References<jupyter_code>%load_ext autoreload
%autoreload 2

import os, sys
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
import scipy<jupyter_output>The autoreload extension is already loaded. To reload it, use:
  %reload_ext autoreload<jupyter_text>Intro  Probabilty theory: PDF (probability densiry function) represenets a distribution of a Conditional distributions: $\left\{\begin{array}{l}p(x, z)=p(z \mid x) p(x) \\ p(z \mid x)=\frac{p(x, z)}{p(x)}\end{array}\right.$E.g. Gaussian pdf: $N ( x ; \mu , Q )=\frac{1}{\sqrt{|2 \pi a |}} \exp \left(-\frac{1}{2}( x - \mu )^{T} Q ^{-1}( x - \mu )\right)$PMF (probability mass function) represents a distribution of a discrete variables.Law of total probability: $\left\{\begin{array}{l}p(z)=\int_{x} p(x, z) d x \\ p(z)=\int_{x} p(z \mid x) p(x) d x\end{array}\right.$$1^{ st }$ and $2^{n d}$ moments: $\left\{\begin{array}{l} E \{ x \}=\int x p( x ) d x \\ \operatorname{Cov}\{ x \}= E \left\{[ x - E \{ x \}][ x - E \{ x \}]^{T}\right\}\end{array}\right.$  Binominal distribution**Bernoulli trial** (or binominal trial) is a random experiemnt with exaclty two posible outcomes.Binominal distribution can be describes of the discrete probability of how manu successes $k$ you get when you conduct $n$ independent bernoulli trials, each with a provaviltity $p$ to result in 1 or $q=1-p$ to resust in 0 with PMFIf $x$ is binomially distribution with parameters $p \in[0,1]$ and $j \in N$$$\operatorname{Pr}[x=i]=\left(\begin{array}{l}n \\k\end{array}\right) p^{l}(1-p)^{n-k}$$wherefactor is the binominal coeefficient, which is how many number of different ways k successes can come to be out of n trials.$$\left(\begin{array}{l}n \\k\end{array}\right)=\frac{n !}{k !(n-k) !}$$It holds $$\mathbb{E} [x] = p n$$<jupyter_code>x = np.random.binomial(n=5, p=0.8, size=1000)
sns.displot(x,kde=False); plt.xlim(-1, 8)
plt.show()
x.mean() - 5*0.8<jupyter_output><empty_output><jupyter_text>Bernoulli DistributionThe Bernoulli distribution is a spesial case of the Binominal distribution, but for a single bernoulli trial only. It is the discrete probability distribution of a trial with 2 possible outcomes, either 1 or 0, with respective probability p and q = 1 - p. If $x$ is Bernoulli distributed with probability, $p \in[0,1]$, it takes the values$$x=\left\{\begin{array}{ll}1 & \text { with probability } p, \\0 & \text { with probability } 1-p .\end{array}\right.$$where k is the possible outcome, and p and q are the respective possibilities.**Where it uses** Bernoulli distribution is used to model the objects distribution given that the object is either detected (k=1) or missdetected<jupyter_code>from scipy.stats import bernoulli
bd = bernoulli(0.7) # Instance of Bernoulli distribution with parameter p = 0.7
X = [0, 1] # Outcome of experiment can take value as 0, 1
plt.figure(figsize=(5,5))
plt.xlim(-1, 2)
plt.bar(X, bd.pmf(X), color='orange', width=0.1)
plt.title('PMF Bernoulli (p=0.7)', fontsize='12'); plt.xlabel('Values of Random Variable X (0, 1)', fontsize='12'); plt.ylabel('Probability', fontsize='15'); plt.show()<jupyter_output><empty_output><jupyter_text>Poisson DistributionDiscrete distributionPoisson PMF with expected value \labda > 0:$$f(k, \lambda) = e^{-\lambda} \frac{\lambda^L}{k!}$$$k$ - the number of events,$\lambda$ - the average number of events occuring. Expeced number of events in interval $[a, b]$It is useful to know that$$\mathbb{E} [x] = Var [x] = \lambda$$<jupyter_code>x = random.poisson(lam=4, size=10)
sns.displot(random.poisson(lam=2, size=1000), kde=False)
plt.show()
print('sample =', x)
#Faussian 
# Uniform<jupyter_output><empty_output><jupyter_text>**Conjugate prior** - when the posterior distribtuion and the prior distribution are of the same probability density familty.**Clutter** - a faulty measurement not belonging to any real objects  Different types of target tracking- **Point object tracking** - at most a single measurement per object per time step.- **Extended object tracking** - involves multiple measurements per objecet. Posible to also estimate the shape and size of objcets.- **Group object tracking** - severla objects treated as a single entity - a group- **Tracking with multipath propagation** - more than one detection per objects per time stamp Caused by multipath phenomenon. Examples: OTHR (over the horizon radar)- **Tracking with unresolved measurements** - involves multiple object cause one measurement. Work with automotive radar, e.g. two vehicles travellin near each other with the same speed can get "merged" measurement (as a single target) Multi object tracking algorithms taxonomy  Kalman Filter - TODO  Single object trackingSOT in clutter - special case of MOT, only one object in environment exist all time**Pros**        1) no need to figure number of objects    2) no need data associationWith comparing with KF we have **new challenges**:    1) missed detection    2) clutter detection (false detection - clutter is more rancdom (no structure))    3) unknown DA (which is clutter, which is object)But previous chellenges still relevantL        1) time varying state variable    2) noisy measurements      Motion modelThe object state is a Markov chain that evolvesas$$p\left(x_{k} \mid x_{k-1}\right)=\pi_{k}\left(x_{k} \mid x_{k-1}\right)$$For instance, we often assume that$$x_{k}=f_{k-1}\left(x_{k-1}\right)+q_{k-1}, \quad q_{k-1} \sim N \left(0, Q_{k-1}\right)$$such that$$\pi_{k}\left(x_{k} \mid x_{k-1}\right)=N\left(x_{k} ; f_{k-1}\left(x_{k-1}\right), Q_{k-1}\right)$$  Measurement modelThe object is detected with probability $P^{ D }\left(x_{k}\right)$, and then generates a measurement from$$p\left(o_{k} \mid x_{k}\right)=g_{k}\left(o_{k} \mid x_{k}\right)$$For instance, we often assume that$$o_{k}=h_{k}\left(x_{k}\right)+v_{k}, \quad v_{k} \sim N \left(0, R_{k}\right)$$such that$$g_{k}\left(o_{k} \mid x_{k}\right)=N\left(o_{k} ; h_{k}\left(x_{k}\right), R_{k}\right)$$**Note: object is not always detected.**We use a matrix (or a sequence) to represent the object detections,$$O_{k}=\left\{\begin{array}{ll}{[]} & \text { if object is undetected, } \\o_{k} & \text { if object is detected. }\end{array}\right.$$We use $\left|O_{k}\right|$ to denote the number of column vectors in $O_{k}$Given $x_{k},\left|O_{k}\right|$ is Bernoulli distributed:$$\left|O_{k}\right|=\left\{\begin{array}{ll}1 & \text { with probability } P^{D}\left(x_{k}\right), \\0 & \text { with probability } 1-P^{D}\left(x_{k}\right) .\end{array}\right.$$Using the matrix notation, we get$$p\left(O_{k} \mid x_{k}\right)=\left\{\begin{array}{ll}1-P^{ D }\left(x_{k}\right) & \text { if } O_{k}=[] \\P^{ D }\left(x_{k}\right) g_{k}\left(o_{k} \mid x_{k}\right) & \text { if } O_{k}=o_{k}\end{array}\right.$$Note: this captures both the probability of detection and, if detected, the distribution of the detection.Given $x_{k}$, the set of vectors in $O_{k}$ is a Bernoulli random finite set.  Gaussian sum filteringNearest neighbours and oribabilistic data associations SOTs use only one Gaussian for approximation. In many complicated scenarious this approximaation is bad. **Idea**: approximate the postrerior - as Gaussian mixture (more than one component) with limithed amount of Gaussians.$$p^{G S F}\left(x_{k-1} \mid Z_{1: k-1}\right)=\sum_{h_{k-1}=1}^{\mathcal{H}_{k-1}} w_{k-1}^{h_{k-1}} p_{k-1 \mid k-1}^{h_{k-1}}\left(x_{k-1}\right)$$  $$\breve{p}^{G S F}\left(x_{k} \mid Z_{1: k}\right)=\sum_{h_{k}=1}^{\dot{\mathcal{H}_{k-1}} \times\left(m_{k}+1\right)} \breve{W}_{k}^{h_{k}} \breve{p}_{k \mid k}^{h_{k}}\left(x_{k}\right)$$**How reduce number of hypotheses?**1) **Pruning** - prune all hypotheses whise weights are smaller than a theshold$$\begin{array}{l}\text { Algorithm 1 Pruning hypotheses with small weights. } \\\hline \text { 1: Input: $\gamma, w^{i}, \hat{x}^{i}, P^{i}, i=1, \ldots, \mathcal{H}$.} \\\text { 2: Output: $\dot{w}^{i}, \dot{x}^{i}, \dot{P}^{i}, i=1, \ldots, \mathcal{H}^{\prime}$ } \\\text { 3: ind $=$ find $\left(\left[w^{1}, \ldots, w^{\mathcal{H}}\right]>\gamma\right)$.} \\\text { 4: Gives a list 'ind' with indexes of weights $>\gamma$.} \\\text { 5: Set $\hat{\mathcal{H}}=$ length $($ ind $)$ and compute $c=\sum_{i=1}^{\mathcal{H}} w^{\text {ind }(i)}$. } \\\text { 6: for $i=1$ to $\mathcal{H}$ do} \\\text { 7: $\quad$ Set $\hat{w}^{i}=w^{i n d(i)} / c, \dot{x}^{i}=\hat{x}^{i n d(i)}$ and $\dot{P}^{i}=P^{i n d(i)}$end for} \\\hline\end{array}$$2) **Merging**   Module 3: Tracking a known number of objectsn (known number of objects) - is assumed to be both known and constant**Pros**    1) no need to figure number of objects    2) no need data associationWith comparing with KF we have **new challenges**:    1) missed detection    2) clutter detection (false detection - clutter is more rancdom (no structure))    3) unknown DA (which is clutter, which is object)  DA - data association Creating cost matrixAssume:n - number of objectsm - number of measurements$$ - log(0) = - \inf $$assignment matrix : $$A=\left[\begin{array}{cccc|cccc}A^{1,1} & A^{1,2} & \ldots & A^{1, m} & A^{1, m+1} & 0 & \ldots & 0 \\A^{2,1} & A^{2,2} & \ldots & A^{2, m} & 0 & A^{2, m+2} & \ldots & 0 \\\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\A^{n, 1} & A^{n, 2} & \ldots & A^{n, m} & 0 & 0 & \ldots & A^{n, m+n}\end{array}\right]$$     Linear sum assignment optimization techniques:    * Hungarian    * Murty    * Gibbs sampling GNN - Global Nearest Neighbours JPDA - Joint Probability Data association MHT - multi hypotheses tracker    special case with M = 1, MHT becomes GNN    * MHT-HO - hypotheses oriented    * MHT-TO - track oriented Density operations:    - grouping by gating    - merging (use KL divergence)    - merging (using EM algorithm) MHT estimator - MAP, expected value<jupyter_code>%load_ext autoreload
%autoreload 2

import os, sys
import numpy as np
import matplotlib.pyplot as plt
import mot<jupyter_output><empty_output><jupyter_text>Gaussian sum filteringNearest neighbours and oribabilistic data associations SOTs use only one Gaussian for approximation. In many complicated scenarious this approximaation is bad. **Idea**: approxaimation the postrerior - as Gaussian mixture (more than one component) with limithed amount of Gaussians.$$p^{G S F}\left(x_{k-1} \mid Z_{1: k-1}\right)=\sum_{h_{k-1}=1}^{\mathcal{H}_{k-1}} w_{k-1}^{h_{k-1}} p_{k-1 \mid k-1}^{h_{k-1}}\left(x_{k-1}\right)$$  $$\breve{p}^{G S F}\left(x_{k} \mid Z_{1: k}\right)=\sum_{h_{k}=1}^{\dot{\mathcal{H}_{k-1}} \times\left(m_{k}+1\right)} \breve{W}_{k}^{h_{k}} \breve{p}_{k \mid k}^{h_{k}}\left(x_{k}\right)$$How reduce number of hypotheses?1) Pruning -2) Merging  Multiple object tracking- uncertainty about the number of objects- uncertainty about when and where the objects appear and dissapear- like before: uncertain object states  RFS - random finite setsRFS is a set where both the cardinality and the variables within the set is random.For describing RFS we will use multiobject pdf.cardinality - |x| **multiobject pdf**    - non negative function on sets that integrates to one    - contains two factors and captures both        - distribution over cardinality        - distribution over the emenebts of the sets    - equals of set with same elements in different order$$p_{\mathbf{x}}(\mathbf{x})=\left\{\begin{array}{ll}\mathcal{N}(v ; 0,1) & \text { if } \mathbf{x}=\{v\} \\0 & \text { if }|\mathbf{x}| \neq 1\end{array}\right.$$<jupyter_code>## Set integrals<jupyter_output><empty_output><jupyter_text>$$\begin{aligned}\operatorname{Pr}[|\mathbf{x}|=n] &=\frac{1}{n !} \int p_{\mathbf{x}}\left(\left\{x_{1}, \ldots, x_{n}\right\}\right) \mathrm{d} x_{1} \cdots \mathrm{d} x_{n} \\&=\frac{1}{n !} \int \exp (-\bar{\lambda}) \lambda\left(x_{1}\right) \cdots \lambda\left(x_{n}\right) \mathrm{d} x_{1} \cdots \mathrm{d} x_{n} \\&=\frac{1}{n !} \exp (-\bar{\lambda}) \prod_{i=1}^{n} \int \lambda\left(x_{i}\right) \mathrm{d} x_{i} \\&=\frac{1}{n !} \exp (-\bar{\lambda}) \bar{\lambda}^{n} \\&=\operatorname{Po}(n ; \bar{\lambda})\end{aligned}$$ $$\begin{array}{l}\text { Algorithm 2 Sampling Bernoulli RFSs } \\\hline \text { 1: Initialize } \mathbf{x}=\emptyset \\\text { 2: if rand }<\mathrm{r} \text { then } \\\text { 3: } \quad x \sim p_{x}(\cdot) \\\text { 4: } \quad \mathbf{x}=\{x\} \\\text { 5: end if } \\\hline\end{array}$$ Algorithm 3 Sampling a MB RFS1: Initialize $\mathbf{x}=\emptyset$2 : for $i=1$ to $N$ do3: if rand $<r_{i}$ then$4: \quad x_{i} \sim p_{i}(\cdot)$5: $\quad \mathbf{x}=\mathbf{x} \cup\left\{x_{i}\right\}$6: end if7: end for$$\begin{array}{l}\text { Algorithm 3 Sampling a MB RFS } \\\hline \text { 1: Initialize $\mathbf{x}=\emptyset$} \\\text { 2: if rand }<\mathrm{r} \text { then } \\\text { 3: } \quad x \sim p_{x}(\cdot) \\\text { 4: } \quad \mathbf{x}=\{x\} \\\text { 5: end if } \\\hline\end{array}$$ $$Algorithm Sampling a MBM RFS1: Initialize $\mathbf{x}=\emptyset$2: Generate $h \sim \operatorname{Cat}(w)$3: for $i=1$ to $N$ do4: if rand $<r_{i}^{h}$ then5:$x_{i} \sim p_{i}^{h}(\cdot)$6:$\mathbf{x}=\mathbf{x} \cup\left\{x_{i}\right\}$7: end if8: end for$$    Bernoulli north modelAt time k an object is born with probability $r_k^B$   MOT with conhugate prior. PMBM tracker.📺 [Part 5: Multiple Object Tracking using conjugate priors](https://youtube.com/playlist?list=PLadnyz93xCLjl51PzSoFhLLSp2hAYDY0H)In FOV we represent the objects using Berniuli denisities (existence probability + state density (gm)). If existence probability will be to low - we will remove this Berniulli entirely.How we can deal with appeared objects. There are two methods:1) Add addtitional bernoulli densitoes where objects are believer to apperare. For example, add bernoulli on edge of FOV. For vehicle, on edge of road. This approach used in MBM filters. 2) Add additional Bernoulli densities ig there is a detection. This measurement driven approach using in PMBM filters.  algorithm- Initialize PMBM_tracker    1) init MBM set    2) init PPP set- for k timestep in K:    * PMBM_predict        PPP_predict            for each component in PPP intensity                                new ppp component state                new_weight = old_weight + log($P_S$)            PPP intensity <- birth model (some model which spawns ppp)                MBM_predict            for each STH in MBM component perform GD update                new sth state <- Kalman predict(old sth state)        * PMBM update        MBM update            for each sth which is parent now create                1) missdetection STH                    likelihood =                         PPP - spawn new tracks            for each PPP which in the gate of considering measurement            create new tracks                                                                      * PMBM_update(measurements)     (**undetected objects**: remain undetected or detected for the first time, **previously detected object**: misdetected or detected again)                - update of PPP intensity: for undetected objects that remain undetected                - update of potential new object detected for the first time => **new Bernoulli**        - update of Bernoulli with associated measurement (simillar to MBM filter)            * use gating to remover bery unlokely association and group Bernoullies/measeuremnents            * for eagch group form cost matrix with negative log likelihood            * use some algorithms to find M associations (Murty, Gibbs sampling)                    - update of misdetected Bernoulli - (similar to MBM filter)        - posterior log wights            * estimates[k] = PMBM_estimate()    * PMBM_reduction        - PPP_prune()                - Bern_prune()            * PMBM_predict()            - Poisson predict            for component in componens:                component.state = gausiian_density.predict(component.state)                component.weight += log(proba_survival)                        - Bernoulli predict              PMBM densityA motivation for changinng birth model  PMBM tracker - method using Bayessian recursion, while it models undetected and detected objects as two different probability distribuitions. It is a RFS based algorithm. The undetected objects are mod- elled using a distribution, while detected objects are modelled by a Multi-Bernoulli Mixture (MBM). Combining the two densities gives a density shown in equation (2.44), where Pk|k is the Poisson density, MBMk|k is the Multi-Bernoulli mixture. It also allows to compute the prediction and update steps for single object densities instead of full multi-object predictions and updates, reducing the complexity.$$$P M B M _{k \mid k}( X )=\sum_{ X ^{u} \uplus X ^{d}= X } P _{k \mid k}\left( X ^{u}\right) M B M _{k \mid k}\left( X ^{d}\right)$$In [11] they derive a proof of conjugacy for the PMBM filter, meaning that the dis- tribution after the prediction and update step will be of the same distribution form as the initial prior. Thus, given the updated PMBM density from previous time step PMBMk|k(Xk) and motion model p(Xk+1|Xk) the next time step’s predicted PMBM density can be written:Thus track oriented is efficient than hypothesis oriented.Each detected target is a modelles as a Bernoulli distribtion.In track oriented approach, this Bernoulli distribution is included in a t ttrach.Track oriented PMBM forms global association hypotheses from the possible combinations of the single target hypotheses, containing one single target hypothesus from each potential target, with the restriction that one measurement can only be assocoated with one STH. $$Algorithm 2.1 Pseudo code for one prediction, update, estimation and reduct step for the PMBM algorithm Inputs:Posterior from previous time step: $P M B M _{k-1 \mid k-1}$ New set of measurements: $Z$ Output:Posterior for current time step: $P M B M _{k \mid k}$Perform prediction, i.e. acquire $P M B M _{k \mid k-1}$Find potential new targets among the Poisson components:for $z \in Z$ do- Perform gating w.r.t all Poisson components if Number of gated Poisson components $>1$ then- Perform Moment Matching end if $z$ within gate of $\bar{x}_{j, i}^{\mu}$ then new detected target $\bar{x}_{j, i}^{d}$ Create\begin{tabular}{l}$-$ \\\hline\end{tabular}end end Update the previously detected targets:for $i \in\left[1, N_{d}\right]$ dofor $s \in\left[1,\right.$ Number of Single Target Hypotheses for $\left.\bar{x}_{j, i}^{d}\right]$ do Create missed detection hypothesis- Perform gating and create plausible hypotheses end end for $j \in[1,$ Number of Global Hypotheses] $d o$- Create cost matrix - Generate the $K$ best global hypotheses using Murty's Algorithm end- Estimate the target statesPerform reduction:Prune Poisson components with $w_{i}^{u}<\Gamma^{u}$ Prune Bernoulli components with $w_{j, i}^{d}<\Gamma^{d}$ Prune Global Hypotheses with $w^{j}<\Gamma^{j}$$$ In MBM filters, an MB birth model is used:In the prediction, add $N_{k}^{ B }$ birth components to each $MB$ in the mixtureIf an object actually appeared and was detected, then in the update this detection can be associated to the birth component, and we can start to track the object.But why add birth components before we know if there are any detections?Could the addition of new Bernoulli components, corresponding to the new potential  objects, not be measurement-driven?Yes, it could, if we use a PPP birth model instead of a MB birth model. Beyond multi-object conjugacy, why is the PMBM model useful for MOT?- Some uncertainties in MOT:- Are there any objects? How many?- Detected objects: Bernoulli existence probabilities- Undetected objects: PPP intensity- If so, what are their states?- Detected objects: Bernoulli state densities- Undetected objects: PPP intensity- Data association? Captured by the MB mixture. THE PBMB MODEL: DETECTED AND UNDETECTED OBJECTSIn the PMBM model, the set of objects $x _{k}$ at time $k$Union of detected objects and undetected objects $x _{k}= x _{k}^{d} \biguplus x _{k}^{u}$- Detected $x _{k}^{d}$ : objects the sensors have detected at least once- Undetected $x _{k}^{u}$ : objects that have never detectedWe are doing tracking based on detections, how could we track undetected objects?!- Representation of their possible existence.- Actually included in many tracking algorithms.- MBM filter: any Bernoulli to which a detection has never been associatedHere it is made explicit. PMBM DENSITYThe Poisson Multi-Bernoulli Mixture density is defined as$$P M B M _{k \mid k}\left( x _{k}\right)=\sum_{ x _{k}^{\omega} \biguplus x _{k}^{d}= x _{k}} P _{k \mid k}^{u}\left( x _{k}^{u}\right) M B M _{k \mid k}^{d}\left( x _{k}^{d}\right)$$PPP density $P _{k \mid k}^{u}(\cdot)$ for undetected objects, typically with mixture intensity,$$\lambda_{k \mid k}^{u}\left(x_{k}\right)=\sum_{t=1}^{N_{k}^{u}} w_{k \mid k}^{u, t} p_{k \mid k}^{u, t}\left(x_{k}\right), \quad\left\{\left(w_{k \mid k}^{u, t}, p_{k \mid k}^{u, t}(\cdot)\right)\right\}_{t=1}^{N_{k}^{u}}$$Multi-Bernoulli Mixture density $M B M _{k \mid k}^{d}(\cdot)$ for detected objects, with parameters$$\left\{\left(\ell_{k \mid k}^{h_{k}},\left\{\left(r_{k \mid k}^{i, h_{k}}, p_{k \mid k}^{i, h_{k}}(\cdot)\right)\right\}_{i=1}^{N_{k}^{h_{k}}}\right)\right\}_{h_{k}=1}^{ H _{k}}$$PMBM density parameterised by the mixture intensity parameters, the MB log-weights, and the Bernoulli parameters of the MBs. If we design an MOT algorithm for the PMBM density, we get a PMBM filterPMBM filter: pseudo-codeFor $k=1,2, \ldots, K$PredictionUpdateReductionEstimation POISSON MULTI-BERNOULLI MIXTURE PREDICTIONPosterior PMBM parametersPrediction$$P M B M _{k+1 \mid k}\left( x _{k}\right)=\int p\left( x _{k+1} \mid x _{k}\right) P M B M _{k \mid k}\left( x _{k}\right) \delta x _{k}$$with transition density $p\left( x _{k+1} \mid x _{k}\right)$ with Probability of survival $P_{k}^{S}\left(x_{k}\right)$ Transition density $\pi_{k+1}\left(x_{k+1} \mid x_{k}\right)$ PPP birth model: $\left\{w_{k+1}^{ B , t}, p_{k+1}^{ B , i}(\cdot)\right\}_{i=1}^{N_{k+1}^{ B +1}}$Predicted PMBM parameters PMBM prediction with PPP birthUndetected and detected objects can be predicted independentlyPredicted undetected parameters consist of union of- predicted parameters from previous time step, and- birth parameters- Each MB can be predicted independently of the other MBsNumber of parameters increases (we add PPP birth params. to the undetected PPP) UNDETECTED PPP PREDICTIONPredicted PPP intensity for undetected objects,$$\lambda_{k+1 \mid k}^{ u }\left(x_{k+1}\right)=\int p\left(x_{k+1} \mid x_{k}\right) P^{S}\left(x_{k}\right) \lambda_{k \mid k}^{ u }\left(x_{k}\right) d x_{k}+\lambda_{k+1}^{ B }\left(x_{k+1}\right)$$The predicted intensity $\lambda_{k+1 \mid k}^{ u }\left(x_{k+1}\right)$ is the sum two intensities:Prediction of the surviving undetected objects $\int p\left(x_{k+1} \mid x_{k}\right) P^{S}\left(x_{k}\right) \lambda_{k \mid k}^{ u }\left(x_{k}\right) d x_{k}$Birth of new undetected objects $\lambda_{k+1}^{B}\left(x_{k+1}\right)$Mixture representations$$\lambda_{k+1 \mid k}^{ u }\left(x_{k+1}\right)=\sum_{t=1}^{N_{k}^{u}} w_{k \mid k}^{ u , t} \int p\left(x_{k+1} \mid x_{k}\right) P^{S}\left(x_{k}\right) p_{k \mid k}^{ u , t}\left(x_{k}\right) d x_{k}+\sum_{i=1}^{N_{k+1}^{ B }} w_{k+1}^{ B , i} p_{k+1}^{ B , i}\left(x_{k+1}\right)$$ Undetected PPP prediction: pseudo-codePosterior parameters: $\left\{\left(w_{k \mid k}^{ u , t}, p_{k \mid k}^{ u , t}(\cdot)\right)\right\}_{t=1}^{N_{k}^{u}}$Predicted parameters:$$\begin{array}{l}\left\{\left(w_{k+1 \mid k}^{ u , t}, p_{k+1 \mid k}^{ u , t}(\cdot)\right)\right\}_{t=1}^{N_{k+1}^{ u }} \\\quad=\left\{\operatorname{Predict}\left(w_{k \mid k}^{ u , t^{\prime}}, p_{k \mid k}^{ u , t^{\prime}}(\cdot)\right)\right\}_{t^{\prime}=1}^{N_{k}^{ u }} \bigcup\left\{\left(w_{k+1}^{ B , t^{\prime \prime}}, p_{k+1}^{ B , t^{\prime \prime}}(\cdot)\right)\right\}_{t^{\prime \prime}=1}^{N_{k+1}^{ B }}\end{array}$$Increased number of mixture parameters $N_{k+1}^{ u }=N_{k}^{ u }+N_{k+1}^{ B }$ PREDICTION OF A POSTERIOR MIXTURE COMPONENTThe predicted PPP weight and density,$$\left(w_{k+1 \mid k}^{ u , t}, p_{k+1 \mid k}^{ u , t}(\cdot)\right)=\operatorname{Predict}\left(w_{k \mid k}^{ u , t}, p_{k \mid k}^{ u , t}(\cdot)\right)$$are given by$$w_{k+1 \mid k}^{ u , t} p_{k+1 \mid k}^{ u , t}\left(x_{k+1}\right)=w_{k \mid k}^{ u , t} \int \pi_{k+1}\left(x_{k+1} \mid x_{k}\right) P^{S}\left(x_{k}\right) p_{k \mid k}^{ u , t}\left(x_{k}^{i}\right) d x_{k}$$and are$$\begin{aligned}w_{k+1 \mid k}^{ u , t} &=w_{k \mid k}^{ u , t} P_{ u , t}^{ S } \\p_{k+1 \mid k}^{ u , t}\left(x_{k+1}\right) &=\int \pi_{k+1}\left(x_{k+1} \mid x_{k}\right) \frac{P^{ S }\left(x_{k}\right) p_{k \mid k}^{ u , t}\left(x_{k}^{i}\right)}{P_{ u , t}^{ S }} d x_{k}\end{aligned}$$where$$P_{ u , t}^{ S }=\int P^{S}\left(x_{k}\right) p_{k \mid k}^{ u , t}\left(x_{k}\right) d x_{k}$$ EXAMPLE: UNDETECTED PPP PREDICTIONConstant $P^{S}$, linear Gaussian motion mode$$P^{S}(x)=P^{S} \text { and } \pi_{k+1}\left(x_{k+1} \mid x_{k}\right)= N \left(x_{k+1} ; F_{k+1} x_{k}, Q_{k+1}\right)$$PPP birth with Gaussian mixture intensity $\sum_{i=1}^{N_{k+1}^{ B }} w_{k+1}^{ B , i} N \left(x_{k+1} ; \mu_{k+1}^{ B , i}, P_{k+1}^{ B , i}\right)$- Posterior intensity $\lambda_{k \mid k}^{ u }\left(x_{k}\right)=\sum_{t=1}^{N_{k}^{u}} w_{k \mid k}^{ u , t} N \left(x_{k} ; \mu_{k \mid k}^{ u , t}, P_{k \mid k}^{ u , t}\right)$Predicted intensity,$$\begin{aligned}\lambda_{k+1 \mid k}^{ u }\left(x_{k+1}\right)=& \sum_{t=1}^{N_{k}^{u}} w_{k \mid k}^{ u , t} P^{S} N \left(x_{k+1} ; F_{k+1} \mu_{k \mid k}^{ u , t}, F_{k+1} P_{k \mid k}^{ u , t} F_{k+1}^{ T }+Q_{k+1}\right) \\&+\sum_{i=1}^{N_{k+1}^{ B }} w_{k+1}^{ B , i} N \left(x_{k+1} ; \mu_{k+1}^{ B , i}, P_{k+1}^{ B , i}\right)\end{aligned}$$ POISSON MULTI-BERNOULLI MIXTURE UPDATE, IN SUMMARYPMBM update for the standard point object modelsFor each prior MB, multiple data associations- For each prior $MB$ and each data association, we get an $MB$ in the posterior MBMFor each Bernoulli, two possibilities:- Either associated to one of the measurements,or misdetected.Any measurement not associated to a prior Bernoulli is eitherclutter- or from an object detected for the first timeWe get a new Bernoulli PMBM UPDATE: DATA ASSOCIATIONWith an MB birth model, Initiation of potential new objects: add birth Bernoulli components in predictionWhen handling the data association, each detection is associated to- one of the prior Bernoullis, or- the clutter PPPWith a PPP birth model, Initiation of potential new objects: measurement driven.When handling the data association, each detection is associated to- one of the prior Bernoullis,- the undetected PPP or the clutter PPPImportant: we treat the potential new objects and the clutter jointly!Convenient to reformulate assignment problem: assign the measurements DATA ASSOCIATION VARIABLE FOR $M_{K}$ DETECTIONS,Let there be $m_{k}$ measurements and $n_{k}$ objects.The association for measurement $z_{k}^{j}$ is denoted $\psi_{k}^{j}$An association for all $m_{k}$ measurement is denoted$$\psi_{k}=\left[\psi_{k}^{1}, \psi_{k}^{2}, \ldots, \psi_{k}^{j}, \ldots, \psi_{k}^{m_{k}}\right]$$$\psi_{k}^{j}$ is defined similarly to how $\theta_{k}^{i}$ was defined,$\psi_{k}^{j}=\left\{\begin{array}{ll}i & \text { if measurement } j \text { is associated to object } i \\ 0 & \text { if measurement } j \text { is associated either to a potential new object, or to clutter }\end{array}\right.$ DATA ASSOCIATION VARIABLE FOR $M_{K}$ DETECTIONS, 2$\Psi_{k}$ is the set of valid association events at time $k$.For $\psi_{k} \in \Psi_{k},$ the following must hold:1. Each measurement must be either from a previously detected object, or clutter/potential new object,$$\psi_{k}^{j} \in\left\{0, \ldots, n_{k}\right\}, \forall j \in\left\{1, \ldots, m_{k}\right\}$$2. Point object assumption: For any pair of two measurements, they cannot be associated to the same previously detected object,$$\forall j, j^{\prime} \in\left\{1, \ldots, m_{k}\right\}$$ Note that 1 . and 2 . on the previous slide together implicitly ensures that we do not associate more than $n_{k}$ measurements to the $n_{k}$ objects.In what follows, unless otherwise stated, we consider associations $\psi_{k} \in \Psi_{k}$.Given a $\psi$, we can find the equivalent $\theta$, and vice versa.$$\begin{aligned}\psi^{j}=i & \Leftrightarrow \quad \theta^{i}=j \\\psi^{j}=0 & \Leftrightarrow \quad \nexists i: \theta^{i}=j \\\nexists j: \psi^{j}=i & \Leftrightarrow \quad \theta^{i}=0\end{aligned}$$ Hypothesis oriented-PMBM update: pseudo-codeInput: $\lambda_{k \mid k-1}^{ u }\left(x_{k}\right),\left\{\left(\ell^{h_{k-1}},\left\{\left(r_{k \mid k-1}^{i, h_{k-1}}, p_{k \mid k-1}^{i, h_{k-1}}(\cdot)\right)\right\}_{i=1}^{N_{k-1}^{n_{k-1}}}\right)\right\}_{h_{k-1}=1}^{ H _{k-1}}$Misdetection update: $\lambda_{k \mid k}^{ u }\left(x_{k}\right)=\left(1-P^{ D }\left(x_{k}\right)\right) \lambda_{k \mid k-1}^{ u }\left(x_{k}\right)$Initialise: $h_{k}=0$For $h_{k-1}=1, \ldots, H _{k-1}$Create cost matrix $L^{h_{k}-1},$ and compute $M_{h_{k-1}}$ associations $\psi_{m}$For $m=1, \ldots, M_{h_{k-1}}$Increase: $h_{k} \leftarrow h_{k}+1$Compute posterior MB parameters: detected, misdetected \& new Bernoulli, log-weight $\tilde{\ell}^{h}$Set $H _{k}=h_{k}$Normalise log-weights $\ell^{h_{k}} \leftarrow \tilde{\ell}^{h_{k}}$Output: $\left\{\left(\ell^{h_{k}},\left\{\left(r_{k \mid k}^{i, h_{k}}, p_{k \mid k}^{i, h_{k}}(\cdot)\right)\right\}_{i=1}^{N_{k}^{h_{k}}}\right)\right\}_{h_{k}=1}^{ H _{k}}$ POISSON MULTI-BERNOULLI MIXTURE UPDATE, "BUILIDING BLOCKS"'- Undetected object: remain undetected, or detected for the first timePreviously detected object: misdetected, or detected againImportant "builiding blocks" of PMBM update:update of PPP intensity for undetected objects that remain undetectedupdate of potential new object detected for the first time $\Rightarrow$ new Bernoulliupdate of Bernoulli with associated measurement - similar to MBM-filterupdate of misdetected Bernoulli - similar to MBM-filterposterior log-weights UNDETECTED OBJECTS MISDETECTED AGAINPosterior PPP intensity for objects that remain undetected,$$\lambda_{k \mid k}^{ u }(x)=\left(1-P^{ D }(x)\right) \lambda_{k \mid k-1}^{ u }(x)$$- Posterior intensity is lower/higher in areas where $\left(1-P^{D}(x)\right)$ is low/high, because it is unlikely/likely that an object was not detected there- Mixture representation of intensity$$\begin{aligned}\lambda_{k \mid k}^{ u }\left(x_{k}\right)=\sum_{t} w_{k \mid k-1}^{ u , t}\left(1-P^{ D }(x)\right) p_{k \mid k-1}^{ u , t}\left(x_{k}\right) \\=\sum_{t} w_{k \mid k-1}^{ u , t} P_{ u , t}^{ MD } \frac{\left(1-P^{ D }(x)\right) p_{k \mid k-1}^{ u , t}\left(x_{k}\right)}{P_{ u , t}^{ MD }} \\\text { where } P_{ u , t}^{ MD }=\int\left(1-P^{ D }(x)\right) p_{k \mid k-1}^{ u , t}\left(x_{k}\right) d x_{k}\end{aligned}$$ OBJECT DETECTED FOR THE FIRST TIME: NEW BERNOULLIIf $\psi^{j}=0,$ then the measurement $z_{k}^{j}$ is either clutter or from a previously undetected object.New Bernoulli component in the posterior MB, with parameters$$\begin{aligned}r_{k \mid k}^{j} &=\frac{\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)}{\lambda_{c}\left(z_{k}^{j}\right)+\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)}, \quad \rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)=\int P^{ D }\left(x_{k}\right) g_{k}\left(z_{k}^{j} \mid x_{k}\right) \lambda_{k \mid k-1}^{ u }\left(x_{k}\right) d x_{k} \\p_{k \mid k}^{j}\left(x_{k}\right) &=\frac{P^{ D }\left(x_{k}\right) g_{k}\left(z_{k}^{j} \mid x_{k}\right) \lambda_{k \mid k-1}^{ u }\left(x_{k}\right)}{\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)}\end{aligned}$$Posterior $r$ conditioned on $v$Relative intensity of: 1 ) detection from previously undetected object; and, 2) clutterPredicted log-likelihood$$\ell_{k}^{ u , j}=\log \left(\lambda_{c}\left(z_{k}^{j}\right)+\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)\right)$$ NEW BERNOULLI: PROBABILITY OF EXISTENCE $<1 ?$Earlier we had that, conditioned on the data association, $r=1$How can we now have a new Bernoulli for which $r<1 ?$It represents two possibilities:Detection was from clutter $-$ no new object Likelihood $\lambda_{c}\left(z_{k}^{j}\right)$Detection was from a new object$$\text { Likelihood } \rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)=\int P^{ D }\left(x_{k}\right) g_{k}\left(z_{k}^{j} \mid x_{k}\right) \lambda_{k \mid k-1}^{ u }\left(x_{k}\right) d x_{k}$$- Represented compactly as a new Bernoulli with probability of existence$$r_{k \mid k}^{j}=\frac{\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)}{\lambda_{c}\left(z_{k}^{j}\right)+\rho_{k \mid k-1}^{ u }\left(z_{k}^{j}\right)}$$ NON-NORMALISED POSTERIOR LOG-WEIGHTSFor a prior $MB h$ and a data association $\psi_{k},$ the non-normalized posterior log-weight is$$\begin{aligned}\tilde{\ell}_{k \mid k}^{h_{k-1}, \psi_{k}} &=\underbrace{\ell_{k \mid k-1}^{h_{k-1}}}_{\text {Prior }}+\underbrace{\sum_{i: \nexists j: \psi^{j}=i} \ell_{k}^{i, 0, h}}_{\text {Misdetection }}+\underbrace{\sum_{j: \psi^{j} \neq 0} \ell_{k}^{\psi^{j}, j, h}}_{\text {Assoc. meas. }}+\underbrace{\sum_{j: \psi^{j}=0} \ell_{k}^{ u , j}}_{\text {Clutter or potential new object }} \\&=\ell_{k \mid k-1}^{h_{k-1}}+\sum_{i=1}^{N^{h}} \ell_{k}^{i, 0, h}+\sum_{j: \psi^{j} \neq 0}\left[\ell_{k}^{\psi^{j}, j, h}-\ell_{k}^{\psi^{j}, 0, h}\right]+\sum_{j: \psi^{j}=0} \ell_{k}^{ u , j}\end{aligned}$$ NON-NORMALISED POSTERIOR LOG-WEIGHTSFor a prior $MB h$ and a data association $\psi_{k},$ the non-normalized posterior log-weight is$$\begin{aligned}\tilde{\ell}_{k \mid k}^{h_{k-1}, \psi_{k}} &=\underbrace{\ell_{k \mid k-1}^{h_{k-1}}}_{\text {Prior }}+\underbrace{\sum_{i: \nexists j: \psi^{j}=i} \ell_{k}^{i, 0, h}}_{\text {Misdetection }}+\underbrace{\sum_{j: \psi^{j} \neq 0} \ell_{k}^{\psi^{j}, j, h}}_{\text {Assoc. meas. }}+\underbrace{\sum_{j: \psi^{j}=0} \ell_{k}^{ u , j}}_{\text {Clutter or potential new object }} \\&=\ell_{k \mid k-1}^{h_{k-1}}+\sum_{i=1}^{N^{h}} \ell_{k}^{i, 0, h}+\sum_{j: \psi^{j} \neq 0}\left[\ell_{k}^{\psi^{j}, j, h}-\ell_{k}^{\psi^{j}, 0, h}\right]+\sum_{j: \psi^{j}=0} \ell_{k}^{ u , j} \\&=\ell_{k \mid k-1}^{h_{k-1}}+\sum_{j=1}^{m_{k}} \tilde{\ell}_{k}^{j, h}+\text { Constant independent of } \psi_{k}\end{aligned}$$where$$\tilde{\ell}_{k}^{j, h}=\left\{\begin{array}{ll}\ell_{k}^{\psi^{j}, j, h}-\ell_{k}^{\psi^{j}, 0, h} & \text { if } \psi^{j} \neq 0 \\\ell_{k}^{ u , j} & \text { if } \psi^{j}=0\end{array}\right.$$ there is an index $j$ for multi-bernoulli mixtureeach j correspond to a global hypothesis.*Global hypothesis represents possible association of measurements to potentially detected targets.(It can be expresses in terms of single target hypothesi)*Single target hypothesis* - sequnece of measurements associated to a potemtially detected target.Given a single target hypothesis, this potentially detected target folows a Bernloulli distribution. Each measurement starts a new single target hypothesis. At folowwing steps, new single target hypotheisi sate created by association prebious single-target hypothesis with current measuremnt or missdetection.Global hypotheses are collection of theses single target hypotheses, with the condition that no measurement is left without being assocation and a measurement can only be assignes to one singlae target hypoethesus. PMBM UPDATE: COST MATRIXLet there be $m_{k}$ detections, and consider an MB $h$ with $N^{h}$ Bernoullis. The cost matrix is$$L^{h}=\left[\begin{array}{cccccccc}-\ell^{1,1, h} & -\ell^{1,2, h} & \ldots & -\ell^{1, N^{h}, h} & -\ell^{1,0} & \infty & \ldots & \infty \\-\ell^{2,1, h} & -\ell^{2,2, h} & \ldots & -\ell^{2, N^{h}, h} & \infty & -\ell^{2,0} & \ldots & \infty \\\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\-\ell^{m_{k}, 1, h} & -\ell^{m_{k}, 2, h} & \ldots & -\ell^{m_{k}, N^{h}, h} & \infty & \infty & \ldots & -\ell^{m_{k}, 0}\end{array}\right]$$where$$\begin{aligned}\ell^{j, 0} &=\log \left(\lambda_{c}\left(z_{k}^{j}\right)+\int P^{ D }\left(x_{k}\right) g_{k}\left(z_{k}^{j} \mid x_{k}\right) \lambda_{k \mid k-1}^{ u }\left(x_{k}\right) d x_{k}\right) \\\ell^{j, i, h} &=\log \left(\frac{r_{k \mid k-1}^{i, h} \int P^{ D }\left(x_{k}^{i}\right) g_{k}\left(z_{k}^{j} \mid x_{k}^{i}\right) p_{k \mid k-1}^{i, h}\left(x_{k}^{i}\right) d x_{k}^{i}}{1-r_{k \mid k-1}^{i, h}+r_{k \mid k-1}^{i, h} \int\left(1-P^{ D }\left(x_{k}^{i}\right)\right) p_{k \mid k-1}^{i, h}\left(x_{k}^{i}\right) d x_{k}^{i}}\right)\end{aligned}$$ PMBM POST PROCESSINGAfter prediction and update, we have a PMBM density $P M B M _{k \mid k}\left( x _{k}\right)$ with params.$$\left\{\left(w_{k \mid k}^{ u , t}, p_{k \mid k}^{ u , t}(\cdot)\right)\right\}_{t=1}^{N_{k}^{u}}, \quad\left\{\left(\ell_{k \mid k}^{h_{k}},\left\{\left(r_{k \mid k}^{i, h_{k}}, p_{k \mid k}^{i, h_{k}}(\cdot)\right)\right\}_{i=1}^{N_{k}^{h_{k}}}\right)\right\}_{h_{k}=1}^{ H _{k}}$$- Reduction:- Reduce $N_{k}^{u}, H _{k}$ and $N_{k}^{h_{k}}$- Important for computational cost Pruning, merging, capping, and recyclingEstimation:Extracting a set of estimated object states from the posterior density. PMBM reduction- MBM pruning: prune $MB h_{k}$ if $\ell_{k \mid k}^{h_{k}} \leq \Gamma$- MBM capping: if $H _{k}>N_{\max },$ keep the $N_{\max }$ MBs with largest log-weights.After pruning and capping the MBM, remaining log-weights are re-normalized.- Bernoulli recycling: in each MB $h_{k},$ recycle Bernoulli $i$ if $r_{k \mid k}^{i, h}<\Gamma^{r}$- PPP reduction: pruning, merging and capping of the mixture intensity Initial prior for each Bernoulli is PPP. 3ERNOULLI RECYCLINGBernoulli recycling: basic ideaInstead of pruning Bernoullis with small $r$, approximate them as PPP, and add the intensity to undetected PPP intensity.- KL-div minimising PPP approximation: intensity $=$ Bernoulli PHD,$$\lambda_{k \mid k}^{h, i, REC }\left(x_{k}\right)=r_{k \mid k}^{h, i} p_{k \mid k}^{h, i}\left(x_{k}\right)$$- Undetected PPP intensity after recycling is$$\lambda_{k \mid k}^{ u , REC }\left(x_{k}\right)=\lambda_{k \mid k}^{ u }\left(x_{k}\right)+\sum_{h} \sum_{i: r_{k \mid k}^{h, i}<\Gamma^{r}} \exp \left(\ell_{k \mid k}^{h}\right) r_{k \mid k}^{h, i} p_{k \mid k}^{h, i}\left(x_{k}\right)$$Note that we must take the normalized hypothesis weight $\exp \left(\ell_{k \mid k}^{h}\right)$ into account WHY RECYCLING?Following the recycling, we have to reduce the undetected PPP intensity.Why not just prune right away?Recycling/pruning lowers the computational complexity, because there are fewer Bernoullis to consider in the data association.- Pruning means that we lose all information contained in what is pruned.By recycling, the information is retained approximately as a PPP.- The Bernoulli recycling threshold can therefore be considerably larger than a Bernoulli pruning threshold.- Empirical studies show that Bernoulli recycling leads to lower computational cost, without sacrificing tracking performance. REDUCING THE UNDETECTED INTENSITYUndetected intensity with mixture representation$$\lambda_{k \mid k}^{ u }\left(x_{k}\right)=\sum_{t=1}^{N_{k}^{u}} w_{k \mid k}^{ u , t} p_{k \mid k}^{ u , t}\left(x_{k}\right)$$- The number of mixture components increases over time, due to:the addition of birth in the prediction the recycling following the updateReduced using pruning, merging and capping. HO-MHT AND TO-MHT- Two MHT approaches to tracking $n$ objects:- Hypothesis oriented (HO): represent each global $n$ object hypothesis explicitly Track oriented (TO): represent each object by local hypotheses. Global $n$ object hypotheses encoded by look-up table. Track oriented is computationally more efficient.- Similar alternatives for the MB mixture in PMBM and MBM filtering- Hypothesis oriented: represent each MB explicitly- Track oriented: represent each Bernoulli by local hypotheses. Each MB (global hypothesis) encoded by look-up table. Again, track oriented is computationally more efficient. TRACK ORIENTED CONJUGATE MULTI-OBJECT FILTERSMBM filter- Add new Bernoullis in prediction- Initiate new Bernoullis in updateNew local hypothesees in update- New local hypothesees in updateLook-up table for MBs- Look-up table for MBsReduction: remove local hypotheses $\quad$ - Reduction: remove local hypotheses and global hypotheses and global hypotheses OBJECT EXISTENCE IS BINARYIn both MBM and PMBM there are Bernoullis with $0<r<1$.Expected cardinality is $r$- $r=0.5 \Rightarrow$ we expect half an object- For example, how should an autonomous car react if there is half a car in front?In reality, an object is either there, or not.Compare to $n$ object tracking: an integer number of objects, no fractions of objectsCan we have a multi-object density such that each hypothesis represents an integer number of objects?Yes, if we change to a so called MBM $_{01}$ representation.The $\delta$ -GLMB filter can be interpreted as having a MBM $_{01}$ representation. sigma G labeleled multi berniulli filter EXPANDING A BERNOULLI TO CERTAIN EXISTENCEA Bernoulli $(r, p(\cdot))$ with $r \in(0,1)$ represents two possibilities,- With probability $r$ we have exactly one object, with state pdf $p(\cdot)$.- With probability $1-r,$ we have exactly zero objects.We can represent this as a Bernoulli mixture density,$$p( x )=r B ^{1}( x )+(1-r) B ^{2}( x )$$where $B ^{1}( x )$ and $B ^{2}( x )$ are Bernoulli densities with parameters$$\left(r^{1}, p^{1}(\cdot)\right)=(1, p(\cdot)), \quad\left(r^{2}, p^{2}(\cdot)\right)=(0, \text { any pdf })$$- Instead of one Bernoulli with uncertain existence $r,$ we have two hypotheses that each have certain existence: either one object $\left(r^{1}=1\right)$ or zero objects $\left(r^{2}=0\right)$. HOW CAN WE GET TRAJECTORIES?PMBM/MBM filter outputs $\hat{ x }_{k \mid k}$Estimate at time $k$ of- Number of objects States of the objectsTrajectory: sequence of states, from initial time to end time.Two approachesSets of labelled objectsSets of trajectories New RFS: Labelled setL - some unique identifierA labelled Bernoulli RFS is, just like the name suggests, parameterised by- Probability of existence $r$object state density $p(x)$ Label $L$ A labelled MB (LMB) RFS is the union of labelled Bernoulli RFSs,$$\left\{\left(r^{i}, p^{i}(\cdot), L^{i}\right)\right\}_{i}$$where the labels are unique.An LMB whose labels are not unique defeats its own purpose. The definition of the LMB multi-object density ensures the uniqueness. LABELLED MBM FILTEREarlier we saw that with MB birth, we get an MBM filter.- If the birth model is labelled MB, we get a labelled MBM (LMBM) filterLabel uniqueness over time is ensured by labelling the birth appropriately, e.g.,- Labelled multi-Bernoulli birth with parameters$$\left\{\left(r_{k}^{ B , i}, p_{k}^{ B , i}(\cdot), L_{k}^{ B , i}\right)\right\}_{i}$$- The labels are tuples$$L_{k}^{ B , i}=\left(k, \alpha_{k}(i)\right)$$where the identifiers $\alpha_{k}(i)$ are such that $\alpha_{k}(i) \neq \alpha_{k}\left(i^{\prime}\right)$ if $i \neq i^{\prime} .$- A simple and natural choice is $\alpha_{k}(i)=i$.  LABELLED MBM MULTI-OBJECT CONJUGATE PRIORLabelled MBM (LMBM) multi-object conjugate priorPrediction: $\quad L M B M _{k \mid k-1}\left( x _{k}\right)=\int p\left( x _{k} \mid x _{k-1}\right) L M B M _{k-1 \mid k-1}\left( x _{k-1}\right) \delta x _{k-1}$Update: $\quad L M B M _{k \mid k}\left( x _{k}\right)=\frac{p\left( z _{k} \mid x _{k}\right) L M B M _{k \mid k-1}\left( x _{k}\right)}{\int p\left( z _{k} \mid x _{k}^{\prime}\right) L M B M _{k \mid k-1}\left( x _{k}^{\prime}\right) \delta x _{k}^{\prime}}$One of the first multi-object conjugate priors for point object tracking to be presented in MOT literature is called the $\delta$ -Generalised Labelled Multi-Bernoulli ( $\delta$ -GLMB) filter.Labelled Multi-Bernoulli birth- MBM $_{01}$ density representation LABELLED MBM FILTER: PREDICTION AND UPDATE- An object label neither changes over time, nor changes due to the detection processTherefore, the labels are unaffected by the prediction and the updateThe prediction and update of the labelled Bernoulli parameters $r$ and $p(\cdot)$ in an LMBM filter is the same as the prediction and update of Bernoulli parameters $r$ and $p(\cdot)$ in the MBM filter.Some challenges when using labels to form trajectories: gaps and switching THE PROBLEM WITH LABELLED PPPA labelled Bernoulli $(r, p(\cdot), L)$ represents either no object, or one objectIf we sample and obtain an object, it must have label $L$ This generalises to LMB and LMBM - we know what the unique labels areA labelled PPP with intensity $\lambda(x)$ and some label distribution. Represents any finite number of labelled objects,$$\left(x^{1}, L^{1}\right),\left(x^{2}, L^{2}\right), \ldots\left(x^{i}, L^{i}\right), \ldots$$The labelled PPP objects are iid. If we sample,The states $x^{i}$ are iid, with PPP intensity $\lambda(x)$ The labels are iid, with some label distribution over the labels $L^{1}, L^{2}, \ldots L^{i}, \ldots$It is possible (non-zero probability) that many objects have the same label Label uniqueness cannot be guaranteed with la PPP HEURISTICALLY LABELLED PMBM FILTERIdea: heuristically modify the PMBM algorithmWhen a new Bernoulli is initiated by a measurement $z_{k}^{j},$ it is given a unique identifier, e.g., $(k, j)$, sometimes called meta-data- Lacks a certain theoretical elegance, but does work in practiceHeuristically "labelled" PMBM filter:No labels for the undetected PPP Meta-data used to heuristically label Bernoullis when they are first initiated; treatment of labelled Bernoulli in subsequent time steps is same as in LMBM. Lacks a sound theoretical basis, not a true labelled filter- In comparison, labelled MBM has a sound theoretical basisImportantly: "labelled" PMBM does not solve the inherent challenges involved with using labels to form trajectories, e.g., gaps and switching.  Challenges when using labels to  trajectories https://cdn.mathpix.com/snip/images/UT-I3xn-Dok5pvRPDY9J2i8zo85bpIJ-IotWEKzZy0w.original.fullsize.png ![image](https://cdn.mathpix.com/snip/images/MeV0I49QiTwQicFbNzvTQ2c5uPcvekYj_rIqq1Mo9MQ.original.fullsize.png) PROS AND CONS OF USING LABELS TO FORM TRAJECTORIESPros- Simple and intuitive idea- Unique labels are a way to try to capture the object identity, which is unique- Requires little modification to add labels to an unlabelled tracking algorithmCons- Typically, the labels are implicit. The true object identity (the explicit label) is not measured by the sensor(s), it is unobservable.- Missed detections can lead to gaps in the trajectory formed by labelled estimatesPhysically unrealistic switching when multi Bernoulli birth is i.i.d., and in challenging scenarios when objects get in close proximity and then separate- Difficulty fusing labelled estimates from different sensors IMPLICIT AND EXPLICIT LABELSExplicit label: corresponds to ID, e.g., person's name, vehicle's registration numberExpiicit labels are most often unobservable, i.e., cannot be known) (ANNA, ABS123)Implicit label: static and unique label assigned when object is bornImplicit labels lack a clear physical meaning (L, L')Assignment of unique implicit labels is arbitraryA different unique assignment can form the same trajectories Gap and switching<jupyter_code>!KL \text { and } CS \text { di }<jupyter_output>zsh:1: parse error near `}'
{'fraction_non_alphanumeric': 0.16716454556614968, 'fraction_numerical': 0.012481073781560747, 'mean_word_length': 4.513254371122391, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 33, 'https://': 3, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 4, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '568001', 'license': 'Apache-2.0', 'n_tokens_mistral': 16472, 'n_tokens_neox': 15673, 'n_words': 5732, 'path': 'notebooks/multi_object_tracking.ipynb', 'repo_name': 'neer201/Multi-Object-Tracking-for-Automotive-Systems-in-python', 'size': '48874'}