Online Vehicle Identity Tracking as Windowed Correlation Clustering

A city camera network sees thousands of short vehicle tracks, called tracklets, and has to decide which of them belong to the same car. The best systems today decide this offline. They collect everything, compare every pair, prune pairs that are physically impossible (a car cannot cover 2 km in ten seconds), and then cluster. That wins benchmarks but cannot run on a live stream.

We propose running this decision online as correlation clustering. Correlation clustering is a way of grouping items from pairwise "same" or "different" votes without fixing the number of groups in advance, and it has recently gained dynamic algorithms with provable approximation factors and polylogarithmic update time. Two ingredients from vehicle tracking make those algorithms fit the problem. First, physical travel-time limits turn old tracklets into frozen history rather than deleted nodes, which avoids the weakest point of dynamic clustering theory: handling deletions. Second, the predicted viewing angle of each car decides whether two images can vote at all. A front view and a rear view share almost no visible parts, so they should abstain from voting rather than cast a confident but wrong vote.

Core Claim

Online multi-camera identity maintenance can be cast as correlation clustering on a sparse signed graph whose structure is fixed by three rules. Pairs that are spatio-temporally infeasible become hard "different" constraints. Pairs whose viewpoints share too little visible surface become default-negative "abstentions" rather than similarity-scored votes. Only feasible, co-visible pairs get a similarity-based sign.

Under this construction, a tracklet stops receiving new edges once every camera it could reach within the maximum travel time has been passed. From then on it can be frozen. An identity stays alive only through its most recent member. The dynamic problem therefore reduces to insertions on a moving "active frontier" plus freezing. That is exactly the regime that insertion-only dynamic correlation clustering handles well (Sparse-pivot, which maintains a (20+ε)-approximation with polylogarithmic amortized insertion time but handles deletions only by periodic full recomputation).

The testable claims are three. The online method should approach offline accuracy on CityFlow. It should revise already-emitted identities rarely. It should expose a tunable accuracy-versus-latency curve through its neighbor-sampling budget.

We are deliberately not claiming that sublinear update time matters at CityFlow's scale. With 40 cameras and 666 identities, recomputing from scratch on the active frontier may be cheap. Whether and where the dynamic algorithm pays off is an empirical question we test directly, not an assumption.

Research Program

Constraint layer. We follow the feasible travel-time windows of Ren et al. and the "alibi" rejection of Kondor et al., which discard candidate pairs that would require impossible speeds. In prior work these filters prune a dense similarity matrix after the fact. Here they do two jobs inside the clustering. They supply hard negative edges, and they define when a tracklet's window closes and it can be frozen. Because Ren et al. identify static windows as brittle under congestion, the maximum travel time per camera link is re-estimated online from recently confirmed matches. This is a simple running quantile, not a learned model.

Replacing manual direction masks with predicted viewpoint. The strongest CityFlow system, Liu et al., gets a large gain from its Direction Based Temporal Mask: IDF1 rose from 0.34 to 0.53 from that mask alone. The mask rejects matches whose exit direction at one intersection contradicts the entry direction at the next. It depends on hand-drawn crossroad zones, which its authors name as the main practical bottleneck.

VCAM predicts vehicle orientation (sin θ, cos θ) from a single crop, but uses it only to reweight feature channels. KPGST showed that predicted pose correlates with driving direction and reported over 10% mAP gain from pose-guided spatio-temporal modeling, but only for pairwise retrieval. We combine the two ideas. Image orientation plus the CityFlow homographies (CityFlow) gives a ground-plane heading at each camera exit. That heading generates the direction mask automatically. This differs from CAMOT, which uses camera elevation angle for association within a single camera, not across a camera network.

Viewpoint-gated signing. Following the "compare only commonly visible parts" idea of PVEN, each tracklet carries a coarse visibility vector over front, rear, side, and top. We compute it from the predicted orientation rather than a full parsing network, which avoids PVEN's segmentation cost and its fragility under occlusion.

A feasible pair receives a similarity-based sign only if its shared visibility exceeds a threshold $\tau$. Otherwise it is treated as "different" by default, as in standard complete-graph correlation clustering. The consequence matters. In pivot-style clustering, a node joins a cluster when it has a positive edge to that cluster's pivot. A front view and a rear view of the same car can therefore still end up together through a side-view pivot that shares parts with both. The system never has to trust a front-versus-rear appearance score.

We test one further variant as an ablation: biasing pivot selection toward side or oblique views. It likely weakens the random-rank analysis behind the approximation guarantee.

Clustering engine. The base is Sparse-pivot's insertion procedure, with its neighbor sampling and its periodic cluster-breaking step. Hard negatives add a repair rule: any cluster that contains an infeasible pair is split at the violating tracklet. Frozen tracklets are removed from the active graph but keep their labels.

We will analyze what survives of the (20+ε) guarantee. Freezing is a time-ordered expiry, not an adversarial deletion, so we expect the analysis to go through on the active frontier. Whether hard constraints preserve a constant factor is an open question we will state honestly rather than assume. Dynamic Agreement is the alternative engine, since its runtime stayed nearly constant as average degree rose from 42.25 to 253.36 on the Drift dataset.

