Feasibility-Scored Association: Constrained Trajectory Smoothing Inside Multi-Object Trackers

Video trackers follow many people at once. At each frame they predict where every existing track will be, then match new detections to those predictions. Almost all of them predict with a constant-velocity Kalman filter. This filter is fast, but it is fooled by dancers who reverse direction, athletes who cut sharply, and even by adversaries who deliberately stop and go. We propose a different way to decide which detection belongs to which track. For every candidate pairing, we ask how much a physically plausible trajectory would have to bend to pass through that detection. "Physically plausible" means bounded acceleration, smooth, and fitted to recent detections in proportion to their confidence. The cost of that bending becomes the matching score. Computed naively, this means solving a small constrained optimization problem for every track–detection pair at every frame, which is thousands of solves per frame. That cost is why tracking researchers have avoided optimization-based motion models.

The trick that makes it affordable comes from numerical linear algebra. When a sequence of linear systems shares the same sparsity pattern, the expensive structural analysis can be done once and only the numbers updated. Here every track's problem has identical structure. Adding one candidate detection to a track's problem changes the system matrix by a small low-rank amount. So one cached factorization per track can score every candidate detection with a few back-substitutions instead of a fresh solve. In two sentences: we replace "how close is this detection to a linear extrapolation" with "how much extra cost does a kinematically feasible trajectory pay to include this detection", and we make that tractable by reusing one factorization per track across all candidates and sharing one symbolic analysis across all tracks.

Core Claim

Our hypothesis is that association errors on motion-dominated benchmarks come largely from the prediction step committing to one extrapolated point too early. Scoring candidates by the increase in a constrained smoothing objective defers that commitment and rejects physically implausible matches. We further claim that the shared structure of the problem makes this cheap enough to run on a CPU.

Concretely, for track $i$ over a window of $T$ frames with stacked states $s$ (box center, scale, and their first two derivatives), the smoother solves

$$J_i(c) = \min_{s} \sum_{t=1}^{T} c_t \lVert z_t - H s_t \rVert^2 + \lambda \sum_{t} \lVert D s_t \rVert^2 \quad \text{s.t.} \quad |a_t| \le a_{\max},\; \text{scale}_t > 0,$$

where $z_t$ is the detection assigned at frame $t$, $c_t$ is its detector confidence (zero when the track was missed), $H$ extracts the box from the state, $D$ extracts jerk (the rate of change of acceleration), $\lambda$ trades smoothness against fit, and $a_t$ is acceleration. The window always contains a slot for the current frame with $c_T = 0$. Testing candidate detection $d$ therefore only raises one diagonal weight block. The association cost is

$$\Delta_{i,d} = J_i(c + \text{conf}_d\, e_T) - J_i(c),$$

where $e_T$ marks the last slot. With the active constraint set held fixed, this cost is a rank-at-most-four update of a cached factorization of the block-banded system matrix.

Research Program

The work has three parts.

Solver core. We first build this core and validate it in isolation. One symbolic analysis is done per window length and shared across all tracks. Numeric factorizations of the block-tridiagonal system are batched once per track per frame. Candidate scores come from low-rank updates with the active set frozen. Only the matches the assignment step actually selects are re-solved exactly with PIQP, an embedded interior-point quadratic programming solver that does symbolic analysis and memory allocation once and then reuses them across problems with fixed sparsity. PIQP supplies the method for the exact solve. Its known weakness, poor warm-starting of interior-point methods, is exactly why we do not call it per candidate.

The design follows the factorization-caching principle used for invariant system matrices in bounded-distortion mapping and chordal-sparsity ADMM. Those works cache a factorization because the matrix never changes. We instead exploit the case where the matrix changes by a low-rank amount per candidate and is structurally identical across many independent problems.

Tracker integration. Second, we drop the solver into a SORT-style tracker, keeping the detector, the two-stage high/low-confidence matching of ByteTrack, and Hungarian assignment unchanged. Only the motion cost changes, from intersection-over-union against a Kalman prediction to $\Delta_{i,d}$, with an IoU tie-break. During occlusion, the same smoother with zero weights produces a constrained prediction, so tracks coast along feasible curves instead of straight lines.

Analysis. Third, we analyze when the frozen-active-set approximation disagrees with the exact solve. We measure how often constraints are active on real data. We also measure how the gain depends on frame rate. OC-SORT motivates this last measurement: its fixed-window velocity heuristic exists because frame-to-frame differencing amplifies box noise, and a jerk-penalized fit addresses the same noise in a principled way.

Relation to prior work. Several lines of work motivate or bound this proposal without doing it. Gong et al. showed that treating occluded people as goal-directed agents lowers miss rate. Their paths come from Dijkstra search on a discrete grid with no continuous kinematics. Our model is continuous, but it does not model obstacles. The moving-horizon estimation literature (differentiable MHE, neural MHE, suboptimal nonlinear MHE) solves sliding-window estimation problems for a single robot. It never faces data association, which is where our cost structure, many tracks times many candidates, arises. Becker et al. use minimum-snap optimization only offline, to synthesize training trajectories. We run the optimization online. Graph solvers for tracking (neural solver, global graph solver) optimize the discrete assignment itself. We change the continuous cost fed to that assignment, and the two are complementary.

