[06-30213][06-30241][06-25024]
Computer Vision and Imaging &
Robot Vision
Dr Hyung Jin Chang Dr Yixing Gao
h.j.chang@bham.ac.uk y.gao.8@bham.ac.uk
School of Computer Science
STRUCTURE FROM MOTION (SFM) A BRIEF OVERVIEW
The aim of SFM
• Givenseveralimagesofsamescene
• Reconstructthecamerapositionsandreconstruct
the 3D scene
• Assumeapartially-calibratedcase,inwhichthe
camera calibration matrices 𝑲 are known. Xiao, J. Multiview 3D Reconstruction for Dummies
SFM pipeline (calibrated cameras)
• Triangulationrequires:
• Knowingcorrespondences.
• Knowingprojectionmatrices 𝑷! !”#:% for all 𝑀 cameras.
• Computingprojectionmatrix𝑷! requires 𝑲! , 𝑹! , 𝒕! .
?
• Matrices 𝑹! , 𝒕! can be computed from essential matrix 𝑬! between first and 𝑗-th view.
• Matrix 𝑬! can be computed from fundamental matrix 𝑭! and calibration matrices 𝑲”and 𝑲!.
SFM pipeline
• Forsimplicity,considerapairofviewswithknown calibration matrices 𝑲𝟏, 𝑲𝟐
• Actually,ifthecameraismoving,thecalibration matrices are equal 𝑲 = 𝑲𝟏 = 𝑲𝟐
• Theapproachgeneralizestomultipleviews
𝐾”,𝐾%
?
Image from: Xiao, J. Multiview 3D Reconstruction for Dummies
Fundamental matrix estimation
Also known as weak calibration.
• Assume known correspondences 𝑥& &'”:), 𝑥*& &'”:)
• Estimate𝐹thatminimizesreprojectionerrorsÚ(F)
li =Fx’i
d (xi , Fx ‘i )
𝒙′& T d(xi ‘,F xi)
l ‘=FTx ii
𝒙&
Ú(F)=1åN (d2(x,Fx’)+d2(x’,FTx))
iiii
i=1
• Nonlinearoptimization(Levenberg-Marquardt),requiresgood
N
initial estimate.
• Usuallyinitializedby8-pointalgorithm(describednext).
Fundamental matrix estimation:
Coordinates of a pair of corresponding points:
Eight
x = (u, v, 1)T, x’= (u’, v’, 1)T
–
point algorithm
Epipolar constraint:
Homogeneous system!
Af = 0
Minimize:
åN T ¢2 (x Fx)
ii
i=1
||F||2 = 1
with constraint
F ¬ last eigenvector(A)
Slide credit: Svetlana Lazebnik
Normalized 8
1. Precondition: Center image points, and scale such that the standard deviation becomes 2 pixels.
• 𝒙+ = 𝑻 𝒙 , 𝒙+ ′ = 𝑻 ′ 𝒙 ′
2. Apply 8-point algorithm to calculate 𝑭% from the
preconditioned points.
3. Enforce rank=2 (e.g., decompose 𝑭%, by SVD set the smallest
eigenvalue to zero and reconstruct 𝑭%).
4. Transform the fundamental matrix back to original units:
Let T and T’ be the transformations used to precondition the points in each image separately. Then the fundamental matrix equals 𝐅 = 𝑻′&𝑭%𝑻.
–
point algorithm
Normalized 8
• Enforcingrank=2:
SVD éd ùév !vùT
–
point algorithm
T ê11 úê11 13ú
F=UDV =Uê d22 ê
éd11
F =U ê d
úê” # “ú
ë
ê 22 ú
dúêv !vú 33ûë 31 33û
ê 0ú ëû
ù úVT
Set d33=0 and reconstruct F
Fundamental matrix estimation
• In general, the correspondences are unknown
• Jointly find the fundamental matrix F AND the correspondences!
(pairs across two views (u’,v’) ↔ (u,v)).
• Approach
1. Find keypoints in each image
2. Calculate possible matches (potential matches)
3. Estimate the epipolar geometry
4. Improve estimate of matches and iterate
Example from Andrew Zisserman
Slide credit: Kristen Grauman
Fundamental matrix estimation
1. Findkey-points(eg.,Harriscorners)
Example from Andrew Zisserman
Slide credit: Kristen Grauman
Fundamental matrix estimation
2. Findcorrespondenceusingproximityconstraints
Example from Andrew Zisserman
Slide credit: Kristen Grauman
Fundamental matrix estimation
• Filter the correspondences by visual similarity
(e.g.,using normalized cross correlation or by a more advanced descriptor)
Example from Andrew Zisserman
Slide credit: Kristen Grauman
RANSAC to robustly estimate F
• Randomlyselectasetofcorrespondences • CalculateFusingthesecorrespondences
• Thisgivestheepipolarconstraint!
• EstimatehowmanycorrespondencessupportF:
• Applyestimatedfundamentalmatrixtoremaining potential correspondences.
• Numberofinliers:pointsthatliecloseenoughtotheir epipolar lines calculated from 𝑭.
• Choose𝑭withmaximalsupport(#inliers)
Slide credit: Kristen Grauman
Input correspondences
Example from Andrew Zisserman
Slide credit: Bastian Leibe
Pruned correspondences
• Correspondencesconsistentwiththeepipolarconstraint
Example from Andrew Zisserman
Slide credit: Bastian Leibe
Epipolar
constraint visualized
Example from Andrew Zisserman
Slide credit: Bastian Leibe
Summary
• RobustestimationofF Potential matches
RANSAC Epipolar. geom.
• Improvebyanonlinearoptimizationofthecostfunction w.r.t. 𝑭 using inliers only:
Ú(F)=1åN (d2(x,Fx’)+d2(x’,FTx))
N
i=1
iiii
SFM pipeline
• Multiple-viewSFM
Nice video (without last part – dense reconstruction)
• 8-pointalgorithminitializesanonlinearoptimization of reprojection errors (bundle adjustment):
minåå(xij -Ki[Ri |ti]Xij)2 ij
• ForanexcellentoverviewofSFMsee:
Xiao, J. Multiview 3D Reconstruction for Dummies
Try SFM at home
• Bundler:StructurefromMotion(SfM)forUnorderedImageCollections PhotoTurism video on YouTube
Shape from X
• Shape from stereo
• Shape from photometric stereo
• Shape from motion
• Shape from shading
• Shape from focus
• Shape from texture
• Shape from contour
• Structured light
Shape from X
• Shapefromtexture
• Shapefromfocus
References
• David A. Forsyth, Jean Ponce, Computer Vision: A Modern Approach (2nd Edition),
• Stereo: Chapter 7
• Structure from motion: Section 8.1
• R. Hartley, A. Zisserman, Multiple View Geometry in Computer Vision, 2nd Edition, Cambridge University Press, 2004
• Camera model and calibration (Chapters 6 in 7)
• Epipolar geometry (Chapter 9)
• Calculating F (Chapters 11.1-11.6)
• Xiao, J. Multiview 3D Reconstruction for Dummies
• Patent Primesense (Kinect): http://patentscope.wipo.int/search/en/WO2007043036
Thank you
Hyung Jin Chang
14/03/2021