An interactive note · Multi-target tracking · Data association

One association problem, two philosophies.

Every scan, a tracker faces the same combinatorial question: which measurement belongs to which target? Exact marginalization requires a sum over valid global association events and is generally combinatorial. This page puts two important routes side by side on one live scenario: belief propagation, which never enumerates events and instead passes messages until the marginal association probabilities emerge; and the Poisson multi-Bernoulli mixture, which represents ambiguity as a weighted mixture of global hypotheses and manages that mixture with hypothesis selection and pruning. Drag anything in Fig. 1 — every figure below recomputes.

Model boundary. The live comparison is an exact benchmark for a normalized one-scan assignment model: existing tracks may be missed or claim at most one measurement, and unassigned measurements have baseline weight 1. It is not a complete PMBM update. In a PMBM filter, a new-target Bernoulli is driven by measurement-specific evidence from the undetected-target Poisson intensity; this demo instead applies a separate birth-versus-clutter slider after association so BP and enumeration receive identical weights.

§1The shared problem: three tracks in a tangle, four measurements

Three targets have predicted positions ẑ_i with innovation covariances S_i (gates drawn at the 99 % χ² contour) — and their gates overlap three ways. A sensor returns four measurements with detection probability P_D and Poisson clutter density λ_c. BP and exhaustive enumeration consume exactly the same existing-track assignment weights ℓ, making their marginal-association comparison exact for the toy model.

Scenario — the three-way tangle

Sensor model

Detection probability 0.90

Clutter density λ_c 5.0×10⁻⁵

Toy birth score λ̃_b 1.0×10⁻⁵

Drag the × marks and the track centers. Everything on this page follows.

Fig. 1 — The scan to be explained: three gates knotted around z₁–z₃, with z₄ off in the clutter. Dashed ellipses are validation gates (99 % χ², 2 dof); thin gray links mark the gated target–measurement pairs, i.e. the only associations either method will consider.

ℓ_ij = P_D·N(z_j; ẑ_i, S_i)/λ_c for gated pairs · ℓ_i∅ = 1−P_D (missed detection) · an unassigned measurement carries normalized baseline weight 1. For display only, its mass is later split by the toy score β̃ = λ̃_b/(λ̃_b+λ_c).

Fig. 2 — Existing-track association weights for the normalized benchmark. BP runs messages over this table; exhaustive enumeration multiplies its entries into global assignment weights. A dot means the pair fell outside the gate.

§2Route one — belief propagation on the association graph

Introduce a target-oriented variable a_i (which measurement did target i generate, or ∅) and a measurement-oriented variable b_j (which target generated measurement j, or clutter/new). Redundant on purpose: the pairwise factors Ψ_ij(a_i,b_j) only enforce that the two bookkeepings agree. Loopy sum–product on this bipartite graph is provably convergent (Williams & Lau, 2014), costs O(n·m) per sweep, and its fixed point delivers approximate marginal association probabilities — no hypothesis is ever written down.

μ_i→j track→measurement · ν_j→i measurement→track · gated out: ℓ = 0 ⇒ μ ≡ 0

hover any edge for its ℓ, μ, ν and the marginal it feeds

p(a_i = ·) — BP marginals; they move only when a ν half-step lands

Convergence — max message change per full sweep

p(b_j = ·) — measurement-oriented marginals; for illustration, unassigned mass splits into ⊕ possible birth vs ∅ clutter by the toy score β̃

State beliefs b(x_i) — Gaussian mixtures, one Kalman-updated component per gated measurement plus the prior for ∅, weighted by the live marginals above (95 % ellipses; opacity ∝ weight; prior P_i = S_i − R with R = 60·I)

μ_i→j = ℓ_ijℓ_i∅ + Σ_k≠j ℓ_ik ν_k→i(1) target i tells measurement j how claimed it already is elsewhere

ν_j→i = 11 + Σ_l≠i μ_l→j(2) measurement j tells target i how contested it is

