An extended object returns several measurements per scan, so the tracker must decide which measurements belong together before it can decide which object they belong to. This page walks through the three families of solutions to that partition-uncertainty problem — each demonstrated on the same toy scene of two elliptical objects, one ambiguous detection, and one clutter point.
The sections organize four mechanisms into three broad viewpoints. B2 deliberately places two distinct approximations side by side: [31] searches for high-weight partition–association hypotheses by stochastic methods, whereas [32] uses belief propagation to obtain marginals without enumerating them. Click any clause to jump to its demo.
At one scan the sensor returns a measurement set Z = {m1, …, mM}. Because each extended object can generate many detections, many standard updates sum over a partition P of Z: disjoint, non-empty cells whose union is Z. A cell can be assigned to an existing or newly detected object. Under the usual Poisson point-clutter model, clutter measurements are normally handled as individual clutter events rather than one multi-measurement clutter source.
The exact multi-object likelihood is a sum over all partitions (and, inside each partition, over all cell-to-object assignments). The number of partitions of M elements is the Bell number B(M) — and it grows super-exponentially. For the M = 10 scene on the right there are already 115 975 partitions; counting associations and clutter labels on top, far more.
Every filter below is a different answer to one question: how do you avoid summing over all of them?
Same ten measurements, many valid groupings
How fast it explodes
Classical extended-target PHD-family updates contain a weighted sum over partitions, but practical implementations replace “all partitions” with a small, heuristically generated candidate set 𝒫cand and make other approximation or moment-matching choices. A common workhorse is distance partitioning [25]: cluster measurements with single linkage at a threshold d, then sweep d over a range; every distinct clustering that appears becomes one candidate. Variants add prediction partitioning, EM or spectral sub-partitioning, and combining/splitting steps.
The update then marginalizes: ν(Z) ≈ ΣP∈𝒫cand ωP · (update given P), with weights ωP proportional to each partition’s likelihood. This is how the ET-GM-PHD [25], the GGIW ET-CPHD [26], the random-matrix PHD [27], and labeled-RFS extended-target filters [28] stay tractable.
That candidate set came from one clustering rule — single-linkage distance. But the choice is free: the partitioning toolbox ↓ swaps in DBSCAN, k-means, spectral, and MCMC on the same ten points.
Distance partitioning — drag the threshold
The full candidate set 𝒫cand from sweeping d, with illustrative likelihood weights ωP
Family A marginalizes over a candidate set 𝒫cand — but which partitions land in that set is entirely up to the clustering rule, and there are many. Each panel below is a separate live example of one method running on the same ten measurements. Drag every control and watch how m₉ (ambiguous) and m₁₀ (clutter) are treated differently. Single-linkage distance partitioning [25] is only the traditional default; no method here is “correct,” which is exactly why the candidate set is a modeling choice.
The Poisson multi-Bernoulli mixture (PMBM) filter [29] takes the opposite stance: don’t pick partitions — keep them. The PMBM density is a conjugate prior for extended-target models, so the posterior is exactly a mixture in which each global hypothesis corresponds to one history of partitions and cell-to-object associations, carrying a weight and its own multi-Bernoulli density.
The price is growth: at every scan each global hypothesis spawns one child per compatible partition–association of the new measurement set, so the mixture multiplies. Tractability comes from hypothesis management — gating, pruning low-weight hypotheses, capping their number, and recycling — exactly what the buttons on the right animate.
The PMB approximations of [30] go one step further: after the update, the mixture is approximated by a single multi-Bernoulli using track-oriented or variational/KL-based methods. Marginal association information survives, while correlations between global hypotheses are discarded (see the split-colored m₉ below).
Global hypotheses = partitions + associations, each with a weight
PMB projection [30]: mixture → single density
Resulting marginals for m₉
| hypothesis about m₉ | marginal prob. |
|---|---|
| from object 2 | 0.46 |
| from object 1 | 0.31 |
| births a new object | 0.14 |
| clutter | 0.09 |
Granström et al. [31] use Gibbs sampling and stochastic optimization to find high-likelihood joint partition–association hypotheses directly, avoiding a separate clustering-then-assignment stage. With an irreducible chain, correct target distribution, adequate mixing, and enough samples, sampling can explore support beyond a fixed heuristic candidate set; in finite time it can still miss modes.
Xia et al. [32] take a different route: a trajectory-PMB filter uses a factor-graph representation and belief propagation to approximate association marginals without enumerating hypotheses. It is not a partition sampler. The live panel on the right demonstrates only the sampling idea from [31].
Gibbs-style sampler over partitions (starts from one giant cell)
Meyer and Williams [33], [34] dissolve the partition variable altogether. Each measurement mi gets its own association variable ai ∈ {existing objects, new object, clutter}, and — crucially — instantiates one new potential object. The joint posterior over object states, existences, and all ai lives on a factor graph, and the sum-product algorithm (SPA) passes messages until the association marginals converge.
No explicit partition is enumerated; “groups” exist implicitly through measurements whose association beliefs concentrate on the same object. For fixed particle count and message iterations, the association layer touches measurement–object pairs and scales roughly as 𝒪(n·M) per iteration; the full particle implementation has additional state and shape-inference costs. [34] extends the machinery to explicit geometric shapes.
Message passing on the association factor graph (schematic SPA)
The factor graph (4 of M measurements shown)
| Family | Representative filters | How partition uncertainty is handled | Cost & failure mode |
|---|---|---|---|
| A · Candidate set | ET-GM-PHD [25]; GGIW ET-CPHD [26]; random-matrix PHD [27]; labeled RFS [28] | Heuristics (distance / prediction partitioning, EM splits) generate a small 𝒫cand; the update marginalizes over it with likelihood weights. | Cheap and simple; but mass outside 𝒫cand is silently zero — the clustering heuristic caps achievable accuracy. |
| B1 · Retain hypotheses | PMBM conjugate prior [29]; PMB / PMBM approximations [30] | Under the assumed model, partition-and-association histories index a conjugate PMBM mixture; PMB approximates that mixture by one density, retaining selected marginals but dropping global correlations. | Statistically principled; hypothesis count multiplies per scan → needs aggressive gating, pruning, capping, recycling. |
| B2 · Direct inference | Gibbs / stochastic optimization [31]; trajectory PMB with BP associations [32] | [31] searches for high-weight joint hypotheses by sampling/optimization; [32] instead uses BP to approximate marginals without enumeration. | Sampling can mix slowly or miss modes; loopy BP can bias marginals. These are distinct approximations with different diagnostics. |
| C · No hard partition | SPA-based scalable EOT [33]; geometric extended objects [34] | One association variable and one new potential object per measurement; SPA on a factor graph yields soft association marginals — partitions never enumerated. | Association messaging is roughly 𝒪(n·M) per iteration for fixed particle count; the complete particle tracker costs more. Delivers approximate marginals, not an explicit best partition. |
Same scene, three lenses: A asks “which few groupings shall we allow?”, B asks “how do we carry many groupings forward?”, C asks “why group at all?”.