PaperlayerView exact revision on arXiv

Source-linked AI summary

Continuous 3D Label Stereo Matching using Local Expansion Moves

Tatsunori Taniai, Yasuyuki Matsushita, Yoichi Sato, Takeshi Naemura

arXiv:1603.08328v3cs.CV

TL;DR

Stereo matching must overcome fronto-parallel bias while inferring continuous 3D plane labels efficiently. The paper introduces graph-cut local expansion moves with spatial propagation and reports comparable or greater accuracy than PMBP alongside faster, filterable inference. Its main implementation boundary is that matching costs remain expensive without acceleration, while filtering requires consistent labels.

  • Problem

    Continuous 3D plane labels cannot be directly handled by standard discrete optimizers because the label space is huge or infinite, while stereo also suffers from fronto-parallel bias.

  • Method

    The method uses local graph-cut alpha-expansions over image cells to combine spatial label propagation with submodular optimization for continuous 3D plane MRFs.

  • Results

    The method achieves comparable or greater accuracy than PMBP, supports cost filtering, and the extended version reports about 2.1x faster running times than its previous GPU implementation.

  • Takeaways & Limitations

    Subproblem-optimal local moves let the method use randomized initialization while jointly updating nearby pixels to obtain smooth disparity solutions.

  • Takeaways & Limitations

    Matching-cost computation remains O(|W|) without filtering, and the filtering scheme depends on a consistent-label property unavailable to most other PatchMatch methods.

Abstract

from arXiv · show

We present an accurate stereo matching method using local expansion moves based on graph cuts. This new move-making scheme is used to efficiently infer per-pixel 3D plane labels on a pairwise Markov random field (MRF) that effectively combines recently proposed slanted patch matching and curvature regularization terms. The local expansion moves are presented as many alpha-expansions defined for small grid regions. The local expansion moves extend traditional expansion moves by two ways: localization and spatial propagation. By localization, we use different candidate alpha-labels according to the locations of local alpha-expansions. By spatial propagation, we design our local alpha-expansions to propagate currently assigned labels for nearby regions. With this localization and spatial propagation, our method can efficiently infer MRF models with a continuous label space using randomized search. Our method has several advantages over previous approaches that are based on fusion moves or belief propagation; it produces submodular moves deriving a subproblem optimality; it helps find good, smooth, piecewise linear disparity maps; it is suitable for parallelization; it can use cost-volume filtering techniques for accelerating the matching cost computations. Even using a simple pairwise MRF, our method is shown to have best performance in the Middlebury stereo benchmark V2 and V3.

1 INTRODUCTION

The paper targets fronto-parallel bias and the difficulty of optimizing continuous 3D plane labels. It introduces local expansion moves that combine graph-cut optimization with spatial propagation for smooth stereo estimates.

  • Slanted patch matching and curvature regularization support a pairwise MRF model for linearly varying disparities and smooth surfaces beyond planes.
  • Continuous 3D labels cannot be directly optimized with standard discrete graph cuts because their label space is huge or infinite.
  • Local expansion moves define regional alpha-expansions that update labels with graph cuts while propagating current labels to nearby pixels.
  • Each local move can assign one disparity plane to multiple pixels simultaneously, helping produce smooth solutions and avoid bad local minima.
  • The method provides subproblem-optimal moves, supports randomized search without external proposals, and permits parallel min-cut and unary-term computation.
  • The extended method reports about 2.1x faster running times than the previous GPU implementation with comparable or greater accuracy.

2 RELATED WORK

Related stereo methods span discrete, segment-based, and continuous formulations. The paper positions its approach as a continuous method combining spatial propagation with graph cuts while enabling cost-volume filtering.

  • Discrete stereo assigns predefined disparity values and can directly use optimizers such as belief propagation, TRW, and graph cuts.
  • Segment-based stereo assigns disparity planes to image regions but constrains reconstructions to piecewise planar surfaces and depends on segmentation quality.
  • Continuous stereo assigns each pixel a distinct continuous disparity value, with prior methods using fusion moves or PatchMatch-based inference.
  • Unlike fusion-based methods, this method uses spatial propagation and randomized search, requiring only a randomized initial solution while retaining submodular graph-cut energies.
  • Cost-volume filtering can reduce matching-cost computation to O(1) for constant-time filters.
  • Dynamic per-pixel labels prevent most PatchMatch methods from using consistent-label cost-volume slices, whereas subregion filtering enables the proposed method to achieve greater accuracy than PMF.

