Continuous 3D Label Stereo Matching using
Local Expansion Moves

Tatsunori Taniai1  Yasuyuki Matsushita2  Yoichi Sato1  Takeshi Naemura1
1The University of Tokyo, Japan
2Osaka University, Japan

TPAMI (accepted in 2017)




Abstract -- 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.

An extended version of our CVPR 2014 paper below.
Our C++ code by OpenCV 3.0 is now available at Github with pre-computed MC-CNN matching costs.

Summary of Changes:
  • Theoretical verification on the preferability for piecewise planar scenes.
  • Proof of the subproblem optimality (submodularity).
  • Speed-up by efficient parallelization on CPU/GPU.
  • Speed-up by incorporating fast cost-map filtering (guided image filter).
  • Algorithm is much clearer and extended (addition of RANSAC proposer).
  • Additional results on convergence analyses in supplementary material.
[Link to arXiv]


Graph Cut based Continuous Stereo Matching
Locally Shared Labels

Tatsunori Taniai1   Yasuyuki Matsushita 2  Takeshi Naemura1
1The University of Tokyo, Japan
2Microsoft Research Asia, China

CVPR 2014




Abstract -- We present an accurate and efficient stereo matching method using locally shared labels, a new labeling scheme that enables spatial propagation in MRF inference using graph cuts. They give each pixel and region a set of candidate disparity labels, which are randomly initialized, spatially propagated, and refined for ontinuous disparity estimation. We cast the selection and propagation of locally defined disparity labels as fusion-based energy minimization. The joint use of graph cuts and locally shared labels has advantages over previous approaches based on fusion moves or belief propagation; it produces submodular moves deriving a subproblem optimality; enables powerful randomized search; helps to find good smooth, locally planar disparity maps, which are reasonable for natural scenes; allows parallel computation of both unary and pairwise costs. Our method is evaluated using the Middlebury stereo benchmark and achieves first place in sub-pixel accuracy.

Code will be made availabe as our journal work with further improvements!
Thank you very much for so many requests for our code.
Unfortunately, the original code is not distributable due to lisence and heavy GPU dependency issues.
Our new C++ implementation for journal work solves these issues (OpenCV 3.0 is the only dependency).
The descriptions of our algorithm would be also much easier to understand.
We have a plan to release the code once our journal is published. Sorry for the inconvenience.
Tatsunori Taniai, November 5th, 2015.
Paper PDF
Poster PDF

Spotlight Video


1st rank at the Middlebury benchmark
(0.5 pixel error theshold)


Additional results without post-processing