Scalable Full Flow with Learned Binary Descriptors

Gottfried Munda, Alexander Shekhovtsov, Patrick Knöbelreiter, Thomas PockarXiv 2017 · arXiv

Abstract

Estimating optical flow for high-resolution imagery is traditionally constrained by the massive memory requirements of 4D cost volumes. This paper presents a scalable approach using a "min-projection" technique to decouple horizontal and vertical motion components, reducing memory complexity from quadratic to linear. Furthermore, the authors introduce a hybrid learning scheme (FQ model) to train fast binary descriptors, enabling efficient Hamming distance matching without sacrificing gradient information during training. Evaluated on the MPI Sintel benchmark, the method demonstrates a 99% reduction in memory usage and a 60x speedup in matching, providing a memory-efficient path for high-accuracy optical flow.

Introduction

Optical flow estimation—the task of determining pixel-wise motion between consecutive video frames—is a cornerstone of computer vision. State-of-the-art methods often rely on building a 4D cost volume that stores matching costs for every possible displacement. However, for high-resolution images and large search ranges, these volumes become prohibitively large. For instance, a 1024x436 image with a 256-pixel search range requires approximately 108 GB of RAM. This bottleneck often forces trade-offs, such as downsampling or limited search windows, which can degrade accuracy. This paper addresses these scalability issues through architectural and training innovations that allow for "full flow" estimation on standard hardware.

Methods

The authors propose a multi-stage pipeline designed for efficiency and speed, focusing on dimensionality reduction and fast matching.

Min-Projection (Dimensionality Reduction)

Instead of storing a full 4D volume, the authors decouple motion into horizontal ($u$) and vertical ($v$) components. By "projecting" the minimum cost onto two separate 3D volumes, memory complexity is reduced from quadratic to linear relative to the search range. This technique allows the aforementioned 108 GB volume to shrink to just 0.8 GB, enabling high-resolution processing on consumer-grade GPUs.

Siamese CNN architecture for learned descriptors and the min-projection correlation process.

Learned Binary Descriptors and Hybrid Learning

To accelerate matching, the system uses a Siamese Convolutional Neural Network (CNN) to learn binary descriptors. Matching these via Hamming distance is significantly faster than floating-point operations.

Training binary networks is challenging because the sign function used for binarization has a zero gradient almost everywhere. The authors introduce a Full-Quantized (FQ) hybrid model to solve this. In this model, the "inner" matching is performed with fast binary descriptors, while the "outer" optimization maintains a non-zero gradient, allowing for effective backpropagation and better accuracy than standard binary training methods.

Decomposed CRF

To ensure spatial smoothness—the principle that neighboring pixels should have similar motion—the authors employ a Conditional Random Field (CRF). To maintain the memory efficiency of the overall pipeline, the CRF is decomposed into manageable sub-problems, keeping the inference process parallelizable and lightweight.

Illustration of the cost function and CRF decomposition for efficient inference.

Results

The researchers evaluated their method on the MPI Sintel optical flow benchmark, focusing on the "Clean" pass.

  • Speed: The use of binary descriptors and the FQ model resulted in a "Winner-Takes-All" matching step that was roughly 60x faster than the full-precision version (0.07 seconds vs. 4.25 seconds).
  • Memory: Memory usage dropped by over 99% (from 108 GB to 0.8 GB) for high-resolution images, confirming the scalability of the min-projection approach.
  • Accuracy: The hybrid FQ model performed significantly better than standard binary CNN training. While it did not surpass the top-tier hand-tuned pipelines on the Sintel leaderboard, it achieved competitive results with a much simpler and more scalable architecture.

Conclusion

The proposed "min-projection" and hybrid binary learning scheme effectively solve the memory bottleneck of 4D cost volumes in optical flow estimation. By treating motion components as quasi-independent and leveraging the speed of binary matching, the authors demonstrate that high-resolution flow is achievable without massive hardware overhead. While current limitations include errors in occluded regions, the core matching engine provides a robust foundation for future scalable computer vision tasks, such as large-scale 3D reconstruction and tracking.

Summary updated

Abstract

We propose a method for large displacement optical flow in which local matching costs are learned by a convolutional neural network (CNN) and a smoothness prior is imposed by a conditional random field (CRF). We tackle the computation- and memory-intensive operations on the 4D cost volume by a min-projection which reduces memory complexity from quadratic to linear and binary descriptors for efficient matching. This enables evaluation of the cost on the fly and allows to perform learning and CRF inference on high resolution images without ever storing the 4D cost volume. To address the problem of learning binary descriptors we propose a new hybrid learning scheme. In contrast to current state of the art approaches for learning binary CNNs we can compute the exact non-zero gradient within our model. We compare several methods for training binary descriptors and show results on public available benchmarks.
BibTeX
@misc{munda2017scalable,
  author = {Gottfried Munda and Alexander Shekhovtsov and Patrick Knöbelreiter and Thomas Pock},
  title = {{Scalable Full Flow with Learned Binary Descriptors}},
  year = {2017},
  eprint = {1707.06427},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1707.06427},
}
Figure