CS计算机代考程序代写 Excel algorithm [06-30213][06-30241][06-25024]

[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