Lesson 29: Structure from Motion¶

This lesson assembles feature matching (Lesson 20), robust estimation (Lesson 23), calibration (Lesson 27), and the essential matrix and pose recovery (Lesson 28) into a complete pipeline that takes 2D image correspondences from two views and recovers both the cameras' relative motion and the 3D positions of the points that were being viewed — Structure from Motion. The one ingredient we haven't yet developed in detail is triangulation: turning a matched 2D point pair, plus known camera poses, into a 3D point. (Lesson 22 showed how to convert disparity to depth in the case of rectified images; this lesson generalizes the idea.)

The classic pipeline, at a glance¶

1. Match features between two images (Lesson 20: SIFT + ratio test).
2. Estimate the essential matrix $E$ from those correspondences, robustly (Lesson 23: RANSAC), using known intrinsics $K$ (Lesson 27: calibration).
3. Recover relative pose $(R, t)$ from $E$ (Lesson 28: cv2.recoverPose) — up to an unknown scale on $t$.
4. Triangulate: for every matched pair, intersect the two corresponding rays in 3D to recover a 3D point — developed in detail for the first time in this lesson.

We use two realistic synthetic photos of a bronze sculpture from the BlendedMVS dataset (Yao et al., 2020). Unlike a photo pair we'd shoot ourselves, these images come with ground truth camera poses, calibration, and geometry for checking the entire pipeline.

Two real photos, with known camera poses¶

As just mentioned, every image ships with a ground-truth $(K, R, t)$. We treat the first photo's camera as the world origin and express the second camera's pose relative to it — giving us P1 and P2_true, the two ground-truth projection matrices this whole lesson tries to recover from image correspondences alone.

Image source: BlendedMVS (CC BY 4.0)

Step 1: feature matching¶

SIFT + ratio test (Lesson 20), run directly on the two photos.

Step 2: robust essential matrix and pose recovery¶

Feed the matched points through the same robust pipeline built in Lessons 23 and 27 to recover the essential matrix and the cameras' relative pose.

As in Lesson 28, recoverPose returns a unit-length translation direction — the actual baseline distance between the cameras is fundamentally unrecoverable from image correspondences alone. We'll come back to that.

Step 3: triangulation¶

Given two camera projection matrices $P_1, P_2$ (each $3\times4$, mapping a 3D point to a 2D image point in homogeneous coordinates) and a matched pixel pair $(x_1, x_2)$, we want the 3D point $X$ satisfying both $x_1 \propto P_1 X$ and $x_2 \propto P_2 X$. Each view contributes 2 independent linear equations in $X$'s 4 homogeneous unknowns (cross-multiplying out the unknown scale factor), by the same DLT/SVD recipe used for homographies (Lesson 24) and the fundamental matrix (Lesson 28):

$$A = \begin{bmatrix} u_1 P_1^{(3)} - P_1^{(1)} \\ v_1 P_1^{(3)} - P_1^{(2)} \\ u_2 P_2^{(3)} - P_2^{(1)} \\ v_2 P_2^{(3)} - P_2^{(2)} \end{bmatrix}, \qquad AX = 0$$

where $P^{(i)}$ denotes row $i$ of $P$. The null space of $A$ (the right singular vector associated with the smallest singular value) gives $X$.

Cheirality: a free sanity check¶

Decomposing $E$ into $(R, t)$ back in Step 2 actually yields four mathematically valid sign combinations; only one places the observed points in front of both cameras, and cv2.recoverPose uses exactly that fact — the cheirality constraint — to pick the right one internally, by triangulating a few points and checking their depth. The check above applies the same idea explicitly: the epipolar constraint alone doesn't rule out a correspondence that triangulates behind a camera, so a mismatched point can still pass RANSAC's inlier test. Requiring positive depth in both views is a free extra filter on top of that — it's what dropped the one inlier flagged above.

Putting it together: reconstruction using estimated pose¶

Now the real test: triangulate using the camera matrix built from recoverPose's estimated $(R, t)$, not the dataset's true pose. Because $t$ was only recovered up to scale, so is the reconstruction — every 3D point comes out a fixed factor smaller than reality. Multiplying by the true baseline length (a bit of cheating, just for evaluation) should recover the correct metric scene.

With real (imperfect) correspondences, the entire pipeline — essential matrix, pose, triangulation — reconstructs the scene to within a small fraction of the camera baseline, using nothing but 2D pixel correspondences and known intrinsics, plus one external number (the true baseline) to fix the scale ambiguity. In practice, that scale reference might come from a known object size in the scene, a second sensor (GPS, IMU, LiDAR), or a calibrated stereo rig (Lesson 22) instead of two arbitrary independent cameras.

Visualizing the reconstruction¶

For a denser, more recognizable point cloud than the strict RANSAC-inlier set used for the numeric check above, we loosen the feature-matching thresholds (SIFT_create(contrastThreshold=0.01), ratio 0.85) to pull in more — slightly noisier — correspondences, then color each 3D point with its actual pixel color from view 1.

From sparse to dense¶

Even with the loosened thresholds above, feature matching only yields a sparse cloud — one 3D point per distinctive image keypoint. As shown above, the sparse cloud is often not very satisfying. But with the camera poses now known, we're no longer limited to distinctive keypoints: multi-view stereo (MVS) estimates a depth for every pixel in every view, by sweeping a plane-hypothesis or patch through space (a generalization of Lesson 22's stereo matching from a rectified pair to arbitrarily-posed calibrated cameras). Those per-view depth maps are then fused — inconsistent estimates filtered out, the rest merged — into the dense colored point cloud (or mesh) that toolkits like COLMAP (Schönberger & Frahm, 2016) produce.

From two views to many: incremental SfM and bundle adjustment¶

Real reconstructions rarely stop at two views. The standard recipe sequentially incorporates new images in 3 steps: 1) match features between the new image and one or more existing images; 2) compute the new camera pose relative to the existing 3D point cloud; and 3) update the 3D point cloud with the new matches by triangulation. Step 2 requires solving Perspective-n-Point (i.e., given 2D-3D correspondences and $K$, recover that camera's pose via cv2.solvePnP).

As views are accumulated, errors compound — pose corrupts the triangulated points, which then corrupt the next recovered pose, and so on. Bundle adjustment fixes this by refining all camera poses and 3D points together in one large nonlinear least-squares optimization that minimizes the total reprojection error summed across every point in every view at once. Bundle adjustment is arguably the single most important step separating a simple two-view pipeline like the one in this lesson from a real SfM system (COLMAP, etc.).

Exercises¶

1. Add extra synthetic pixel noise (e.g. rng.normal(0, 1.0, x1_in.shape)) on top of the already-real detections in x1_in/x2_in before triangulating. How much does the reconstruction error grow, and does it grow uniformly, or worse for points farther from the cameras (Lesson 22's disparity-depth relationship: distant points produce smaller, noisier parallax)?
2. Look up cv2.solvePnP's signature and sketch (in words) how you'd extend this notebook to a third view: which 3D points from the view1/view2 reconstruction would you match into the new image, and how would solvePnP's inputs and outputs map onto the pieces we already have (K, matched 2D points, and the existing 3D point cloud)?
3. This pair (views 0 and 2) has a deliberately generous baseline for reliable matching. Swap in views 0 and 1 instead (a much shorter baseline — you'll need their .npz camera parameters from the same BlendedMVS scene). How does the shorter baseline affect the number of RANSAC inliers, and the accuracy of the recovered pose and reconstruction, compared to the wider-baseline pair used above?