💻 computer science

Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking

Tetris 是一种视频目标跟踪系统，它将视频分解为基于瓦片的多联骨牌模型以实现细粒度的时空采样，在将跟踪精度损失控制在 5% 以内的同时，实现了比参考流水线高达 68.8 倍的吞吐量。

原作者： Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung

发布于 2026-05-26

📖 1 分钟阅读☕ 轻松阅读

原作者： Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图通过监控摄像头观察一条繁忙的高速公路，以清点每一辆车并追踪它们的去向。旧有的做法就像聘请一位超级侦探，去查看视频的每一帧画面、屏幕上的每一寸区域，以找出每一辆车。

问题出在哪里？这位侦探将 99% 的时间都花在盯着空旷的天空、树木以及没有车辆的空旷路段上。他们工作得极其努力，却在大量无关紧要的事情上浪费了巨大的能量。

Tetris 是一个新系统，它充当这位侦探的智能管理者。Tetris 不再让侦探查看整个屏幕，而是将视频分解成由小方格组成的网格（就像国际象棋棋盘），并采用一种巧妙的策略，只向侦探展示那些确实有车辆的方格。

以下是 Tetris 的工作原理，使用简单的类比说明：

1. “方格”策略（空间无关性）

想象视频屏幕是一个巨大的拼图。在典型的交通视频中，大多数拼图块只是蓝天或空旷的沥青路面。

旧方法：侦探每一秒都要查看整个拼图。
Tetris 方法：Tetris 拥有一个“智能扫描仪”，快速扫视每一块拼图。如果某块只是天空，就将其扔进垃圾桶；如果某块有车，就保留它。这意味着侦探只需检查那些真正重要的拼图块。

2. “多连块”形状（不再使用枯燥的方框）

以前的系统试图将重要的拼图块组合成整齐的矩形框（像画框一样）。但车辆经常沿对角线或曲线移动。在一个对角线排列的车辆周围画一个矩形框，会包含大量空白区域（就像试图把蛇塞进方形盒子里）。

Tetris 方法：Tetris 使用称为**多连块（polyominoes）**的形状。把它们想象成俄罗斯方块（Tetris）的积木（因此得名）。如果车辆排成对角线，Tetris 就会构建一个对角线形状的积木来完美贴合它们。它不会浪费时间去查看方形框内那些空白的角落。

3. “智能跳过”（空间可变采样）

道路的不同部分并不相同。

停车线：车辆在此处不可预测地停止和启动。需要非常密切地监视（每一帧都要看）。
高速公路出口：车辆以稳定的速度行驶。可以较少频率地监视（每第 4 帧或第 8 帧看一次），而不会丢失追踪。
旧方法：以前的系统对整个屏幕一视同仁。如果它们为了节省时间而跳过帧，可能会错过车辆在停车标志前突然刹车的情况；如果它们查看所有内容，又会在稳定的高速公路上浪费时间。
Tetris 方法：Tetris 学习每个方格的“个性”。它知道停车线需要高度关注，而高速公路出口可以跳过。它为屏幕上的每一个方格制定定制的时间表。

4. “打包”（俄罗斯方块游戏）

在 Tetris 过滤掉垃圾并决定要查看哪些方格后，它手头有一堆来自不同时刻的、分散且形状各异的积木（多连块）。

问题：你不能把这些分散的形状一个接一个地喂给侦探；那样太慢了。
Tetris 方法：Tetris 玩一场俄罗斯方块游戏。它将不同帧中的所有重要形状紧密地打包进一个单一的、整齐的矩形（称为“画布”）中。它们被完美地拼接在一起，几乎不留任何空白空间。
结果：Tetris 不再要求侦探查看 100 个独立的帧，而是给它们一个单一的、打包好的画布。侦探只需工作一次，Tetris 再将结果解包，告诉你车辆在原始视频中的位置。

结果

该论文在七个不同的真实世界交通视频上测试了这个系统。

准确性：其准确性几乎与“做所有事情”的方法一样（准确率损失不到 5%）。
速度：它比以前的智能系统快17 倍，比旧的“查看一切”方法快高达69 倍。

简而言之：Tetris 阻止计算机浪费时间去查看空旷的天空和稳定的道路。它只关注车辆，按照它们移动的确切形状，以它们所需的确切速度进行观察，并将它们打包在一起，以便计算机一次性处理。这就像聘请了一位只盯着嫌疑人、而不是整个城市的侦探。

技术摘要：Tetris——面向高效高保真视频对象跟踪的图块级采样

1. 问题陈述

Tetris 所解决的核心挑战是轨迹实例化（track materialization）的高计算成本，即把原始视频转换为可重用的对象轨迹以供下游分析（如计数、检索、运动分析）使用的过程。在现代“检测即跟踪”（tracking-by-detection）流水线中，对象检测器消耗了 99.4%–99.9% 的运行时间。尽管先前的系统试图通过时间帧采样（跳帧）或空间剪枝（裁剪矩形感兴趣区域，即 ROIs）来降低这一成本，但这些方法存在显著局限性：

时间采样：消除了细粒度轨迹重建所需的帧间运动信息，导致轨迹断裂或身份切换。
矩形 ROI：无法紧密包围非矩形的相关区域（例如对角线行驶的车辆路径），迫使检测器处理大量无关的背景像素。

作者观察到，固定摄像头部署（在交通和监控中很常见）提供了先前工作尚未充分利用的独特优化机会：