p(a_i=j) ∝ ℓ_ij ν_j→i, p(a_i=∅) ∝ ℓ_i∅(3) read the marginals off the fixed point

t = 0 is the uncoupled start: ν ≡ 1, so each track just normalizes its own row of Fig. 2. One time step is one application of (1) followed by (2) — exactly the two half-steps of the player above. The iterations exist purely to negotiate the one-to-one constraint.

Fig. 3 — Left: the complete bipartite Williams–Lau factor graph — every (aᵢ, bⱼ) pair carries a consistency factor Ψ (mid-edge diamond); faint dashed edges are gated out (ℓᵢⱼ = 0, so μ ≡ 0 and the pair is inert). Every live edge wears its two current messages: μᵢ→ⱼ in the track’s color, νⱼ→ᵢ in slate — the bold set is the one that just updated. One time step = two presses of Half-step ▸: first all μ fire left→right, then all ν answer right→left, and only then do the marginals, edge thicknesses and Δ move. Hover any edge for its numbers.

§3Route two — PMBM: keep the hypotheses, prune the tail

The Poisson multi-Bernoulli mixture is a conjugate multi-object posterior under the standard point-target model: a Poisson process represents never-detected targets and a multi-Bernoulli mixture represents detected ones. Each global hypothesis is one compatible association story. The table below visualizes that hypothesis bookkeeping for the page’s normalized assignment model; a full PMBM update additionally computes a measurement-specific Bernoulli existence and state density from the undetected-target Poisson intensity.

f(X) = Σ_h w_h · f^ppp(X^u) Π_i f^bern_h,i(X_i)(4) undetected Poisson ⊎ multi-Bernoulli mixture

w_A ∝ Π_(i,j)∈A ℓ_ij · Π_{i missed} ℓ_i∅ · Π_{j unassigned} 1(5) exact weight in this normalized assignment benchmark

Exact inference for this benchmark carries every valid A. Practical PMBM implementations instead generate selected high-weight children using assignment or sampling methods, then prune and recycle. The problem here is small enough to enumerate every gated assignment, providing the exact reference for §4 — but not the full PMBM state update.

Keep the k best global hypotheses 5

Fig. 4 — Every valid assignment hypothesis in the normalized benchmark, ranked by eq. 5. Each row assigns a measurement to at most one existing track or leaves it unassigned. The ⊕ badge uses β̃ only as a visual birth-versus-clutter split; a real PMBM Bernoulli uses measurement-dependent PPP evidence. Slide k to see how truncation discards normalized assignment mass. The first row is the toy model’s highest-weight association event, not by itself a complete PMBM multi-object estimate.

p(a_i = ·) — exact marginals, obtained by summing all hypotheses above

Fig. 5 — Summing every row gives the exact existing-track association marginals for this normalized model — the quantity §2 approximates without constructing the list.

§4Head-to-head on the same scan

Same ℓ, same normalized assignment question, two answers. BP is exact when the relevant factor graph is acyclic; in loopy graphs it is approximate. Dragging changes both graph structure and weights, so more overlap can increase the discrepancy, but error is not a monotone function of “loopiness.” The live table reports what actually happens for each configuration.

BP marginals (converged)

Exact / PMBM marginals

|difference|, percentage points

Fig. 6 — The numerical price of approximate marginalization in this scan. BP is exact on an acyclic association factor graph; on a loopy graph its Bethe fixed point may differ from exhaustive enumeration, with the size and direction determined by the actual weights.

Fig. 7 — The difference compounds over time. PMBM branches every scan and prunes (dashed = discarded); identity ambiguity can stay unresolved until later evidence settles it. A BP-based tracker instead re-negotiates marginals within each scan and carries a single belief set forward — O(n·m) flat cost, but modes merged at every step (the JPDA-style coalescence risk).

The bridge: they meet in the middle

