SORT: Simple Online and Realtime Tracking

论文: Simple Online and Realtime Tracking (ICIP 2016)
作者: Alex Bewley, Zongyuan Ge, Lionel Ott, Fabio Ramos, Ben Upcroft
代码: abewley/sort（~200 行 Python）

一句话总结：SORT 用”卡尔曼滤波预测 + IoU 匈牙利匹配”三步循环实现多目标跟踪，极简但奠基–后续 DeepSORT、ByteTrack、OC-SORT 全部基于此框架。

一、背景：多目标跟踪（MOT）

1.1 什么是 MOT

多目标跟踪（MOT）：在视频每一帧检测出所有物体后，还要保持每个物体跨帧的身份（ID）–”第 1 帧的人 A，在第 2 帧还是 A，不是 B”。

1.2 Tracking-by-Detection 范式

SORT 采用 tracking-by-detection：先用检测器（YOLO/Faster R-CNN）逐帧出框，再用跟踪算法把相邻帧的框关联起来保持 ID。

1
2
3

帧1: 检测 [人, 人, 人]  ->  分配 ID: 1, 2, 3
帧2: 检测 [人, 人, 人]  ->  哪个是 ID1? 哪个是 ID2? -> 关联 -> 更新轨迹
帧3: 检测 [人, 人, 人, 人]  ->  新的人是谁? -> 新建 ID4

SORT 的核心问题：给定上一帧的跟踪结果和当前帧的检测结果，怎么知道哪个检测对应哪个跟踪？

1.3 MOT 评测指标

指标	全称	含义
MOTA	Multiple Object Tracking Accuracy	$\text{MOTA} = 1 - \frac{FN + FP + IDSW}{GT}$，综合漏检+误检+ID切换
MOTP	Multiple Object Tracking Precision	匹配检测框与 GT 的平均 IoU，衡量定位精度
IDSW	ID Switch	一个物体被切换了 ID 的次数（越少越好）
FP	False Positive	误检框数（跟踪输出但 GT 没有）
FN	False Negative	漏检框数（GT 有但跟踪没输出）
IDs	ID F1	ID 分配的 F1 分数

SORT 的主要短板是 IDSW 高（只用 IoU 关联，遮挡后易切换 ID），DeepSORT 用外观特征改善此问题。

二、整体流程

SORT 对每一帧执行”预测-匹配-更新”三步循环：

flowchart TD
    A["当前帧检测结果<br/>dets = [box1, box2, ...]"]
    B["上一帧轨迹 trks"]
    C["卡尔曼滤波: 预测<br/>每个轨迹预测新位置"]
    D["预测框列表 predicts"]
    E["匈牙利匹配<br/>dets × predicts 的 IoU 代价矩阵<br/>找最优配对, IoU < 阈值的丢弃"]
    F{"匹配结果"}
    G["卡尔曼更新<br/>用检测修正预测"]
    H["新建轨迹<br/>初始化卡尔曼滤波"]
    I{"丢失帧数 > max_age?"}
    J["删除轨迹"]
    K["丢失计数 +1"]
    L{"匹配次数 >= min_hits?"}
    M["输出轨迹"]
    N["不输出"]
    O["下一帧重复"]

    B --> C --> D
    A --> E
    D --> E
    E --> F
    F -->|"匹配成功"| G
    F -->|"未匹配检测"| H
    F -->|"未匹配轨迹"| I
    I -->|"是"| J
    I -->|"否"| K
    G --> L
    H --> L
    K --> L
    L -->|"是"| M
    L -->|"否"| N
    M --> O
    N --> O
    O -.-> A

三、卡尔曼滤波详解 ⭐

卡尔曼滤波是 SORT 的核心：预测每个轨迹在当前帧的位置，用检测结果更新（修正）预测。它是一个”信息融合”过程–融合”模型预测”与”传感器观测”，得到更准的估计。

3.1 状态向量与观测向量

SORT 用 7 维状态向量描述每个跟踪目标：

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

符号	含义	说明
$u, v$	框中心坐标	直接观测
$s$	框面积（scale）	直接观测
$r$	宽高比（aspect ratio）	直接观测，模型假设不变（无速度分量）
$\dot{u}, \dot{v}$	中心速度	隐含，不可直接观测
$\dot{s}$	面积变化速度	隐含，不可直接观测

