4/13/2021
CSE 473/573
Introduction to Computer Vision and Image Processing
‘-
STEREO VISION II
‘-
1
4/13/2021
World point
image point (left)
Focal length
optical center (left)
Depth of p
‘- (right)
optical center (right)
image point
baseline
Geometry for a simple stereo system • Assume parallel optical axes, known camera parameters
(i.e., calibrated cameras). What is expression for Z? Similar triangles (pl, P, pr) and (Ol, P, Or):
Txx T lr
Zf Z
Zff T
xl – xr
disparity
‘-
2
4/13/2021
Another Way of looking at Depth
‘-
4/13/2021
5
Depth from disparity
image I(x,y) Disparity map D(x,y)
‘-
image I ́(x ́,y ́)
(x ́,y ́)=(x+D(x,y), y)
So if we could find the corresponding points in two images, we could estimate relative depth…
3
General case, with calibrated cameras • The two cameras need not have parallel optical axes.
‘-
4/13/2021
Vs.
Grauman
Stereo correspondence constraints
‘-
• Given p in left image, where can corresponding point p’ be?
4
4/13/2021
Stereo correspondence constraints
‘-
• Given p in left image, where can corresponding point p’ be?
Stereo correspondence constraints
‘-
5
4/13/2021
Stereo correspondence constraints
•Geometry of two views allows us to constrain where the corresponding pixel for some image point in the first view must occur in the second view.
epipolar line
epipolar plane
epipolar line
‘-
Epipolar constraint: Why is this useful?
• Reduces correspondence problem to 1D search along conjugate epipolar lines
Adapted from Steve Seitz
Epipolar geometry
‘-
• Epipolar Plane • Baseline
• Epipoles • Epipolar Lines Adapted from M. Pollefeys, UNC
6
4/13/2021
Epipolar geometry: terms
• Baseline: line joining the camera centers
• Epipole: point of intersection of baseline with the image plane
• Epipolar plane: plane containing baseline and world point ‘-
• Epipolar line: intersection of epipolar plane with the image plane
• All epipolar lines intersect at the epipole
• An epipolar plane intersects the left and right image planes in epipolar lines
Grauman
Epipolar constraint
‘-
• Potential matches for p have to lie on the corresponding epipolar line l’.
• Potential matches for p’ have to lie on the corresponding epipolar line l.
http://www.ai.sri.com/~luong/research/Meta3DViewer/EpipolarGeo.html
Source: M. Pollefeys
7
4/13/2021
Questions?
• If you have questions, try to get them answered before
we proceed!
‘-
4/13/2021
15
Fundamental matrix
• Let p be a point in left image, p’ in right image
l
p
• Epipolar relation
• p maps to epipolar line l’ • p’ maps to epipolar line l
l’
‘- p’
• Epipolar mapping described by a 3×3 matrix F
8
4/13/2021
Fundamental matrix
• This matrix F is called • the “Essential Matrix”
• when image intrinsic parameters are known • the “Fundamental Matrix”
• more generally (uncalibrated case)
• Can solve for F from point correspondences
• Each (p, p’) pair gives one linear equation in entries of F
• F has 9 entries, but really only 7 or 8 degrees of freedom.
• With 8 points it is simple to solve for F, but it is also possible with 7. See Marc Pollefey’s notes for a nice tutorial
‘-
Estimating the Fundamental Matrix • 8-point algorithm
• Least squares solution using SVD on equations from 8 pairs of correspondences
• Enforce det(F)=0 constraint using SVD on F • 7-point algorithm
• Use least squares to solve for null space (two vectors) using SVD and 7 pairs of correspondences
• Solve for linear combination of null space vectors that satisfies det(F)=0
• Minimize reprojection error • Non-linear least squares
Note: estimation of F (or E) is degenerate for a planar scene.
‘-
9
4/13/2021
Palace of Gaudì Astorga, Spain
‘-
4/13/2021
19
VLFeat’s 800 most confident matches among 10,000+ local features.
‘-
10
4/13/2021
Epipolar lines
‘-
Keep only the matches at are “inliers” with respect to the “best” fundamental matrix
‘-
11
4/13/2021
CAMERA CALIBRATION
‘-
Calibrating the Camera
Use an scene with known geometry
• Correspond image points to 3D points
• Get least squares solution (or non-linear solution)
Known 3D locations
Known 2D image coords
‘-
sv m21 m22 m23 m24 Z
sm m m m
31 32 33 341
summmmX 11 12 13 14Y
Unknown Camera Parameters
12
4/13/2021
How do we calibrate a camera?
Known 2D image coords
880 214 43 203 270 197 886 347 745 302 943 128 476 590 419 214 317 335 783 521 235 427 665 429 655 362 427 333 412 415 746 351 434 415 525 234 716 308 602 187
Known 3D
locations
312.747 309.140 30.086
305.796 311.649 30.356
307.694 312.358 30.418
310.149 307.186 29.298
311.937 310.105 29.216
‘-
311.202 307.572 30.682 307.106 306.876 28.660 309.317 312.490 30.230 307.435 310.151 29.318 308.253 306.300 28.881 306.650 309.301 28.905 308.069 306.831 29.189 309.671 308.834 29.029 308.255 309.955 29.267 307.546 308.613 28.963 311.036 309.206 28.913 307.518 308.175 29.069 309.950 311.262 29.990 312.160 310.772 29.080 311.988 312.709 30.514
Estimate of camera center
1.0486 -0.3645 -1.6851 -0.4004 -0.9437 -0.4200 1.0682 0.0699 0.6077 -0.0771 1.2543 -0.6454 -0.2709 0.8635 -0.4571 -0.3645 -0.7902 0.0307 0.7318 0.6382 -1.0580 0.3312 0.3464 0.3377 0.3137 0.1189 -0.4310 0.0242 -0.4799 0.2920 0.6109 0.0830 -0.4081 0.2920 -0.1109 -0.2992 0.5129 -0.0575 0.1406 -0.4527
1.5706 -0.1490 0.2598 ‘- -1.5282 0.9695 0.3802
-0.6821 1.2856 0.4078
0.4124 -1.0201 -0.0915 1.2095 0.2812 -0.1280 0.8819 -0.8481 0.5255 -0.9442 -1.1583 -0.3759 0.0415 1.3445 0.3240 -0.7975 0.3017 -0.0826 -0.4329 -1.4151 -0.2774 -1.1475 -0.0772 -0.2667 -0.5149 -1.1784 -0.1401 0.1993 -0.2854 -0.2114 -0.4320 0.2143 -0.1053 -0.7481 -0.3840 -0.2408 0.8078 -0.1196 -0.2631 -0.7605 -0.5792 -0.1936 0.3237 0.7970 0.2170 1.3089 0.5786 -0.1887 1.2323 1.4421 0.4506
13
4/13/2021
Unknown Camera Parameters
Known 2d image coords
su m 11
m m
m XKnown 3d 14Ylocations
12 13
sv m21
sm m m m
m22 m23
31 32 sumXmYmZm
m24 Z 33 341
11 12 13 ‘-14 sv m21X m22Y m23Z m24
s m31 X m32Y m33Z m34 u m11 X m12Y m13Z m14
m31X m32Y m33Z m34
v m21X m22Y m23Z m24 m31X m32Y m33Z m34
Unknown Camera Parameters
sum m m mX
Known2d 11 12 13 14YKnown3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
31 32 33 341
u m11 X m12Y m13Z m14 ‘-
m31X m32Y m33Z m34 v m21X m22Y m23Z m24
m31X m32Y m33Z m34
(m31 X m32Y m33Z m34 )u m11 X m12Y m13Z m14
(m31 X m32Y m33Z m34 )v m21 X m22Y m23Z m24
m31uX m32uY m33uZ m34u m11 X m12Y m13Z m14 m31vX m32vY m33vZ m34v m21 X m22Y m23Z m24
14
4/13/2021
Unknown Camera Parameters
sum m m mX
Known2d 11 12 13 14YKnown3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
31 32 33 341
m31vX m32vY m33vZ m34v m21 X m22Y m23Z m24
m31uX m32uY m33uZ m34u m11 X m12Y m13Z m14 ‘-
0m11Xm12Ym13Zm14 m31uXm32uYm33uZm34u 0m21Xm22Ym23Zm24 m31vXm32vYm33vZm34v
Unknown Camera Parameters
sum m m mX
Known2d 11 12 13 14Y Known3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
31 32 33 341
0m11Xm12Ym13Zm14 m31uXm32uYm33uZm34u
0m21Xm22Ym23Zm24 m31vXm32vYm33vZm34v
• Method 1 – homogeneous linear system. Solve for m’s entries using linear least squares
‘-
m11 m12 m13
[U, S, V] = svd(A); M = V(:,end); M=reshape(M,[],3)’;
For python, see numpy.linalg.svd
X1 Y1 Z1 1 0 0 0 0 u1X1 u1Y1 u1Z1 u1 14
0 0 0 0 X Y Z 1 vX vY vZ vm21 0
0
111 11 11 11 1m22
m23 Xn Yn Zn 1 0 0 0 0 unXn unYn unZn unm 0
0000XYZ1vXvYvZv240 nnn nnnnnnnm31
m32 m33
m 34
15
4/13/2021
Unknown Camera Parameters
sum m m mX Known 2d 11 12 13 14 Y
Known 3d locations
image coords sv m21 m22 m23 m24 Z
sm m m m
31 32
• Method 2 – nonhomogeneous linear system. Solve for m’s entries using linear least squares
m22
Xn Yn Zn 1 0 0 0 0 unXn unYn unZnm23 un
0 0 0 0 X Y Z 1 vX vY vZm v n n n nn nn nn24n
34 1
‘-
Ax=b form
X1 Y1 Z1 1 0 0 0 0 u1X1 u1Y1 u1Z1m14
M = A\Y;
M = [M;1];
M = reshape(M,[],3)’;
For python, see numpy.linalg.solve
u1 0 0 0 0 X Y Z 1 vX vY vZm v
m11 m12 m13
33
111 111111211
m31 m32
m 33
Calibration with linear method
• Advantages
• Easy to formulate and solve
• Provides initialization for non-linear methods
• Disadvantages
• Doesn’t directly give you camera parameters
• Doesn’t model radial distortion
• Can’t impose constraints, such as known focal length
• Non-linear methods are preferred
• Define error as difference between projected points and measured points
• Minimize error using Newton’s method or other non-linear optimization
‘-
16
4/13/2021
Recovering the camera center
xKR tX x u s ur r r t
This is not the camera center -C. It is –RC (because a point will berotatedbeforetx,ty, and t are added)
011 12 13 xy wv0 v r r r t
0 21 22 23 yz
z
This is t * K
1 0 0 1r r r t
su
s
31
32
33 z1
‘-
* * *
* * *
* * *
*
*
*
sv
X Y
So K-1 m4 is t So we need
-R-1 K-1 m4 to get C
Q is K * R. So we just need -Q-1 m4
Q
1
Z
STEREO MATCHING
‘-
34
17
4/13/2021
Correspondence problem
‘-
Multiple match hypotheses satisfy epipolar constraint, but which is correct?
Figure from Gee & Cipolla 1999
Correspondence problem
• Beyond the hard constraint of epipolar geometry, there are “soft” constraints to help identify corresponding points
• Similarity
• Uniqueness ‘- • Ordering
• Disparity gradient
• To find matches in the image pair, we will assume • Most scene points visible from both views
• Image regions for the matches are similar in appearance
18
4/13/2021
Dense correspondence search
‘-
• compare with every pixel / window on same epipolar line in right image
• pick position with minimum match cost (e.g., SSD, normalized correlation)
For each epipolar line
For each pixel / window in the left image
Adapted from Li Zhang
Correspondence search with similarity constraint
Left
Right
scanline
Matching cost
‘-
• Slide a window along the right scanline and compare contents of that window with the reference window in the left image
• Matching cost: SSD or normalized correlation
disparity
19
4/13/2021
Left
Right
scanline
‘-
SSD
Left
Right
scanline
‘-
Norm. corr
20
4/13/2021
‘-
Intensity profiles
Source: Andrew Zisserman
‘-
Neighborhoods of corresponding points are similar in intensity patterns.
Source: Andrew Zisserman
21
4/13/2021
Correlation-based window matching
‘-
‘-
22
4/13/2021
‘-
Correlation-based window matching
‘-
23
4/13/2021
Correlation-based window matching
‘-
???
Textureless regions are non‐distinct; high ambiguity for matches.
Effect of window size
‘-
Source: Andrew Zisserman
24
4/13/2021
Effect of window size
Want window large enough to have sufficient intensity variation, yet small enough to contain only pixels with about the same disparity.
Figures from Li Zhang
‘-
W = 3
W = 20
Correspondence problem
• Beyond the hard constraint of epipolar geometry, there are “soft” constraints to help identify corresponding points
• Similarity
• Disparity gradient – depth doesn’t change too quickly.
‘-
• Uniqueness • Ordering
25
4/13/2021
Uniqueness constraint
• Up to one match in right image for every point in left
image
‘-
Figure from Gee & Cipolla 1999
Problem: Occlusion
• Uniqueness says “up to match” per pixel
• When is there no match?
‘-
Occluded pixels
26
4/13/2021
Disparity gradient constraint
• Assume piecewise continuous surface, so want disparity
estimates to be locally smooth
‘-
Figure from Gee & Cipolla 1999
Ordering constraint
• Points on same surface (opaque object) will be in same
order in both views
‘-
Figure from Gee & Cipolla 1999
27
4/13/2021
Ordering constraint
• Won’t always hold, e.g. consider transparent object, or an occluding surface
‘-
Figures from Forsyth & Ponce
Next Time
• Finish Stereo Matching • Motion and Optical Flow
‘-
28