StereoScan: Dense 3d in Real-time
Andreas Geiger, Julius Ziegler, Christoph Stiller

K ARLSRUHE I NSTITUTE OF T ECHNOLOGYKIT – University of the State of Baden-Wuerttemberg andNational Laboratory of the Helmholtz Associationwww.kit.edu

Contents

1

Motivation and Related Work

2

StereoScan: Approach3

Experimental Evaluation / Future Work

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

2/24

Contents

1

Motivation and Related Work

2

StereoScan: Approach3

Experimental Evaluation / Future Work

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

3/24

Motivation
stereo sequence

3d reconstruction

Goal:
Real-time 3d from stereo video on a single CPU
Applications:
Environment mapping / place recognition
Scene understanding
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

4/24

Motivation
stereo sequence

3d reconstruction

Goal:
Real-time 3d from stereo video on a single CPU
Applications:
Environment mapping / place recognition
Scene understanding
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

4/24

Related Work

[MonoSLAM, Davison et al.]Simultaneous Localization and Mapping
Real-time systems exist
Mostly sparse features
Focus: loop-closure
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

5/24

Related Work

[3d Recording for Archeological Fieldwork, Pollefeys et al.][Building Rome in a Day, Agarwal et al.]

Structure-from-Motion
Monocular ⇒ requires motion
Multiple views of a single object
Computationally demanding

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

6/24

Related Work

[Stixel World, Badino et al.]Stixel World
Compact medium-level representation
Integration: Multiple Kalman filters
Can not represent overhanging structures
or strongly curved roads

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

7/24

Contents

1

Motivation and Related Work

2

StereoScan: Approach3

Experimental Evaluation / Future Work

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

8/24

StereoScan - Overview

CPU with SSE3 instruction set
Core 1

12 fpsCore 24 fps

Scene flow

Dense stereo

Egomotion

Fusion + 3d reprojection

frame 2
image planeframe 1

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

frame 1

9/24

StereoScan - Scene Flow

CPU with SSE3 instruction set
Core 1

12 fpsCore 24 fps

Scene flow

Dense stereoEgomotion

Fusion + 3d reprojection

frame 2
image planeframe 1

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

frame 1

10/24

StereoScan - Feature Detection

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

11/24

StereoScan - Feature Detection

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

11/24

StereoScan - Feature Detection

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

11/24

StereoScan - Feature Detection

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

11/24

StereoScan - Feature Description

16 locations within 11 × 11 block window∂I ∂I( ∂u, ∂v ) ⇒ 32 bytes per descriptor

Efficient Sum-of-Absolute-Differences (SAD) via SIMD
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

12/24

StereoScan - Feature Matchingright imagetime

left image

Feature matching:Detect interest points using non-maximum-suppression
Match 4 images in a ’space-time’ circle
Use epipolar constraints for left ↔ right matching
Accept if last feature coincides with first feature
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

13/24

StereoScan - Feature Matchingright image

timeleft image

Feature matching:Detect interest points using non-maximum-suppression
Match 4 images in a ’space-time’ circle
Use epipolar constraints for left ↔ right matching
Accept if last feature coincides with first feature
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

13/24

StereoScan - Feature Matchingright image

timeleft image

Feature matching:Detect interest points using non-maximum-suppression
Match 4 images in a ’space-time’ circle
Use epipolar constraints for left ↔ right matching
Accept if last feature coincides with first feature
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

13/24

StereoScan - Feature Matchingright image

timeleft image

Feature matching:Detect interest points using non-maximum-suppression
Match 4 images in a ’space-time’ circle
Use epipolar constraints for left ↔ right matching
Accept if last feature coincides with first feature
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

13/24

StereoScan - Feature Matchingright image

timeleft image

Feature matching:Detect interest points using non-maximum-suppression
Match 4 images in a ’space-time’ circle
Use epipolar constraints for left ↔ right matching
Accept if last feature coincides with first feature
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

13/24

StereoScan - Feature Matching

Fast feature matching:
1st: Match a sparse set of interest points within each class
Build statistics over likely displacements within each bin
Use this statistics for speeding up 2nd matching stage
Rejection outliers (Delaunay triangulation)
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

14/24

StereoScan - Feature Matching

Fast feature matching:
1st: Match a sparse set of interest points within each class
Build statistics over likely displacements within each bin
Use this statistics for speeding up 2nd matching stage
Rejection outliers (Delaunay triangulation)

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

14/24

StereoScan - Feature Matching

Fast feature matching:
1st: Match a sparse set of interest points within each class
Build statistics over likely displacements within each bin
Use this statistics for speeding up 2nd matching stage
Rejection outliers (Delaunay triangulation)
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

14/24

StereoScan - Feature Matching

Fast feature matching:
1st: Match a sparse set of interest points within each class
Build statistics over likely displacements within each bin
Use this statistics for speeding up 2nd matching stage
Rejection outliers (Delaunay triangulation)
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

14/24

StereoScan - Egomotion

CPU with SSE3 instruction set
Core 1

12 fpsCore 24 fps

Scene flow

Dense stereo

Egomotion

Fusion + 3d reprojection

frame 2
image planeframe 1

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

frame 1

15/24

StereoScan - Egomotion

minr,tNX(l)xi − π (l) (Xi ; r, t)2(r )+ xi− π (r ) (Xi ; r, t)

2i=1

Minimize reprojection errors (Gauss-Newton + RANSAC)
Kalman Filter (constant acceleration model)
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

16/24

StereoScan - 3D Fusion

CPU with SSE3 instruction set
Core 1

12 fpsCore 24 fps

Scene flow

Dense stereo

Egomotion

Fusion + 3d reprojection

frame 2
image planeframe 1

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

frame 1

17/24

StereoScan - 3D Fusion

Greedy pixel association by reprojection into next frame
Depth fusion based on stereo uncertainty
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

18/24

Contents

1

Motivation and Related Work

2

StereoScan: Approach3

Experimental Evaluation / Future Work

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

19/24

Experiments - Scene Flow

43.5

Kitt et al. 2010
our method
our method (2 scales)

Running time (s)

32.5
2
1.5
1
0.5
005000
10000
Number of features

StageFilterNMS
Matching 1
Matching 2Refinement
Total timeTime
6.0 ms
12 ms
2.8 ms10.7 ms
5.1 ms36.6 ms

15000

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

20/24

Experiments - Scene Flow

StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

21/24

Experiments - Egomotion Estimation

110Kitt et al. 2010
our method
0

Running time (s)10Stage
RANSAC
Refinement
Kalman filter
Total time

−1

10−2

10Time
3.8 ms
0.4 ms
0.1 ms
4.3 ms−310050100

150 200 250
Number of features

300

350400StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

22/24

Experiments - Egomotion Estimation
80z [meters]

7060
5040
302010GPS/IMU
Kitt et al. 2010
our method

0−120

−100

−80

−60

−40

−200x [meters]
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

23/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3Dreconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24

Conclusion and Future Work
Conclusion:
Proposed a real-time 3D
reconstruction algorithm
Real-time on a single CPU
Large-scale stereo imagery
Code: www.cvlibs.net
Future Work:
Handle dynamic objects
Integrate multiple frames
3d urban scene
understanding (CVPR’11)

Thank you!
StereoScan: Dense 3d in Real-time – Source code: www.cvlibs.net

24/24