Optical flow is the per-pixel motion between two video frames. The most accurate recent estimators face a resource conflict. Models built on a cost volume, a table of similarity scores between every pixel and every candidate displacement, can find large motions, but the table grows with the fourth power of image size. They therefore have to work on images shrunk eight-fold, which blurs thin objects and motion edges. WAFT removes the table entirely and refines flow by warping at half resolution. It reports top rankings on Spring, Sintel and KITTI, but its authors say it fails when the starting estimate is far off, for example under extreme motion blur and large displacement on Sintel's 'Ambush 1' (WAFT). This proposal keeps warping as the default and adds a search over displacements only at the few pixels where warping visibly fails. That search uses a pruning rule borrowed from bounded discretization in motion planning: it skips most of the cost volume and still provably finds the best-matching displacement.
In two sentences: when a warping-only flow network leaves a large photometric residual at a pixel, we search for that pixel's best match over a coarse-to-fine tree of candidate displacements. A cheap upper bound on the matching score lets us discard whole regions of the tree without ever scoring them. This gives cost-volume-level recovery of large motions where it is needed and warping-level memory everywhere else, with a guarantee that the search never discards the true best match. That guarantee is the property fixed top-k truncation lacks.
Core Claim
The open tension sits between two camps. On one side are cost-volume methods that claim explicit matching is necessary: PWC-Net, Separable Flow, EMD-Flow and HCVFlow. On the other side is WAFT's evidence that spatial resolution matters more than the matching table. We claim both are partly right, because warping errors are spatially concentrated. If explicit matching is applied to perhaps a few percent of pixels, and done exactly, it should close WAFT's large-displacement failures while costing far less memory than any dense volume.
The method's contribution comes from the motion-planning literature. A Lower Bounding Framework for Motion Planning amid Dynamic Obstacles in 2D discretizes at two levels, coarse cells and then finer boundary sub-segments. It uses relaxations that keep a valid bound, and refining the discretization tightens that bound; in its experiments this halved uncertainty about solution quality, from 16.5% to 8.1%. We apply the same logic to displacement space instead of the robot's workspace.
The bound itself is simple. Partition the candidate target locations into a hierarchy of spatial bins. For each bin, store the per-channel maximum $M_c$ and minimum $m_c$ of the target features. For a query feature $q$, the similarity to any target $f$ in the bin then satisfies
$$q \cdot f \;\le\; \sum_c \max(q_c M_c,\; q_c m_c),$$
where $c$ indexes feature channels. Search proceeds best-first. A bin is opened only if its bound exceeds the best exact score found so far, and the search stops once no unopened bin can beat the incumbent. The number of retained candidates is therefore set per pixel by the bound. Ambiguous pixels with several near-equal peaks open many bins; textured pixels open few. Memory is proportional to the bins actually visited, not to $H \times W \times H \times W$.
Research Program
The system has three parts. First, a WAFT backbone runs unchanged, using the released code at princeton-vl/WAFT. Second, a trigger flags pixels using the warped-feature residual after a few update iterations, and optionally the variance of predicted flow across iterations. Third, the certified search runs at flagged pixels over a feature pyramid of the second frame. The best match it returns, plus a few runner-up peaks, is injected back into WAFT's transformer update as candidate initializations, and refinement continues.
The bins are built once per frame pair by max/min pooling. This is cheap and parallel. It also avoids the problem Two-step Planning of Dynamic UAV Trajectories using Iterative δ-Spaces warns about, where building the pruned structure costs more than the pruning saves.
The main risk is that box bounds become loose in high dimensions. Over 256 channels the bound may be so weak that almost nothing gets pruned. We address this in two ways. We bound in a learned low-dimensional matching projection (16 to 32 channels), then rescore the survivors exactly. We also add a training loss that encourages features to cluster spatially, which tightens bin extents. Whether pruning actually removes most of the volume is the first thing we measure. If it does not, the "certified" framing collapses into an expensive search and the idea fails.
The search is exact for the projected features, so analysis can separate two error sources. One is search error, which should be zero by construction. The other is representation error, where the best feature match is not the true motion. The second is what fixed top-k methods conflate with the first, and we measure it separately.
Baselines
The do-nothing reference is WAFT itself, run from the released checkpoint at the same resolution, with the same iteration count and the same training data (FlyingChairs and FlyingThings3D pretraining, then the standard Sintel/KITTI/Spring fine-tuning). WAFT is the strongest existing method on this question: it ranks first on Spring, Sintel and KITTI and is 1.3x faster than FlowFormer++ (WAFT). Our addition must beat it on average error and must not regress elsewhere. The file gives no per-benchmark end-point error for WAFT, so we have no reported result found on Lacuna for WAFT's Sintel or KITTI end-point error and will reproduce it ourselves. Its reported memory is 9.2 GiB at half resolution on TartanAir, where SEA-RAFT runs out of memory. Beating it means lower end-point error on Sintel Final and on the large-displacement and Ambush subsets, with no more than a small fixed increase in memory.
The strongest memory-efficient cost-volume method is HCVFlow (Hybrid Cost Volume). It keeps a fixed top-8 set of global candidates plus a local dense volume. It reports 16.80% F1-all on KITTI against RAFT's 17.40%, and 1.5 GB of memory at 1080p against RAFT's 8.3 GB. Running the WAFT error-concentration test (Decisive Checks) on RAFT and HCVFlow outputs gives the cost-volume reference curve. For an accuracy reference among cost-volume models, EMD-L reports an F1-all of 4.51 on KITTI-2015 (EMD-Flow). We compare at matched memory on DAVIS 1080p and 4K, where HCVFlow reports 6 GB at 4K and RAFT fails even on 48 GB GPUs.
The ablation that isolates the key ingredient keeps the trigger and the injection fixed and replaces certified search with a fixed top-k at flagged pixels, with k chosen to match our average candidate count. If certified search does not beat this on ambiguous and occluded pixels, the per-pixel adaptive candidate count is not doing the work. A second ablation replaces the residual trigger with random pixel selection at the same budget, to test whether failures really are spatially predictable.
Why not just…?
Why not just run a cheap coarse cost-volume model everywhere and initialize WAFT from it? This is the most serious threat. At Sintel resolution an eighth-scale volume is affordable, and a cascade like this might recover most of Ambush 1. We will run exactly this cascade, using a RAFT-style eighth-scale estimate as WAFT's initialization, at matched compute. Our expected advantage appears in two regimes. At 1080p and 4K, even coarse all-pairs volumes become the memory bottleneck, as the HCVFlow measurements show. And coarse volumes erase thin fast objects before matching, which is PWC-Net's error-propagation problem. If the cascade matches us at all resolutions, we will report that and present the work as an analysis of where warping fails, not as a method.
Why not just increase k in a top-k hybrid volume? A larger k costs memory at every pixel, and it still cannot guarantee keeping the true match when correlation peaks are flat or have many modes (HCVFlow leaves k=8 static). The matched-budget top-k ablation answers this directly. We also report the rate at which the best feature match is dropped, measured against exhaustive search on cropped regions.
Why not just run WAFT for more iterations or at full resolution? WAFT's failures arise when the initial estimate lies outside what local warping can correct, and extra iterations of a local update do not create a global search. We test this by plotting error against iteration count on the Ambush and large-displacement subsets. Higher resolution is limited by the memory WAFT already uses.
Decisive Checks
Three results decide whether the idea is right. First, an error-concentration study. On Sintel, KITTI and Spring validation splits, measure what fraction of WAFT's total end-point error comes from the worst 1%, 5% and 10% of pixels, and how well the warp residual ranks those pixels. If error is not concentrated, or the residual cannot find it, the trigger premise fails. Second, pruning efficiency: report the fraction of bins opened per flagged pixel as a function of projection dimension and image resolution. The method needs this to stay well below the dense volume to make sense. Third, the headline comparison: end-point error on Sintel Final overall and on its large-displacement subset, KITTI-2015 F1-all, and Spring error, with peak memory and latency on DAVIS at 1080p and 4K. These are measured against WAFT, the coarse-volume cascade, HCVFlow and the fixed top-k ablation under one training recipe. Success means lower error than WAFT on large displacements and blur, no regression elsewhere, and lower memory than HCVFlow at 4K.
References
- WAFT: Warping-Alone Field Transforms for Optical Flow
- PWC-Net: CNNs for Optical Flow Using Pyramid, Warping, and Cost Volume
- Separable Flow: Learning Motion Cost Volumes for Optical Flow Estimation
- Explicit Motion Disentangling for Efficient Optical Flow Estimation
- Hybrid Cost Volume for Memory-Efficient Optical Flow
- A Lower Bounding Framework for Motion Planning Amid Dynamic Obstacles in 2D
- Two-step Planning of Dynamic UAV Trajectories Using Iterative δ-Spaces