PAPER NOTES · FIGURE 4
Message passing for multitarget tracking
A guided reading of Meyer, Kropfreiter, Williams, Lau, Hlawatsch, Braca and Win (2018).
From uncertain matches
to uncertain tracks
Follow one scan through prediction, association, and the birth or survival of possible targets.
\(y_-^{1}\)
\(f^{1}\)
\(\underline y^{1}\)
\(q^{1}\)
\(a^{1}\)
\(b^{1}\)
\(v^{1}\)
\(\overline y^{1}\)
\(y_-^{2}\)
\(f^{2}\)
\(\underline y^{2}\)
\(q^{2}\)
\(a^{2}\)
\(b^{2}\)
\(v^{2}\)
\(\overline y^{2}\)
\(\Psi^{1,1}\)
\(\Psi^{1,2}\)
\(\Psi^{2,1}\)
\(\Psi^{2,2}\)
01
Read the graph
02
Walk every message
03
Check the beliefs
Arrow keys advance · Page Up / Page Down navigate from the demo · Escape returns focus to the slides
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 241–243
1 / 12
01 · FIGURE 4, REDRAWN
One scan contains two kinds of uncertainty
Target state and existence sit outside; measurement ownership is resolved in the middle.
Previous
Legacy targets at the current scan
Possible new targets
\(y_-^{1}\)
\(f^{1}\)
\(\underline y^{1}\)
\(q^{1}\)
\(a^{1}\)
\(b^{1}\)
\(v^{1}\)
\(\overline y^{1}\)
\(y_-^{2}\)
\(f^{2}\)
\(\underline y^{2}\)
\(q^{2}\)
\(a^{2}\)
\(b^{2}\)
\(v^{2}\)
\(\overline y^{2}\)
\(\Psi^{1,1}\)
\(\Psi^{1,2}\)
\(\Psi^{2,1}\)
\(\Psi^{2,2}\)
Circles: variables · Green squares: transitions · Red squares: local factors and association constraints
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 242
2 / 12
01 · THE VARIABLES
A potential target may not exist
An association choice and an existence indicator answer different questions.
\[y=(x,r),\qquad r\in\{0,1\}\]
\(\underline y^j\): a legacy candidate carried from the previous scan.
\(\overline y^m\): a possible new target introduced by measurement \(m\).
\[a^j\in\{0,1,2\},\quad b^m\in\{0,1,2\}\]
\(a^j=m\): target \(j\) produced measurement \(m\).
\(a^j=0\): no detection from that target.
\(b^m=j\): measurement \(m\) came from legacy target \(j\).
\(b^m=0\): new target or clutter.
A new candidate is created for each measurement; its posterior existence may remain very small.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 236–243
3 / 12
01 · A CONCRETE NUMERICAL INSTANCE
Two cells make every sum inspectable
The figure and update rules come from the paper. These numerical choices are for teaching.
\[y\in\{\varnothing,L,R\},\quad x_L=0,\ x_R=1\]
\[\begin{aligned}\widetilde f_-^1&=[0.10,\ 0.80,\ 0.10]\\\widetilde f_-^2&=[0.20,\ 0.15,\ 0.65]\end{aligned}\]
Each vector lists absent, left, right. The absent entry aggregates the paper’s normalized dummy state density.
\[f(y\mid y_-)=\begin{pmatrix}1&0&0\\0.05&0.8075&0.1425\\0.05&0.1425&0.8075\end{pmatrix}\]
Rows: previous state. Columns: current state.
\[\begin{aligned}z_1&=0.30,\quad z_2=0.62,\quad p_D=0.85\\L_m(x)&=\mathcal N(z_m;x,0.35^2)\end{aligned}\]
Clutter intensity = 0.5 · Expected new detections = 0.3 · New-target location mass = [0.5, 0.5]
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 236–243
4 / 12
02 · BEFORE THE ASSOCIATION LOOP
Local factors turn states into association weights
Prediction is a probability vector. The outgoing measurement weights are generally unnormalized.
\[q^j(y,a)=\begin{cases}\mathbf1[a=0]&y=\varnothing\\1-p_D&y\ne\varnothing,\ a=0\\p_D L_a(x)/\lambda_c&y\ne\varnothing,\ a>0\end{cases}\]
\[\beta_j(a)=\sum_y q^j(y,a)\alpha_j(y)\]
\[\beta_1\approx[0.2733,\ 0.9371,\ 0.4758]\]
\[\xi_m(0)=1+B_m,\qquad\xi_m(j)=1\]
\[B_m=\sum_x\frac{\mu_n f_n(x)L_m(x)}{\lambda_c}\]
The 1 is the absent-new-target contribution. The extra mass supports a new detection.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 240–243
5 / 12
02 · THE FIGURE 4 WALKTHROUGH
Follow the information out and back
Only the association block repeats. The rest of the scan runs in one forward-time schedule.
\(y_-^{1}\)
\(f^{1}\)
\(\underline y^{1}\)
\(q^{1}\)
\(a^{1}\)
\(b^{1}\)
\(v^{1}\)
\(\overline y^{1}\)
\(y_-^{2}\)
\(f^{2}\)
\(\underline y^{2}\)
\(q^{2}\)
\(a^{2}\)
\(b^{2}\)
\(v^{2}\)
\(\overline y^{2}\)
\(\Psi^{1,1}\)
\(\Psi^{1,2}\)
\(\Psi^{2,1}\)
\(\Psi^{2,2}\)
1
Predict
previous posterior → transition → state
2
Evaluate
state → local weights for a and b
3
Associate
iterate through the consistency factors
4
Return
association evidence → state factors
5
Form beliefs
normalize state and existence weights
Next: advance one message, select its output entry, then inspect the sum that produced it.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 242–243
6 / 12
02 · INTERACTIVE FIGURE 4
Walk the graph, one message at a time
Use Next message, or choose a stage. Select a track, measurement, and output entry to inspect.
1 / 17 · Send the previous posterior
\(y_-^{1}\)
\(f^{1}\)
\(\underline y^{1}\)
\(q^{1}\)
\(a^{1}\)
\(b^{1}\)
\(v^{1}\)
\(\overline y^{1}\)
\(y_-^{2}\)
\(f^{2}\)
\(\underline y^{2}\)
\(q^{2}\)
\(a^{2}\)
\(b^{2}\)
\(v^{2}\)
\(\overline y^{2}\)
\(\Psi^{1,1}\)
\(\Psi^{1,2}\)
\(\Psi^{2,1}\)
\(\Psi^{2,2}\)
Track 1 → transition factor
\[\widetilde f_-^1=[0.10,\ 0.80,\ 0.10]\]
The entries are absent, left, and right. The next message will sum this posterior through the transition matrix.
Next: prediction → local weights → association loop → state beliefs.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 242–243
7 / 12
03 · INSIDE THE ASSOCIATION BLOCK
One message leaves out one neighbor
The consistency factor prevents two targets from claiming the same measurement.
\[\Psi^{j,m}(a,b)=\mathbf1\big[(a=m)\Longleftrightarrow(b=j)\big]\]
\[\nu^{[\ell]}_{m,j}(a)\propto\sum_b\Psi^{j,m}(a,b)\,\xi_m(b)\!\prod_{i\ne j}\varphi^{[\ell-1]}_{i,m}(b)\]
\[\varphi^{[\ell]}_{j,m}(b)\propto\sum_a\Psi^{j,m}(a,b)\,\beta_j(a)\!\prod_{n\ne m}\nu^{[\ell]}_{n,j}(a)\]
Excluding the recipient avoids immediately sending its own information back to it.
Each message has two distinct values. The demo rescales nonmatching entries to 1.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 232, 243
8 / 12
03 · WHAT COMES OUT OF THE GRAPH
Stable messages can still give approximate beliefs
The demo checks its small loopy graph against all seven valid association matchings.
\[\widetilde f(\underline y^j)\propto\alpha_j(\underline y^j)\gamma_j(\underline y^j)\]
\[\widetilde f(\overline y^m)\propto\varsigma_m(\overline y^m)\]
Candidate
BP existence
Exact existence
Legacy 1
84.77%
85.73%
Legacy 2
71.55%
73.33%
New 1
7.17%
6.68%
New 2
7.98%
7.44%
Defaults, after 3 sweeps. Exact means exhaustive inference for this two-cell teaching model, not ground-truth tracking.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 243
9 / 12
04 · ACROSS TIME
Today’s new candidates become tomorrow’s legacy set
Messages travel forward through time; there is no backward smoothing pass in this schedule.
Updated legacy candidates
\[\widetilde f(\underline y_k^1),\quad\widetilde f(\underline y_k^2)\]
Updated new candidates
\[\widetilde f(\overline y_k^1),\quad\widetilde f(\overline y_k^2)\]
→
Prediction at the next scan
\[y_{k+1}^j\sim f(y_{k+1}^j\mid y_k^j)\]
After optional pruning, both groups enter the same legacy-target prediction step.
Declaring and pruning targets uses existence thresholds; the demo keeps all candidates so their beliefs stay visible.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 236–237, 243–244
10 / 12
04 · WHY MESSAGE PASSING HELPS
Local updates replace a global assignment sum
Each sweep visits target–measurement pairs and reuses compact summaries.
What scales
The two-valued consistency messages admit scalar ratios. With shared sums, one association sweep costs work proportional to the number of candidate pairs.
\[O(n_p n_m)\quad\text{per DA sweep}\]
What the figure does not promise
A fixed number of sweeps does not certify exact posterior marginals.

Continuous-state integration, particle counts, gating, and the number of potential targets also affect total tracking cost.
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 232–234, 242–244
11 / 12
SOURCES & SCOPE
Read alongside Figure 4 and Section IX-A
The diagram is redrawn; the source PDF is linked, not redistributed.
Message Passing Algorithms for
Scalable Multitarget Tracking
Florian Meyer, Thomas Kropfreiter, Jason L. Williams, Roslyn A. Lau,
Franz Hlawatsch, Paolo Braca and Moe Z. Win.
Proceedings of the IEEE, 106(2), 221–259, February 2018.
DOI: 10.1109/JPROC.2018.2789427 ↗
Paper in the Australian National University repository ↗
Static reading / print view ↗
Companion: factor graphs & sum-product ↗
BAI LIPING · RANDOM THOUGHTS
Meyer et al. (2018) · p. 221–259
12 / 12