3 PROPOSED METHOD

The method represents disparities with per-pixel 3D plane labels in a pairwise MRF, combining slanted patch matching with curvature-based smoothness. It optimizes this model with data and pairwise terms designed to favor piecewise planar disparity while remaining compatible with graph cuts.

  • 3.2 Formulation: Each pixel is assigned a 3D plane fp = (ap, bp, cp), producing disparity dp = apu + bpv + cp.The method estimates a mapping from image pixels to plane labels in a label space L.
  • 3.2 Formulation: The energy combines a unary photo-consistency term with a pairwise smoothness term over neighboring pixels.The unary term measures matching-pixel photo-consistency, while the pairwise term penalizes disparity discontinuities.
  • 3.2 Formulation: Slanted patch matching evaluates support-pixel dissimilarity under a disparity plane, using adaptive support weights computed with guided image filtering.The support window is centered at p, and the filtering weights replace the bilateral weights used in prior slanted patch matching.
  • 3.2 Formulation: The curvature-based smoothness term compares neighboring plane assignments through disparity differences and truncates the penalty to permit sharp depth-edge jumps.Its contrast-sensitive weight includes a user-defined parameter γ and a small lower bound for robustness to image noise.
  • 3.2 Formulation: When neighboring pixels share a plane, the smoothness penalty is zero, favoring piecewise linear disparities and piecewise planar object surfaces.With fronto-parallel planes, the term reduces to 2|cp − cq|, extending the traditional truncated linear model without its fronto-parallel bias.
  • 3.2 Formulation: The smoothness term satisfies expansion-move submodularity, enabling its use with graph-cut optimization.The paper states this property as Lemma 1 and refers to prior work and Appendix A for the proof.

3.3 Local expansion moves

Local expansion moves adapt α-expansions to continuous 3D plane labels by localizing candidate labels and propagating them across neighboring regions. Graph-cut updates preserve subproblem optimality while randomized perturbations refine the solution.

  • Traditional exhaustive α-expansions are impractical because the plane-label space (a, b, c) is continuous and three-dimensional.
  • Local expansion moves use different candidate labels according to pixel location instead of applying one α label globally.This localization reflects spatially varying disparity distributions.
  • Grid-cell size balances localization against propagation range, while multiple grid structures help balance these factors.Smaller cells provide finer localization but shorter propagation ranges.
  • Each αij-expansion selects and perturbs a label from its center cell, then uses graph cuts to choose between current labels and αij within the expansion region.The candidate represents a disparity plane d = au + bv + c.
  • Larger expansion regions than label-selection regions allow center-cell labels to propagate to nearby pixels.This spatial propagation is the key distinction between the center region Cij and expansion region Rij.
  • Iterative propagation and refinement steps use unperturbed and perturbed αij-expansions, producing piecewise linear disparity maps by moving multiple pixels at once.The method can also incorporate RANSAC proposals and randomized refinement.

Mutually-disjoint local α-expansions

The method schedules overlapping local expansions through groups of mutually disjoint regions. This grouping enables parallel execution while preserving independence between expansions.

  • Local α-expansions are grouped because overlapping expansion regions cannot be performed simultaneously.
  • Each group contains mutually disjoint expansions selected at regular cell intervals, yielding 16 groups under the described grouping rule.
  • One-cell gaps between neighboring expansions guarantee submodularity and independence within each group.
  • Expansions in the same group are processed in parallel, including during the optimization procedure.

Submodularity and independence

