CS代写 EBU7240 Computer Vision

EBU7240 Computer Vision
Changjae Oh
Semester 1, 2021

Objectives
• To understand epipolar geometry for stereo vision
• To understand epipolar constraint in calibrated/uncalibrated case

view geometry

Epipolar geometry
• Baseline – line connecting the two camera centers
• 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
• Epipolar Lines – intersections of epipolar plane with image
planes (always come in corresponding pairs)

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

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.

• An important concept for stereo vision
constraint
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)
Credit: K. Kitani

• An important concept for stereo vision
constraint
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

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
=[I 0]X, x =K−1x =[R t]X norm pixel
rse of the calibration matrices to get normalized image coordinates:

constraint: Calibrated case
x X =(x,1)T x I 01 R t1  
The vectors Rx, t, and x’ are coplanar

constraint: Calibrated case
x[t(Rx)]=0 Recall:
x¢ [t ]Rx=0
0−az aybx ab= a 0 −a b =[a ]b
zxy −a a 0b
The vectors Rx, t, and x’ are coplanar

constraint: Calibrated case
x[t(Rx)]=0
x¢ [t ]Rx=0 x¢ Ex=0
The vectors Rx, t, and x’ are coplanar
Essential Matrix
(Longuet-Higgins, 1981)

constraint: Calibrated case
𝑬𝒙 is the epipolar line associated with 𝒙 (𝒍′ = 𝑬𝒙 ) ̶ Recall: a line is given by ax + by + c = 0 or
lTx=0 where l=b, x=y
c 1  

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

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:
ˆˆ ˆ−1 ˆ−1 xTEx=0 x=K x, x=K x

constraint: Uncalibrated case
x = K −1 x
ˆ −1  x=Kx
xT F x = 0 with
F = K −T E K −1
Fundamental Matrix
(Faugeras and Luong, 1992)

constraint: Uncalibrated case
ˆ T ˆ xT F x = 0 with F = K −T E K −1 x Ex=0
• 𝑭𝒙 is the epipolar line associated with 𝒙(𝒍′ = 𝑭𝒙)
• 𝑭𝑇𝒙′ is the epipolar line associated with 𝒙′(𝒍 = 𝑭𝑇𝒙′)
• 𝑭𝒆=0and𝑭𝑇𝒆′=0
• 𝑭 is singular (rank two)
• 𝑭 has seven degrees of freedom

Estimating the fundamental matrix

point algorithm
x=(u,v,1)T, x=(u,v,1)  f11 f12 f13  u
f11  f12 
 f13  21
uu uv u vu vv v u v 1f22=0
Solve homogeneous linear system using eight or more matches
u v 1f21 f22
f23v=0 f 1
f   23
 f31   f32  f33
Enforce rank-2 constraint (take SVD of F and throw out the smallest singular value)

Problem with eight
point algorithm
uu uv u vu vv v u v
 f13   21
 f11   f12 
f22 f23

Problem with eight
point algorithm
 f11   f12 
uu uv u vu vv v u v
 f13   21
 32 • Can be fixed by rescaling the data
• Poor numerical conditioning
f22 f23
 f31  f

EBU7240 Computer Vision
Semester 1, 2021
Changjae Oh

Objectives
• To understand the computational approach to depth estimation from stereo images
• To understand active method for depth estimation

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

Problem formulation
• Given a calibrated binocular stereo pair, fuse it to produce a depth image
Dense depth map

Computational Stereo Pipeline
Left Image Right Image
Epipolar Rectification
Rectified Left Image Rectified Right Image
Disparity Map
Stereo Matching
Triangulation

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
Epipolar constraint:
xTEx=0, E=[t]R
R = I t = (T, 0, 0)
E=[t]R=0 0 −T
0 0 0u 0  
(u v 1)0 0 −T v =0 (u v 1)−T =0    
Tv=Tv The y-coordinates of corresponding points are the same!
0T 01 Tv  

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

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

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
Left Image Right Image
Epipolar Rectification
Rectified Left Image Rectified Right Image
Disparity Map
Stereo Matching
Triangulation

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
• 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
Left Image
Right Image
Epipolar Rectification
Rectified Left Image
Disparity Map
Rectified Right Image
Stereo Matching
Triangulation

