SORT

SORT (Simple Online and Realtime Tracking) is a multi-object tracking algorithm introduced by Bewley et al. at ICIP 2016. It follows the tracking-by-detection pattern: a detector finds boxes in every frame, and SORT links them into trajectories using a Kalman filter per object and the Hungarian algorithm for frame-to-frame assignment, with no appearance features. The authors argued that, given a strong detector, these classical components rival far more complex online trackers at a fraction of the cost. It became a standard object tracking baseline that DeepSORT, ByteTrack, and OC-SORT build on.

Problem

SORT solves online multi-object tracking: detections of the same object must share a persistent identity, identities start and end as objects appear and leave, and frame $t$ is processed using only its detections and the state carried over from frame $t-1$.

Inputs and Outputs

Input: per frame, detected boxes $[x_1, y_1, x_2, y_2]$, usually with confidence scores. SORT never looks at the image. In the paper, detections came from Faster R-CNN with a VGG16 backbone, keeping person detections with confidence above 0.5.

Output: per frame, the boxes of confirmed tracks, each with an integer identity.

Intuition

SORT bets that three things usually suffice. Good detections: if the detector rarely misses or fires on background, the tracker only has to connect the dots. A simple motion model: between frames, objects move little and at roughly constant velocity, so a Kalman filter on each box predicts its next position and smooths detector jitter. Frame-to-frame assignment: the best one-to-one matching between predicted boxes and detections, by overlap, links them. Appearance, long-term occlusion reasoning, and re-identification are deliberately left out.

Algorithm

Each track holds a Kalman filter on the box center $(u, v)$, area $s$, and aspect ratio $r$, plus the velocities of center and area:

$$\mathbf{x} = [u, v, s, r, \dot{u}, \dot{v}, \dot{s}]^\top .$$

The aspect ratio is assumed constant, so it has no velocity; this is the bounding-box state mentioned in the Kalman filter article. For each frame:

for each frame with detections D:
    predict every track one frame ahead
    C[i, j] = IoU(detection i, predicted box of track j)
    solve the assignment that maximizes total IoU (Hungarian algorithm)
    discard assigned pairs with IoU < IoU_min
    Kalman-update each matched track with its detection
    start a new track for each unmatched detection
    report matched tracks that have passed probation
    delete tracks unmatched for too long

Prediction and association. Every track is propagated with the constant-velocity model; an unmatched track keeps its uncorrected prediction. The paper’s cost is the IoU distance between detections and predicted boxes; the reference implementation passes negative IoU to a linear assignment solver. This is global nearest neighbor data association.

Track creation. A detection whose overlap with every track is below $\mathrm{IoU}_{\min}$ starts a track from the box geometry, with zero velocity and a large velocity variance. The track must keep matching detections through a probationary period, of unstated length in the paper, so that isolated false positives do not become tracks. The reference implementation (github.com/abewley/sort) reports a track only after min_hits consecutive matches (default 3), not counting the creating frame, so an object first appears on its fourth consecutive detection; a missed frame resets the count. During the first min_hits frames of a sequence, every matched track is reported.

Track deletion. The paper terminates tracks not detected for $T_{\text{lost}} = 1$ frame, because the constant-velocity model predicts poorly over long gaps and re-identification was out of scope. The reference implementation removes a track once the frames since its last match exceed max_age (default 1): a track coasts, unreported, through one missed frame and is deleted after two consecutive misses. An object detected again after deletion gets a new identity.

Mathematical Formulation

A detection with width $w = x_2 - x_1$ and height $h = y_2 - y_1$ gives the measurement

$$\mathbf{z} = [u, v, s, r]^\top = \left[\, x_1 + \tfrac{w}{2},\; y_1 + \tfrac{h}{2},\; w h,\; \tfrac{w}{h} \,\right]^\top ,$$

and a state maps back to a box through $w = \sqrt{s r}$ and $h = s / w$. With one frame as the time step, the motion and measurement models are

$$\mathbf{x}_{t} = F \mathbf{x}_{t-1} + \mathbf{w}_t, \qquad F = \begin{bmatrix} I_4 & E \\ 0 & I_3 \end{bmatrix}, \qquad E = \begin{bmatrix} I_3 \\ \mathbf{0}^\top \end{bmatrix},$$ $$\mathbf{z}_t = H \mathbf{x}_t + \mathbf{n}_t, \qquad H = \begin{bmatrix} I_4 & 0 \end{bmatrix},$$

with $\mathbf{w}_t \sim \mathcal{N}(0, Q)$ and $\mathbf{n}_t \sim \mathcal{N}(0, R)$: $u$, $v$, and $s$ advance by their velocities, $r$ stays fixed, and the first four components are observed. The reference implementation uses fixed diagonal matrices, with ten times more measurement variance on area and aspect ratio than on the center, small process noise on the velocities, and an initial velocity variance a thousand times that of the observed components.

The overlap between a detection $A$ and a predicted box $B$ is

$$\mathrm{IoU}(A, B) = \frac{|A \cap B|}{|A \cup B|} = \frac{|A \cap B|}{|A| + |B| - |A \cap B|} \in [0, 1].$$

