💻 computer science

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

Tetris is a video object tracking system that decomposes videos into a tile-based polyomino model to enable fine-grained spatiotemporal sampling, achieving up to 68.8x higher throughput than reference pipelines while maintaining tracking accuracy within a 5% loss margin.

Original authors: Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung

Published 2026-05-26

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to watch a busy highway from a security camera to count every car and track where they are going. The old way of doing this is like hiring a super-detective to look at every single frame of the video, every single inch of the screen, to find every car.

The problem? The detective spends 99% of their time staring at empty sky, trees, and empty road sections where no cars are. They are working incredibly hard but wasting a massive amount of energy on things that don't matter.

Tetris is a new system that acts like a smart manager for this detective. Instead of making them look at the whole screen, Tetris breaks the video down into a grid of small square tiles (like a chessboard) and uses a clever strategy to only show the detective the tiles that actually have cars in them.

Here is how Tetris works, using simple analogies:

1. The "Tile" Strategy (Spatial Irrelevance)

Imagine the video screen is a giant jigsaw puzzle. In a typical traffic video, most of the puzzle pieces are just blue sky or empty asphalt.

Old Way: The detective looks at the whole puzzle every second.
Tetris Way: Tetris has a "smart scanner" that quickly glances at each puzzle piece. If a piece is just sky, it throws it in the trash. If a piece has a car, it keeps it. This means the detective only has to examine the pieces that actually matter.

2. The "Polyomino" Shape (No More Boring Boxes)

Previous systems tried to group the important pieces into neat, rectangular boxes (like a picture frame). But cars often move in diagonal lines or curves. A rectangular box around a diagonal line of cars would include a lot of empty space (like trying to fit a snake into a square box).

Tetris Way: Tetris uses shapes called polyominoes. Think of these like Tetris blocks (hence the name). If the cars are in a diagonal line, Tetris builds a diagonal block to fit them perfectly. It doesn't waste time looking at the empty corners inside a square box.

3. The "Smart Skip" (Spatially Varying Sampling)

Not all parts of the road are the same.

The Stop Line: Cars stop and start unpredictably here. They need to be watched very closely (every frame).
The Highway Exit: Cars move at a steady speed. They can be watched less often (every 4th or 8th frame) without losing track.
Old Way: Previous systems treated the whole screen the same. If they skipped frames to save time, they might miss a car braking suddenly at a stop sign. If they watched everything, they wasted time on the steady highway.
Tetris Way: Tetris learns the "personality" of each tile. It knows the stop line needs high attention and the highway exit can be skipped. It creates a custom schedule for every single tile on the screen.

4. The "Packing" (The Tetris Game)

After Tetris filters out the trash and decides which tiles to watch, it has a bunch of scattered, oddly shaped blocks (the polyominoes) from different moments in time.

The Problem: You can't feed these scattered shapes to the detective one by one; it's too slow.
Tetris Way: Tetris plays a game of Tetris. It takes all the important shapes from different frames and packs them tightly together into a single, neat rectangle (a "canvas"). It fits them together so perfectly that there is almost no empty space left.
The Result: Instead of asking the detective to look at 100 separate frames, Tetris gives them one single, packed canvas. The detective does their work once, and Tetris unpacks the results to tell you where the cars were in the original video.

The Results

The paper tested this system on seven different real-world traffic videos.

Accuracy: It stayed almost as accurate as the "do everything" method (losing less than 5% accuracy).
Speed: It was 17 times faster than previous smart systems and up to 69 times faster than the old "look at everything" method.

In short: Tetris stops the computer from wasting time looking at empty sky and steady roads. It only looks at the cars, in the exact shapes they move, at the exact speed they need, and packs them all together so the computer can process them in one go. It's like hiring a detective who only looks at the suspects, not the whole city.

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

1. Problem Statement

The core challenge addressed by Tetris is the high computational cost of track materialization—the process of converting raw video into reusable object tracks for downstream analytics (e.g., counting, retrieval, motion analysis). In modern tracking-by-detection pipelines, the object detector consumes 99.4–99.9% of the runtime. While prior systems attempt to reduce this cost through temporal frame sampling (skipping frames) or spatial pruning (cropping rectangular Regions of Interest, or ROIs), these approaches suffer from significant limitations:

Temporal Sampling: Erases inter-frame motion required for fine-grained trajectory reconstruction, leading to fragmented tracks or identity switches.
Rectangular ROIs: Fail to tightly enclose non-rectangular relevant regions (e.g., diagonal vehicle paths), forcing the detector to process large amounts of irrelevant background pixels.

The authors observe that stationary camera deployments (common in traffic and surveillance) offer unique opportunities for optimization that prior work has not fully exploited:

Spatial Irrelevance: A mean of 94.5% of spatial regions per frame contain no objects of interest.
Spatially Varying Sampling Requirements: Different regions tolerate different sampling rates based on local motion patterns (e.g., accelerating vehicles at an intersection require higher sampling than steady-speed vehicles exiting).
Tight Non-Rectangular Clustering: Relevant regions form connected, non-rectangular shapes; axis-aligned bounding boxes enclose 40% more area than the actual relevant content.

2. Methodology

