CS计算机代考程序代写 python algorithm 4/13/2021

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):
Txx T lr
Zf Z
Zff 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 
sm m m m
   31 32 33 341
summmmX    11 12 13 14Y

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  XKnown 3d 14Ylocations
12 13
sv  m21
sm m m m
m22 m23
   31 32 sumXmYmZm 
m24  Z  33 341
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
sum m m mX
Known2d    11 12 13 14YKnown3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
   31 32 33 341
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
sum m m mX
Known2d    11 12 13 14YKnown3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
   31 32 33 341
m31vX  m32vY  m33vZ  m34v  m21 X  m22Y  m23Z  m24

m31uX  m32uY  m33uZ  m34u  m11 X  m12Y  m13Z  m14 ‘-
0m11Xm12Ym13Zm14 m31uXm32uYm33uZm34u 0m21Xm22Ym23Zm24 m31vXm32vYm33vZm34v
Unknown Camera Parameters
sum m m mX
Known2d    11 12 13 14Y Known3d
imagecoords svm21 m22 m23 m24Z locations
sm m m m
   31 32 33 341
 0m11Xm12Ym13Zm14 m31uXm32uYm33uZm34u
0m21Xm22Ym23Zm24 m31vXm32vYm33vZm34v
• 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 vm21 0
0
 111 11 11 11 1m22
  m23 Xn Yn Zn 1 0 0 0 0 unXn unYn unZn unm  0
0000XYZ1vXvYvZv240  nnn nnnnnnnm31
m32 m33
m   34
15

4/13/2021
Unknown Camera Parameters
sum m m mX Known 2d 11 12 13 14  Y 
Known 3d locations
image coords sv  m21 m22 m23 m24   Z 
sm 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 unZnm23 un
0 0 0 0 X Y Z 1 vX vY vZm v  n n n nn nn nn24n
34   1  
‘-
Ax=b form
X1 Y1 Z1 1 0 0 0 0 u1X1 u1Y1 u1Z1m14
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 vZm v
m11 m12 m13
33
111 111111211
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
xKR tX x u  s ur r r t
This is not the camera center -C. It is –RC (because a point will berotatedbeforetx,ty, and t are added)
   011 12 13 xy wv0  v r r r t 
0 21 22 23 yz
z
This is t * K
1 0 0 1r r r t
  su
s 
31
32
33 z1 
‘-
* * *
* * *
* * * 
*
*
* 
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