Multi-Object Tracking Architecture: Implementing DeepSORT with Python

1. Executive Summary & Problem Formulation

Object detection networks (like YOLO, SSD, or Faster R-CNN) map bounding boxes onto individual static images. However, they possess zero temporal memory. If a neural network detects a pedestrian in frame $N$, and detects a pedestrian slightly to the left in frame $N+1$, the network cannot inherently prove these are the same physical entity.

Multi-Object Tracking (MOT) is the mathematical problem of linking discrete bounding box detections across a temporal sequence of video frames to assign stable, persistent ID numbers to individual actors.

If we rely purely on spatial overlap—using metrics like Intersection over Union (IoU) to associate boxes from frame to frame—the tracking pipeline shatters the moment two actors cross paths. An IoU-only tracker (like the original SORT algorithm) suffers from catastrophic identity switching during occlusion. When a bus drives in front of a pedestrian, the pedestrian's track terminates. When the bus passes, the pedestrian receives a brand new ID.

To build an occlusion-resilient tracking architecture, we must fuse two distinct sources of information: 1. Kinematic Motion Prediction: Using a Kalman Filter to project where a tracked object should be in the next frame based on linear velocity. 2. Appearance Feature Embedding: Using a convolutional neural network (CNN) to extract a high-dimensional mathematical fingerprint (an embedding vector) of the object's visual appearance.

DeepSORT (Simple Online and Realtime Tracking with a Deep Association Metric) solves the identity assignment problem by formulating it as a bipartite matching problem, scored by a weighted combination of spatial Mahalanobis distance and visual Cosine distance, and solved via the Hungarian Algorithm.

2. Mathematical & Architectural Theory

The State Space and Kinematic Projection

DeepSORT tracks each object's state using an 8-dimensional linear discrete Kalman filter: $$\mathbf{x} = [u, v, \gamma, h, \dot{x}, \dot{y}, \dot{\gamma}, \dot{h}]^T$$ where: - $(u, v)$ is the bounding box center coordinate. - $\gamma$ is the aspect ratio. - $h$ is the box height. - The remaining variables represent the respective linear velocities.

When a new frame arrives, the Kalman filter predicts the expected location of all existing tracks.

The Cost Matrix formulation

We now have a list of $M$ predicted track locations, and a list of $N$ fresh bounding box detections from our YOLO network. We must determine which detection belongs to which track.

We construct an $M \times N$ Cost Matrix $\mathbf{C}$. The cost value $c_{i,j}$ represents how likely it is that track $i$ corresponds to detection $j$.

DeepSORT computes $c_{i,j}$ by fusing two distinct distance metrics:

1. Spatial Mahalanobis Distance ($D_M$) Measures how many standard deviations the new detection is from the track's predicted location, factoring in the Kalman filter's uncertainty covariance: $$D_M(i, j) = (\mathbf{d}_j - \mathbf{y}_i)^T \mathbf{S}_i^{-1} (\mathbf{d}_j - \mathbf{y}_i)$$ where $\mathbf{y}_i$ is the predicted position of track $i$, $\mathbf{S}_i$ is the predicted covariance matrix, and $\mathbf{d}_j$ is the coordinate of detection $j$.

2. Visual Cosine Distance ($D_C$) The system crops the image patch of detection $j$ and runs it through a feature extractor network (typically a ResNet re-id model) to produce a 128-dimensional unit-length embedding vector $\mathbf{r}_j$. We compare this against the historical appearance vector gallery of track $i$ ($\mathcal{R}_i$) using cosine distance: $$D_C(i, j) = \min_{\mathbf{r}_k \in \mathcal{R}_i} \left( 1 - \mathbf{r}_j^T \mathbf{r}_k \right)$$

The final cost matrix fuses these metrics via a weighting parameter $\lambda$: $$c_{i,j} = \lambda D_M(i, j) + (1 - \lambda) D_C(i, j)$$

The Hungarian Algorithm (Munkres Assignment)

Once the Cost Matrix is populated, we must find the optimal global assignment that minimizes the total sum of costs. A greedy approach (picking the lowest cost match iteratively) traps the system in local minima, causing incorrect swaps when targets are crowded.

The Hungarian Algorithm is a combinatorial optimization method that solves the assignment problem in $\mathcal{O}(N^3)$ time, guaranteeing the mathematically optimal global pairing of tracks to detections.

Cascaded Matching and Track Lifecycle

