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
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
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
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