�ݺ�ߣ

Lecture 9 & 10:
Stereo Vision
Professor Fei-Fei Li
Stanford Vision Lab
Lecture 9 & 10 -
Fei-Fei Li 1 21-0ct-14

Dimensionality Reduction Machine (3D to 2D)
30 world
Point of observation
20 image
Figures? Stephen E. Palmer, 2002
Fei-Fei Li Lecture 9 & 10 -

Real-world camera+ Real-world transformation
�ݺ�ߣ inspiration: S. Savarese

What we will learn today?
? Introduction to stereo vision
? Epipolar geometry: a gentle intro
? Parallel images & image rectification
? Solving the correspondence problem
? Homographic transformation
? Active stereo vision system
Reading:
[HZ] Chapters: 4, 9, 11
[FP] Chapters: 10
Lecture 9 & 10 - 21-0ct-14
Fei-Fei Li

Recovering 3D from Images
? How can we automatically compute 3D geometry
from images?
- What cues in the image provide 3D information?
Real 30 world 20 image
Point of observation
Lecture 9 & 10 - 10 21-0ct-14
Fei-Fei Li

Visual Cues for 3D
? Shading
Merle Norman Cosmetics, LosAngeles
V )
Q)
>
ro
I
..,
.-t=
"'C
Q)
1...
u
Q)
"'C
V l
Lecture 9 & 10 - 11 21-0ct-14
Fei-Fei Li

Visual Cues for 3D
? Shading
V )
Q)
>
ro
? Texture
I
..,
.-t=
"'C
Q)
The Visual Cliff, by William Vandivert, 1960 1...
u
Q)
"'C
V l
Lecture 9 & 10 - 12 21-0ct-14
Fei-Fei Li

Visual Cues for 3D
? Shading
? Texture
? Focus V )
Q)
>
ro
I
..,
.-t=
"'C
Q)
From TheArt of Photography, Canon
1...
u
Q)
"'C
V l
Lecture 9 & 10 - 13 21-0ct-14
Fei-Fei Li

Visual Cues for 3D
? Shading
? Texture
? Focus
V )
Q)
>
ro
I
..,
.-t=
"'C
Q)
? Motion 1...
u
Q)
"'C
V l
Lecture 9 & 10 - 14 21-0ct-14
Fei-Fei Li

Visual Cues for 3D
? Shading
? Others:
- Highlights
- Shadows
- Silhouettes
- Inter-reflections
- Symmetry
- Light Polarization
? Texture
? Focus
? Motion
Shape From X
? X= shading, texture, focus, motion, ...
? We'll focus on the motion cue
V )
Q)
>
ro
I
..,
.-t=
"'C
Q)
1...
u
Q)
"'C
V l
Lecture 9 & 10 - 15 21-0ct-14
Fei-Fei Li

Stereo Reconstruction
? The Stereo Problem
- Shape from two (or more) images
- Biological motivation
. '
known
camera
viewpoints
. /
V )
Q)
>
ro
I
..,
.-t=
"'C
Q)
1...
u
Q)
"'C
V l
Lecture 9 & 10 - 16 21-0ct-14
Fei-Fei Li

Why do we have two eyes?
I I )
Q)
>
ro
I
....,
:t=
""C
Q)
lo...
vs.
u
Q)
""C
V l
Cyclope Odysseus
Lecture 9 & 1 0 -

1. Two is better than one
I I )
Q)
>
ro
I
....,
:t=
""C
Q)
lo...
u
Q)
""C
V l
Lecture 9 & 10 -

2. Depth from Convergence
d==
K - - d - - l l l - l
k ---------- d2---------
-
Human performance: up to 6-8feet
c
V l
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l
Lecture 9 & 10 -

Reading:
[FP] Chapters: 10
Lecture 9 & 10 -

Epipolar geometry
0
? Epipolar Plane
? Baseline
? Epipolar Lines
0'
? Epipoles e, e'
=intersections of baseline with image planes
= projections of the other camera center
=vanishing points of camera motion direction
Lecture 9 & 10 -

Example: Converging image planes
Lecture 9 & 10 -

Epipolar Constraint
p
? Potential matches for p have to lie on the corresponding epipolar line/'.
? Potential matches for p' have to lie on the corresponding epipolar line/.
Lecture 9 & 10 - 24 21-0ct-14
Fei-Fei Li

Cross product as matrix multiplication
0
az
-ay
-az
0
ax
aY
-aX
0
bx
b
y
b
z
axb = = [ax]b
"skew symmetric matrix"
Lecture 9 & 10 - 21-0ct-14
28
Fei-Fei Li