空间无关性：平均每帧中 94.5% 的空间区域不包含任何感兴趣对象。
空间变化的采样需求：不同区域根据局部运动模式容忍不同的采样率（例如，交叉口加速的车辆需要比匀速驶离的车辆更高的采样率）。
紧密的非矩形聚类：相关区域形成连通的、非矩形的形状；轴对齐的边界框所包围的面积比实际相关内容多出 40%。

2. 方法论

Tetris 引入了一种基于图块的多联骨牌（tile-based polyomino）数据模型和一个执行引擎，将视频帧分解为正方形图块的网格。它在用户提供的对象检测器和跟踪器之前运行，通过三个优化算子的流水线进行操作：

A. 数据模型：图块与多联骨牌

图块（Tiles）：每帧被划分为 $T_S \times T_S$ 像素的网格。图块被分类为相关（包含对象）或无关（背景）。
多联骨牌（Polyominoes）：相连的相关图块被分组为多联骨牌（由边相邻的正方形组成的任意二维形状）。这允许系统处理跨越多个图块的对象而无需将其拆分，从而避免了矩形 ROI 的低效性。

B. 执行流水线

系统在检测器之前运行三个算子：

相关性分类：一个轻量级分类器（基于 ShuffleNet）预测每个图块的相关性。与先前的代理模型不同，它基于三个输入进行条件判断：
- RGB 图块图像。
- 帧差图像（捕捉运动）。
- 图块位置（捕捉稳定的场景先验，如车道或天空）。
- 输出：一组相关的多联骨牌。
多联骨牌剪枝（ILP）：Tetris 不是跳过整个帧，而是基于学习到的最大图块采样间隔跳过特定的多联骨牌。
- 学习间隔：在一次训练阶段中，系统测量每个图块在不同采样间隔（ $\gamma \in \{1, 2, 4, 8, 16\}$ ）下的经验误跟踪率。
- 优化：对于用户指定的误跟踪率容忍度 $\bar{M}$ ，系统推导出最大间隔矩阵 $\bar{G}_{\bar{M}}$ 。随后，它构建一个**整数线性规划（ILP）**问题，以选择要处理的多联骨牌子集，使得每个图块的采样频率都足以满足其特定的间隔约束，同时最小化处理的图块总数。
多联骨牌打包：幸存的多联骨牌（可能来自不同帧）使用首次适应降序（First-Fit-Descending, FFD）启发式算法打包进固定大小的矩形**画布（canvases）**中。这在保持原始对象尺度的同时，最小化了检测器的调用次数（ $|C|$ ）。

C. 运行时工件与帕累托前沿

在处理完整数据集之前，Tetris 执行一次性的准备阶段：

训练专用于用户检测器的相关性分类器。
学习最大图块采样间隔。
通过扫描系统配置（包括误跟踪率容忍度 $\bar{M}$ 、相关性阈值 $T_r$ 和全帧采样率 $s$ ），生成吞吐量 - 精度权衡的帕累托前沿。
用户根据吞吐量或精度要求选择一个工作点（配置），执行引擎随后将其应用于剩余视频。

3. 主要贡献

基于图块的多联骨牌数据模型：一种新颖的抽象，实现了细粒度的时空剪枝，使系统能够跳过无关图块，并比矩形 ROI 方法更高效地处理非矩形对象形状。
学习最大图块采样间隔：一种方法，将针对每个图块间隔分配的指数级搜索转化为对标量误跟踪率容忍度的一维扫描。这使得 ILP 剪枝器能够根据经验将采样密度自适应地调整到局部运动模式。
执行引擎：一个包含三个算子（分类、剪枝、打包）的流水线，在不牺牲跟踪保真度的情况下减少检测器调用，且与所使用的具体检测器或跟踪器无关。

4. 实验结果

作者在七个固定视频数据集（包括 CalDoT、Amsterdam 和新的 B3D 数据集）上评估了 Tetris，涵盖了多样的交通场景。

精度与吞吐量：在相对于全帧、每帧参考流水线5% 的 HOTA（高阶跟踪精度）损失界限下：
- Tetris 在所有 7 个数据集上均保持在 5% 界限内。
- 先前的系统（OTIF、LEAP）在7 个数据集中的 3 个上超出了该界限。
- 在此精度水平下，Tetris 的吞吐量比先前系统高出1.5 倍至 17.4 倍。
- Tetris 的吞吐量比参考流水线高出4.7 倍至 68.8 倍。
更高容忍度：在 10% HOTA 损失界限下，Tetris 的吞吐量比先前系统最高高出24.7 倍，比参考流水线高出91.2 倍。
消融研究：
- 向分类器添加帧差和位置输入，使 F1 分数平均提高了 1.26%。
- 打包算法实现了**88.93%**的平均打包效率（最高达 99.62%），证明了画布利用的高效性。
- 用于学习间隔的一维容忍度扫描被证明位于或接近穷举式每图块搜索的帕累托前沿，验证了该启发式方法的效率。

5. 意义与主张

论文声称，Tetris 通过超越粗粒度的时间采样和矩形空间剪枝，代表了高效视频分析的重大进步。通过利用固定摄像头的空间稳定性，Tetris 以显著降低的计算成本实现了高保真跟踪（细粒度轨迹）。

作者强调，他们的方法对于交通监控和安防中的固定摄像头部署特别有效，在平衡吞吐量与跟踪精度方面，其表现始终优于先前的最先进系统（OTIF 和 LEAP）。该系统学习和适应局部运动模式的能力，使其即使在激进地剪枝数据时也能保持高保真度，这是均匀采样策略所缺乏的能力。

局限性：当前系统依赖于固定摄像头的假设。将这些图块级优化扩展到移动摄像头（其空间模式随时间变化）被确定为未来的工作方向。