The assignment picks pairs $(i, j)$, each detection $d_i$ and predicted box $b_j$ used at most once, that maximize $\sum \mathrm{IoU}(d_i, b_j)$; pairs with $\mathrm{IoU}(d_i, b_j) < \mathrm{IoU}_{\min}$ are then dropped, leaving both sides unmatched rather than re-pairing them.

Parameters

The reference implementation exposes three parameters:

• iou_threshold ($\mathrm{IoU}_{\min}$, default 0.3). Higher values reject more wrong matches but break tracks under fast motion, low frame rates, or jittery boxes; lower values let neighbors swap.
• max_age (default 1). Unmatched frames tolerated before deletion. Larger values bridge short occlusions, but a coasting track drifts and may capture the wrong detection.
• min_hits (default 3). Consecutive matches before a track is reported. Larger values suppress false-positive tracks but delay real objects and drop short ones.

The paper reports tuning the initial covariances, $\mathrm{IoU}_{\min}$, and $T_{\text{lost}}$ on a training and validation split.

Complexity

With $N$ detections and $M$ tracks, a frame costs $O(NM)$ for the IoU matrix, $O(M)$ for the seven-dimensional Kalman steps, and $O(n^3)$ worst case for the assignment, with $n = \max(N, M)$. For tens of objects this is negligible next to the detector. The authors report that tracking, excluding detection, runs at 260 Hz on one core of a 2.5 GHz Intel i7, over 20 times faster than other state-of-the-art trackers; in their MOTChallenge 2015 speed–accuracy plot, the only faster tracker was far less accurate.

Implementation

A compact SORT following the reference implementation’s state, noise settings, and track rules, on three synthetic objects. Object A is missed in frame 6, and a false positive appears once in frame 5:

import numpy as np
from scipy.optimize import linear_sum_assignment

# Constant-velocity model on z = [u, v, s, r]; state x = [u, v, s, r, du, dv, ds].
F = np.eye(7)
F[0, 4] = F[1, 5] = F[2, 6] = 1.0
H = np.eye(4, 7)
Q = np.diag([1, 1, 1, 1, 0.01, 0.01, 0.0001])  # noise settings of the reference code
R = np.diag([1, 1, 10, 10])


def box_to_z(b):  # [x1, y1, x2, y2] -> [u, v, s, r]
    w, h = b[2] - b[0], b[3] - b[1]
    return np.array([b[0] + w / 2, b[1] + h / 2, w * h, w / h])


def x_to_box(x):
    w = np.sqrt(x[2] * x[3])
    h = x[2] / w
    return np.array([x[0] - w / 2, x[1] - h / 2, x[0] + w / 2, x[1] + h / 2])


def iou(a, b):  # pairwise IoU between box arrays of shape (n, 4) and (m, 4)
    tl = np.maximum(a[:, None, :2], b[None, :, :2])
    br = np.minimum(a[:, None, 2:], b[None, :, 2:])
    inter = np.prod(np.clip(br - tl, 0, None), axis=2)
    area = lambda c: (c[:, 2] - c[:, 0]) * (c[:, 3] - c[:, 1])
    return inter / (area(a)[:, None] + area(b)[None, :] - inter)


class Track:
    count = 0

    def __init__(self, box):
        self.x = np.r_[box_to_z(box), 0, 0, 0]  # velocities start at zero
        self.P = np.diag([10, 10, 10, 10, 1e4, 1e4, 1e4])  # ...with large variance
        Track.count += 1
        self.id, self.misses, self.streak = Track.count, 0, 0

    def predict(self):
        if self.x[2] + self.x[6] <= 0:  # keep the area positive
            self.x[6] = 0
        self.x, self.P = F @ self.x, F @ self.P @ F.T + Q
        if self.misses > 0:
            self.streak = 0
        self.misses += 1
        return x_to_box(self.x)

    def update(self, box):
        y = box_to_z(box) - H @ self.x
        S = H @ self.P @ H.T + R
        K = self.P @ H.T @ np.linalg.inv(S)
        self.x, self.P = self.x + K @ y, (np.eye(7) - K @ H) @ self.P
        self.misses, self.streak = 0, self.streak + 1


class Sort:
    def __init__(self, max_age=1, min_hits=3, iou_threshold=0.3):
        self.max_age, self.min_hits, self.iou_min = max_age, min_hits, iou_threshold
        self.tracks, self.frame = [], 0

    def update(self, dets):
        self.frame += 1
        preds = np.array([t.predict() for t in self.tracks]).reshape(-1, 4)
        cost = iou(dets, preds)
        rows, cols = linear_sum_assignment(-cost)  # maximize total IoU
        matched_dets = set()
        for d, t in zip(rows, cols):
            if cost[d, t] >= self.iou_min:  # reject low-overlap pairs
                self.tracks[t].update(dets[d])
                matched_dets.add(d)
        for d in range(len(dets)):
            if d not in matched_dets:  # unmatched detection: new tentative track
                self.tracks.append(Track(dets[d]))
        out = [(t.id, x_to_box(t.x)) for t in self.tracks
               if t.misses == 0
               and (t.streak >= self.min_hits or self.frame <= self.min_hits)]
        self.tracks = [t for t in self.tracks if t.misses <= self.max_age]
        return out