Epipolar Constraint
? E p' is the epipolar line associated with p' (I= E p')
? E
Tp is the epipolar line associated with p (I'= E
Tp)
? Eis singular (rank two)
? Ee' =0 and E
Te =0
? Eis 3x3 matrix; 5 DOF
Lecture 9 & 10 - 21-0ct-14
30
Fei-Fei Li

Reading:
[FP] Chapters: 10
Lecture 9 & 10 - 31 21-0ct-14
Fei-Fei Li

Simplest Case: Parallel images
? Image planes of cameras
are parallel to each other
and to the baseline
? Camera centers are at same
height
? Focal lengths are the same
V )
Q)
>
ro
I
......,
+-'
""C
Q)
u
Q)
""C
V )
Lecture 9 & 10 - 32 21-0ct-14
Fei-Fei Li

Triangulation --depth from disparity
p
z
0 Baseline 0 '
B
dz
.sparz.ty = u - u' =
B .f
- -
z
Disparity is inversely proportional to depth!
V l
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l
Lecture 9 & 10 - 21-0ct-14
36
Fei-Fei Li

Stereo image rectification
V )
Q)
>
ro
I
......,
+-'
""C
Q)
u
Q)
""C
V )
Lecture 9 & 10 -

Rectification example
Lecture 9 & 10 - 21-0ct-14
39
Fei-Fei Li

Application: view morphing
S.M. Seitz and C. R. Dyer, Proc. 5/GGRAPH 96, 1996, 21-30
I I I
Lecture 9 & 10 - 40 21-0ct-14
Fei-Fei Li

Lecture 9 & 10 - 41 21-0ct-14
Fei-Fei Li

Lecture 9 & 10 - 42 21-0ct-14
Fei-Fei Li

Lecture 9 & 10 - 43 21-0ct-14
Fei-Fei Li

Removing perspective distortion
- (rectification)
- - "

Reading:
[FP] Chapters: 10
Lecture 9 & 10 - 45 21-0ct-14
Fei-Fei Li

Stereo matching:
solving the correspondence problem
? Hypothes is 1
o Hypothes is 2
o Hypothes is 3
oc
'
? Goal: finding matching points between two images
Lecture 9 & 10 - 46 21-0ct-14
Fei-Fei Li

Basic stereo matching algorithm
? For each pixel in the first image
- Find corresponding epipolar line in the right image
- Examine all pixels on the epipolar line and pick the best match
- Triangulate the matches to get depth information i
- ,
+ - '
""0
Q)
u
Q)
""0
V l
? Simplest case: epipolar lines are scanlines
- When does this happen?
Lecture 9 & 10 - 21-0ct-14
47
Fei-Fei Li

Basic stereo matching algorithm
? If necessary, rectify the two stereo images to transform
epipolar lines into scanlines
? For each pixel x in the first image
- Find corresponding epipolar scanline in the right image
- Examine all pixels on the scanline and pick the best match x'
- Compute disparity x-x' and set depth(x) = 1/(x-x')
Lecture 9 & 10 - 21-0ct-14
48
Fei-Fei Li

Correspondence problem
? Let's make some assumptions to simplify the
matching problem
- The baseline is relatively small (compared to the
depth of scene points)
- Then most scene points are visible in both views
- Also, matching regions are similar in appearance
V l
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l
Lecture 9 & 10 - 21-0ct-14
49
Fei-Fei Li

Correspondence search with similarity constraint
Left
Matching cost
? �ݺ�ߣ a window along the right scanline and
compare contents of that window with the
reference window in the left image
? Matching cost: SSD or normalized correlation
V l
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l
Lecture 9 & 10 - 50 21-0ct-14
Fei-Fei Li

Left
0
( f )
( f )
Lecture 9 & 10 - 51 21-0ct-14
Fei-Fei Li

Left
c
0
Lecture 9 & 10 - 52 21-0ct-14
Fei-Fei Li

Effect of window size
W==3
- Smaller window
+ More detail
? More noise
-Larger window
+ Smoother disparity maps
? Less detail
W==20
Lecture 9 & 10 - 53 21-0ct-14
Fei-Fei Li

The similarity constraint
? Corresponding regions in two images should be similar in
appearance
? ...and non-corresponding regions should be different
? When will the similarity constraint fail?
V l
Lecture 9 & 10 - 54 21-0ct-14
Fei-Fei Li
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l

Limitations of similarity constraint
Textureless surfaces Occlusions, repetition
V l
Q)
>
ro
I
- ,
+ - '
""0
Q)
u
Q)
""0
V l

Results with window search
Ground truth
Lecture 9 & 10 - 56 21-0ct-14
Fei-Fei Li

