Multitarget Tracking · Reading & print view

01 / 12

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.

Read the graph

Walk every message

Check the beliefs

Meyer et al. (2018) · p. 241–243

02 / 12

One scan contains two kinds of uncertainty

Target state and existence sit outside; measurement ownership is resolved in the middle.

Legacy targets at the current scan

Possible new targets

Circles: variables · Green squares: transitions · Red squares: local factors and association constraints

Meyer et al. (2018) · p. 242

03 / 12

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.

Meyer et al. (2018) · p. 236–243

04 / 12

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]

Meyer et al. (2018) · p. 236–243

05 / 12

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.

Meyer et al. (2018) · p. 240–243

06 / 12

Follow the information out and back

Only the association block repeats. The rest of the scan runs in one forward-time schedule.

Predict

previous posterior → transition → state

Evaluate

state → local weights for a and b

Associate

iterate through the consistency factors

Return

association evidence → state factors

Form beliefs

normalize state and existence weights

Next: advance one message, select its output entry, then inspect the sum that produced it.

Meyer et al. (2018) · p. 242–243

07 / 12

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

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.

Meyer et al. (2018) · p. 242–243

08 / 12

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.

Meyer et al. (2018) · p. 232, 243

09 / 12

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%

Meyer et al. (2018) · p. 243

10 / 12

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.

Meyer et al. (2018) · p. 236–237, 243–244

11 / 12

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.

Meyer et al. (2018) · p. 232–234, 242–244

12 / 12

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 ↗

Companion: factor graphs & sum-product ↗

Meyer et al. (2018) · p. 221–259