Efficient Large-Scale Stereo Matching
Andreas Geiger*,Martin Roser* and Raquel Urtasun***K ARLSRUHE I NSTITUTE OF T ECHNOLOGYKIT – University of the State of Baden-Wuerttemberg andNational Laboratory of the Helmholtz Association**TOYOTA T ECHNOLOGICAL I NSTITUTE AT C HICAGO

www.kit.edu

Contents

1

Motivation and Related Work

2

Efficient Large-Scale Stereo Matching3

Experimental Evaluation

4

Summary and Future Work

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

2/24

Contents

1

Motivation and Related Work

2

Efficient Large-Scale Stereo Matching3

Experimental Evaluation

4

Summary and Future Work

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

3/24

Motivation

CameraLaserscanner

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

4/24

Why is 3D from Stereo hard?

Ambiguities
Textureless regions
Sensor saturation
Non-Lambertian surfaces∆z grows quadraticallyComputational burden

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

5/24

Why is 3D from Stereo hard?

Ambiguities
Textureless regions
Sensor saturation
Non-Lambertian surfaces∆z grows quadraticallyComputational burden

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

5/24

Why is 3D from Stereo hard?

Ambiguities
Textureless regions
Sensor saturation
Non-Lambertian surfaces∆z grows quadraticallyComputational burden

distance error
focal length

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

disparity error
baseline

5/24

Related Work: Local Methods
Local Methods
Winner-takes-All
Examples
Block matching(Scharstein 02)
Adaptive windows(Kanade 94, Yoon 06)
Plane-sweep(Collins 96, Gallup 07)
Problems
Small matching ratios
Border bleeding

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

6/24

Related Work: Global Methods
Global Methods
Minimize 1D/2D energy E(d) = Edata (d) + λEsmooth (d)ExamplesGraph cuts, Belief propagation(Kolmogorov 02, Felzenszwalb 06)
Variational methods(Pock 07, Zach 09)
Fusion moves(Woodford 08, Bleyer 10)
Problems
Computational and memory
requirements
Pairwise potentials
can not model planarity
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

7/24

Related Work: Seed-and-GrowSeed-and-Grow Methods
Grow disparity components from random seeds
Examples(Cech 07)
(Sara 03)
Problems
Slanted/textureless surfaces
No dense disparity maps

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

8/24

Contents

1

Motivation and Related Work

2

Efficient Large-Scale Stereo Matching3

Experimental Evaluation

4

Summary and Future Work

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

9/24

Idea

Assumption: rectified images
Image pairs contain ’easy’ and ’hard’ correspondences
Robustly match ’easy’ correspondences on regular grid
Build prior on dense search space ⇒ dense matching
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

10/24

Idea

EasyHardAssumption: rectified images
Image pairs contain ’easy’ and ’hard’ correspondences
Robustly match ’easy’ correspondences on regular grid
Build prior on dense search space ⇒ dense matching
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

10/24

Idea

Robust Match

Assumption: rectified images
Image pairs contain ’easy’ and ’hard’ correspondences
Robustly match ’easy’ correspondences on regular grid
Build prior on dense search space ⇒ dense matching
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

10/24

Idea

Assumption: rectified images
Image pairs contain ’easy’ and ’hard’ correspondences
Robustly match ’easy’ correspondences on regular grid
Build prior on dense search space ⇒ dense matching
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

10/24

Efficient Large-Scale Stereo
Notation
Robust support points S = {s1 , ..., sM }with sm = (um vm dm )T
Disparity dn ∈ N
Observations on = (un vn fn )T
Local image features fn
Algorithm
Split image domain into support points S and dense pixels
Assume factorization of distribution over disparity,observations and support points into ...

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

11/24

Efficient Large-Scale Stereo
Notation
Robust support points S = {s1 , ..., sM }with sm = (um vm dm )T
Disparity dn ∈ N
Observations on = (un vn fn )T
Local image features fn
Algorithm
Split image domain into support points S and dense pixels
Assume factorization of distribution over disparity,observations and support points into ...

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

11/24

Efficient Large-Scale Stereo
Notation
Robust support points S = {s1 , ..., sM }with sm = (um vm dm )TDisparity dn ∈ N
Observations on = (un vn fn )T
Local image features fnAlgorithm
Split image domain into support points S and dense pixels
Assume factorization of distribution over disparity,observations and support points into ...

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

11/24

ModelRight Image

Left Image

Graphical Model
Support Points

Support Points

Observations

Observation in left image

(l)

(r )

(l)

(r )

(l)

p(dn , on , on , S) ∝ p(dn |S, on ) p(on |on , dn )|{z}|{z}Prior
Likelihood
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

12/24

ModelRight Image

Left Image

Graphical Model
Support Points

Support Points

Observations

Observation in left image