观测向量是 4 维：$\mathbf{z} = [u, v, s, r]$（检测器输出的框）。

为什么用 $(s, r)$ 而非 $(w, h)$？ SORT 假设宽高比 $r$ 在运动中不变（状态转移矩阵中 $r$ 无速度项），用 $(s, r)$ 可解出 $(w, h)$：$w = \sqrt{s \cdot r}$, $h = \sqrt{s / r}$。这样只需对 3 个量（$u, v, s$）建模速度，而非 4 个。

3.2 状态转移矩阵 F（匀速运动模型）

SORT 假设物体做匀速直线运动（位置 += 速度 × dt，dt=1 帧）：

$$
\mathbf{F} = \begin{bmatrix}
1 & 0 & 0 & 0 & 1 & 0 & 0 \
0 & 1 & 0 & 0 & 0 & 1 & 0 \
0 & 0 & 1 & 0 & 0 & 0 & 1 \
0 & 0 & 0 & 1 & 0 & 0 & 0 \
0 & 0 & 0 & 0 & 1 & 0 & 0 \
0 & 0 & 0 & 0 & 0 & 1 & 0 \
0 & 0 & 0 & 0 & 0 & 0 & 1 \
\end{bmatrix}
$$

左上 4×4：位置部分（$u, v, s, r$）的”自保持”
右上 4×3：位置 += 速度（$u’ = u + \dot{u}$, $v’ = v + \dot{v}$, $s’ = s + \dot{s}$）
第 4 行（$r$）：无速度项，$r’ = r$（宽高比不变假设）
右下 3×3：速度自保持（匀速假设：$\dot{u}’ = \dot{u}$）

3.3 观测矩阵 H

从 7 维状态中取出 4 维观测：