Tetris introduces a tile-based polyomino data model and an execution engine that decomposes video frames into a grid of square tiles. It operates upstream of the user-provided object detector and tracker through a pipeline of three optimized operators:

A. Data Model: Tiles and Polyominoes

Tiles: Each frame is divided into a grid of $T_S \times T_S$ pixels. Tiles are classified as relevant (containing objects) or irrelevant (background).
Polyominoes: Connected relevant tiles are grouped into polyominoes (arbitrary 2D shapes formed by edge-adjacent squares). This allows the system to process objects that span multiple tiles without splitting them, avoiding the inefficiency of rectangular ROIs.

B. The Execution Pipeline

The system runs three operators before the detector:

Relevance Classification: A lightweight classifier (based on ShuffleNet) predicts the relevance of each tile. Unlike prior proxy models, it conditions on three inputs:
- RGB tile image.
- Frame-difference image (capturing motion).
- Tile position (capturing stable scene priors like lanes or sky).
- Output: A set of relevant polyominoes.
Polyomino Pruning (ILP): Instead of skipping whole frames, Tetris skips specific polyominoes based on learned maximum tile sampling gaps.
- Learning Gaps: During a one-time training phase, the system measures empirical mistrack rates for each tile at various sampling gaps ( $\gamma \in \{1, 2, 4, 8, 16\}$ ).
- Optimization: For a user-specified mistrack-rate tolerance $\bar{M}$ , the system derives a matrix of maximum gaps $\bar{G}_{\bar{M}}$ . It then formulates an Integer Linear Program (ILP) to select a subset of polyominoes to process such that every tile is sampled frequently enough to satisfy its specific gap constraint, minimizing the total number of tiles processed.
Polyomino Packing: The surviving polyominoes (which may come from different frames) are packed into fixed-size rectangular canvases using a First-Fit-Descending (FFD) heuristic. This minimizes the number of detector invocations ( $|C|$ ) while preserving the original object scale.

C. Runtime Artifacts and Pareto Frontier

Before processing the full dataset, Tetris performs a one-time preparation phase:

Trains the relevance classifier specialized to the user's detector.
Learns the maximum tile sampling gaps.
Generates a Pareto frontier of throughput-accuracy trade-offs by sweeping system configurations (including the mistrack-rate tolerance $\bar{M}$ , relevance threshold $T_r$ , and whole-frame sampling rate $s$ ).
The user selects an operating point (configuration) based on throughput or accuracy requirements, which the execution engine then applies to the remaining video.

3. Key Contributions

Tile-based Polyomino Data Model: A novel abstraction that enables fine-grained spatiotemporal pruning, allowing the system to skip irrelevant tiles and handle non-rectangular object shapes more efficiently than rectangular ROI approaches.
Learning Maximum Tile Sampling Gaps: A method that transforms an exponential search over per-tile gap assignments into a one-dimensional sweep over a scalar mistrack-rate tolerance. This allows the ILP pruner to adapt sampling density to local motion patterns empirically.
Execution Engine: A three-operator pipeline (Classify, Prune, Pack) that reduces detector calls without sacrificing tracking fidelity, agnostic to the specific detector or tracker used.

4. Experimental Results

The authors evaluated Tetris on seven stationary-video datasets (including CalDoT, Amsterdam, and new B3D datasets) covering diverse traffic scenarios.

Accuracy vs. Throughput: At a 5% HOTA (Higher Order Tracking Accuracy) loss bound relative to a full-frame, every-frame reference pipeline:
- Tetris stays within the 5% bound on all 7 datasets.
- Prior systems (OTIF, LEAP) exceed this bound on 3 of the 7 datasets.
- Tetris achieves 1.5× to 17.4× higher throughput than prior systems at this accuracy level.
- Tetris achieves 4.7× to 68.8× higher throughput than the reference pipeline.
Higher Tolerance: At a 10% HOTA loss bound, Tetris achieves up to 24.7× higher throughput than prior systems and 91.2× higher than the reference pipeline.
Ablation Studies:
- Adding frame-difference and position inputs to the classifier improved F1 scores by an average of 1.26%.
- The packing algorithm achieved an average packing efficacy of 88.93% (up to 99.62%), demonstrating efficient canvas utilization.
- The one-dimensional tolerance sweep for learning gaps was shown to lie on or near the Pareto frontier of an exhaustive per-tile search, validating the heuristic's efficiency.

5. Significance and Claims

The paper claims that Tetris represents a significant advancement in efficient video analytics by moving beyond coarse-grained temporal sampling and rectangular spatial pruning. By exploiting the spatial stability of stationary cameras, Tetris achieves high-fidelity tracking (fine-grained trajectories) at significantly reduced computational costs.

The authors emphasize that their approach is particularly effective for stationary-camera deployments in traffic monitoring and surveillance, where it consistently outperforms prior state-of-the-art systems (OTIF and LEAP) in balancing throughput and tracking accuracy. The system's ability to learn and adapt to local motion patterns allows it to maintain high fidelity even when aggressively pruning data, a capability that uniform sampling strategies lack.

Limitations: The current system relies on the assumption of stationary cameras. Extending these tile-level optimizations to moving cameras, where spatial patterns shift over time, is identified as a direction for future work.