To prioritize tracking reliable, long-standing objects over fresh, uncertain ones, DeepSORT utilizes a Cascaded Matching strategy. It runs the Hungarian Algorithm repeatedly in a loop, first attempting to assign detections to tracks that were successfully updated in the very last frame. If detections remain unassigned, it runs the algorithm again against tracks that have been lost for 1 frame, then 2 frames, up to a maximum threshold ($A_{max} = 30$ frames).

If a track remains unassigned beyond $A_{max}$, it is permanently deleted. If a detection remains completely unassigned across all cascades, it spawns a brand new tentative track.

3. Concrete Implementation: DeepSORT Association Logic

Below is a Python implementation demonstrating the core architectural logic of the cost matrix construction and the Hungarian assignment step using scipy.optimize.linear_sum_assignment.

This code isolates the association module, assuming the YOLO detections and the ReID embeddings have already been computed.

import numpy as np
from scipy.optimize import linear_sum_assignment

class Track:
    def __init__(self, track_id: int, embedding: np.ndarray, state_mean: np.ndarray, state_cov: np.ndarray):
        self.track_id = track_id
        # Gallery of recent appearance vectors to handle rotational changes
        self.features = [embedding]
        self.mean = state_mean
        self.covariance = state_cov
        self.time_since_update = 0
        self.hits = 1

class Detection:
    def __init__(self, bbox: np.ndarray, confidence: float, embedding: np.ndarray):
        self.bbox = bbox
        self.confidence = confidence
        self.feature = embedding

def cosine_distance(features_a: np.ndarray, features_b: np.ndarray) -> np.ndarray:
    """
    Computes pairwise cosine distance between two sets of L2-normalized vectors.
    Returns a distance matrix of shape (len(features_a), len(features_b)).
    """
    # Since vectors are L2-normalized, cosine similarity is just the dot product
    similarity = np.dot(features_a, features_b.T)
    # Cosine distance = 1 - cosine similarity
    distance = 1.0 - similarity
    # Clip to avoid floating point precision issues
    return np.clip(distance, 0.0, 2.0)

def compute_cost_matrix(tracks: list[Track], detections: list[Detection], lambda_weight: float = 0.5) -> np.ndarray:
    """
    Constructs the fused M x N cost matrix combining appearance and spatial distance.
    """
    num_tracks = len(tracks)
    num_detections = len(detections)
    cost_matrix = np.zeros((num_tracks, num_detections), dtype=np.float32)

    if num_tracks == 0 or num_detections == 0:
        return cost_matrix

    det_features = np.array([d.feature for d in detections])

    for i, track in enumerate(tracks):
        # 1. Visual Cosine Distance (Compare detection against track's feature gallery)
        track_features = np.array(track.features)
        dist_matrix = cosine_distance(track_features, det_features)
        # Take the minimum distance against the gallery
        min_cosine_dist = dist_matrix.min(axis=0)

        for j, det in enumerate(detections):
            # 2. Spatial Mahalanobis Distance
            # Extract center (u, v) and height from the detection bounding box
            det_pos = np.array([det.bbox[0] + det.bbox[2]/2, det.bbox[1] + det.bbox[3]/2])
            track_pos = track.mean[:2]
            
            # Use the position block of the covariance matrix
            pos_cov = track.covariance[:2, :2]
            
            diff = det_pos - track_pos
            try:
                inv_cov = np.linalg.inv(pos_cov)
                mahalanobis_sq = diff.T @ inv_cov @ diff
            except np.linalg.LinAlgError:
                # Fallback to extreme cost if covariance collapses
                mahalanobis_sq = 1000.0

            # 3. Fuse metrics
            cost_matrix[i, j] = (lambda_weight * mahalanobis_sq) + ((1.0 - lambda_weight) * min_cosine_dist[j])

            # Apply Gating: If the distance exceeds a physical threshold, block the assignment
            # 9.487 is the 95% chi-square threshold for 4 DOF
            if mahalanobis_sq > 9.487 or min_cosine_dist[j] > 0.2:
                cost_matrix[i, j] = 1e5  # Effectively infinity

    return cost_matrix

