Source-linked AI summary
Fast Optical Flow using Dense Inverse Search
Till Kroeger, Radu Timofte, Dengxin Dai, Luc Van Gool
TL;DR
Optical-flow research has improved accuracy but often at runtimes unsuitable for real-time and computationally constrained applications. The paper introduces Dense Inverse Search, combining efficient patch correspondence search, multiscale densification, and variational refinement. DIS achieves comparable flow quality with one- to two-order-of-magnitude speedups, reaching 10–600 Hz on 1024×436 images using one CPU core.
Problem
Optical-flow methods face pressure to improve quality and speed because high runtime limits real-time and computationally constrained applications.
Method
DIS combines inverse search for patch correspondences, multiscale patch aggregation for dense displacement fields, and variational refinement.
Results
One- to two-order-of-magnitude speedups over state-of-the-art methods are achieved at comparable flow quality, with 10–600 Hz on 1024×436 images using one CPU core.
Takeaways & Limitations
DIS is suitable for visual applications requiring high-speed dense optical flow, including tracking, motion segmentation, and activity recognition.
Takeaways & Limitations
The method can lose small and fast motions in its coarse-to-fine approach, and large-displacement errors are difficult to recover through refinement.
Abstract
from arXiv · showhide
Most recent works in optical flow extraction focus on the accuracy and neglect the time complexity. However, in real-life visual applications, such as tracking, activity detection and recognition, the time complexity is critical. We propose a solution with very low time complexity and competitive accuracy for the computation of dense optical flow. It consists of three parts: 1) inverse search for patch correspondences; 2) dense displacement field creation through patch aggregation along multiple scales; 3) variational refinement. At the core of our Dense Inverse Search-based method (DIS) is the efficient search of correspondences inspired by the inverse compositional image alignment proposed by Baker and Matthews in 2001. DIS is competitive on standard optical flow benchmarks with large displacements. DIS runs at 300Hz up to 600Hz on a single CPU core, reaching the temporal resolution of human's biological vision system. It is order(s) of magnitude faster than state-of-the-art methods in the same range of accuracy, making DIS ideal for visual applications.
1. Introduction
DIS targets optical flow that remains close to state-of-the-art quality while substantially reducing runtime for real-time and computationally constrained applications. It combines fast inverse patch correspondence search, multi-scale aggregation, and variational refinement, reaching 10–600 Hz on a single CPU core.
- Motivation: Optical flow must improve both quality and speed for tracking, activity recognition, embedded systems, autonomous robots, and large-scale processing.Higher speed permits subsequent processing and deployment in computationally constrained scenarios.
- Motivation: Recent advances in large-displacement handling often incur runtimes unsuitable for real-time or computationally constrained applications.Prior work has only occasionally balanced accuracy and runtime through efficiency or specialized parallel hardware.
- Related work: The paper positions DIS within approaches that trade complex algorithms for simpler methods, high frame rates, and smaller search spaces.Related work also uses coarse-to-fine optimization, feature matching, learning, and parallel computation to address speed or accuracy.
- DIS approach: DIS uses inverse search for patch correspondences, multi-scale aggregation for dense flow estimation, and fast variational refinement.The inverse search is inspired by inverse compositional image alignment, while aggregation improves robustness against outlier correspondences.
- Results: 10–600 Hz: DIS operates on 1024×436 images using a single CPU core while remaining close to state-of-the-art flow quality.The reported range reaches the temporal resolution of human biological vision; the figure comparison excludes preprocessing time.
- Results: 1–2 orders of magnitude faster: DIS matches previous methods at comparable flow-quality operating points on Sintel and KITTI.It is also reported as significantly more accurate than existing methods operating at equal speed.
2. Proposed method
DIS combines inverse patch search, multi-scale densification, and variational refinement to estimate dense optical flow efficiently. Its design emphasizes robustness, coarse-to-fine initialization, and parallelizable processing while retaining several configurable extensions.
- Fast inverse search for correspondences: DIS extracts patch correspondences by minimizing patch-level squared differences with iterative inverse Lucas–Kanade updates.The inverse formulation avoids recomputing image gradients, Jacobians, and Hessians at every iteration.
- Fast optical flow with multi-scale reasoning: The method processes a scale pyramid from coarse to fine, reinitializing patches from the previous scale’s dense flow.Intermediate dense fields smooth displacements, filter outliers, and reduce the number of patches at coarser scales.
- Fast optical flow with multi-scale reasoning: Dense flow is formed by weighted averaging of overlapping patch displacements, while large updates are reset to their initial estimates for outlier robustness.Weights depend on patch overlap and local intensity differences between templates and warped images.
- Fast Variational refinement: Variational refinement minimizes an energy combining intensity, gradient, and displacement-smoothness terms on the current scale.The refinement uses intensity images and omits a feature-matching term.
- Extensions: Patch optimization and per-pixel refinement are independently parallelizable, although experiments use a single CPU core because thread-creation overhead matters at fast runtimes.The implementation achieved an almost linear speed-up with the number of cores using OpenMP.
- Extensions: Color images, forward-backward consistency, and robust error norms were evaluated as extensions but were rejected in the fast configuration because their observed benefits did not justify runtime costs.Color increased runtime, consistency doubled runtime, and robust norms slowed convergence.
3. Experiments
The experiments evaluate parameter sensitivity, sparse inverse-search correspondences, and the complete DIS pipeline on Sintel and KITTI. Results show a favorable speed–accuracy trade-off, with robustness from densification and strong performance across operating points.
- Experimental design: The experiments analyze parameter selection, inverse-search correspondences, complete-pipeline performance, and the benefit of higher frame-rates.Evaluation covers Sintel and KITTI training and testing benchmarks, with timing comparisons against CPU- and GPU-based baselines.
- Parameter selection: Finer scales, more patch iterations, and higher patch density generally lower average end-point error, while patch sizes of 8 and 12 pixels are optimal.These settings can increase run-time, so their value depends on the available time budget.
- Parameter selection: Variational refinement always significantly reduces error for a moderate run-time increase.The fastest 600 Hz operating point omits refinement, while the 300 Hz point retains it.
- Inverse-search evaluation: Patch averaging in DIS increases robustness to outliers, lowers error for approximately correct matches, and enables fewer coarse-scale patches for lower run-time.Without densification, inverse search is strongly affected by outliers because implicit SSD minimization is sensitive to orientation, contrast, and deformation changes.
- Sintel results: At approximately 6 pixels average end-point error on Sintel, DIS is approximately two orders of magnitude faster than the fastest CPU baseline and more than one order faster than the fastest GPU baseline.Operating point (2) provides the best reported trade-off between run-time and flow error.
- KITTI results: On KITTI, the Sintel conclusions also apply without dataset-specific parameter optimization; DIS is on par with RLOF and FlowNet while remaining one order of magnitude faster.Both comparison methods use GPUs, whereas DIS runs on a single CPU core.
4. Conclusions
The method achieves large runtime reductions at comparable flow quality, but its coarse-to-fine design and L2 matching leave specific motion and appearance changes unresolved.
- Two orders of magnitude faster at the same error level than current state-of-the-art methods on Sintel and KITTI benchmarks.
- Small and fast motions can sometimes be lost beyond recovery because of the coarse-to-fine approach.
- L2 matching is not invariant to contrast changes, deformations, and occlusions.
A. Derivation of the fast inverse search in § 2.1 of the paper
The fast inverse search reformulates patch alignment so the update can be computed efficiently, avoiding repeated gradient and Hessian recomputation. For optical flow, the warp update simplifies to direct displacement subtraction.
- Inverse-search optimization: The method estimates patch displacement by iteratively minimizing a warp-based image-matching objective.It uses Gauss-Newton minimization with a first-order Taylor expansion.
- Inverse-search optimization: For optical flow, the warp Jacobian becomes the 2 × 2 identity matrix.This follows from the translational warp used for optical flow.
- Inverse-search optimization: A least-squares formulation provides a closed-form parameter update by setting the objective derivative with respect to ∆u to zero.The matrix x ST S approximates the Hessian.
- Inverse compositional formulation: Inverse compositional alignment swaps the image and template roles so the gradient-dependent quantities can be pre-computed.This avoids re-evaluating S and the Hessian at every iteration.
- Parameter update: The inverse update composes the current warp with the inverse incremental warp, reducing to u ← u − ∆u for optical flow.The direct update contrasts with the forward parameter update u ← u + ∆u.
- Iteration cost: Each iteration computes the image-difference and gradient sum, solves a linear system for ∆u, and updates the warp parameter.Image gradients therefore need not be recomputed during each iteration.
B. Extensions: Color, forward-backward consistency, robust error norms
The paper evaluates color, consistency, and robust-norm extensions alongside implementation and runtime behavior. Although the extensions reduce flow error, their gains are judged insufficient to justify their inclusion, while runtime scales predictably with image area and scale.
- Extensions: The evaluated extensions replace intensity images with RGB color, enforce forward-backward consistency, or use robust error norms.The robust alternatives examined are the L1 and Huber norms.
- Forward-backward consistency: Forward-backward consistency runs the algorithm in both directions and merges overlapping forward and backward patch estimates during densification.Other algorithm steps run independently for the two flow directions.
- Robust error norms: The L1 and Huber variants transform each pixel’s matching error before squaring so that the corresponding robust norm is minimized iteratively.The transformation is introduced because the original objective directly minimizes an L2 norm.
- Extension evaluation: All tested extensions decrease optical-flow error, but the reduction is too small to justify including them in the method.The comparison uses six operating points on the Sintel training benchmark.
- Implementation and runtime: The implementation derives speed from fast DIS initialization, slower variational refinement, pre-allocation, SSE instructions, in-place operations, and early termination.Initialization and variational refinement account for 32% and 57% of runtime per scale, respectively.
- Implementation and runtime: Runtime scales linearly with image area and grows approximately by a factor of 4 for each finer scale.The reported DIS (2) timing on Sintel-resolution images is 3.32 ms over three scales.
D. Plots for more operating points on the KITTI and Sintel benchmarks
The paper plots additional operating points for Sintel and KITTI training benchmarks using varied parameter settings and optional variational refinement. The refinement is most advantageous for small displacements, while large-displacement errors are difficult to recover.
- Benchmark plots: The plots cover Sintel and KITTI training benchmarks across the paper’s four operating points and additional parameter settings.Both settings with and without variational refinement are shown.
- Effect of refinement: Variational refinement brings its strongest advantage in the small-displacement range.This observation is reported from the plotted benchmark results.
- Effect of refinement: Large-displacement errors cannot be recovered easily by variational refinement.The limitation is stated as an observation from the additional operating-point plots.
E. Plots for experiments § 3.3 and § 3.4 including preprocessing time
Including preprocessing changes the runtime picture: at several tens or hundreds of Hertz, preprocessing can dominate total runtime and complicate comparisons. The evaluation therefore isolates flow-computation time from preprocessing overheads.
- Preprocessing is excluded for all methods to compare actual flow-computation time without constant overheads.The excluded operations include disk access, image rescaling, and gradient computation.
- Shared or unnecessary preprocessing is especially relevant in robotics streaming applications and multi-task systems.
- At several tens or hundreds of Hertz, preprocessing dominates total runtime and makes analysis difficult when included.Figure 12 plots Sintel and KITTI endpoint error against total runtime including preprocessing.
F. More exemplary results for KITTI and Sintel (training)
Additional training-set examples visualize optical-flow results for the proposed method and comparison methods on Sintel and KITTI. Error maps for the Sintel examples are provided separately.
- Figures 13–16 show exemplary optical-flow results on the Sintel and KITTI training subsets.
- The examples compare the proposed method with Ground Truth, Farneback, Pyramidal LK, PCA-Flow, and DeepFlow at stated operating frequencies.
- Error maps corresponding to the Sintel examples in Figures 13 and 14 are plotted in Figures 17 and 18.
G. Error maps on Sintel-training
Sintel-training error maps expose where the method makes errors, including motion discontinuities, large displacements, and frame boundaries during fast motion.
- Error heat maps for the Sintel training subset are shown in Figures 17 and 18.The maps are paired with the exemplary Sintel results.
- Typical errors occur at motion discontinuities, including the first block of Figure 17.
- Typical errors also occur for large displacements and at frame boundaries during fast motions.The passage gives the third block of Figure 17 and the second block of Figure 18 as examples.
H. More exemplary results for the high frame-rate experiment on Sintel-training in § 3.5
The high-frame-rate and stereo examples organize results by temporal step size, method, and error or runtime metrics. They illustrate how DIS is evaluated across changing temporal resolution and a related stereo-depth task.
- High-frame-rate experiment: Figures 19 and 20 compare new ground truth, DeepFlow, DIS, and original images across step sizes from 1 to 10 frames.Rows encode step sizes, while columns encode the compared outputs and intermediate DIS flow.
- Stereo-depth experiment: Operating points (1) and (2) remain faster than all baselines at the same error, although the speed benefit is smaller than in optical-flow experiments.
- Stereo-depth experiment: For all baseline methods, optimal performance uses a downscaled input image pair rather than the finest resolution.
- High-frame-rate experiment: The figure description states that large displacements are significantly better preserved by DIS through higher frame-rates.
- Stereo-depth experiment: Figure 21 evaluates Middlebury stereo depth using endpoint error versus runtime and pixel-error percentages below 2, 4, and 10 pixels.The stereo formulation removes the vertical degree of freedom and estimates horizontal displacements.