Abstract
This paper presents a novel optimization framework for stereo matching that utilizes Local Expansion Moves to handle continuous 3D plane labels. By combining the randomized search efficiency of PatchMatch with the global optimization strengths of Graph Cuts, the proposed method achieves high accuracy while maintaining computational efficiency. The approach localizes $\alpha$-expansions and incorporates spatial propagation, effectively mitigating fronto-parallel bias and achieving state-of-the-art results on the Middlebury benchmarks.
Introduction
Stereo matching—estimating depth by comparing two images—traditionally struggles with a trade-off between accuracy and efficiency. Many algorithms suffer from "fronto-parallel bias," assuming surfaces are flat and face the camera directly, which leads to "staircase" artifacts on slanted or curved surfaces. While using 3D plane labels $(a, b, c)$ can address this, it creates an infinite, continuous label space that standard discrete optimizers cannot handle. Existing solutions like PatchMatch Belief Propagation (PMBP) or Fusion Moves are often computationally expensive or lack the subproblem optimality that makes Graph Cuts powerful. This work introduces Local Expansion Moves to bridge the gap between randomized local search and global discrete optimization.
Methodology
The core innovation is the Local Expansion Move, which adapts the traditional expansion move framework for localized, continuous label optimization.
- Localization and Spatial Propagation: The image is divided into a grid of cells. Each cell performs its own local $\alpha$-expansion using candidate labels relevant to its specific location. Successful 3D planes are then "proposed" to neighboring cells. Integrating these proposals into a Graph Cut framework allows multiple pixels to be updated to the same plane simultaneously, ensuring piecewise linear smoothness.
- Hierarchical Grids: The optimization iterates through different grid sizes. Large grids help propagate labels across large, textureless regions, while small grids refine fine details.
- Fast Cost Filtering: The authors leverage a "consistent-label property" within local regions to use Guided Image Filtering. This reduces the complexity of matching cost calculations from $O(\text{window size})$ to $O(1)$.
- Energy Function: The method uses a pairwise Markov Random Field (MRF) that combines slanted patch matching (data term) and curvature regularization (smoothness term).
Key Results and Evaluation
The method (LE-GF) was evaluated on the Middlebury Stereo Benchmarks (V2 and V3), which feature diverse scenes like Teddy and Playroom. At the time of publication, LE-GF achieved the #1 average rank on both benchmarks. On Middlebury V2, it achieved a bad-pixel rate of just 5.97% at a 0.5-pixel threshold.
Beyond accuracy, the method is highly parallelizable; a four-core CPU implementation achieved a 3.8x speedup, outperforming many previous GPU-heavy approaches in both speed and accuracy. Qualitative results show significantly smoother surfaces and better-defined edges compared to previous state-of-the-art methods.
Conclusion and Future Work
Local Expansion Moves successfully bridge the gap between randomized search and global optimization. The authors prove that these local moves are submodular, guaranteeing that each step can be solved optimally and efficiently using standard min-cut/max-flow algorithms. Future work may involve integrating asymmetric occlusion terms into the MRF and addressing fronto-parallel biases that can be re-introduced by CNN-based matching costs.
Summary updated