1 of 52

Lecture 8: Estimating geometry

1

Slides mostly from N. Snavely

2 of 52

Recall: triangulation

Given projection pi of unknown 3D point X in two or more images (with known cameras Pi), find X

Source: D. Fouhey

3 of 52

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

4 of 52

Triangulation

Rays in principle should intersect, but in practice usually don’t exactly due to noise, numerical errors.

p1

p2

X?

Source: D. Fouhey

5 of 52

Triangulation – Geometry

p1

p2

X

Find shortest segment between viewing rays, set X to be the midpoint of the segment.

Source: D. Fouhey

6 of 52

Triangulation – Geometry

p1

p2

X

Find shortest segment between viewing rays, set X to be the midpoint of the segment.

Source: D. Fouhey

7 of 52

Estimating 3D structure

  • Given many images, how can we…
    1. Figure out where they were all taken from?
    2. Build a 3D model of the scene?

​

​

​

​

​

This is the structure from motion problem

7

Source: N. Snavely

8 of 52

Today

  • Structure from motion
  • Multi-view stereo
  • Visual SLAM

8

9 of 52

Structure from motion

9

  • Input: images with pixels in correspondence pi,j = (ui,j,vi,j)

​

  • Output
    • Structure: 3D location xi for each point pi
    • Motion: camera parameters Rj , tj possibly Kj

​

  • Objective function: minimize reprojection error

Reconstruction (side)

(top)

Source: N. Snavely

10 of 52

Camera calibration & triangulation

  • Suppose we know 3D points
    • And have matches between these points and an image
    • Computing camera parameters similar to homography estimation

​

  • Suppose we have know camera parameters, each of which observes a point
    • We can solve for the 3D location

​

  • Seems like a chicken-and-egg problem, but in SfM we can solve both at once

10

Source: N. Snavely

11 of 52

Feature detection

11

  • Same process as with homography estimation
  • Detect features using SIFT

Source: N. Snavely

12 of 52

Feature matching

Match features between each pair of images

12

Source: N. Snavely

13 of 52

Feature matching

13

  • Remove bad matches using ratio test.
  • Other tricks: throw out matches that aren’t on epipolar lines.

Source: N. Snavely

14 of 52

Correspondence estimation

  • Track each feature across the dataset.
  • Link up pairwise matches to form connected components of matches across several images.

14

Image 1

Image 2

Image 3

Image 4

Source: N. Snavely

15 of 52

Correspondence estimation

15

Image 1

Image 2

Image 3

Image 4

A point track: the same 3D point projects to all 4 image positions.

16 of 52

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

17 of 52

Structure from motion

  • Minimize sum of squared reprojection errors:

​

​

​

​

​

​

  • Minimizing this function is called bundle adjustment.
    • Optimized using non-linear least squares
  • Lots of outliers: use robust loss functions (e.g., Huber) and solve incrementally

17

predicted

image location

observed

image location

indicator variable:

is point i visible in image j ?

Source: N. Snavely

18 of 52

Incremental structure from motion

18

Source: N. Snavely

19 of 52

Is SfM always uniquely solvable?

No. Consider the Necker cube:

Source: N. Snavely

20 of 52

Is SfM always uniquely solvable?

Two interpretations:

Image source: Wikipedia

21 of 52

Can also reconstruct from video

Source: N. Snavely

22 of 52

Applications: Visual Reality & Augmented Reality

Source: N. Snavely

23 of 52

Application: Simultaneous localization and mapping (SLAM)

Scape: Building the ‘AR Cloud’: Part Three —3D Maps, the Digital Scaffolding of the 21st Century

https://medium.com/scape-technologies/building-the-ar-cloud-part-three-3d-maps-the-digital-scaffolding-of-the-21st-century-465fa55782dd

Source: N. Snavely

24 of 52

Today

  • Structure from motion
  • Multi-view stereo
  • Stereo matching algorithms

24

25 of 52

Multi-view stereo

Source: N. Snavely

Can we estimate depth, now that we have pose?

26 of 52