Disjoint local expansions yield submodular, independent graph-cut subproblems. The optimization combines random initialization, grid-level scheduling, parallel updates, and post-processing.

  • Simultaneously applying disjoint αij-expansions can be represented as a fusion-energy minimization over a proposal labeling.
  • The resulting binary energies are submodular, so each move can be solved optimally with graph cuts.This permits standard GC rather than QPBO-GC.
  • Assignments in different expansion regions are independent because gaps prevent chains of valid pairwise interactions between them.
  • The algorithm uses multiple grid sizes and performs mutually independent expansions in parallel for the selected grid level.
  • Random initialization, iterative expansions, and left-right consistency with weighted median filtering complete the optimization procedure.

3.5 Fast implementation

Matching-cost computation is accelerated by exploiting consistent labels within expansion regions and applying subregion cost filtering. The scheme reduces the per-term cost toward O(1), but filtering requires the consistent-label property.

  • Matching-cost computation is expensive because each term requires O(|W|) work for a matching window of size |W|.
  • During an αij-expansion, all pixels in Rij share αij, enabling matching costs to be computed jointly over a filtering region Mij.
  • Consistent labels reduce raw-cost computation from O(|W||Rij|) to O(|Mij|), yielding approximately O(1) per unary term when the regions are similar in size.
  • Constant-time edge-aware filtering similarly makes cost aggregation approximately O(1).
  • The filtering acceleration cannot be used in other PatchMatch-based methods unless they also have the consistent-label property.

4 EXPERIMENTS

Experiments evaluate the method on Middlebury benchmarks and against related optimizers, showing strong accuracy, stable convergence, smoother disparities, and substantial acceleration from cell sizing, parallelization, and cost filtering.

  • 4.1 Evaluation on the Middlebury benchmark V2: The method achieves Middlebury V2's best average rank, 3.9, and a 5.97% bad-pixel rate among more than 150 stereo methods.LE-GF outperforms other listed methods even without post-processing, while LE-BF has comparable accuracy to the previous algorithm.
  • 4.2 Evaluation on the Middlebury benchmark V3: On Middlebury V3, the method outperforms all 63 listed methods across every bad-pixel metric and region combination except bad 4.0-all.The default comparison uses the bad 2.0 metric on non-occluded regions.
  • 4.3 Effect of grid-cell sizes: The (S, M, L) grid-cell combination converges faster and more accurately than alternatives, while larger cells produce smoother disparities, especially in occluded regions.The combined cell sizes improve both energy reduction and accuracy; larger cells also improve smoothness.
  • 4.3 Effect of grid-cell sizes: Small cells increase cost-filtering overhead, whereas medium and large cells provide almost the same efficiency.This explains why the smallest-cell configuration is inefficient despite its finer spatial partitioning.
  • 4.4 Acceleration schemes: CPU parallelization gives about 3.5x speed-up, GPU unary-cost computation gives about 19x speed-up, and guided filtering gives about 5.3x speed-up.GPU-plus-CPU parallelization yields about 1.7x additional speed-up for LE-BF, while CPU LE-GF approaches GPU LE-BF efficiency.
  • 4.5–4.6 Comparisons with PMBP and PMF: Compared with PMBP and PMF, the method reaches lower energies and greater accuracy, while producing smoother disparities around edges and occlusions.Against PMBP, the advantage persists with parallelization; against PMF, explicit smoothness supports more stable optimization.
  • 4.7 Comparison with Olsson et al. [33]: Against Olsson et al., the method converges faster and produces qualitatively smoother surfaces, while RANSAC helps recover large texture-less planes.The method generally performs comparably with or without the RANSAC proposer and outperforms the comparison method.

5 CONCLUSIONS

