Parallax Trackingבס״ד

Multi-target tracking, sensor fusion and estimation

Interactive tutorial · with Claude AI assistance

Several sensors report only the direction to each of several targets. The tracker has to decide which report belongs to which target, and each method here is a different answer to that question.

Joint Probabilistic Data Association

JPDA never assigns a detection to one track. Each track is updated with every detection near it, weighted by how likely that pairing is, so ambiguity widens the estimate instead of picking a side.

Parallax Tracking — every figure below is computed as you read it

Abstract—JPDA declines to associate at all. Within each cluster of tracks whose gates overlap it enumerates the feasible joint association events — the assignments in which no measurement is used twice and no track claims two — weights each by its likelihood, and marginalises to obtain, for every track–measurement pair, the probability β that they belong together. Each track is then updated with the β-weighted combination of all measurements in its gate, and its covariance inflated by the spread of those innovations, so that the filter’s own uncertainty records the ambiguity rather than concealing it. No decision is ever made, so no decision can be wrong. The price is paid elsewhere: the estimate is drawn toward whatever else is nearby, and when two targets cross, both tracks are drawn toward each other.

Index Terms—probabilistic data association, feasible joint events, soft assignment, track coalescence, existence probability.

PredictF x, F P Fᵀ + QGated² ≤ γClustershared gatesJoint eventsenumerate · weightMarginals βper track–meas. pairWeighted update+ spread of νall interpretations, averaged
Fig. 1. Joint probabilistic data association. The clustering box is what makes the enumeration tractable: only tracks whose gates actually overlap have to be reasoned about together.

I. Introduction

The previous method commits, and every failure it has follows from that. The obvious repair is to commit better; the less obvious one, and the subject of this article, is not to commit at all.

Joint probabilistic data association [2] replaces the choice with a weighted average. Every measurement in a track’s gate contributes to that track, in proportion to how probable that pairing is once the competing claims of neighbouring tracks have been accounted for. No association is ever declared, so none can ever be wrong, and there is no wrong decision to recover from because there was no decision.

What this buys is graceful degradation under clutter and, more importantly, a covariance that tells the truth: a track that could not separate two measurements says so in its reported uncertainty rather than reporting a false precision. What it costs is the ability to hold two targets apart when they cross, because an average of two interpretations is neither of them. The sections below give the joint event, the weights derived from it, the update those weights drive, and the point at which the enumeration has to be bounded.

II. Problem formulation

A. What is given, what is returned

The inputs are those of the previous method: T predicted tracks and m detections, gated. What leaves the association stage is different in kind. It is not a permutation but a matrix of weights βij, one per gated pair, giving the probability that measurement j belongs to track i, together with βi0, the probability that track i was not detected at all.

B. The hypothesis space

A joint event θ is a whole assignment: a statement about every track and every measurement at once, feasible when it respects the rule that a measurement has one source and a track has one measurement. The hypothesis space is the set of all feasible joint events, and the distinction that matters is that it is a space of complete assignments and not of pairs. A pair has no probability on its own; it acquires one only by summing the events that contain it.

The space is enumerated afresh at every scan and nothing is carried between scans except the filtered state, which is what makes this method memoryless in the sense the Limitations section returns to.

C. The score

Let Z be the current measurement set. The posterior probability of a feasible joint event is, up to a normalising constant,

P(θ | Z) ∝ Πj∈θ (1/λ) N(νij; 0, Sij) · PDd (1 − PD)T−d(1)

with λ the clutter density, d the number of tracks detected in θ and T the cluster size. Each detected pair contributes a likelihood ratio of exactly the form Appendix C derives — the measurement density under the track against its density under the clutter model — so the events are comparable to each other despite containing different numbers of detections.

The clutter count cancels. A Poisson clutter model contributes a factor depending on how many false alarms the scan actually contained, and that factor is identical for every event, so it divides out under normalisation. The weights can therefore be computed without knowing or estimating the number of false alarms — only their density.

III. The algorithm

A. Clustering, which is exact and not an approximation

Two tracks compete if they share a measurement at the current scan. That relation is a graph on the tracks and its connected components are the clusters. Tracks in different components share no measurement, so no joint event can contain a term coupling them: solving the components separately gives exactly the answer that solving them together would, and it is the only reason the enumeration that follows is affordable at all.

the gate, as a bipartite graphT₁T₂T₃T₄z₁z₂z₃z₄z₅tracksmeasurementsinducesthe track graph, and its componentsT₁T₂T₃T₄share z₂share z₄no measurement joins the two, so they are solved separately and the answer is still exact
Fig. S1. The gate as a bipartite graph, and the track graph it induces. Two components here, so enumeration runs on each separately and the cost falls from exponential in four tracks to exponential in two. What clustering does not do is help when the scene is dense: if every gate overlaps every other, the graph is one component and the decomposition is trivial.

