Lecture 8: Estimating geometry
1
Slides mostly from N. Snavely
Recall: triangulation
Given projection pi of unknown 3D point X in two or more images (with known cameras Pi), find X
Source: D. Fouhey
Triangulation
p1
p2
X?
Given projection pi of unknown 3D point X in two or more images (with known cameras Pi), find X
Why is the calibration here important?
Source: D. Fouhey
Triangulation
Rays in principle should intersect, but in practice usually don’t exactly due to noise, numerical errors.
p1
p2
X?
Source: D. Fouhey
Triangulation – Geometry
p1
p2
X
Find shortest segment between viewing rays, set X to be the midpoint of the segment.
Source: D. Fouhey
Triangulation – Geometry
p1
p2
X
Find shortest segment between viewing rays, set X to be the midpoint of the segment.
Source: D. Fouhey
Estimating 3D structure
This is the structure from motion problem
7
Source: N. Snavely
Today
8
Structure from motion
9
Reconstruction (side)
(top)
Source: N. Snavely
Camera calibration & triangulation
10
Source: N. Snavely
Feature detection
11
Source: N. Snavely
Feature matching
Match features between each pair of images
12
Source: N. Snavely
Feature matching
13
Source: N. Snavely
Correspondence estimation
14
Image 1
Image 2
Image 3
Image 4
Source: N. Snavely
Correspondence estimation
15
Image 1
Image 2
Image 3
Image 4
A point track: the same 3D point projects to all 4 image positions.
Structure from motion
16
Camera 1
Camera 2
Camera 3
R1,t1
R2,t2
R3,t3
X1
X4
X3
X2
X5
X6
X7
p1,1
p1,2
p1,3
Source: N. Snavely
Structure from motion
17
predicted
image location
observed
image location
indicator variable:
is point i visible in image j ?
Source: N. Snavely
Incremental structure from motion
18
Source: N. Snavely
Is SfM always uniquely solvable?
No. Consider the Necker cube:
Source: N. Snavely
Is SfM always uniquely solvable?
Two interpretations:
Image source: Wikipedia
Can also reconstruct from video
Source: N. Snavely
Applications: Visual Reality & Augmented Reality
Source: N. Snavely
Application: Simultaneous localization and mapping (SLAM)
Scape: Building the ‘AR Cloud’: Part Three —3D Maps, the Digital Scaffolding of the 21st Century
Source: N. Snavely
Today
24
Multi-view stereo
Source: N. Snavely
Can we estimate depth, now that we have pose?
Multi-view stereo
reference view
neighbor views
Source: Y. Furukawa
Is this a surface point?
Multi-view stereo
Source: Y. Furukawa
reference view
neighbor views
Evaluate the likelihood of a particular depth for a particular reference patch:
Patch from reference View
Corresponding patches at depth guess in other views
?
Multi-view stereo
reference view
neighbor views
Source: Y. Furukawa
Photometric error across different depths
Multi-view stereo
reference view
neighbor views
Source: Y. Furukawa
Photometric error across different depths
Multi-view stereo
reference view
neighbor views
Source: Y. Furukawa
Solve for a depth map over the whole reference view
Photometric error across different depths
Multi-view stereo: advantages
Source: N. Snavely
Choosing the stereo baseline
What’s the optimal baseline?
width of
a pixel
Large Baseline
Small Baseline
all of these
points project
to the same
pair of pixels
Multiple-baseline stereo
z
width of
a pixel
width of
a pixel
z
pixel matching score
M. Okutomi and T. Kanade, “A Multiple-Baseline Stereo System,” IEEE Trans. on Pattern Analysis and Machine Intelligence.
Source: N. Snavely
Depth is ambiguous from local information alone!
34
Today
35
Recall: Stereo matching based on sum-of-squared distance
36
SSD
dmin d
Best matching disparity
Source: N. Snavely
Window size
37
W = 3
W = 20
Source: N. Snavely
Stereo as energy minimization
38
Source: N. Snavely
Stereo as energy minimization
39
Squared distance between windows I(x, y) and J(x + d(x,y), y)
Source: N. Snavely
Stereo as energy minimization
40
y = 141
x
d
Simple pixel / window matching: choose the minimum of each pixel independently
Source: N. Snavely
Greedy selection of best match
41
Source: N. Snavely
Stereo as energy minimization
42
{
{
match cost
smoothness cost
Want each pixel to find a good match in the other image
Adjacent pixels should (usually) move about the same amount
Source: N. Snavely
Stereo as energy minimization
43
match cost:
smoothness cost:
4-connected neighborhood
8-connected neighborhood
: set of neighboring pixels
Source: N. Snavely
Smoothness cost
44
“Potts model”
L1 distance
How do we choose V?
Source: N. Snavely
Dynamic programming
: minimum cost of solution such that d(x,y) = i
Recurrence:
Base case:
(L = max disparity)
Source: N. Snavely
Dynamic programming
y = 141
x
d
Source: N. Snavely
Dynamic programming
Source: N. Snavely
Dynamic programming
Source: D. Huttenlocher
Stereo as a minimization problem
Source: N. Snavely
Better methods exist...
Graph cuts model
Boykov et al., Fast Approximate Energy Minimization via Graph Cuts,
International Conference on Computer Vision, September 1999.
Ground truth
Greedy selection
Source: N. Snavely
Deep learning + MRF refinement
51
[Zbontar & LeCun, 2015]
Left
Right
Positive
Negative
Query patch
Next lecture: Motion estimation