Baselines

Naive reference: SORT. The naive reference is SORT's constant-velocity Kalman filter with IoU matching. OC-SORT reports it at 47.9 HOTA on DanceTrack. ByteTrack, at 47.3 HOTA on DanceTrack as reported by Huang et al., is the same motion model with better low-confidence handling. It shows how far association logic alone gets.

Strongest heuristic competitor: OC-SORT. OC-SORT re-runs Kalman updates along a virtual path after re-detection, estimates velocity over a multi-frame window, and runs above 700 FPS on one CPU. It is the strongest competitor because it targets the same failure, non-linear motion and occlusion, with no learned components and no solver. It reports 54.6 HOTA on DanceTrack and 62.1 HOTA on MOT20.

Strongest existing method: MambaMOT+. MambaMOT+ from Huang et al. is a selective state-space network trained on box histories. It reports 56.1 HOTA and 54.9 IDF1 on DanceTrack, 71.3 HOTA on SportsMOT, and 28.8 FPS on an RTX 4080. We also run KalmanFormer, which reports 66.6 HOTA on MOT17 and 63.2 HOTA on MOT20, as the transformer-residual alternative.

Fairness protocol. Every method consumes the identical fixed detection files per benchmark. Published numbers mix detectors, so we rerun the public code rather than compare against table entries. Hyperparameters are tuned on the validation split under an equal budget: the same number of configurations for $\lambda$, $a_{\max}$, and window length as for OC-SORT's thresholds. Learned baselines get their published training recipe. Speed is reported on the same CPU, with GPU timing listed separately for learned models.

What counts as winning. Beating OC-SORT means a consistent HOTA and IDF1 gain on DanceTrack and SportsMOT test sets at no less than 100 FPS on CPU. Beating MambaMOT+ in accuracy is not required for the claim to matter. Matching it without a GPU or training data would already be informative.

Ablations isolating the key ingredient. Three ablations separate the parts of the method. The first removes the inequality constraints. The smoother then becomes a confidence-weighted linear smoother whose cost needs no solver. The second keeps the constraints but uses the smoother only for prediction, with an IoU cost. The third replaces low-rank scoring with an exact PIQP solve per pair, which measures approximation error and the speedup the amortization buys.

Why not just…?

Why not just use OC-SORT's heuristics? OC-SORT's re-update is retrospective. It corrects velocity only after the target reappears and cannot reject a wrong match made during or right after a sharp maneuver. Its fixed velocity window also has no notion of a feasible acceleration. The head-to-head on identical detections settles this. The breakdown by occlusion length and by trajectory curvature shows where any gain comes from. If OC-SORT matches us everywhere, the proposal fails.

Why not just train a learned motion model like MambaMOT+? This is a genuine threat on accuracy, since it is the strongest reported DanceTrack result. Our bet is narrower: comparable association quality with no training data, no GPU, and explicit, inspectable constraints. Those constraints should matter under adversarial stop-and-go motion, where Wang et al. report 100% white-box ID-transfer success against Kalman-based trackers in CARLA and up to 93% transfer across trackers. We test both models under the same injected maneuvers. A learned model may also absorb such maneuvers if they appear in training; we report that honestly if it happens.

Why not just use an unconstrained sliding-window smoother, or a Kalman filter with an acceleration gate? This is the most dangerous alternative. An unconstrained quadratic fit with fixed weights is a precomputed linear operator, and a chi-square gate on Kalman residuals approximates "reject implausible jumps" almost for free. If either matches the constrained version, the solver contributes nothing and we will say so. The first ablation and an added Kalman-plus-gate variant, tuned under the same budget, decide this. The constrained version must win specifically on frames where constraints are active. We report that subset separately.

Why not just call PIQP per pair without amortization? It may be fast enough on sparse scenes. On crowded MOT20 frames, however, the pair count grows as tracks times detections. The exact-solve ablation reports frames per second against crowd density so the reader can see where amortization starts to matter.

Proposed Experiments and Decisive Checks

We evaluate on DanceTrack and SportsMOT, where motion dominates, and on MOT17 and MOT20 as sanity checks where linear motion is adequate. On MOT17 and MOT20 we expect parity, not gains. The metrics are HOTA, IDF1, AssA, and identity switches, plus CPU frames per second and the share of frames with active constraints.

For robustness, we inject Go-and-Stop and Stop-and-Go maneuvers following the ADVTRAJ description into held-out DanceTrack tracks and, where feasible, into CARLA scenes. We measure ID-transfer rate, including an adaptive attacker that knows $a_{\max}$. No reported result was found on Lacuna for ID-transfer rate against OC-SORT or learned trackers, so all of these numbers are new.

Three outcomes are decisive. First, the constrained cost must beat the unconstrained-smoother and gated-Kalman ablations on DanceTrack AssA, with the gain concentrated on active-constraint frames. Second, low-rank scoring must agree with exact re-solves on at least 99% of final assignments. Third, the full tracker must stay above 100 FPS on CPU on MOT20-density scenes. Failing the first falsifies the idea. Failing the second or third falsifies the amortization claim but leaves the modeling claim testable.