Baselines

The naive reference is visual-only association with single-camera tracking and no spatio-temporal filtering. Liu et al. report a baseline IDF1 of 0.3048 for this setting. The classic reference is the CityFlow paper's offline tracklet clustering with spatio-temporal models, which reports 46.3% IDF1 (CityFlow).

The strongest existing method is the offline system of Liu et al.. It combines crossroad zones, the direction mask, tracklet filtering, sub-clustering in adjacent cameras, and a ResNeXt ensemble, and it reports 0.8095 IDF1, ranking first on AICITY21. It is the strongest competitor because it has all the spatio-temporal knowledge we use plus hindsight.

For fairness, both systems receive the same detections, the same single-camera tracklets, and the same ReID embeddings; we reuse one backbone rather than their ensemble. We also report the offline system rerun with that same single backbone, because the published 0.8095 includes ensembling we will not match. Beating this baseline means coming within about 0.03 IDF1 of the rerun offline system while emitting each identity within a bounded delay. Exceeding it online is not expected.

The strongest online competitor is DyGLIP. It predicts links between tracklets with attention over a sliding window and runs at 300–500 nodes per second. It reports gains of 37.2% MOTA and 11.1% IDF1 over the ELECTRICITY baseline on CityFlow; the file gives no absolute IDF1. We rerun it on the same embeddings with its published window size, give it the same hyperparameter search budget as our method, and compare at matched per-tracklet latency.

We also include the online greedy pipeline of Ren et al., which reports 0.5763 IDF1 and placed sixth. It is the simple "filter, then match" competitor.

Three ablations isolate our ingredients. Hand-drawn direction masks in place of the orientation-derived ones test the viewpoint-to-direction component. Similarity scores on all feasible pairs, with no abstention, test viewpoint gating. Exact pivot clustering recomputed from scratch on the active frontier at every arrival tests whether the dynamic algorithm, rather than the formulation, is doing any work.

Why not just…?

Why not just run the offline clustering pipeline? It will likely remain more accurate, and Liu et al. is the ceiling we measure against. Its cost is structural, however. It needs all tracklets and dense pairwise matrices, and its authors cite ensembling and re-ranking overhead as barriers to real-time use. Our experiments report the accuracy gap as a function of how long the system may wait before committing an identity. That delay-versus-IDF1 curve answers the question directly.

Why not just greedily match each new tracklet to the best feasible candidate? Greedy online matching, in the style of Ren et al., is cheap. It cannot undo an early wrong merge, and it cannot connect a front view to a rear view through a third, side-on view. Correlation clustering can re-cluster, which costs identity revisions. We therefore measure both IDF1 and the number of revised labels. If greedy matching reaches the same IDF1, the clustering machinery is not justified on CityFlow, and we will say so.

Why not just recompute clustering from scratch on the active window? This is the most serious threat. Freezing keeps the active frontier small, and at CityFlow scale an exact recomputation may run in real time. If it does, the contribution is the formulation (constraint negatives, viewpoint abstention, freezing), not the dynamic algorithm. The frontier-scaling experiment below determines at what frontier size recomputation stops meeting a real-time budget. If that size is far beyond realistic traffic, we drop the efficiency claim.

Why not just use a stronger ReID backbone? The file's evidence points against this. The best visual-only model on CityFlow reached 32.0% mAP (CityFlow). Santore et al. argue that look-alike vehicles cannot be separated by appearance at all. The no-filter ablation re-checks this with our backbone.

Proposed Experiments

The main benchmark is CityFlow, measured by IDF1. We add per-tracklet update latency, identity revisions per tracklet, and emission delay.

The decisive accuracy check compares our online system with the single-backbone rerun of Liu et al. and with DyGLIP. The decisive viewpoint check compares orientation-derived direction masks with hand-drawn ones. If the automatic masks recover most of the 0.34→0.53 gain that hand-drawn masks produced in Liu et al., the manual-configuration bottleneck is addressed.

We validate viewpoint gating separately on VeRi-776, which has timestamps and camera topology. We compare retrieval mAP with and without abstention against the 68.6% reported for VCAM (VCAM) and the 68.73% reported for KPGST (KPGST).

The trade-off experiment sweeps Sparse-pivot's neighbor-sampling budget and plots IDF1 against update latency. This gives an accuracy-efficiency curve analogous to the depth knob of hierarchical EDCS, but measured on real tracking streams.

The frontier-scaling stress test densifies traffic. We overlay time-shifted copies of CityFlow with identities kept distinct, and we lengthen windows to mimic congestion. We then record where recompute-from-scratch exceeds a fixed real-time budget while the dynamic engine stays under it. This test is constructed, not a published benchmark, and we report it as such. The file lists no reported result on Lacuna for any correlation-clustering tracker on CityFlow, so every number in this experiment will be new.