Source-linked AI summary
Accurate Optical Flow via Direct Cost Volume Processing
Jia Xu, René Ranftl, Vladlen Koltun
TL;DR
Optical flow estimation needs accurate handling of large search spaces, yet full four-dimensional cost-volume processing was considered impractical. The paper makes this approach efficient through learned embeddings and four-dimensional semi-global matching, achieving leading benchmark accuracy with competitive speed. It reports the best published general-purpose results on both Sintel and KITTI 2015.
Problem
Full four-dimensional cost-volume processing could provide stereo-like structural benefits, but its computational requirements had been considered impractical for optical flow.
Method
The pipeline learns compact feature embeddings, constructs the full four-dimensional cost volume, processes it with four-dimensional semi-global matching, and postprocesses the resulting flow.
Results
The approach achieves the highest reported Sintel accuracy and reduces KITTI 2015 Fl-all error by 29.5% relative to PatchBatch while maintaining competitive running time.
Takeaways & Limitations
The results make a step toward unifying optical flow and stereo estimation through direct, efficient four-dimensional cost-volume processing.
Takeaways & Limitations
On Sintel, failures typically involve dramatic occlusion, strong motion blur, or large motion of untextured objects; on KITTI, shading and overexposure dominate.
Abstract
from arXiv · showhide
We present an optical flow estimation approach that operates on the full four-dimensional cost volume. This direct approach shares the structural benefits of leading stereo matching pipelines, which are known to yield high accuracy. To this day, such approaches have been considered impractical due to the size of the cost volume. We show that the full four-dimensional cost volume can be constructed in a fraction of a second due to its regularity. We then exploit this regularity further by adapting semi-global matching to the four-dimensional setting. This yields a pipeline that achieves significantly higher accuracy than state-of-the-art optical flow methods while being faster than most. Our approach outperforms all published general-purpose optical flow methods on both Sintel and KITTI 2015 benchmarks.
1. Introduction
Optical flow remains difficult despite its importance and structural similarity to stereo, because full cost-volume processing has been considered computationally infeasible. The paper shows that regular four-dimensional processing can combine high accuracy with speed.
- Optical flow remains challenging because of large displacements, textureless regions, motion blur, and non-Lambertian effects.
- Stereo methods explicitly construct regular cost volumes, whereas optical-flow methods commonly use nearest-neighbor search and coarse-to-fine analysis.
- Full four-dimensional cost-volume construction and optimization had been considered impractical because of computational requirements.
- The approach constructs the full four-dimensional cost volume in a fraction of a second and applies four-dimensional semi-global matching.
- 29.5%: the Fl-all error reduction on KITTI 2015 relative to PatchBatch, while outperforming published domain-agnostic methods.
2. Related Work
Related methods address optical-flow difficulty through learned matching, restricted search, multi-scale analysis, end-to-end networks, or domain-specific supervision. This paper instead directly processes the regular cost volume while emphasizing speed and compactness.
- Large displacements create both patch-appearance changes and a large correspondence search space.
- Learned matching functions based on convolutional networks have been adopted for optical flow, including in this work.
- The paper directly constructs the cost volume, achieving higher accuracy and more than an order-of-magnitude greater speed than Full Flow.
- End-to-end flow networks are fast but use tens of millions of parameters and require substantial external training data.
- The proposed network has 112K parameters and was trained from scratch on each benchmark without dataset augmentation.
- Domain-specific semantic-supervision methods can achieve high automotive-dataset accuracy but have limited generalization ability.
3. Overview
The pipeline extracts features, constructs and processes a downsampled four-dimensional cost volume, then converts semi-dense matches into dense refined flow. Its processing combines SGM, consistency checks, interpolation, and refinement.
- Feature extraction, cost-volume construction, and cost-volume processing operate on images downsampled by a factor of three in each dimension.
- A convolutional network produces per-pixel embeddings, and distances between embeddings populate the four-dimensional cost volume.
- Four-dimensional semi-global matching removes outliers and regularizes flow while retaining regular, parallel, efficient operation.
- Forward-backward consistency removes inconsistent matches before postprocessing.
- EpicFlow interpolation, complementary image segmentation, homographies, inpainting, and variational refinement produce dense subpixel-resolution flow.
4. Feature Embedding
The feature-embedding stage learns compact patch representations for efficient, robust matching and cost-volume construction. Unit-length embeddings allow parallel vector-product computation over a discrete rectangular search space.
- A small convolutional network embeds image patches into a compact Euclidean space robust to geometric and radiometric distortions.
- The four-layer network uses 3×3 filters, no stride, pooling, or padding, and outputs normalized unit-length feature vectors.
- The network’s receptive field is 9×9 pixels, corresponding to 27×27 pixels in the original images after downsampling.
- Feature dimensionality trades expressive power against distance-computation cost, with surprisingly low dimensionality supporting discriminative embeddings.
- Training uses triplets in which an anchor patch is paired with a ground-truth positive and nearby negative patches.
- At test time, fully convolutional embeddings and vector products enable efficient cost-volume construction.
- 46: cost-volume construction scales as O(MNR^2d), making feature dimensionality directly affect computational cost.
5. Cost Volume Processing
Flow-SGM adapts semi-global matching to the full four-dimensional optical-flow cost volume, using pathwise dynamic programming and parallel computation to make regularized processing practical.
- Flow-SGM applies semi-global matching to the full four-dimensional cost volume, addressing tractability, efficiency, and accuracy together.The method is presented as an adaptation of SGM, rather than a restricted optical-flow variant.
- The optical-flow energy uses a two-dimensional displacement label and ℓ1-neighborhood distance, extending classical SGM's scalar-displacement formulation.The regularization terms are defined over two-dimensional flow neighborhoods.
- Flow-SGM approximately minimizes the energy by independently optimizing paths with dynamic programming, then accumulating their costs into a filtered cost volume.The implementation uses four cardinal directions: two horizontal and two vertical.
- The final flow estimate selects, independently for each pixel, the displacement with the smallest cost in the filtered cost volume.The method computes forward and backward flow to remove inconsistent matches before subsequent processing.
- GPU parallelism and compact integer storage address the cost volume's memory and computation demands.Costs are rescaled to 8-bit integers, while the filtered volume uses 16 bits per entry.
6. Postprocessing
The postprocessing stage converts semi-dense correspondences into dense, subpixel-resolution flow by combining EpicFlow with homography-based inpainting for large occluded regions.
- EpicFlow synthesizes dense flow from semi-dense matches using locally weighted affine models, but is less reliable in large occluded regions.The complementary scheme is designed to improve inpainting specifically where matches are sparse or absent.
- The complementary method uses low-level appearance and edge cues to identify planar segments and fit homographies to their semi-dense matches.It uses a segmentation hierarchy and greedy bottom-up fitting strategy.
- Valid segment homographies extrapolate flow within those segments, while remaining segments are inpainted with EpicFlow.This combines planar extrapolation with the baseline interpolation scheme.
- The inpainting scheme uses no semantic information, adds little computation time, and can enhance flow synthesis in large occluded regions.It relies on the same low-level edge cues as EpicFlow and is therefore broadly applicable.
7. Experiments
Experiments on Sintel and KITTI 2015 show strong benchmark accuracy, effective learned matching and Flow-SGM processing, rapid cost-volume construction, and identifiable failure cases.
- MPI Sintel: At the time of writing, DC Flow ranked first on Sintel and outperformed competing methods on seven of nine evaluation metrics.This included the main all-pixels metric and particularly strong performance in fast-motion regions.
- KITTI 2015: 14.86 Fl-all error was 29.5% lower than PatchBatch, the most accurate prior domain-agnostic method on KITTI 2015.The approach also outperformed DiscreteFlow by 9.5% on non-occluded regions.
- KITTI 2015: The approach outperformed two domain-specific KITTI methods without using domain-specific information, while only one such pipeline surpassed it.Its performance was particularly accurate in background regions and competitive in foreground regions.
- Ablation study: Replacing NCC with the learned feature embedding in Full Flow consistently lowered error on both Sintel and KITTI.The controlled experiment used a 64-dimensional embedding and kept the rest of the Full Flow pipeline fixed.
- Ablation study: Adding Flow-SGM further increased accuracy beyond winner-takes-all and surpassed the corresponding Full Flow variants.In the WTA condition, EpicFlow interpolation consumed 97% of running time.
- Ablation study: Homography-based inpainting maintained high Sintel accuracy and significantly improved KITTI accuracy, consistent with KITTI's mostly rigid scenes.Feature embeddings with dimensionality as low as 10 also performed remarkably well.
- Runtime: Cost-volume construction took 80 milliseconds in the fast condition and 260 milliseconds in the accurate condition.EpicFlow dominated the fast setting, while cost-volume processing and postprocessing accounted for most of the accurate setting's runtime.
- Qualitative results: Failure cases on Sintel typically involved dramatic occlusion, strong motion blur, or large motion of untextured objects, while KITTI failures mainly involved shading and overexposure.Qualitative figures show ground-truth flow, predictions, and error maps for Sintel, and predictions with threshold-coded error maps for KITTI.
8. Conclusion
The paper presents direct four-dimensional cost-volume processing for optical flow, combining learned features with efficient semi-global matching. This approach unifies optical flow and stereo estimation while achieving high accuracy and competitive runtimes.
- The approach directly constructs and processes the full four-dimensional optical-flow cost volume.A learned feature embedding enables accurate construction in a fraction of a second.
- Efficient semi-global matching adapts classical stereo-estimation ideas to the four-dimensional optical-flow setting.The method uses the cost volume’s regularity for efficient processing.
- The resulting pipeline combines high accuracy with competitive runtimes and outperforms prior methods on standard benchmarks.The paper frames this as a step toward unifying optical flow and stereo estimation.