Better methods exist... (CS231a)
-
Graph cuts Ground truth
Y. Boykov, 0. Veksler, and R. Zabih,
FastApproximate Energy Minimization via Graph Cuts, PAMI 2001
Lecture 9 & 10 - 57 21-0ct-14
Fei-Fei Li

The role of the baseline
Small Baseline Large Baseline
?Small baseline:
?Large baseline:
large depth error
difficult search problem
�ݺ�ߣ credit: S. Seitz
Lecture 9 & 10 - 58 21-0ct-14
Fei-Fei Li

Problem for wide baselines: Foreshortening
l l'
? Matching with fixed-size windows will fail!
? Possible solution: adaptively vary window size
? Another solution: model-based stereo (CS231a)
�ݺ�ߣ credit: J. Hayes
Lecture 9 & 10 - 59 21-0ct-14
Fei-Fei Li

? Parallel images
Reading:
[FP] Chapters: 10
Lecture 9 & 10 - 21-0ct-14
60
Fei-Fei Li

Reminder: transformations in 2D
SpeciaI case
from lecture 2
(planar rotation
& translation)
u'
v' -
1
u
v
1
u
v
1
R t
0 1
= H e
- 3 DOF
- Preserve distance (areas)
- Regulate motion
of rigid object

Reminder: transformations in 2D
Generic case
(rotation in 3D, scale
& translation)
u'
v' -
1
aI a2 a3
a4 as a6
a7 as a9
u
v
1
u
v
1
= H
- 8 DOF
- Preserve colinearity

Goal: estimate the homographic
transformation between two images
Assumption: Given a set of corresponding points.
Lecture 9 & 10 -

Goal: estimate the homographic
transformation between two images
Assumption: Given a set of corresponding points.
Question: How many points are needed? - - - ? At least 4 points
(8 equations)
Hint: DoF for H? 8!
Lecture 9 & 10 -

DLT algorithm (direct Linear Transformation)
Unknown [9x1]
Pi' xH pi =0
l
I
'
A. h = 0
1
I
-
Function of
measurements
hl
h2
hl h2
h4 hs h
6
h7 h9
[2x9]
h=
H =
h9
I
9x1
2independentequations
Lecture 9 & 10 -
Fei-Fei Li 21-0ct-14
66

How to solve A 2 Nx 9 h 9x1 = 0 ?
Singular Value Decomposition (SVD)!
Lecture 9 & 10 -
68

Singular Value Decomposition (SVD)!
l
u 2 n x 9 L 9 x 9 V T
9x9
Last column of V gives h! ?
H!
I Why? See pag 593 of AZ I Lecture 9 & 10 -
69

[U,D,V] = svd(A,O);
x = V( : , end) ;
Lecture 9 & 10 -

Clarification about SVD
pmxn = U xn Dnxn ............. xn
/
Has n orthogonal
columns

Orthogonal
matrix
? This is one of the possible SVD decompositions
? This is typically used for efficiency
? The classic SVD is actually:
pmxn = IQ]mxm D mxniTi:n
/
orthogonal Orthogonal
Lecture 9 & 10 -

Lecture 9 & 10 -

Reading:
[FP] Chapters: 10
Lecture 9 & 10 -

Active stereo (shadows)
J. Bouguet & P. Perona, 99
S. Savarese, J. Bouguet & Perona, 00
Lecture 9 & 10 -

Active stereo (color-coded stripes)
Rapid shape acquisition: Projector+ stereo cameras
L.Zhang, B. Curless, and S. M. Seitz. Rapid Shape Acquisition Using Color Structured Light and Multi-pass Dynamic
Programming. 3DPVT 2002
Lecture 9 & 10 - 79 21-0ct-14
Fei-Fei Li

Active stereo {stripe)
Digital Michelangelo Project
http://graphics.stanford.edu/projects/mich/
? Optical triangulation
Project a single stripe of laser light
Scan it across the surface of the object
This is a very precise version of structured light scanning
Lecture 9 & 10 - 21-0ct-14
80
Fei-Fei Li

Laser scanned models
The Digital Michelangelo Project, Levoy et al.
Lecture 9 & 10 - 81 21-0ct-14
Fei-Fei Li

Lecture 9 & 10 - 21-0ct-14
82
Fei-Fei Li

Fei-Fei Li Lecture 9 & 10 - 83 21-0ct-14

1.0 mm resolution (56 million triangles)

Reading:
[FP] Chapters: 10
Lecture 9 & 10 - 21-0ct-14
86
Fei-Fei Li

�ݺ�ߣ

Binder1.pptx

More Related Content

Binder1.pptx