Source-linked AI summary
Full Flow: Optical Flow Estimation By Global Optimization over Regular Grids
Qifeng Chen, Vladlen Koltun
TL;DR
Optical-flow estimation traditionally relies on local refinement or descriptor-based initialization, whereas global optimization over the full mapping space has been difficult. The paper uses a regular-grid Markov random field with structure-exploiting optimization and reports state-of-the-art accuracy on Sintel and KITTI 2015 without external descriptors.
Problem
Global optimization of classical optical-flow objectives over full mapping spaces is difficult, while local refinement and descriptor-based initialization have important limitations for large displacements.
Method
The method globally optimizes a classical Horn-Schunck-type objective over dense regular-grid mappings as a Markov random field, exploiting regularity to accelerate message passing without descriptor matching.
Results
The approach achieves state-of-the-art accuracy on the Sintel and KITTI 2015 optical-flow benchmarks.
Takeaways & Limitations
Full-space global optimization of the classical flow objective is feasible and can produce accurate large-displacement optical flow without externally defined descriptors.
Takeaways & Limitations
The efficient min-convolution algorithm assumes a convex penalty function, although other linear-time algorithms can handle non-convex functions.
Abstract
from arXiv · showhide
We present a global optimization approach to optical flow estimation. The approach optimizes a classical optical flow objective over the full space of mappings between discrete grids. No descriptor matching is used. The highly regular structure of the space of mappings enables optimizations that reduce the computational complexity of the algorithm's inner loop from quadratic to linear and support efficient matching of tens of thousands of nodes to tens of thousands of displacements. We show that one-shot global optimization of a classical Horn-Schunck-type objective over regular grids at a single resolution is sufficient to initialize continuous interpolation and achieve state-of-the-art performance on challenging modern benchmarks.
1. Introduction
Optical flow is important for visual perception and many computer-vision tasks, but classical optimization refines one candidate locally and can get trapped in local minima. The paper instead globally optimizes the classical objective over full regular grids, avoiding descriptor matching while achieving state-of-the-art benchmark accuracy.
- Optical flow supports self-motion control, spatial-layout estimation, object perception, visual odometry, reconstruction, segmentation, tracking, and recognition.
- The classical dense-flow objective combines a data term penalizing visually dissimilar matches with a regularization term penalizing incoherent motion.
- Traditional iterative local refinement maintains one candidate flow, does not optimize globally, and is prone to local minima.
- Global optimization has generally been considered intractable without substantial restrictions, and prior discrete methods heuristically pruned flows using descriptor matching.
- The proposed method globally optimizes the classical objective over full discrete-grid mappings, exploits regularity for faster inner-loop computation, and uses no separately defined descriptor matching.
- The approach achieves state-of-the-art accuracy on both the Sintel and KITTI 2015 optical-flow benchmarks.
2. Background
Prior optical-flow methods typically refine flows locally or use descriptor-based initialization, while global formulations often impose restrictive assumptions. This work treats the objective as a dense-grid Markov random field and makes full-space optimization feasible by exploiting regular structure.
- Local refinement can be accurate for small displacements but does not optimize the objective globally over the full flow space.
- Descriptor matching can improve initialization for large displacements but is separately trained or designed, may not optimize a coherent objective, and can produce globally suboptimal initializations.
- Earlier global formulations use quadratic relaxation or functional lifting and impose assumptions such as convexity of the regularizer or data term.
- The proposed formulation treats the classical objective as a Markov random field with dense grids and large two-dimensional label spaces.
- Full-space optimization avoids heuristic pruning and separately defined descriptors, while preserving the regular structure of mappings.
- Min-convolution algorithms exploit full-grid regularity to reduce message-passing complexity from quadratic to linear.
3. Model
The model represents optical flow as discrete mappings from pixels to bounded displacements, using a buffer zone, patch-based data costs, and spatial regularization. Its regular-grid structure supports global optimization, while some fast algorithms require convex penalties.
- Each pixel maps to a displaced location in an augmented domain containing a surrounding buffer zone that absorbs out-of-field motion.
- Figure 1 connects each source pixel spatially to four neighbors and temporally to (2ς + 1)2 target pixels.
- The displacement bound ς is estimated from training data; on KITTI it is 242 pixels at full resolution and 81 pixels for the 1/3-resolution optimization.
- The objective uses a 4-connected grid and a data term that penalizes mappings between dissimilar source and target pixels.
- The data term uses truncated normalized cross-correlation between patches, with a constant penalty for mappings into the buffer zone.
- The regularizer penalizes componentwise flow differences and can use L1, Charbonnier, Lorentzian, or generalized Charbonnier penalties.
- Message passing becomes linear-time for supported penalty functions, while the described efficient min-convolution algorithm assumes convex ρ.
- Regularization is attenuated along color discontinuities using a Laplace weight and couples horizontal and vertical flow components.
4. Optimization
The method makes full-grid global optimization tractable by exploiting the regular two-dimensional label space and accelerating TRW-S message updates from quadratic to linear complexity.
- The model is a discrete Markov random field whose nodes and two-dimensional labels can both number in the tens of thousands.
- TRW-S optimizes the dual of a linear-programming relaxation over candidate flow labels L = [−ς, ς]2 ∩Z2.
- Message passing: Messages are updated during ordered forward-backward passes, with each pixel sending messages to not-yet-visited neighbors.
- Complexity reduction: O(M 2) brute-force message updates are reduced to O(M) by rewriting the update as min-convolutions.
- Complexity reduction: The two-dimensional min-convolution decomposes into one-dimensional min-convolutions, yielding total O(M) complexity.
- Min-convolution: The fastest min-convolution algorithm assumes convex ρ, although the broader solution strategy accommodates non-convex penalties.
5. Implementation
Implementation uses parallelized TRW-S, forward-backward consistency checking, and EpicFlow interpolation to convert discrete optimization into subpixel flow.
- Parallelization: Parallel diagonal wavefront processing reduces each TRW-S iteration from 256 to 39 seconds, a factor of 6.6, on a 6-core CPU with hyper-threading.
- Occlusion handling: Forward-backward consistency checking discards matches that disagree with corresponding forward and backward flow fields.
- Postprocessing: Figure 2 compares the optimized flow after consistency checking with the EpicFlow-interpolated result and displays corresponding EPE maps truncated at 10 pixels.
- Postprocessing: EpicFlow interpolation produces subpixel-resolution flow, allowing discrete optimization on 1/3-resolution images while retaining state-of-the-art performance.
6. Experiments
Experiments evaluate the approach on MPI Sintel and KITTI 2015, compare it with prior methods, and isolate the effects of data terms, regularizers, and truncation. The approach achieves strong benchmark performance, while controlled results emphasize the importance of global optimization and patch-based data terms.
- Runtime: 51 seconds computes the 1.3 billion unary-cost-volume values, while three TRW-S iterations take about 2 minutes and L1 acceleration reduces this to about 30 seconds.EpicFlow interpolation takes 3 seconds, and parameters are trained on 5% of each dataset by grid search.
- Benchmark evaluation: MPI Sintel and KITTI 2015 provide challenging benchmark evaluations of the approach.MPI Sintel includes clean and final sequences with large-displacement effects; KITTI 2015 contains outdoor dynamic scenes captured from a car.
- Comparison to prior work: The approach outperforms EpicFlow and four other methods on almost all MPI Sintel metrics, ranking second on EPE-all for both final and clean sequences.Compared with EpicFlow, EPE-all decreases by 6.2% on final sequences and 12.5% on clean sequences.
- Comparison to prior work: Visual comparisons show strong recovery of large-displacement regions on MPI Sintel, while KITTI results are usually similar to DiscreteFlow and better than EpicFlow.The approach ranks first on s40+ in Table 1, but some KITTI scenes contain outliers where it is less accurate than DiscreteFlow.
- Controlled experiments: The patch-based truncated NCC data term is much more effective than the pixelwise Horn-Schunck data term, regardless of the regularizer.The controlled evaluation varies data term, penalty function, and truncation, with free parameters selected by grid search.
- Controlled experiments: Global optimization and a patch-based data term are the key factors, while the regularizer’s detailed form is less important within the global framework.The classical quadratic regularizer remains competitive, and the highest accuracy is achieved with the L1 penalty.
7. Conclusion
The paper concludes that globally optimizing a classical Horn-Schunck-type objective over full regular grids is feasible and sufficient for state-of-the-art optical flow accuracy. The simple framework also leaves room for improved data terms and continuous interpolation.
- Global optimization over full regular grids is feasible because their regular structure enables significant computational optimizations.
- State-of-the-art accuracy on challenging optical flow benchmarks can be obtained without externally defined descriptors.
- The flow objective itself can produce accurate mappings despite large displacements.
- More advanced data terms and improved continuous interpolation could further increase accuracy.
- The global optimization output can serve as a canonical initialization for benchmarking continuous interpolation schemes.