Find your next learning step
The cheapest local match can make every other trajectory worse. A tracklet graph exposes that coupling and lets a global flow choose a coherent set of paths instead of a sequence of isolated guesses.
Open the chapter contents · Remote Sensing root · Gold Standard of Education · How X Works
Chapter contents
Choose the route closest to the question, or read from Chapter 1 for the complete argument. The chapters remain open on the page; these grouped routes are an index.
Route 1 · Build graph and costs
Route 2 · Work the global flow
Route 3 · Test future evidence and gates
Route 4 · Check limits and evidence
Route 5 · Ask and continue
CHAPTER 1 OF 12 · BUILD GRAPH AND COSTS
1. Build tracklets before trajectories
A detection is one observation in one frame. A tracklet is a short run of detections already linked with relatively high confidence. Global association treats tracklets as units and asks which can belong to the same longer trajectory.
This change of scale matters in aerial and satellite imagery. Objects may be tiny, revisit gaps long and detections intermittent. A tracklet can pool motion and appearance evidence that no single detection carries reliably.
CHAPTER 2 OF 12 · BUILD GRAPH AND COSTS
2. Draw the directed graph
Represent each tracklet as a node. Draw a directed edge from tracklet i to j only when time order, reachable motion and scene constraints permit i to precede j. Add source and sink connections for births and deaths.
| Graph element | Remote-sensing meaning | Typical evidence |
|---|---|---|
| node | one candidate tracklet | detections, times, positions, appearance summary |
| transition edge | possible continuation | gap, velocity, heading, geography, sensor change |
| source or sink edge | entry or exit | field of view, boundary, confidence, occlusion |
CHAPTER 3 OF 12 · WORK THE GLOBAL FLOW
3. Convert evidence into costs
A minimum-cost flow solver minimises a total objective subject to capacity and conservation constraints. Low-cost edges are preferred, but a learned score is not automatically a calibrated probability. Costs may combine negative log-likelihoods, hand-tuned penalties or learned affinities.
Keep the components inspectable: motion cost, appearance cost, gap penalty, sensor-switch penalty, birth cost and death cost. If components are rescaled, record the version. A global optimum is only optimal for the graph and costs it was given.
CHAPTER 4 OF 12 · WORK THE GLOBAL FLOW
4. Work a four-tracklet flow
Suppose early tracklets A and B can connect to later tracklets C and D. Transition costs are A→C = 2, A→D = 3, B→C = 2.5 and B→D = 9. Each later tracklet accepts at most one predecessor.
A greedy pass processing A first chooses A→C because 2 is smallest. B is then forced to D at cost 9, for total 11. Global flow chooses A→D at 3 and B→C at 2.5, for total 5.5. The locally second-best edge preserves a much better joint assignment.
| Assignment rule | Selected links | Total transition cost |
|---|---|---|
| greedy, A first | A→C, B→D | 11.0 |
| global one-to-one flow | A→D, B→C | 5.5 |
CHAPTER 5 OF 12 · WORK THE GLOBAL FLOW
5. Explain the nonlocal decision
The solver does not “know” identity. It compares complete feasible flows. A choice at A changes which edges remain available to B, so the value of A→C depends on evidence elsewhere in the graph.
This is the central transfer from local association: the best edge is not necessarily part of the best set of paths. Capacity constraints, births, deaths and missed-detection edges create opportunity costs that a pairwise threshold cannot see.
CHAPTER 6 OF 12 · TEST FUTURE EVIDENCE AND GATES
6. Changed context: add a later observation
Add tracklet E after D. Let D→E cost 0.5 and C→E cost 8, and suppose E’s motion strongly continues D. The globally preferred history may now preserve A→D→E even if A→C looked slightly better at the earlier boundary.
The example explains retrospective relinking without pretending the future changes the past. Later evidence changes the best explanation of an ambiguous earlier assignment. Online systems can approximate this with a sliding window; fully offline systems can use the whole sequence.
CHAPTER 7 OF 12 · TEST FUTURE EVIDENCE AND GATES
7. Gate before optimising
Global optimisation cannot rescue physically impossible edges if they are allowed cheaply. Apply transparent gates for maximum speed, time gap, map topology, sensor geometry and exclusion zones before solving. Keep a margin for model error so that the true edge is not pruned too early.
Gating and costing have different jobs. A gate says “impossible or outside the model.” A cost says “possible but more or less plausible.” Mixing them into one opaque threshold makes failures hard to diagnose.
CHAPTER 8 OF 12 · TEST FUTURE EVIDENCE AND GATES
8. Handle births, deaths and false tracklets
Source and sink costs determine how readily paths begin and end. Detection-selection costs decide whether a weak tracklet is used at all. If birth is too cheap, the solution fragments. If death is too expensive, unrelated tracklets can be forced together.
Calibrate these costs with the operating environment. At a scene boundary, a death may be unsurprising. In an open field with dense revisit coverage, a sudden disappearance may deserve a larger penalty. Scene-aware costs should be declared, not smuggled into an identity score.
CHAPTER 9 OF 12 · CHECK LIMITS AND EVIDENCE
9. Limits and common misconceptions
Minimum-cost flow is globally solvable for common linear formulations, but higher-order interactions, group motion and multi-commodity identity constraints can change complexity. Tracklet construction errors also propagate: a wrong detection inside a node may be harder to undo than a wrong edge.
Global does not mean all-knowing, and minimum cost does not mean maximum truth. The solution depends on detections, gates, costs and temporal window. Remote-sensing changes in view angle, ground sampling distance and illumination can break appearance summaries built for street video.
CHAPTER 10 OF 12 · CHECK LIMITS AND EVIDENCE
10. Build an evidence check
Store the graph actually solved: node provenance, every retained and pruned edge, cost components, capacities, solver version and selected paths. Evaluate identity switches, fragmentation, false trajectories, missed trajectories and time-to-decision, stratified by gap length and sensor condition.
Run ablations that remove appearance, motion or geographic constraints. Compare greedy, framewise assignment and global flow on the same detections. Inspect counterfactual near-optimal paths for ambiguous cases rather than reporting only one scalar benchmark.
CHAPTER 11 OF 12 · ASK AND CONTINUE
11. Questions readers should ask
Why not connect every detection directly?
You can, but tracklets reduce graph size and aggregate evidence. The trade-off is that tracklet mistakes become structural.
Is an edge cost a probability?
Only if it was derived and calibrated as one. Many systems use useful but uncalibrated scores.
Must global tracking be offline?
No. Sliding windows and incremental flow methods provide bounded-delay approximations, though later evidence outside the window cannot repair earlier choices.
CHAPTER 12 OF 12 · ASK AND CONTINUE
12. Continue through verified routes
Begin with the Remote Sensing root, Gold Standard of Education and How X Works. Continue through Identity Confidence, Deferred Assignment and Retrospective Relinking, Object Persistence, Track Fragmentation and Event Identity Across Revisit Gaps and Dormant Tracks, Re-Identification and Long-Gap Reconnection.
Primary routes include Zhang, Li and Nevatia’s global data association using network flows, Pirsiavash, Ramanan and Fowlkes’ globally optimal greedy-style tracking framework, and Wang, Wang and Yu’s efficient minimum-cost circulation formulation. The four-tracklet ledger is an original teaching example.
Top · Contents · Previous · How X Works