def associate_detections_to_tracks(tracks: list[Track], detections: list[Detection]) -> tuple[list, list, list]:
    """
    Solves the bipartite matching problem using the Hungarian algorithm.
    Returns: (matches, unmatched_tracks, unmatched_detections)
    """
    if len(tracks) == 0:
        return [], [], list(range(len(detections)))
    if len(detections) == 0:
        return [], list(range(len(tracks))), []

    # Build cost matrix
    cost_matrix = compute_cost_matrix(tracks, detections, lambda_weight=0.1)

    # Solve Hungarian Assignment
    row_indices, col_indices = linear_sum_assignment(cost_matrix)

    matches = []
    unmatched_tracks = []
    unmatched_detections = []

    # Validate assignments against the infinity gating threshold
    for track_idx, det_idx in zip(row_indices, col_indices):
        if cost_matrix[track_idx, det_idx] >= 1e5:
            unmatched_tracks.append(track_idx)
            unmatched_detections.append(det_idx)
        else:
            matches.append((track_idx, det_idx))

    # Collect unassigned items that the Hungarian algorithm skipped entirely
    for i in range(len(tracks)):
        if i not in row_indices and i not in unmatched_tracks:
            unmatched_tracks.append(i)

    for j in range(len(detections)):
        if j not in col_indices and j not in unmatched_detections:
            unmatched_detections.append(j)

    return matches, unmatched_tracks, unmatched_detections

4. Edge Cases, Optimization & Memory Considerations

ReID Embedding Collapse

The accuracy of DeepSORT depends entirely on the discriminative power of the ReID feature extractor. Standard models (like OSNet or Wide-ResNet) are trained on massive pedestrian datasets (Market-1501). If you run this exact model on a traffic camera to track identical white sedans, the cosine distance between the embeddings of different cars will be near zero.

When the visual appearance metric collapses, the cost matrix becomes flat, and the algorithm degrades into a pure Kalman filter spatial tracker. You must train a custom feature extraction network specifically calibrated for your target domain using triplet loss or contrastive loss, ensuring that intra-class variation (different angles of the same object) yields tighter clustering than inter-class variation.

Gallery Growth and Memory Leaks

To handle objects rotating in 3D space, tracks store a gallery of past feature vectors (e.g., track.features.append(new_embedding)). If a track persists for 30 minutes at $30\text{ FPS}$, the gallery will hold 54,000 vectors. Computing the matrix dot product against a gallery of this size blocks the main thread.

You must limit the feature gallery size (typically $N_{max} = 100$). Treat the gallery as a FIFO ring buffer. When a new vector is appended, drop the oldest vector to guarantee bounded $\mathcal{O}(1)$ cost matrix computation time.

Non-Linear Camera Motion

The Kalman filter inside standard DeepSORT assumes a linear constant-velocity model. If the physical camera itself is mounted on a rapidly turning drone or a bumpy vehicle, the entire frame shifts between detections. The Kalman filter will misinterpret this global camera ego-motion as the individual object accelerating rapidly.

To deploy DeepSORT on moving cameras, you must inject an ego-motion compensation step. Before running the Kalman predict step, compute an affine or homography transformation matrix of the background (using ORB features or phase correlation), and apply this global transformation matrix directly to the Kalman state vectors to shift the bounding boxes back into alignment with the new frame.

5. Benchmarks & Practical Engineering Takeaways

We benchmarked tracking identity stability across a crowded occlusion dataset (MOT16).

Engineering Guidelines

• Delay Track Confirmation: Do not instantly validate a track on a single detection. False positives from the object detector will spawn ghost tracks. Require a tentative track to hit at least 3 successful assignments over 5 frames before promoting it to a confirmed state and drawing a box on the screen.
• Batch the ReID Network: Do not run the appearance CNN inside a loop for each bounding box. Crop all $N$ bounding boxes from the frame using array slicing, resize them to the input tensor shape, concatenate them into a single batch $[N, C, H, W]$, and execute a single forward pass through the GPU.
• Tune $\lambda$ dynamically: Set $\lambda = 0.9$ (favoring appearance) for high-FPS feeds where objects move predictably. Shift $\lambda$ closer to $0.1$ (favoring spatial distance) if objects are small and lack defining visual features.

6. References & Cross-Links

• Wojke, N., Bewley, A., & Paulus, D. (2017). Simple Online and Realtime Tracking with a Deep Association Metric. IEEE International Conference on Image Processing (ICIP).
• Kuhn, H. W. (1955). The Hungarian Method for the assignment problem. Naval Research Logistics Quarterly.
• Susam, A. (2026). Discrete Kalman Filter Implementation for 1D and 2D Sensor Tracking. Read Article.
• Susam, A. (2026). Optimizing GPU-Accelerated Image Processing Pipelines with CUDA and OpenCV. Read Article.