Description

In this programming assignment, we will implement key elements of structure from motion except for bundle adjustment. Structure from motion takes a set of images and compute camera poses and 3D point cloud, simultaneously. It has been widely used in computer vision, graphics, robotics, and even medical imaging. Photo tourism (http: //phototour.cs.washington.edu/) and motion capture from body-mounted cameras
(http://drp.disneyresearch.com/projects/mocap/) are successful applications of structure from motion.

(a) INPUT: Images

Side view Top view Oblique view
(b) OUTPUT: 3D reconstruction
Figure 1 illustrates a set of input images and 3D reconstruction of camera poses and scene points. Points in the ground plane and two facades are reconstructed, which forms orthogonal angles. Our task is to implement the key elements in the structure from motion: to estimate fundamental matrix and essential matrix, point triangulation, camera localization via PnP, and nonlinear refinement.
We provide camera intrinsic parameter, K, and 2D point correspondences between three images (noisy image correspondences are already filtered by RANSAC). We also provide visualization tools: 3D camera and point visualization and image reprojection visualization. These visualizations help to debug the each function.
2 Technical Details
The MATLAB script run sfm.m will be the main script to run this assignment. It loads data.mat that includes 2D correspondences, x1 ↔ x2 ↔ x3, camera intrinsic parameter, K, and three images, I1, I2, and I3. The correspondences are established by nearest neighbor search in SIFT local descriptors filtered by fundamental matrix based RANSAC. Based on the correspondences, we will reconstruct 3D point cloud, X ∈ Rn×3, where n is the number of the 3D points, and two relative camera poses, (R2,C2) and (R3,C3), with respect to the first camera, (R1 = I3,C1 = 03).
The script run sfm.m sequentially calls EstimateFundamentalMatrix, EssentialMatrixFromFundamentalMatrix, LinearTriangulation, LinearPnP, and NonlinearTriangulation.
2.1 Fundamental Matrix Estimation
Given N ≥ 8 correspondences between two images, x1 ↔ x2, implement the following function that linearly estimates a fundamental matrix, F, such that xT2 Fx1 = 0:
F = EstimateFundamentalMatrix(x1, x2)
(INPUT) x1 and x2: N×2 matrices whose row represents a correspondence.
(OUTPUT) F: 3×3 matrix with rank 2.
The fundamental matrix can be estimated by solving linear least squares (Ax = 0). Because of noise on correspondences, the estimated fundamental matrix can be rank 3. The last singular value of the estimated fundamental matrix must be set to zero to enforce the rank 2 constraint. NOTE: normalize the fundamental matrix such that ||F|| = 1.
2.2 Essential Matrix Estimation
Given the fundamental matrix computed by Section 2.1, estimate E = KTFK:
E = EssentialMatrixFromFundamentalMatrix(F, K)
(INPUT) K: 3×3 camera intrinsic parameter
(INPUT) F: fundamental matrix
(OUTPUT) E: 3×3 essential matrix with singular values (1,1,0).
reconstructing it with (1,1,0) singular values, i.e., E . NOTE:
normalize the essential matrix such that ||E|| = 1.
2.3 Linear Triangulation
We will provide the relative camera transform between image 1 (R1 = I3,C1 = 03) and image 2 (C2,R2). Given the relative transformation and point correspondences, x1 ↔ x2, triangulate 3D points using linear least squares:
X = LinearTriangulation(K, C2, R2, x1, x2)
(INPUT) C1 and R1: the first camera pose
(INPUT) C2 and R2: the second camera pose
(INPUT) x1 and x2: two N × 2 matrices whose row represents correspondence between the first and second images where N is the number of correspondences.
(OUTPUT) X: N × 3 matrix whose row represents 3D triangulated point.
2.4 Linear Camera Pose Estimation
We will register the image 3 into the reconstructed coordinate system using 2D-3D correspondences, x ↔ X. The camera pose estimation uses linear least squares to compute the camera projection matrix,[ ] P ∈ R3×4, and factors out camera intrinsic parameter: K−1P = R t where t is camera translation in the camera coordinate system, i.e., C = −RTt. R must be cleaned up such that it is orthogonal matrix with the determinant 1 and t must be rescaled:
R = UDVT (1)
Rc = UVT, tc = t/D1,1 if det(UVT) = 1
T) = −1 (2) t/D1,1 if det(UV
where D1,1 is the first singular value of the R. Rc and tc are the cleaned-up rotation and translation for the camera.
IMPORTANT NOTE: While theoretically you can use the x directly when solving for the P matrix then use the K matrix to correct the error, this is more numeically unstable, and thus it is better to calibrate the x values before the computation of P then extract R and t directly
[C R] = LinearPnP(X, x, K)
(INPUT) X and x: N×3 and N×2 matrices whose row represents correspondences between 3D and 2D points, respectively.
(INPUT) K: intrinsic parameter
(OUTPUT) C and R: camera pose (C,R).
2.5 Nonlinear Triangulation
Given three camera poses and linearly triangulated points, X, refine the locations of the 3D points that minimizes reprojection error:
X = NonlinearTriangulation(K, C2, R2, C3, R3, x1, x2, x3, X0)
(INPUT) C2 and R2: the second camera pose
(INPUT) C3 and R3: the third camera pose
(INPUT) x1, x2, and x3: N × 2 matrices whose row represents correspondence between the first, second, and third images where N is the number of correspondences.
(INPUT and OUTPUT) X: N × 3 matrix whose row represents 3D triangulated point.
We will minimize reprojection error:
minimize, (3)
X
where
KRi (X − Ci). (4)
Ci and Ri are the ith camera optical center and orientation. We can solve this nonlinear optimization by finding ∆X:
∆X =(JTJ)−1 JT (b − f(X))(5)
T b =x˜1 y˜1 x˜2 y˜2 x˜3 y˜3(6) []T
f(X) =u1/w1 v1/w1 u2/w2v2/w2 u3/w3 v3/w3 (7)
where J is the Jacobian for X:
T
J =(8)
(9)
(10)
(11)
(12)
where K and R .
You will iteratively update Xnew = Xold + ∆X to find the local minimum.
3 Visualizing Results
We provide two visualization tools: DisplayCorrespondence and Display3D. These functions display reprojection error onto an image and 3D camera and points, respectively.
4 Submitting
To submit your results, run the submission script, which will test your functions. This script will generate a mat file called RoboticsPerceptionWeek4Submission.mat. Upload this file onto the assignment page, and you should receive your score immediately.