(l)

(r )

(l)

(r )

(l)

p(dn , on , on , S) ∝ p(dn |S, on ) p(on |on , dn )|{z}|{z}PriorLikelihood
Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

12/24

Prior and Likelihood(l)Prior p(dn |S, on )Support pt. triangulation
Piecew. linear manifold
Local extrapolation
(r )

(l)

Likelihood p(on |on , dn )Laplace distribution
5 × 5 block window
3 × 3 Sobel filter

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

13/24

Prior and Likelihood(l)Prior p(dn |S, on )Support pt. triangulation
Piecew. linear manifold
Local extrapolation
(r )

(l)

Likelihood p(on |on , dn )Laplace distribution
5 × 5 block window
3 × 3 Sobel filter

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

13/24

Sampling from the model

Left image

Sample mean

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

14/24

Sampling from the model

Left image

Sample mean

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

Right image

14/24

Contents

1

Motivation and Related Work

2

Efficient Large-Scale Stereo Matching3

Experimental Evaluation

4

Summary and Future WorkEfficient Large-Scale Stereo Matching – Code: http://cvlibs.net

15/24

Middlebury Benchmark

900 x 750 pixels, ground truth

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

16/24

Middlebury Benchmark

900 x 750 pixels, 0.4 seconds

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

16/24

Middlebury Benchmark

1300 x 1100 pixels, ground truth

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

16/24

Middlebury Benchmark

1300 x 1100 pixels, 1 second

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

16/24

Accuracy (on cones image pair)
20

Error >2px [%]15

uniform prior
Cech 07
Felzenszwalb 06
Kolmogorov 01
Kostkova 03
our method

105000.5
11.5
Image resolution [Megapixel]

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

217/24

Running times (on cones image pair)

2000

50
Kolmogorov 01
Kostkova 03
our method

Felzenszwalb 06
Cech 07
uniform prior
our method

40
Running time [s]Running time [s]

1500

1000

30

20500
10000.5
11.5
Image resolution [Megapixel]

2000.51
1.5
Image resolution [Megapixel]

2[For more details see: Geiger et al., ACCV 2010]

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

18/24

3D Reconstruction: Brussels

2 seconds[http://cvlab.epfl.ch/data/strechamvs/]

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

19/24

3D Face Reconstruction[http://www.fujifilm.com/products/3d]

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

20/24

Urban Scene Reconstruction

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

21/24

Contents1

Motivation and Related Work

2

Efficient Large-Scale Stereo Matching3

Experimental Evaluation

4

Summary and Future Work

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

22/24

Summary

Simple prior based on sparse feature matches
Reduced ambiguities and run-timeTakes into account slanted surfaces
Real-time 3D reconstruction of static scenes on CPU
C++ / MATLAB code available at http://cvlibs.net

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

23/24

Summary

Simple prior based on sparse feature matches
Reduced ambiguities and run-timeTakes into account slanted surfaces
Real-time 3D reconstruction of static scenes on CPU
C++ / MATLAB code available at http://cvlibs.net

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

23/24

Summary

Simple prior based on sparse feature matches
Reduced ambiguities and run-timeTakes into account slanted surfaces
Real-time 3D reconstruction of static scenes on CPU
C++ / MATLAB code available at http://cvlibs.net

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

23/24

Summary

Simple prior based on sparse feature matches
Reduced ambiguities and run-timeTakes into account slanted surfaces
Real-time 3D reconstruction of static scenes on CPU
C++ / MATLAB code available at http://cvlibs.net

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

23/24

Summary

Simple prior based on sparse feature matches
Reduced ambiguities and run-timeTakes into account slanted surfaces
Real-time 3D reconstruction of static scenes on CPU
C++ / MATLAB code available at http://cvlibs.net

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

23/24

Future WorkDevelop better priors
Incorporate segmentation / global reasoning on lines
GPU implementation(goal: 20 fps at 1-2 megapixels)
Employ as unitary potentials on global methods⇒ smaller label sets

Thank you!

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

24/24

Future Work

Develop better priors
Incorporate segmentation / global reasoning on lines
GPU implementation(goal: 20 fps at 1-2 megapixels)
Employ as unitary potentials on global methods⇒ smaller label sets

Thank you!

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

24/24

Future WorkDevelop better priors
Incorporate segmentation / global reasoning on lines
GPU implementation(goal: 20 fps at 1-2 megapixels)
Employ as unitary potentials on global methods⇒ smaller label sets

Thank you!

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

24/24

Future Work

Develop better priors
Incorporate segmentation / global reasoning on lines
GPU implementation(goal: 20 fps at 1-2 megapixels)
Employ as unitary potentials on global methods⇒ smaller label sets

Thank you!

Efficient Large-Scale Stereo Matching – Code: http://cvlibs.net

24/24