B. Marginalisation

The weight of a pair is the sum over all events that make that pairing:

βij = Σθ: θ(i)=j P(θ | Z)(2)
1. gatez₁z₂z₃T₁T₂●●●●a dot is a pair inside the gate2. every feasible joint eventT₁ → —T₂ → —B·BT₁ → z₁T₂ → —G₁₁·BT₁ → z₂T₂ → —G₁₂·BT₁ → —T₂ → z₂B·G₂₂T₁ → —T₂ → z₃B·G₂₃T₁ → z₁T₂ → z₂G₁₁G₂₂T₁ → z₁T₂ → z₃G₁₁G₂₃T₁ → z₂T₂ → z₃G₁₂G₂₃no measurement twice, no track twice; weights multiply down a column3. marginaliseβᵢⱼ = Σ over events pairing Tᵢ with zⱼβᵢ₀ = Σ over events leaving Tᵢ undetectedβᵢ₀ + Σⱼ βᵢⱼ = 1one update per track, from every measurement in its gate
Fig. S2. Two tracks, three measurements, and the eight events consistent with the gate. An event is a whole assignment and not a pair, which is the distinction the formulation exists to preserve: the weights multiply down a column, and summing the columns that pair a given track with a given measurement, then normalising, gives that pair’s β.

C. The update, and the term that makes it honest

The update uses the combined innovation νi = Σj βij νij and a covariance with three terms rather than one:

Pi = βi0 P− + (1−βi0)(P− − K S KT) + K [ Σj βij νijνijT − νiνiT ] KT(3)

The bracket is the spread of the innovations, and it is what makes the method honest. It is zero when one measurement takes all the weight and grows as the weight is shared, so a track that could not tell two measurements apart says so in its covariance. This is precisely what a committing tracker cannot do: having chosen, it has nothing left to be uncertain about, which is why it reports 13 m for a ghost.

D. Track maintenance

This is the one method here whose tracks do not live and die by the score of Appendix C. Track life is governed instead by an existence probability propagated alongside the state: a track whose gate keeps coming up empty loses existence probability and is deleted, one whose existence probability rises past a threshold is confirmed, and a candidate is admitted at a third. The same corroboration requirement from a second viewpoint is applied on top. Table A1 carries the three values.

They are not independent. The deletion threshold must lie below the birth threshold, or a track is admitted below the level at which it would immediately be deleted and the two rules fight each other every scan.

E. Bounding the enumeration

Exact evaluation of (2) requires summing over all feasible events, and counting the events of a gate is a matrix permanent, which is #P-hard. It is therefore bounded: exact below a cluster size and an event count given in Table A1, and above that a cheaper approximation that discounts each pair by the total claim on its row and column.

That approximation is not a joint distribution, and its βi0 is a remainder rather than a sum over events in which the track went undetected. The difference is a real limitation of the covariance it produces and not merely of its running time, which is why the exact path is kept for every cluster small enough to afford it.

PredictClusterconnected componentsEnumerateevery joint eventApproximaterow/column claim≤ 9 tracksotherwiseMarginaliseβᵢⱼUpdatecombined ν + spreadExistenceconfirm · deletenext scan — no choice was made
Fig. S3. Control flow for one scan. The branch is the only place the method approximates anything, and the return path carries no decision — which is the property the whole design exists to preserve.

IV. Advantages and cost

There is no hard error to recover from. A wrong choice is the failure mode GNN and MHT are built around; JPDA does not make choices, so under dense clutter it degrades gracefully where a hard assignment degrades abruptly. At four sensors it measures 2.4 m OSPA, the best of the four.

The covariance is calibrated. The spread term of (3) means the reported uncertainty reflects the ambiguity actually present. Measured at four sensors, JPDA contains the truth inside its own 2σ contour more often than any other method here.

Track life is principled. An existence probability is a quantity with a meaning, and it deletes tracks for a stated reason rather than because a hand-set score crossed a hand-set threshold.

Cost. Exact enumeration is exponential in cluster size and #P-hard in general, which is why both cluster size and event count are capped. Measured solo at three sensors: 2.5 ms per step, the same as MHT.

V. Limitations

Coalescence. When two targets cross, each track’s gate contains both measurements, both β approach one half, and both estimates are pulled toward the mean of the pair. The tracks do not swap identity — they merge — and they separate again only when the geometry does. This is the structural weakness that motivated MHT, and it is the reason the trade is right under clutter and wrong under crossings.

No identity memory. Averaging is memoryless. Nothing accumulates over scans that could later disambiguate a pairing, which is exactly what MHT adds.

