Introduction to computer vision 9

Jean Ponce

jean.ponce@ens.fr

​

Zuhaib Akhtar za2023@nyu.edu

Ayush Jain aj3152@nyu.edu

​

​

​

Slides will be available after classes

Stereopsis

• Marr-Poggio algorithm
• Correlation-based stereo
• Adding global constraints: uniqueness,

ordering, smoothness

• Adding more cameras

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�
• Simplest case: epipolar lines are scanlines
• When does this happen?

Rectification

All epipolar lines are parallel in the rectified image plane.

Rectification example

Epipolar constraint example

Reconstruction from Rectified Images

Disparity: d=u’-u.

Depth: z = -B/d.

Binocular fusion: a problem of correspondence

A Cooperative Model (Marr and Poggio, 1976)

Excitory connections: continuity

Inhibitory connections: uniqueness

Iterate: C = Σ C - wΣ C + C .

e

i

0

A Cooperative Model (Marr and Poggio, 1976)

Excitory connections: continuity

Inhibitory connections: uniqueness

Iterate: C = Σ C - wΣ C + C .

e

i

0

Reprinted from Vision: A Computational Investigation into the Human Representation and Processing of Visual Information by David Marr.

© 1982 by David Marr. Reprinted by permission of Henry Holt and Company, LLC.

Correlation Methods (1970--)

Normalized Correlation: minimize θ instead.

Slide the window along the epipolar line until w.w’ is maximized.

Left

Right

scanline

Correlation-based methods

Norm. corr

Failures of correlation-based methods

Textureless surfaces

Occlusions, repetition

Non-Lambertian surfaces, specularities

Effect of window size

• Smaller window
• More detail
• More noise
• Larger window
• Smoother disparity maps
• Less detail

W = 3

W = 20

Results

Correlation-based matching

Ground truth

Data

Correlation Methods: Foreshortening Problems

Solution: add a second pass using disparity estimates to warp

the correlation windows, e.g. Devernay and Faugeras (1994).

Reprinted from “Computing Differential Properties of 3D Shapes from Stereopsis without 3D Models,” by F. Devernay and O. Faugeras,

Proc. IEEE Conf. on Computer Vision and Pattern Recognition (1994). © 1994 IEEE.

How can we improve window-based matching?

• The similarity constraint is local: each reference window is matched independently.

​

• Need to enforce global correspondence constraints.

Non-local constraints

• Uniqueness
• For any point in one image, there should be at most one matching point in the other image

Non-local constraints

• Uniqueness
• For any point in one image, there should be at most one matching point in the other image
• Ordering
• Corresponding points should be in the same order in both views

Non-local constraints

• Uniqueness
• For any point in one image, there should be at most one matching point in the other image
• Ordering
• Corresponding points should be in the same order in both views

Ordering constraint does not (always) hold

Non-local constraints

• Uniqueness
• For any point in one image, there should be at most one matching point in the other image
• Ordering
• Corresponding points should be in the same order in both views
• Smoothness
• We expect disparity values to change slowly (for the most part)

Scanline stereo

• Try to coherently match pixels on the entire scanline
• Different scanlines are still optimized independently

“Shortest paths” for scan-line stereo

Can be implemented with dynamic programming

(Baker & Binford’81, Ohta & Kanade ’85)

correspondence

Slide credit: Y. Boykov

Shortest path stereo in real life

• Scanline stereo generates streaking artifacts��������
• Can’t use dynamic programming to find spatially coherent disparities and correspondences on a 2D grid

Stereo matching as energy minimization

I₁

I₂

D

• Energy functions of this form can be minimized using “graph cuts” (aka min-cut/max-flow algorithms)

Y. Boykov, O. Veksler, and R. Zabih, Fast Approximate Energy Minimization via Graph Cuts, PAMI 2001

W₁(i )

W₂(i+D(i ))

D(i )

Combinatorial optimization with unary and binary terms

Quadratic pseudo-Boolean

function optimization

Binary variables

Generalization to integer variables

• n integer variables in 0..K-1

• nK binary variables (Darbon, 2009)
• x =0 if x≤k and 1 otherwise

k

Quadratic integer function optimization

Submodular case

Min-cut max-flow problems

(Boros & Hammer, 2002)

Otherwise

NP hard

Efficient exact algorithms

(Ford & Fulkerson ‘56)

(Goldberg & Tarjan ‘88)

(Boykov & Kolgomorov ’04)

Quadratic integer function optimization

For example:

with g convex (Ishikawa ‘03)

Min-cut max-flow problems

(Boros & Hammer, 2002)

Otherwise

NP hard

Efficient exact algorithms

(Ford & Fulkerson ‘56)

(Goldberg & Tarjan ‘88)

(Boykov & Kolgomorov ’04)

Quadratic pseudo-Boolean function optimization

For example:

with g convex (Ishikawa ‘03)

Min-cut max-flow problems

(Boros & Hammer, 2002)

Otherwise

NP hard

Efficient

approximate

algorithms

(Boykov et al.’01)

Combinatorial optimization:

​

• Submodularity is “too restrictive” for

certain stereo settings (use non-convex g for example)

​

​

​

​

​

• Use iterative approximate solutions

such as alpha expansion (Boykov et al.

2001)

​

Graph cuts

Ground truth

For the latest and greatest: http://www.middlebury.edu/stereo

Y. Boykov, O. Veksler and R. Zabih, “Fast Approximate Energy

Minimization via Graph Cuts, PAMI 2001.

Results

More Views (Okutami and Kanade, 1993)

Pick a reference image, and slide the corresponding

window along the corresponding epipolar lines of all

other images, using inverse depth relative to the first

image as the search parameter.

Use the sum of correlation scores to rank matches.

Reprinted from “A Multiple-Baseline Stereo System,” by M. Okutami and T. Kanade, IEEE Trans. on Pattern

Analysis and Machine Intelligence, 15(4):353-363 (1993). \copyright 1993 IEEE.

I1

I2

I10

Reprinted from “A Multiple-Baseline Stereo System,” by M. Okutami and T. Kanade, IEEE Trans. on Pattern

Analysis and Machine Intelligence, 15(4):353-363 (1993). \copyright 1993 IEEE.

Structure from motion

• Problem statement
• Ambiguities
• Euclidean SFM
• Affine SFM

The Euclidean (perspective) Structure-from-Motion Problem

Given m (internally) calibrated perspective images of n fixed

points P_j we can write

Problem: estimate the m 3x4 matrices M_i = [R_i t_i] and

the n positions P_j from the mn correspondences p_ij .

2mn equations in 11m (or rather 5m)+3n unknowns

Overconstrained problem, that can be solved

using (non-linear) least squares!

(Normalized coordinates)

The Euclidean Ambiguity of Euclidean SFM

If R_i, t_i, and P_j are solutions,

So are R_i’, t_i’, and P_j’, where

In fact, the absolute scale cannot be recovered since:

When the intrinsic parameters are known (normalized coordinates)

Euclidean ambiguity up to a similarity transformation.

Euclidean motion from E (Longuet-Higgins, 1981)

Singular Value Decomposition

square roots of

Euclidean motion from E (Longuet-Higgins, 1981)

• Given F computed from n > 7 point correspondences, and its

SVD F= UWV^T, compute E=U diag(1,1,0) V^T.

​

Euclidean motion from E (Longuet-Higgins, 1981)

Euclidean motion from E (Longuet-Higgins, 1981)

Euclidean motion from E (Longuet-Higgins, 1981)

Euclidean reconstruction. Mean relative error: 3.1%