3D Reconstruction

Structure from motion recovers the 3-D structure of a scene from several photographs taken at slightly different viewpoints. The input is only 2-D pixel correspondences across images; the geometry recovers both where the cameras were and where the world points sit.

Two views of the same point are not independent, and epipolar geometry is what constrains the matches. If a world point projects to $x$ in one image and $x^{\prime }$ in the other (homogeneous pixel coordinates), the pair obeys the epipolar constraint

where $F$ is the $3\times 3$ fundamental matrix of rank 2. $F$ collapses the correspondence search to a line: for each $x$, its match lies on the epipolar line $Fx$ in the other image. Eight or more correspondences fix $F$ up to scale — the eight-point algorithm, a linear least-squares solve for the smallest singular vector of the constraint matrix. With known intrinsics $K$, the essential matrix $E=K^{\prime \top }FK$ factors into a relative rotation $R$ and translation $t$ by SVD.

Once the two camera matrices $P,P^{\prime }$ are known, each matched pair $(x,x^{\prime })$ back-projects to two rays whose intersection is the world point $X$. Triangulation under measurement noise means the rays rarely meet exactly; the direct linear transform stacks the constraints $x\times PX=0$ and $x^{\prime }\times P^{\prime }X=0$ and takes the least-squares $X$ as the smallest singular vector.

Pose estimation and triangulation each accumulate error, and bundle adjustment corrects both at once, minimizing the total reprojection error over all cameras $P_i$ and points $X_j$:

where $\pi$ projects a world point through a camera, $x_{ij}$ is the observed pixel, and $v_{ij}$ flags whether point $j$ is visible in view $i$. It is a large sparse nonlinear least-squares problem, solved with Levenberg-Marquardt.

You can read the full report.