At two sensors it hits the same wall as everything else (171 m), because averaging over interpretations that tie exactly returns their midpoint, and the midpoint of a target and its ghost is neither.

VI. Validation

No reference implementation of this method exists in the source material, so there is no reference for it to be verified against. It is an original design and is measurement-validated only: characterised by the medians in Table III and by the tuning study behind them, taken on seed sets disjoint from those used to tune it. It is not, and is not claimed to be, a reproduction of any published implementation.

What is checked directly is the machinery rather than the outcome: that the enumerated events are exactly the feasible ones, that the weights of a cluster sum to unity, and that the exact and approximate paths agree where both are affordable. Those are properties, not benchmarks, and they are the part of this method that admits a definite answer.

Table IResult at the current epoch
Live: the running scenario's own numbers, not a recorded benchmark. For reproducible medians see Table III.
Fig. 2aMean 2σ major axis, recent history
Step changes are sensors being added or removed; the sawtooth is track birth and death.
Table IIIThe four algorithms, five-seed medians
Method2 sen.3 sen.4 sen. ms/stepvalidation
OSPA at cutoff 200 m and clutter 2, in metres; lower is better. Every cell is the median of five seeds — the same configuration has been measured spanning 4.5 to 162.9 across seeds, so a single-seed figure is noise. Tuned on one seed set, reported on a disjoint one. Timing measured solo at three sensors. Click a row to open that article.
Fig. 2. The Cramér–Rao position bound as a body. One target at the origin, its sensors around it, and the 2σ covariance ellipsoids of a converged EKF and of a batch Gauss–Newton solution, both normalised by σ · reff so the absolute noise level cancels. Drag to orbit; the sensor list and both estimators are behind the gear. Three-dimensional because with a single target there is nothing to associate, hence no filter and nothing that can diverge.
Table IIGeometry and accuracy for the constellation above

Appendix — common to all four methods

References

  1. D. B. Reid, “An algorithm for tracking multiple targets,” IEEE Trans. Autom. Control, vol. 24, no. 6, pp. 843–854, 1979.
  2. Y. Bar-Shalom and E. Tse, “Tracking in a cluttered environment with probabilistic data association,” Automatica, vol. 11, no. 5, pp. 451–460, 1975.
  3. K. G. Murty, “An algorithm for ranking all the assignments in order of increasing cost,” Oper. Res., vol. 16, no. 3, pp. 682–687, 1968.
  4. S. Deb, M. Yeddanapudi, K. Pattipati and Y. Bar-Shalom, “A generalized S-D assignment algorithm for multisensor-multitarget state estimation,” IEEE Trans. Aerosp. Electron. Syst., vol. 33, no. 2, pp. 523–538, 1997.
  5. D. Schuhmacher, B.-T. Vo and B.-N. Vo, “A consistent metric for performance evaluation of multi-object filters,” IEEE Trans. Signal Process., vol. 56, no. 8, pp. 3447–3457, 2008.
  6. S. C. Nardone and V. J. Aidala, “Observability criteria for bearings-only target motion analysis,” IEEE Trans. Aerosp. Electron. Syst., vol. 17, no. 2, pp. 162–166, 1981.
  7. D. P. Bertsekas, “The auction algorithm: a distributed relaxation method for the assignment problem,” Ann. Oper. Res., vol. 14, pp. 105–123, 1988.
  8. R. B. Langley, “Dilution of precision,” GPS World, vol. 10, no. 5, pp. 52–59, 1999.
  9. Y. Bar-Shalom, S. S. Blackman and R. J. Fitzgerald, “Dimensionless score function for multiple hypothesis tracking,” IEEE Trans. Aerosp. Electron. Syst., vol. 43, no. 1, pp. 392–400, 2007.
  10. A. Wald, “Sequential tests of statistical hypotheses,” Ann. Math. Statist., vol. 16, no. 2, pp. 117–186, 1945.
  11. J. Munkres, “Algorithms for the assignment and transportation problems,” J. SIAM, vol. 5, no. 1, pp. 32–38, 1957.
  12. P. R. J. Östergård, “A new algorithm for the maximum-weight clique problem,” Nordic J. Computing, vol. 8, no. 4, pp. 424–436, 2001.
  13. T. A. Feo, M. G. C. Resende and S. H. Smith, “A greedy randomized adaptive search procedure for maximum independent set,” Oper. Res., vol. 42, no. 5, pp. 860–878, 1994.
  14. T. Kurien, “Issues in the design of practical multitarget tracking algorithms,” in Multitarget-Multisensor Tracking: Advanced Applications, Y. Bar-Shalom, Ed. Artech House, 1990, ch. 3.