$$
\mathbf{H} = \begin{bmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 \
0 & 1 & 0 & 0 & 0 & 0 & 0 \
0 & 0 & 1 & 0 & 0 & 0 & 0 \
0 & 0 & 0 & 1 & 0 & 0 & 0 \
\end{bmatrix}
$$

即 $\mathbf{z} = \mathbf{H} \cdot \mathbf{x}$，只观测 $(u, v, s, r)$，速度不可直接观测。

3.4 预测（Predict）

每帧开始时，对每个轨迹执行预测：

$$
\hat{\mathbf{x}}{k|k-1} = \mathbf{F} \cdot \mathbf{x}{k-1|k-1}
$$
$$
\hat{\mathbf{P}}{k|k-1} = \mathbf{F} \cdot \mathbf{P}{k-1|k-1} \cdot \mathbf{F}^T + \mathbf{Q}
$$

$\hat{\mathbf{x}}_{k|k-1}$：预测的状态（位置 += 速度）
$\hat{\mathbf{P}}_{k|k-1}$：预测的协方差矩阵（不确定性，随预测增大）
$\mathbf{Q}$：过程噪声（模型无法描述的运动不确定性，如突然转弯）

直觉：基于上一帧的位置和速度，推算”物体这一帧应该在哪”。推算越远越不准（协方差增大）。

3.5 更新（Update）

匹配成功后，用检测框修正预测：

$$
\mathbf{y}k = \mathbf{z}k - \mathbf{H} \hat{\mathbf{x}}{k|k-1} \quad \text{(残差：观测 - 预测)}
$$
$$
\mathbf{S}k = \mathbf{H} \hat{\mathbf{P}}{k|k-1} \mathbf{H}^T + \mathbf{R} \quad \text{(残差协方差)}
$$
$$
\mathbf{K}k = \hat{\mathbf{P}}{k|k-1} \mathbf{H}^T \mathbf{S}k^{-1} \quad \text{(卡尔曼增益)}
$$
$$
\mathbf{x}{k|k} = \hat{\mathbf{x}}{k|k-1} + \mathbf{K}_k \mathbf{y}k \quad \text{(修正后的状态)}
$$
$$
\mathbf{P}{k|k} = (\mathbf{I} - \mathbf{K}k \mathbf{H}) \hat{\mathbf{P}}{k|k-1} \quad \text{(修正后的协方差)}
$$

符号	含义
$\mathbf{z}_k$	检测框（观测值）
$\mathbf{y}_k$	残差（检测与预测的偏差）
$\mathbf{R}$	观测噪声（检测器的不确定性）
$\mathbf{K}_k$	卡尔曼增益（权衡信任预测还是信任观测）
$\mathbf{P}$	协方差矩阵（状态估计的不确定性）

直觉：预测说”物体在这”，检测说”物体在那”，卡尔曼增益 $\mathbf{K}$ 决定”更信谁”。预测准（$\mathbf{P}$ 小）时 $\mathbf{K}$ 小、信任预测；检测准（$\mathbf{R}$ 小）时 $\mathbf{K}$ 大、信任检测。更新后不确定性减小。

3.6 初始化

新轨迹首次创建时：

初始状态：$\mathbf{x}_0 = [u, v, s, r, 0, 0, 0]$（速度初始化为 0）
初始协方差：$\mathbf{P}_0$ 设为较大值（速度部分 $\times 1000$，位置部分 $\times 10$），表示”初始速度完全不确定”
观测噪声 $\mathbf{R}$：面积和宽高比部分 $\times 10$（这两项检测不如位置准）

3.7 源码（KalmanBoxTracker）

class KalmanBoxTracker:
    count = 0
    def __init__(self, bbox):
        # 7维状态, 4维观测
        self.kf = KalmanFilter(dim_x=7, dim_z=4)
        self.kf.F = np.array([[1,0,0,0,1,0,0],  # 状态转移矩阵 F
                              [0,1,0,0,0,1,0],
                              [0,0,1,0,0,0,1],
                              [0,0,0,1,0,0,0],  # r 无速度项
                              [0,0,0,0,1,0,0],
                              [0,0,0,0,0,1,0],
                              [0,0,0,0,0,0,1]])
        self.kf.H = np.array([[1,0,0,0,0,0,0],  # 观测矩阵 H
                              [0,1,0,0,0,0,0],
                              [0,0,1,0,0,0,0],
                              [0,0,0,1,0,0,0]])
        # 噪声设置
        self.kf.R[2:, 2:] *= 10.       # 观测噪声: 面积/宽高比部分放大
        self.kf.P[4:, 4:] *= 1000.     # 初始协方差: 速度部分高度不确定
        self.kf.P *= 10.
        self.kf.Q[-1, -1] *= 0.01      # 过程噪声: 面积速度噪声较小
        self.kf.Q[4:, 4:] *= 0.01

        self.kf.x[:4] = bbox_to_state(bbox)  # 初始状态 (速度=0)
        self.id = KalmanBoxTracker.count      # 分配全局 ID
        KalmanBoxTracker.count += 1
        # 轨迹状态计数器
        self.hits = 0                # 总匹配次数
        self.hit_streak = 0          # 连续匹配次数
        self.time_since_update = 0   # 距上次匹配的帧数
        self.age = 0                 # 总存活帧数

    def predict(self):
        self.kf.predict()                     # 卡尔曼预测
        self.age += 1
        if self.time_since_update > 0:
            self.hit_streak = 0               # 中断连续匹配
        self.time_since_update += 1
        return self.kf.x[:4]                  # 返回预测框

    def update(self, bbox):
        self.time_since_update = 0            # 重置丢失计数
        self.hits += 1
        self.hit_streak += 1
        self.kf.update(bbox_to_z(bbox))       # 卡尔曼更新

四、数据关联：IoU + 匈牙利算法

4.1 IoU 代价矩阵

对 $M$ 个检测框和 $N$ 个预测框，计算两两 IoU，构成 $M \times N$ 代价矩阵：

$$
\text{cost}_{ij} = 1 - \text{IoU}(\text{det}_i, \text{pred}_j)
$$

IoU 越大（越重叠）→ cost 越小（越应该匹配）；
IoU = 0（完全不重叠）→ cost = 1。

为什么用 IoU 而非欧氏距离？ IoU 同时考虑位置和大小，对框的尺度不敏感；欧氏距离只看中心点，忽略框大小。

4.2 匈牙利算法

匈牙利算法在代价矩阵上找全局最优一对一配对（总 cost 最小），使得：

每个检测最多配一个预测
每个预测最多配一个检测

源码用 scipy.optimize.linear_sum_assignment 实现：

from scipy.optimize import linear_sum_assignment

def associate(detections, trackers, iou_threshold=0.3):
    if len(trackers) == 0:
        return [], np.arange(len(detections)), []

    # 1. 计算 IoU 矩阵 [M检测 × N预测]
    iou_matrix = iou_batch(detections, trackers)

    # 2. 匈牙利算法求最优匹配（最小化 -IoU = 最大化 IoU）
    row_indices, col_indices = linear_sum_assignment(-iou_matrix)
    matched_indices = np.array(list(zip(row_indices, col_indices)))

    # 3. 过滤 IoU < 阈值的配对
    # 4. 收集未匹配的检测和预测
    unmatched_dets = [d for d in range(len(detections)) if d not in matched_indices[:, 0]]
    unmatched_trks = [t for t in range(len(trackers)) if t not in matched_indices[:, 1]]

    # 过滤低 IoU 配对
    valid = []
    for m in matched_indices:
        if iou_matrix[m[0], m[1]] < iou_threshold:
            unmatched_dets.append(m[0])
            unmatched_trks.append(m[1])
        else:
            valid.append(m)

    return valid, unmatched_dets, unmatched_trks

为什么用匈牙利而非贪心？ 贪心按 IoU 从大到小逐个配，可能局部最优但全局次优。例如 det1 和 pred1 的 IoU=0.8（最高），但 pred1 其实属于 det2（IoU=0.7），贪心会配错。匈牙利找全局最优，避免这种冲突。

4.3 IoU 阈值过滤

匈牙利匹配只是”建议”，IoU 阈值是”判决”–即使匈牙利配对了，IoU < 0.3 也会被拒绝，该检测变未匹配、该轨迹变未匹配。

五、轨迹管理

5.1 轨迹状态机

每个轨迹有 3 个关键计数器：

计数器	含义	何时变化
`hits`	总匹配次数	匹配成功 +1
`hit_streak`	连续匹配次数	匹配成功 +1，丢失时归 0
`time_since_update`	距上次匹配的帧数	匹配时归 0，每帧 +1
`age`	总存活帧数	每帧 +1

5.2 三种情况处理

① 匹配成功：用检测框更新卡尔曼滤波（predict → update），time_since_update=0，hit_streak++。

② 未匹配检测 → 新建轨迹：初始化新卡尔曼滤波（速度=0），分配新 ID，加入轨迹列表。新轨迹需连续匹配 min_hits 次才输出（防误检）。

③ 未匹配轨迹 → 标记丢失：time_since_update++。若超过 max_age，从轨迹列表删除。

5.3 输出条件

轨迹被输出需满足：

if (trk.time_since_update < 1) and \      # 当前帧匹配成功
   (trk.hit_streak >= self.min_hits or \   # 连续匹配 >= min_hits
    self.frame_count <= self.min_hits):    # 或前 min_hits 帧内（特殊分支）
    output.append(trk)

5.4 关键参数

参数	默认值	含义	调大效果
`max_age`	30	轨迹最多丢失多少帧才删除	更耐遮挡，但可能残留幽灵轨迹
`min_hits`	3	新轨迹连续匹配多少帧才输出	更保守（减少误检），但延迟输出
`iou_threshold`	0.3	IoU 低于此值的配对被丢弃	更严格（减少错误关联），但可能漏匹配

5.5 源码（Sort 主循环）

class Sort:
    def __init__(self, max_age=30, min_hits=3, iou_threshold=0.3):
        self.max_age = max_age
        self.min_hits = min_hits
        self.iou_threshold = iou_threshold
        self.trackers = []
        self.frame_count = 0

    def update(self, dets):
        self.frame_count += 1

        # 1. 预测：所有轨迹做卡尔曼预测
        trks = [t.predict() for t in self.trackers]

        # 2. 关联：检测 × 预测 的 IoU 匈牙利匹配
        matched, unmatched_dets, unmatched_trks = \
            associate(dets, trks, self.iou_threshold)

        # 3. 更新匹配成功的轨迹
        for det_idx, trk_idx in matched:
            self.trackers[trk_idx].update(dets[det_idx])

        # 4. 为未匹配检测新建轨迹
        for i in unmatched_dets:
            self.trackers.append(KalmanBoxTracker(dets[i]))

        # 5. 输出 + 清理超时轨迹
        ret = []
        for trk in self.trackers:
            if trk.time_since_update < self.max_age:              # 未超时
                if (trk.hit_streak >= self.min_hits) or \
                   (self.frame_count <= self.min_hits):            # 达输出条件
                    ret.append(trk.to_output())
        # 删除超时轨迹
        self.trackers = [t for t in self.trackers if t.time_since_update < self.max_age]
        return ret

六、逐帧示例

以下来自剪藏的调试过程，展示完整的循环逻辑。

第 1 帧：检测到 3 人。轨迹列表空 → 3 个检测全未匹配 → 初始化 3 个卡尔曼滤波（速度=0），创建轨迹 1/2/3。hit_streak=1 < min_hits=3，不输出。

第 2 帧：检测 3 人。对 3 个轨迹做卡尔曼预测（位置+=速度，但速度=0，所以预测≈上帧）→ 3 个预测框。与 3 个检测算 IoU → 匈牙利全匹配 → 用检测更新卡尔曼（此时速度开始被估计出来）。hit_streak=2 < 3，不输出。

第 3 帧：同上全匹配。hit_streak=3 ≥ min_hits=3 → 输出 3 个轨迹。

第 4-11 帧：稳定跟踪 3 人。

第 12 帧：检测 4 人。3 个匹配成功，1 个未匹配检测 → 新建轨迹 4。轨迹 4 hit_streak=1 < 3，不输出。

第 13 帧：4 检测 4 预测，全匹配。但轨迹 4 hit_streak=2 < 3，输出仍 3。

第 14 帧：轨迹 4 hit_streak=3 ≥ 3 → 输出 4 个轨迹。

第 19 帧：1 个检测与预测虽被匈牙利匹配，但 IoU=0.15 < 阈值 0.3 → 丢弃配对 → 该检测变未匹配（新建轨迹），该轨迹变未匹配（time_since_update++）。

关键：匈牙利匹配只是”建议”，IoU 阈值是”判决”。即使配对了，IoU 不够也会被拒绝。

七、优缺点与改进方向

优点 ✅

极简：仅卡尔曼+IoU 匹配，无深度学习外观模型，~200 行代码
实时：卡尔曼+匈牙利都是轻量算法，速度瓶颈只在检测器
在线：逐帧处理，不需要未来帧
奠基性：后续 DeepSORT、ByteTrack、OC-SORT 全部基于 SORT 框架

局限 ❌

局限	原因	后续改进
无外观特征	只用 IoU，遮挡后 ID 丢失	DeepSORT 加 ReID 外观特征
ID 频繁切换	密集场景 IoU 匹配易混淆	ByteTrack 用低分检测二次匹配
不可恢复丢失轨迹	超 `max_age` 即删除	OC-SORT 加”观测为中心恢复”
依赖检测质量	漏检→轨迹丢失，误检→虚假轨迹	ByteTrack 利用低分检测缓解
匀速运动假设	转弯/变速时预测偏差大	OCSORT 加”观测为中心”动量修正

改进路线

SORT (2016)           基础框架：KF + IoU 匹配
  ↓
DeepSORT (2017)       + 外观特征(ReID) + 马氏距离 → 减少 IDSW
  ↓
ByteTrack (2022)      + 低分检测二次匹配 → 挖掘漏检
  ↓
OC-SORT (2023)        + 观测为中心恢复 → 遮挡后恢复轨迹

八、总结

SORT 的精髓是把跟踪简化为”预测-匹配-更新”三步循环：

卡尔曼滤波预测：用匀速模型推算每个轨迹在当前帧的位置（状态转移矩阵 F + 协方差传播）；
IoU 匈牙利匹配：检测框与预测框算 IoU 代价矩阵，匈牙利算法求全局最优配对，IoU 阈值过滤；
更新/新建/删除：匹配的更新卡尔曼（增益 K 加权融合预测与观测），未匹配检测建新轨迹，未匹配轨迹超 max_age 删除。

三个参数（max_age / min_hits / iou_threshold）控制跟踪行为。SORT 证明了”仅靠运动关联就能做实时跟踪”，成为 MOT 领域的起点。

SORT 详解