Depth from disparity
x = B1 -x¢ = B2 fzfz
z x-x¢ B+B x x’ =12
f B1 B2 f f z O Baseline O’
disparity = x − x = B  f z
Disparity is inversely proportional to depth!

Depth from disparity
x = B1 x¢ = B2
fz fz z x-x¢ B-B
xx’ =12 fBf fz
disparity = x − x = B  f z

So the key point is..
Left Image
Right Image
Epipolar Rectification
Rectified Left Image Rectified Right Image
Disparity Map
Stereo Matching
Triangulation

Taxonomy of stereo matching
Computational stereo
Local methods
Window-based matching Adaptive Weight
Cost Volume Filtering Dynamic programming Graph cuts
Belief propagation
Active stereo
Global methods
Laser scan Structured light Time-of-Flight
+ Deep learning based approaches

A naï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

• Instead of matching single pixel,
̶ center a small window on a pixel and match the whole window in the right image.
based matching

• In a formal way,
based matching
the disparity 𝑑𝒙 of a pixel 𝒙 in the left image is computed as
Where Let’s split this equation into three steps! 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 𝒙
𝑑𝒙 = argmin ෍ 𝑐(𝒒,𝒒−𝒅)
0≤𝑑≤𝑑𝑚𝑎𝑥 𝒒∈𝑊 𝒙
𝑐(𝒒, 𝒒 − 𝒅) 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)

A common pipeline for local methods
Matching cost computation
෍ 𝑐(𝒒,𝒒−𝒅) 𝑑𝒙 = argmin ෍ 𝑐(𝒒,𝒒−𝒅)
𝒒∈𝑊 0≤𝑑≤𝑑𝑚𝑎𝑥 𝒒∈𝑊 𝒙𝒙
Cost aggregation
Disparity computation

Effect of window size
W = 3 Smaller window
+ More detail • More noise
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?
Matching cost computation
𝑑𝒙 = argmin ෍ 𝑐(𝒒,𝒒−𝒅)
0≤𝑑≤𝑑𝑚𝑎𝑥 𝒒∈𝑊 𝒙
All pixels in 𝑊 have the same influence 𝒙
on the aggregated costs
Cost aggregation
Disparity computation
෍ 𝑐(𝒒,𝒒−𝒅)

Adaptive support weight
Matching cost computation
Cost aggregation
Disparity computation
෍ 𝑤(𝒙,𝒒)𝑐(𝒒,𝒒−𝒅) 𝒒∈𝑊
𝑑𝒙 = argmin ෍ 𝑐(𝒒,𝒒−𝒅)
0≤𝑑≤𝑑𝑚𝑎𝑥 𝒒∈𝑊 𝒙
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
Cost aggregation
Disparity computation
෍ 𝑤(𝒙,𝒒)𝑐(𝒒,𝒒−𝒅) 𝒒∈𝑊
𝑑𝒙 = argmin ෍ 𝑐(𝒒,𝒒−𝒅)
0≤𝑑≤𝑑𝑚𝑎𝑥 𝒒∈𝑊 𝒙
∆𝑐𝒙𝒒: 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
• The similarity constraint is local
̶ Each reference window is matched independently
• Need to enforce non-local correspondence constraints
based matching?

• Uniqueness
̶ For any point in one image, there should be at most one matching point in the other i mage
local constraints

• Uniqueness
̶ For any point in one image, there should be at most one matching point in the other i mage
• Ordering
̶ Corresponding points should be in the same order in both views
local constraints
Ordering constraint doesn’t hold

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

Stereo datasets
• Middlebury stereo datasets • KITTI
• 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

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

Active stereo with structured light
http://en.wikipedia.org/wiki/Structured-light_3D_scanner

: Structured infrared light
Kinect in infrared

Laser scanning
Digital Michelangelo Project Levoy et al.
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
Source: S. Seitz

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

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

Related Posts