Multi-view stereo

reference view

neighbor views

Source: Y. Furukawa

Is this a surface point?

27 of 52

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

?

28 of 52

Multi-view stereo

reference view

neighbor views

Source: Y. Furukawa

Photometric error across different depths

29 of 52

Multi-view stereo

reference view

neighbor views

Source: Y. Furukawa

Photometric error across different depths

30 of 52

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

31 of 52

Multi-view stereo: advantages

  • Can match windows using more than 1 neighbor, giving a stronger match signal

​

  • If you have lots of potential neighbors, can choose the best subset of neighbors to match per reference image

​

  • Can reconstruct a depth map for each reference frame, and the merge into a complete 3D model

Source: N. Snavely

32 of 52

Choosing the stereo baseline

What’s the optimal baseline?

    • Too small: large depth error
    • Too large: difficult search problem

width of

a pixel

Large Baseline

Small Baseline

all of these

points project

to the same

pair of pixels

33 of 52

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.

  • For larger baselines, must search larger area in second image
  • For short baselines, estimated depth will be less precise due to narrow triangulation

Source: N. Snavely

34 of 52

Depth is ambiguous from local information alone!

34

35 of 52

Today

  • Structure from motion
  • Multi-view stereo
  • Visual SLAM

35

36 of 52

Recall: Stereo matching based on sum-of-squared distance

36

SSD

​

dmin d

Best matching disparity

Source: N. Snavely

37 of 52

Window size

37

W = 3

W = 20

Source: N. Snavely

38 of 52

Stereo as energy minimization

  • What defines a good stereo correspondence?
    1. Match quality
      • Want each pixel to find a good match in the other image
    2. Smoothness
      • If two pixels are adjacent, they should (usually) move about the same amount

38

Source: N. Snavely

39 of 52

Stereo as energy minimization

39

  • Find disparity map d that minimizes an energy function , where d is disparity.

​

  • Simple pixel / window matching

Squared distance between windows I(x, y) and J(x + d(x,y), y)

Source: N. Snavely

40 of 52

Stereo as energy minimization

40

y = 141

x

d

Simple pixel / window matching: choose the minimum of each pixel independently

Source: N. Snavely

41 of 52

Greedy selection of best match

41

Source: N. Snavely

42 of 52

Stereo as energy minimization

  • Better objective function

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

43 of 52

Stereo as energy minimization

43

match cost:

smoothness cost:

4-connected neighborhood

8-connected neighborhood

: set of neighboring pixels

Source: N. Snavely

44 of 52

Smoothness cost

44

“Potts model”

L1 distance

How do we choose V?

Source: N. Snavely

45 of 52

Dynamic programming

  • Can minimize this independently per row scanline using dynamic programming (DP)
  • Basic idea: incrementally build a table of costs D one column at a time

: minimum cost of solution such that d(x,y) = i

Recurrence:

Base case:

(L = max disparity)

Source: N. Snavely

46 of 52

Dynamic programming

  • Finds “smooth”, low-cost path through cost volume from left to right

y = 141

x

d

Source: N. Snavely

47 of 52

Dynamic programming

Source: N. Snavely

48 of 52

Dynamic programming

  • Can we apply this trick in 2D as well?

​

​

​

​

​

​

​

​

  • No: dx,y-1 and dx-1,y may depend on different values of dx-1,y-1

Source: D. Huttenlocher

49 of 52

Stereo as a minimization problem

  • The 2D problem has many local minima
    • Famous problem: doing inference in a Markov Random Field (MRF)
    • Gradient descent doesn’t work well

​

  • And a large search space
    • n x m image w/ k disparities has knm possible solutions
    • Finding the global minimum is NP-hard in general

​

  • Good approximations exist (see Szeliski textbook):
    • Graph cuts
    • Belief propagation

Source: N. Snavely

50 of 52

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

51 of 52

Deep learning + MRF refinement

51

[Zbontar & LeCun, 2015]

Left

Right

Positive

Negative

Query patch

52 of 52

Next lecture: Motion estimation