Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking Conference: tetris-db.github.io ; ;
Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung · 2026
Read Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking Conference: tetris-db.github.io ; ; by Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25538.txt.
Introduction
Chanwut Kittivorawong and colleagues cut the cost of turning still-camera video into reusable object tracks. Earlier systems sample whole frames over time, spacing detections too widely to trace true paths. Tetris instead splits frames into tiles, groups useful tiles into polyomino shapes, prunes repeats with an integer program under an accuracy cap, and packs survivors for detection. Across seven still-video sets it stays within five percent of full-frame accuracy while running about seventeen times faster than prior systems.
Catalog record
| CREATOR | Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75527 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25538
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tetris: Tile-level Sampling for Efficient and High-Fidelity Video Object Tracking Conference: tetris-db.github.io ; ; Chanwut Kittivorawong, Alena Chao, Charlie Si, Alvin Cheung Abstract . Track materialization converts raw video into reusable object tracks that downstream queries can run against without rerunning tracking, but extracting those tracks efficiently and with high fidelity remains expensive. Prior systems reduce cost through temporal frame sampling, erasing the inter-frame motion that fine-grained tracking requires. In stationary video, however, large portions of each frame contain no objects of interest, and the remaining regions tolerate different sampling rates. We present Tetris, a track-extraction system that decomposes videos into a tile-based polyomino data model, enabling fine-grained spatiotemporal pruning that reduces detector calls with minimal fidelity loss. Tetris runs three operators upstream of the user-provided detector: a classifier identifies relevant tiles and groups them into polyominoes, an integer linear program (ILP) prunes redundant polyominoes under a user-specified accuracy constraint, and a packer assembles the survivors into canvases that minimize detector calls. Across 7 stationary-video datasets, Tetris stays within a 5% tracking accuracy loss of a full-frame, every-frame reference pipeline, whereas prior systems exceed this bound on 3 of the 7 datasets. At this 5% bound, Tetris achieves up to 17.4 × \times higher throughput than prior systems and up to 68.8 × \times higher than the reference pipeline. 1. Introduction Track materialization from video converts raw video into a reusable set of object tracks that downstream analytics can query repeatedly ( 5 ; 18 ) . For stationary cameras deployed in traffic monitoring and surveillance, each track is a per-object trajectory that supports queries such as counting, retrieval, and motion analysis. Because each materialized track can serve many downstream queries, systems compute tracks once, store them, and reuse them. The bottleneck in this workload is track extraction, the compute-intensive process that produces reusable tracks from raw video. Modern tracking-by-detection pipelines spend 99.4–99.9% of their runtime inside the object detector ( Table 1 ), and long continuous video streams amplify this cost at scale. Reducing the number of detector invocations, or the amount of pixel data each invocation must process, is therefore the primary lever for improving throughput. Many downstream tasks demand fine-grained trajectories, not merely object presence. Decentralized vehicle coordination in understructured traffic scenes relies on per-vehicle trajectories recovered from object tracks ( 32 ) , and traffic-flow studies such as the I-24 MOTION phantom-jam experiment depend on recovering when each vehicle decelerates, re-accelerates, and whether its motion propagates or damps a stop-and-go wave ( 25 ) . Missing, imprecise, or temporally coarse tracks are harmful during abrupt motion changes; producing tracks at the fidelity that such queries require is exactly what makes track extraction expensive. Prior track-materialization systems reduce cost through two strategies, both with corresponding accuracy limits. OTIF ( 5 ) and LEAP ( 33 ) apply whole-frame sampling, which erases the inter-frame motion that fine-grained tracking requires. OTIF additionally crops sampled frames with axis-aligned rectangular regions of interest (ROIs), that is, rectangles whose edges are parallel to the image axes. Such windows still enclose irrelevant pixels whenever the underlying relevant region is non-rectangular. § 2.2 discusses both strategies in detail. Stationary-camera deployments are common in traffic monitoring and surveillance, and they expose a property that prior work has not fully exploited. Because the camera does not move and the scene’s physical layout is fixed, the spatial distribution of relevant content is stable over time. Objects recur in the same image regions and follow the same scene-induced motion patterns. This stability makes it possible to prune at a granularity finer than whole frames and with shapes finer than rectangular ROIs. We identify three properties of stationary video that make this stability exploitable, discussed in more detail in § 2.3 . First, spatial irrelevance : a mean of 94.5% of spatial regions per frame contain no objects of interest. Second, spatially varying sampling requirements : different regions tolerate different sampling rates because local motion patterns demand different temporal resolution, making any single whole-frame sampling rate either wasteful or inaccurate. Third, tight non-rectangular clustering : relevant regions form connected but non-rectangular shapes whose axis-aligned enclosing rectangles contain 40% more area than the regions themselves. To exploit these properties, we present Tetris, a track-extraction system that decomposes stationary-camera video into a tile-based polyomino data model ( 11 ) , enabling fine-grained spatiotemporal pruning that reduces detector calls without sacrificing fidelity. Tetris divides each frame into a grid of square tiles and groups connected relevant tiles into polyominoes, non-rectangular regions that tightly enclose relevant content ( § 4 ). Importantly, Tetris is agnostic to the object detector and tracker, and it lets the user define the accuracy target ( § 6.3 ). The Tetris execution engine ( § 5 ) runs an optimized tracking pipeline of three operators (classify, prune, pack) upstream of the user-provided detector, then unpacks the resulting detections for the tracker ( § 3 ). This extraction-time pipeline is preceded by a one-time training phase that, once per dataset, trains a lightweight relevance classifier specialized to the user-provided detector ( § 6.1 ) and learns the maximum tile sampling gaps the pruner relies on ( § 6.2 ). To use Tetris, users provide a stationary-camera video dataset, an object detector and a tracker, and either a throughput requirement or an accuracy requirement. Tetris then runs a one-time preparation step on samples from the dataset, producing the artifacts needed for efficient extraction. These artifacts include a relevance classifier, learned maximum tile sampling gaps, and a Pareto frontier of candidate configurations that helps the user select an operating point. After the user selects a configuration, Tetris’s execution engine extracts tracks on the remaining video data under that configuration. On seven publicly available stationary-video datasets, Tetris keeps HOTA loss below 5% relative to the reference pipeline ( § 2.1 ), while prior systems exceed this bound on 3 of the 7 datasets. At this 5% bound, Tetris delivers 1.5-17.4 \times higher throughput than prior systems and 4.7-68.8 \times higher throughput than the reference pipeline. At a 10% HOTA-loss bound, Tetris achieves 1.6-24.7 \times higher throughput than prior systems and 10.4-91.2 \times higher throughput than the reference pipeline ( § 7 ). In sum, we make the following contributions. • A tile-based polyomino data model and an execution engine for efficient track extraction. The engine runs three operators upstream of the user-provided detector: a classifier identifies polyominoes of relevant tiles, an ILP prunes redundant polyominoes constrained by learned maximum tile sampling gaps, and a polyomino packing algorithm packs survivors into fewer canvases to minimize detector invocations. • A method for learning maximum tile sampling gaps from empirical per-tile mistrack rates. For each mistrack-rate tolerance, the method selects the largest measured gap that remains within the tolerance at each tile, turning an exponential search over per-tile gap assignments into a one-dimensional sweep over the scalar tolerance. At runtime, these gaps become ILP constraints that let the execution engine prune polyominoes according to empirically measured mistrack rates. • An evaluation on seven stationary-video datasets demonstrating that, at a 5% HOTA-loss bound, Tetris consistently meets the bound, whereas prior systems fail to do so on 3 of the 7 datasets. Compared with prior systems at