Marginal multi-Bernoulli/Poisson filters such as TOMB/P approximate a PMBM-style mixture by a single multi-Bernoulli using marginal association probabilities; BP is one efficient way to approximate those marginals. That is a specific bridge between the frameworks. It does not mean that every BP/SPA tracker is simply a PMBM filter with its hypotheses removed.

§5Cheat sheet

	Belief propagation (SPA / BP tracker)	PMBM
object kept	Marginal association probabilities p(a_i=j); one belief per track	Weighted mixture of global hypotheses; a Bernoulli per potential target per hypothesis, plus a Poisson for the undetected
core computation	Iterated messages (1)–(2) on the bipartite graph until fixed point	Hypothesis generation (Murty’s k-best or Gibbs) + weight update (5) + pruning, recycling, merging
cost / scan	`O(T·n·m)`, T ≈ tens of sweeps; embarrassingly scalable, message-parallel	`O(k·N³)` per Murty call plus hypothesis bookkeeping; combinatorial pressure managed, not removed
what’s approximate	The marginals themselves (Bethe fixed point; exact on acyclic factor graphs, potentially biased with loops)	The PMBM family is conjugate for the assumed model; implementations also approximate single-target integrals and use gating, hypothesis selection/pruning, merging, and numerical state representations
ambiguity over time	Marginalized each scan in many BP-based filters; efficient, but projection can merge modes and promote coalescence	Retained global histories preserve competing explanations; trajectory variants can represent identity and history explicitly
track birth	Depends on the tracker; scalable SPA methods can introduce measurement-oriented potential objects	Undetected-target PPP; each measurement can create a Bernoulli whose evidence depends on the PPP intensity and likelihood
reach for it when	n, m are large; hard real-time budgets; dense scenes where enumeration is hopeless anyway	Ambiguity is the point: crossing / closely spaced targets, identity matters, offline or accuracy-first pipelines
lineage	JPDA’s soft spirit, made scalable and convergent	MHT’s hypothesis spirit, made Bayes-exact via RFS conjugacy

Table 1 — The one-screen version. Neither column dominates: retaining hypotheses is valuable when ambiguity and identity matter; BP is attractive when scale and latency dominate.

§References

J. L. Williams and R. Lau, “Approximate evaluation of marginal association probabilities with belief propagation,” IEEE Trans. Aerosp. Electron. Syst., 50(4), 2014 — the message schedule and convergence proof behind §2.

J. L. Williams, “Marginal multi-Bernoulli filters: RFS derivation of MHT, JIPDA, and association-based MeMBer,” IEEE Trans. Aerosp. Electron. Syst., 51(3), 2015 — TOMB/P and MOMB/P, the bridge of §4.

F. Meyer et al., “Message passing algorithms for scalable multitarget tracking,” Proc. IEEE, 106(2), 2018 — a broader BP/SPA tracking framework.

Á. F. García-Fernández et al., “Poisson multi-Bernoulli mixture filter: direct derivation and implementation,” IEEE Trans. Aerosp. Electron. Syst., 54(4), 2018 — the standard point-target PMBM recursion.

Model notes for the demo: one scan, point targets, linear-Gaussian existing-track likelihoods, and normalized unassigned-measurement weight 1. The post-hoc toy split β̃ = λ̃_b/(λ̃_b+λ_c) is deliberately decoupled from association and must not be read as the general PMBM birth update. Under the standard PMBM point-target model, a measurement z has new-target evidence e(z) = ∫p_D(x)l(z|x)λ^u(x)dx and existence e(z)/(c(z)+e(z)); its state density is proportional to the same integrand. The simplified split keeps BP and enumeration byte-identical. Gating uses χ²(2 dof) = 9.21. The state-belief strip assumes R = 60·I and Gaussian priors with P_i = S_i − R. “Exact” on the page means exhaustive summation of every gated assignment in this toy model (≤ 73), not an exact real-world tracker.

A single self-contained HTML file · no libraries, no network · the solver in your browser is the real Williams–Lau iteration, not an illustration of one.