The paper concludes that local expansion moves provide an accurate and efficient graph-cut framework for continuous 3D plane-label stereo. Comparisons show efficiency advantages and comparable or higher accuracy against related methods, while future extensions target broader correspondence estimation and improved occlusion handling.

  • 5 CONCLUSIONS: Local expansion moves provide subproblem-optimal graph-cut inference for continuous 3D plane labels using only a randomized initial solution.The method differs from fusion moves by producing submodular moves that permit exact graph-cut inference for each subproblem.
  • 5 CONCLUSIONS: Compared with PMBP, the method improves efficiency while achieving comparable or greater accuracy.The reported comparisons include faster convergence, lower energies, and greater accuracy at convergence.
  • 5 CONCLUSIONS: Compared with PMF, subregion cost filtering yields a fast method with greater accuracy.The paper notes that lighter-weight constant-time filtering could make the method faster still.
  • 5 CONCLUSIONS: The optimization strategy may extend beyond stereo to more general correspondence-field estimation.The paper also suggests incorporating graph-cut occlusion handling to potentially improve accuracy.
  • 5 CONCLUSIONS: Against Olsson et al., the method is faster and produces smoother surfaces, despite using the same energy function in the visual comparison.The comparison reports a strong piecewise-planar bias in the competing result for the ArtL dataset.

APPENDIX A PROOF OF LEMMA 1

The appendix proves that the pairwise potential satisfies the submodularity condition required for expansion moves, including its truncated form.

  • Proof of Lemma 1: The proof bounds the pairwise disparity difference by four alpha-relative terms, yielding the expansion-move submodularity inequality.The triangle inequality decomposes the difference between labels β and γ through α.
  • Proof of Lemma 1: The truncated pairwise function also satisfies submodularity.The appendix explicitly transfers the property from the untruncated function to its truncated version.

APPENDIX B ADDITIONAL RESULTS

Additional experiments on Middlebury V3 training images examine grid-cell sizes under controlled settings and support the proposed multiscale combination.

  • Additional experimental setup: The additional analyses evaluate error-rate transitions on 15 Middlebury V3 training image pairs using the bad 2.0 metric over all regions.Unless otherwise noted, methods use one CPU core, the same energy function, and no post-processing.
  • Effect of grid-cell sizes: The proposed (S, M, L) grid-cell combination performs best among five configurations for most image pairs.Small, medium, and large cells are set proportionally to 1%, 3%, and 9% of image width.

Efficiency comparison by parallelization

The method compares favorably with PMBP and PMF while supporting substantial parallel speed-up and faster convergence than Olsson et al.'s optimizer.

  • Parallelization: Four CPU cores provide about 3.8x average speed-up for the local expansion move algorithm.The comparison uses 15 Middlebury V3 training image pairs and the same energy function without post-processing.
  • Comparison with PMBP: Both guided-filter and bilateral-filter variants consistently outperform PMBP in accuracy at convergence.The guided-filter variant also converges much faster than the alternatives.
  • Comparison with PMF: With explicit regularization, the method consistently outperforms PMF across all image pairs.Both methods use the same energy function, but PMF optimizes only its data term.
  • Comparison with Olsson et al.: The method is about 6x faster than Olsson et al.'s optimizer while reaching comparable or better accuracies for most image pairs.Both methods optimize the same energy function differently on a single CPU core.

Comparison with Olsson et al.

The convergence analysis evaluates grid-cell combinations and compares the method against PMBP, PMF, and Olsson et al.'s optimizer on Middlebury V3 image pairs.

  • Grid-cell combinations: The (S, M, L) grid-cell combination outperforms four alternative combinations for most image pairs.Small, medium, and large grid-cells are set to 1%, 3%, and 9% of image width, respectively.
  • Parallelization: Parallel local expansion moves achieve about 3.8x average speed-up on four CPU cores.The parallelization analysis covers 15 Middlebury V3 training image pairs.
  • Comparison with PMBP: The method using guided or bilateral filtering consistently outperforms PMBP in accuracy at convergence.The guided-filter variant shows much faster convergence than the other methods.
  • Comparison with PMF: The method consistently outperforms PMF across all image pairs under the same energy function.PMF optimizes only its data term, whereas the proposed method includes explicit regularization.
  • Comparison with Olsson et al.: The method is about 6x faster than Olsson et al.'s optimizer for comparable or better accuracies on most image pairs.Both methods are evaluated on a single CPU core using the same energy function without post-processing.
Loading 1603.08328v3…