Structure from Motion (SfM)

Structure from Motion (SfM) is a computer vision technique for reconstructing 3D structures from 2D image (sequential and non-sequential). This project demonstrates the end-to-end pipeline for SfM, including feature detection, camera pose estimation, triangulation, and 3D point cloud generation with code, mathematical representation and open source alternatives.

Reconstruction pipeline

The following steps are typically used in standard structure from motion.

1. Camera Model

It is a mathematical representation that describes how a 3D point in the world is projected onto a 2D image plane. Simple pinhole camera model is represented by the following mathematical formula:

• x: 2D point in the image (in homogeneous coordinates).
• K: Intrinsic camera matrix (focal length, principal point).
• R, t: Camera rotation and translation (extrinsic parameters).
• X: 3D point in the scene.
• s: Projective scale.

2. Feature Detection

Detect stable keypoints x_i and compute descriptors to match them across images. Common choices include Scale-Invariant Feature Transform (SIFT) and Oriented FAST and Rotated BRIEF (ORB).

3. Feature Matching

Once features are detected across several images taken from different viewpoints, the next step is to match them across images. This is where the descriptors come in, as they uniquely identify the features.

• Match descriptors x_i ↔ x_j between image pairs.
• Compare descriptors using a suitable distance metric. A k-d tree can accelerate nearest-neighbor searches for floating-point descriptors; binary descriptors such as ORB use Hamming distance.
• Filter out outliers using techniques like RANSAC.

4. Fundamental Matrix Estimation

The Fundamental Matrix F satisfies the epipolar constraint:

To estimate F:

1. Use the eight-point algorithm: Construct a linear system from matched points and solve A*f = 0.
2. Enforce the rank-2 constraint on F by applying Singular Value Decomposition (SVD).

5. Essential Matrix Estimation

The Essential Matrix E is derived from F and camera intrinsics K:

Decompose E into relative rotation R and translation t using SVD.

6. Triangulation

For each matched feature pair, compute the 3D point X by solving a system and applying SVD.

7. Bundle Adjustment

Refine camera parameters and 3D points by minimizing the reprojection error using non-linear least squares methods like the Levenberg-Marquardt algorithm.

8. Sparse Point Cloud

Combine triangulated points X into a sparse point cloud representing the scene.

9. Dense Reconstruction (Optional)

To densify the sparse point cloud, use Multi-View Stereo (MVS) to estimate depth for every pixel.