# Three objects: A moves right, B moves left, C moves down.
# A is missed in frame 6 and a one-frame false positive appears in frame 5.
rng = np.random.default_rng(0)
tracker = Sort()
for f in range(1, 11):
    gt = [[10 + 8 * f, 20, 40 + 8 * f, 80],
          [200 - 6 * f, 30, 230 - 6 * f, 90],
          [100, 120 + 5 * f, 140, 160 + 5 * f]]
    dets = np.array(gt, float) + rng.normal(0, 1.0, (3, 4))
    if f == 6:
        dets = dets[1:]
    if f == 5:
        dets = np.vstack([dets, [300, 200, 320, 240]])
    shown = ", ".join(f"id{i}:({b[0]:.0f},{b[1]:.0f})" for i, b in tracker.update(dets))
    print(f"frame {f}: {len(dets)} dets -> {shown}")

Output:

frame 1: 3 dets -> id1:(18,20), id2:(193,30), id3:(99,124)
frame 2: 3 dets -> id1:(24,20), id2:(187,30), id3:(100,131)
frame 3: 3 dets -> id1:(34,20), id2:(181,30), id3:(100,136)
frame 4: 3 dets -> id1:(42,20), id2:(175,31), id3:(100,140)
frame 5: 4 dets -> id1:(51,21), id2:(169,31), id3:(100,145)
frame 6: 2 dets -> id2:(164,31), id3:(100,149)
frame 7: 3 dets -> id2:(158,31), id3:(100,154)
frame 8: 3 dets -> id2:(151,31), id3:(100,159)
frame 9: 3 dets -> id1:(82,20), id2:(146,31), id3:(100,164)
frame 10: 3 dets -> id1:(89,20), id2:(140,30), id3:(101,170)

The objects are reported from frame 1 because of the start-up rule. The false positive starts a tentative track that is never reported and is deleted two frames later. Object A coasts through its missed frame, is matched again in frame 7 under the same identity, and returns to the output in frame 9, after three consecutive matches. The reference implementation produces identical identities and boxes on the same detections.

Properties and Behavior

• Detection quality dominates. On the paper’s validation sequences, replacing the ACF pedestrian detector with Faster R-CNN (VGG16) raised SORT’s MOTA from 15.1 to 34.0; the switch also helped the more complex MDP tracker. On the 2015 MOTChallenge test set, SORT’s MOTA of 33.4 was the highest among the online trackers the authors compared.
• Overlap favors similar boxes. The authors argue that IoU association handles short occlusions by passing objects: only the occluder is detected and matches its own track, while the hidden track is left unassigned rather than pulled onto the wrong object. With $T_{\text{lost}} = 1$, though, it survives only briefly.
• Greedy in time. Each frame’s assignment is final; a wrong match is never revisited.

Limitations

• Identity switches. Crossing or occluding objects can exchange identities when predicted boxes overlap the wrong detections. In the paper’s benchmark table, SORT had more identity switches (1,001) than any other online tracker listed.
• No appearance model or re-identification. Objects in similar positions cannot be told apart by how they look, and an object missed for longer than max_age frames returns under a new identity.
• Linear motion. Abrupt maneuvers, nonlinear motion such as dancing, and camera motion, treated as object motion, make predictions miss their detections.
• Overlap-only gating. Small or fast objects can move more than their own size between frames, giving zero IoU even for an obvious match.

Variants

DeepSORT (Wojke, Bewley & Paulus, 2017) adds appearance: a CNN trained offline on person re-identification data embeds each box, and the cost combines the smallest cosine distance to a track’s last 100 embeddings with the Kalman Mahalanobis distance, which also gates implausible pairs (the reported experiments used appearance alone in the cost). A matching cascade gives priority to recently seen tracks, SORT’s IoU matching handles the rest, and lost tracks survive 30 frames. On MOT16 with the same detections, identity switches fell about 45%, from 1,423 to 781.

ByteTrack (Zhang et al., 2022) also uses low-confidence detections: after matching high-score detections, it matches the remaining tracks to low-score ones, often occluded objects, and discards unmatched low-score boxes.

OC-SORT (Cao et al., 2023) corrects the error a track accumulates while coasting: when a lost track is matched again, it re-updates the filter along a virtual trajectory between the observations before and after the gap. It also adds an observation-based motion-direction term to the IoU cost and a second pass matching unmatched tracks’ last observations to leftover detections. The authors report over 700 frames per second on a CPU given detections, and strong results on DanceTrack, whose motion is highly nonlinear.

BoT-SORT (Aharon, Orfaig & Bobrovsky, 2022) extends ByteTrack: it warps Kalman predictions by a frame-to-frame affine camera-motion estimate from tracked background keypoints, estimates box width and height directly, and, with re-identification, uses the element-wise minimum of the IoU distance and a gated appearance distance as the cost.

StrongSORT (Du et al., 2023) upgrades DeepSORT’s detector, embedding, and association, and adds AFLink, which links tracklets without appearance information, and Gaussian-smoothed interpolation to fill gaps from missed detections.