We address the problem of tracking multiple objects in densely packed environments where occlusion and posture variation present significant challenges. Rather than relying solely on detection, we propose Constrained Sequential Labeling (CSL), which formulates tracking as labeling mid-level features by object identifiers while maintaining hard constraints through constraint propagation. The CSL method enables flexible cost functions and constraints to represent complex dependencies beyond standard network-flow approaches. We include a learning algorithm for constraints with proven convergence properties. Testing on challenging footage from volleyball, basketball, and pedestrian scenarios demonstrates improved performance relative to existing methods.

Multi-object tracking (MOT) in crowded scenes is a fundamental yet challenging task. The dominant paradigm — tracking-by-detection — first detects objects in each frame, then associates detections across frames. This approach is typically formulated as a data association problem, solved via network flow optimization or Hungarian algorithm. However, these formulations assume pairwise costs between detections and cannot express higher-order dependencies such as "two tracks should not overlap in space" or "a track's appearance should vary smoothly". In densely packed scenarios like team sports, these limitations lead to frequent identity switches and fragmented trajectories.

We propose a fundamentally different formulation: Constrained Sequential Labeling (CSL). Instead of associating detections, we extract mid-level features (superpixels or detection fragments) and assign each an object identity label. The labeling is performed sequentially over time, with hard constraints enforced through constraint propagation — a technique borrowed from constraint satisfaction problems (CSP) in artificial intelligence. This formulation naturally accommodates higher-order dependencies, arbitrary cost functions, and domain-specific constraints that are difficult or impossible to express in flow-based frameworks.

Multi-object tracking methods can be categorized by their optimization strategy. Network-flow methods model tracking as minimum-cost flow and can be solved globally optimally in polynomial time, but are limited to pairwise interactions. Conditional Random Field (CRF) approaches can encode richer dependencies but require approximate inference. Multiple Hypothesis Tracking (MHT) maintains a tree of hypotheses but is exponential in the number of objects. Our CSL approach combines the expressiveness of CRF-like models with the efficiency of constraint propagation, offering a middle ground between optimality and expressiveness.

At each time step t, we extract a set of mid-level features F_t = {f_1, ..., f_m} from the video frame. Each feature is a localized region (e.g., a detection bounding box or a superpixel cluster) characterized by position, appearance histogram, and motion vector. The goal is to assign each feature a label from the set {0, 1, ..., K}, where labels 1 through K represent tracked objects and label 0 represents background. The labeling at time t is denoted L_t = {l_1, ..., l_m}. A cost function C(L_t | L_{t-1}, F_t) evaluates the quality of the labeling given the previous labeling and current features.

The key novelty lies in incorporating hard constraints into the labeling process via constraint propagation. We define several types of constraints: (1) Uniqueness: each object label appears at most once per time step; (2) Spatial exclusion: features within a certain distance cannot share the same non-background label; (3) Appearance consistency: the appearance of a tracked object should not change drastically between consecutive frames. These constraints are enforced by iteratively pruning the domain of possible labels for each feature, a process analogous to arc consistency in constraint satisfaction. This pruning dramatically reduces the search space, making the optimization tractable.

Rather than manually tuning the constraint parameters, we propose a learning algorithm that automatically determines the constraint thresholds from training data. The learning procedure minimizes a loss function that penalizes both missed constraints (leading to identity switches) and overly strict constraints (leading to track fragmentation). We prove that this learning algorithm converges to a fixed point under mild assumptions. The learned constraints are domain-adaptive: constraints learned for volleyball differ from those for pedestrian tracking, reflecting the distinct spatial and temporal characteristics of each scenario.

We evaluate on three challenging multi-object tracking scenarios: volleyball (6 players per team, frequent occlusion), basketball (5 players per team, fast motion), and pedestrian sequences from standard MOT benchmarks. On the volleyball dataset, CSL achieves significant reductions in identity switches (40-60% fewer) compared to network-flow baselines while maintaining competitive MOTA scores. On basketball sequences, the track fragmentation rate is reduced by 35%. On standard pedestrian benchmarks, CSL achieves competitive performance with state-of-the-art methods. Ablation studies confirm that constraint propagation is essential — removing it degrades performance to below the network-flow baseline, and learned constraints consistently outperform hand-tuned ones.

We have presented Constrained Sequential Labeling (CSL), a novel formulation for multi-object tracking that goes beyond pairwise data association by incorporating hard constraints through constraint propagation. The approach naturally handles higher-order dependencies and is accompanied by a constraint learning algorithm with convergence guarantees. Experiments demonstrate that CSL is particularly effective in densely packed scenarios with frequent occlusions. Future work includes extending CSL to online tracking settings and incorporating deep learning-based appearance models for more robust feature representations.