CS代考 EBU6230)

PowerPoint 프레젠테이션

Changjae Oh

Copyright By PowCoder代写 加微信 powcoder

Computer Vision
– Stereo: Epipolar geometry –

Semester 1, 22/23

Objectives

• To understand epipolar geometry for stereo vision

• To understand epipolar constraint in calibrated/uncalibrated case

Two-view geometry

• Epipolar Plane – plane containing baseline (1D family)

• Epipoles
= intersections of baseline with image planes
= projections of the other camera center
= vanishing points of the motion direction

• Baseline – line connecting the two camera centers

Epipolar geometry

• Epipolar Lines – intersections of epipolar plane with image
planes (always come in corresponding pairs)

Epipolar constraint

• If we observe a point x in one image, where can
the corresponding point x’ be in the other image?

Epipolar constraint

• Potential matches for x have to lie on the corresponding
epipolar line l’.

• Potential matches for x’ have to lie on the corresponding
epipolar line l.

Epipolar constraint

• An important concept for stereo vision

Credit: K. Kitani

Task: Match point in the left image to point in the right image

How would you do it?
Block matching to the entire image? (EBU6230)

Epipolar constraint

• An important concept for stereo vision

Task: Match point in the left image to point in the right image

Want to avoid search over entire image

(if the images have been rectified)
Epipolar constraint reduces search to a single line

Epipolar constraint example

• Epipolar constraint reduces search range to a single line

Epipolar constraint: Calibrated case

• Intrinsic and extrinsic parameters of the cameras are known, world coordin
ate system is set to that of the first camera

• Then the projection matrices are given by K[I | 0] and K’[R | t]

• We can multiply the projection matrices (and the image points) by the inve
rse of the calibration matrices to get normalized image coordinates:

XtRxKxX,IxKx ][0][

Epipolar constraint: Calibrated case

x x’ = Rx+t

The vectors Rx, t, and x’ are coplanar

Epipolar constraint: Calibrated case

0])([ = xRtx ¢x

x x’ = Rx+t

The vectors Rx, t, and x’ are coplanar

Epipolar constraint: Calibrated case

0])([ = xRtx ¢x

x x’ = Rx+t

Essential Matrix
(Longuet-Higgins, 1981)

The vectors Rx, t, and x’ are coplanar

Epipolar constraint: Calibrated case

• 𝑬𝒙 is the epipolar line associated with 𝒙 (𝒍′ = 𝑬𝒙 )

̶ Recall: a line is given by ax + by + c = 0 or

, where0 y

Epipolar constraint: Calibrated case

• 𝑬𝒙 is the epipolar line associated with 𝒙 (𝑙′ = 𝑬𝒙)
• 𝑬𝑇𝒙′ is the epipolar line associated with 𝒙’ (𝑙 = 𝑬𝑇𝒙′)
• 𝑬𝒆 = 0 and 𝐸𝑇𝒆′ = 0
• 𝑬 is singular (rank two)
• 𝑬 has five degrees of freedom

Epipolar constraint: Uncalibrated case

• The calibration matrices K and K’ of the two cam
eras are unknown

• We can write the epipolar constraint in terms of
unknown normalized coordinates:

0ˆˆ = xEx
T xKxxKx ==

Epipolar constraint: Uncalibrated case

Fundamental Matrix
(Faugeras and Luong, 1992)

0ˆˆ = xEx

−−== KEKFxFx

Epipolar constraint: Uncalibrated case

• 𝑭𝒙 is the epipolar line associated with 𝒙(𝒍′ = 𝑭𝒙)
• 𝑭𝑇𝒙′ is the epipolar line associated with 𝒙′(𝒍 = 𝑭𝑇𝒙′)
• 𝑭𝒆 = 0 and 𝑭𝑇𝒆′ = 0
• 𝑭 is singular (rank two)
• 𝑭 has seven degrees of freedom

0ˆˆ = xEx

−−== KEKFxFx

Estimating the fundamental matrix

The eight-point algorithm

Enforce rank-2 constraint
(take SVD of F and throw out
the smallest singular value)

vuvvvuvuvuuu

)1,,(,)1,,( vuvu
T == xx

Solve homogeneous
linear system using
eight or more matches

Problem with eight-point algorithm

vuvvvuvuvuuu

vuvvvuvuvuuu

Problem with eight-point algorithm

• Poor numerical conditioning

• Can be fixed by rescaling the data

Changjae Oh

Computer Vision

Semester 1, 22/23

Objectives

• To understand the computational approach to depth estimation
from stereo images

• To understand active method for depth estimation

Two-View Stereo

Many slides adapted from

Stereograms

• Humans can fuse pairs of images to get a sensation of depth

Stereograms: Invented by Sir Charles Wheatstone, 1838

Stereograms

Stereograms

• Humans can fuse pairs of images to get a sensation of depth

Autostereograms: www.magiceye.com

Home

Stereograms

• Humans can fuse pairs of images to get a sensation of depth

Autostereograms: www.magiceye.com

Home

Problem formulation

• Given a calibrated binocular stereo pair, fuse it to produce a depth image

image 1 image 2

Dense depth map

Computational Stereo Pipeline

Rectification

Stereo Matching

Triangulation

Left Image Right Image

Rectified Left Image Rectified Right Image

Disparity Map

Epipolar rectification – Why needed?

• 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 corresponding scanlines
̶ When does this happen?

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

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

• Then epipolar lines fall along the hori
zontal scan lines of the images

Essential matrix for parallel images

RtExEx ][,0

Epipolar constraint:

( ) ( ) TvvT

R = I t = (T, 0, 0)

The y-coordinates of corresponding points are the same!

Stereo image rectification

Stereo image rectification

• Reproject image planes
• onto a common plane parallel to the line between optical centers

C. Loop and Z. Zhang. Computing Rectifying Homographies for Stereo Vision. CVPR 1999

http://dev.ipol.im/~morel/Dossier_MVA_2011_Cours_Transparents_Documents/2011_Cours7_Document2_Loop-Zhang-CVPR1999.pdf

Stereo image rectification

1. Rotate the right camera by R
(aligns camera coordinate system orientation only)

2. Rotate (rectify) the left camera so that the epipole is at infinity

3. Rotate (rectify) the right camera so that the epipole is at infinity

4. Adjust the scale

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Stereo image rectification

1. Compute E to get R

2. Rotate right image by R

3. Rotate both images by Rrect

4. Scale both images by H

Rectification example

Another rectification example

Unrectified

Stereo Matching

• Finding the corresponding points in epipolar line

Rectification

Stereo Matching

Triangulation

Left Image Right Image

Rectified Left Image Rectified Right Image

Disparity Map

Basic stereo matching algorithm

• If necessary, rectify the two stereo images to transfo
rm epipolar lines into scanlines

• 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

Correspondence search

Matching cost

Left Right

• Slide a window along the right scanline and com
pare contents of that window with the reference
window in the left image

• Matching cost: SSD or normalized correlation

Correspondence search
Left Right

Correspondence search
Left Right

Norm. corr

Basic stereo matching algorithm

• If necessary, rectify the two stereo images to transform epipo
lar 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’

̶ Triangulate the matches to get depth information

Depth from disparity

• Performing triangulation

Rectification

Stereo Matching

Triangulation

Left Image Right Image

Rectified Left Image Rectified Right Image

Disparity Map

Depth from disparity

xxdisparity

Disparity is inversely proportional to depth!

Depth from disparity

xxdisparity

Basic stereo matching algorithm

• If necessary, rectify the two stereo images to transform epipo
lar 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) = B*f/(x–x’)

So the key point is..

Rectification

Stereo Matching

Triangulation

Left Image Right Image

Rectified Left Image Rectified Right Image

Disparity Map

Taxonomy of stereo matching

Local methods

Global methods

Computational

Window-based matching

Dynamic programming

Structured light

Time-of-Flight

Laser scan

Adaptive Weight

+ Deep learning based approaches

Graph cuts

Belief propagation

Cost Volume Filtering

A naïve stereo algorithm

• For each pixel x of the left image:

̶ Compare color of x against the color of each pixel on the same horizontal scanline
in the right image.

̶ Select the pixel of most similar color as matching point

Window-based matching

• Instead of matching single pixel,

̶ center a small window on a pixel and match the whole window in the right image.

Window-based matching

• In a formal way,

̶ the disparity 𝑑𝒙 of a pixel 𝒙 in the left image is computed as

• argmin returns the value at which the function takes a minimum

• 𝑑𝑚𝑎𝑥 is a parameter defining the maximum disparity (search range).

• 𝑊𝒙 is the set of all pixels inside the window centred on 𝒙

• 𝑐(𝒒, 𝒒 − 𝒅) is a function that computes the colour difference between a pixel 𝒒 of the left image and a
pixel 𝒒 − 𝒅 of the right image (e.g. Sum of absolute difference in RGB values)

𝑑𝒙 = argmin

𝑐(𝒒, 𝒒 − 𝒅)

Let’s split this equation into three steps!

A common pipeline for local methods

Matching cost
computation

aggregation

computation

𝑐(𝒒, 𝒒 − 𝒅) ෍

𝑐(𝒒, 𝒒 − 𝒅) 𝑑𝒙 = argmin

𝑐(𝒒, 𝒒 − 𝒅)

Effect of window size

̶ Smaller window
+ More detail

• More noise

W = 3 W = 21

̶ Larger window
+ Smoother disparity maps

• Less detail

Problem of Untextured Regions

̶ There has to be a certain amount of colour variation inside the window

Aperture Problem

̶ There needs to be a certain amount of texture with vertical orientation

Problem of Repetitive Patterns

̶ There needs to be a certain amount of repetitive texture

Effect of these problems

Foreground fattening problem

̶ Foreground objects are clearly enlarged when using large kernels (windows)

Foreground fattening problem: why?

All pixels in 𝑊𝒙 have the same influence
on the aggregated costs

Matching cost
computation

aggregation

computation

𝑐(𝒒, 𝒒 − 𝒅) ෍

𝑐(𝒒, 𝒒 − 𝒅) 𝑑𝒙 = argmin

𝑐(𝒒, 𝒒 − 𝒅)

Adaptive support weight

Matching cost
computation

aggregation

computation

𝑐(𝒒, 𝒒 − 𝒅) 𝑑𝒙 = argmin

𝑐(𝒒, 𝒒 − 𝒅)෍

𝑤(𝒙, 𝒒)𝑐(𝒒, 𝒒 − 𝒅)

1. Assumption: Two points are likely to lie on the same disparity if they are similar in color
2. Only pixels that lie on the same disparity contribute to the aggregated matching costs

-> No foreground fattening

[Yoon,CVPR05]

Adaptive support weight

Matching cost
computation

aggregation

computation

𝑐(𝒒, 𝒒 − 𝒅) 𝑑𝒙 = argmin

𝑐(𝒒, 𝒒 − 𝒅)෍

𝑤(𝒙, 𝒒)𝑐(𝒒, 𝒒 − 𝒅)

𝑤 𝒙, 𝒒 = 𝒆𝒙𝒑 −

∆𝑐𝒙𝒒: colour distance between x and q

∆𝑠𝒙𝒒: spatial distance between x and q

[Yoon,CVPR05]

Window-based Adaptive support-weight

[Yoon,CVPR05]

How can we improve window-based matching?

• The similarity constraint is local

̶ Each reference window is matched independently

• Need to enforce non-local correspondence constraints

Non-local constraints

• Uniqueness

̶ For any point in one image, there should be at most one matching point in the other i

Non-local constraints

• Uniqueness

̶ For any point in one image, there should be at most one matching point in the other i

• Ordering

̶ Corresponding points should be in the same order in both views

Ordering constraint doesn’t hold

Non-local constraints

• Uniqueness

̶ For any point in one image, there should be at most one matching point in the other i

• Ordering

̶ Corresponding points should be in the same order in both views

• Smoothness

̶ We expect disparity values to change slowly (for the most part)

Stereo datasets

• Middlebury stereo datasets

• Synthetic data

Active stereo with structured light

• Project “structured” light patterns onto the object

̶ Simplifies the correspondence problem

̶ Allows us to use only one camera

L. Zhang, B. Curless, and S. M. Seitz. Rapid Shape Acquisition Using Color Structured Light and Multi-pass Dynamic Programming. 3DPVT 2002

http://grail.cs.washington.edu/projects/moscan/

Active stereo with structured light

L. Zhang, B. Curless, and S. M. Seitz. Rapid Shape Acquisition Using Color Structured Light and Multi-pass Dynamic Programming. 3DPVT 2002

http://grail.cs.washington.edu/projects/moscan/

Active stereo with structured light

http://en.wikipedia.org/wiki/Structured-light_3D_scanner

http://en.wikipedia.org/wiki/Structured-light_3D_scanner

Kinect: Structured infrared light

Kinect in infrared

Kinect in infrared

Laser scanning

• 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

Digital Michelangelo Project

Levoy et al.
http://graphics.stanford.edu/projects/mich/

Source: S. Seitz

http://graphics.stanford.edu/projects/mich/

Laser scanned models

The Digital Michelangelo Project, Levoy et al. Source: S. Seitz

Laser scanned models

The Digital Michelangelo Project, Levoy et al.
Source: S. Seitz

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com