Structure from Motion

Structure from Motion algorithms allows us to reconstruct a 3D image from a set of 2 or more distinct images whose relative pose is unknown. This is the main technique for visual odometry.

Two-View SfM

For a given 3D feature $P^w$, the relative pose of the camera between two views, $[R_1^2{t}_1^2]$ may not be known. We can use the stereo vision process to find $[R_1^2{t}_1^2]$ and well $P^w$. For example, the relative pose may come from the movement of the camera between two time instances, ${\tau }_1$ and ${\tau }_2$. This is called Two-View SfM.

Assume the camera pose at time $t_1$ is a reference (i.e.) world frame, the image taken at $t_1$ would be given by

$${\lambda }_1{\overline{p}}^1=K[I|0]{\overline{P}}^w=K{P}^w$$

and the image taken at at $t_2$ would be

$${\lambda }_2{\overline{p}}^2=K[R_1^2|t_1^2]{\overline{P}}^w=K{R}_1^2{P}^w+K{t}_1^2$$

where because image points are projective, each comes with an unknown positive depth/scale ${\lambda }_i$.

Working in normalized (calibrated) image coordinates:

$${\overline{x}}^1=K^{-1}{\overline{p}}^2,{\overline{x}}^2:=K^{-1}{\overline{p}}^2$$

Because the world frame is the first camera, the 3D points coordinates in camera 1 are simply ${\lambda }_1{\overline{x}}_1$.

In these coordinates the intrinsics, and the geometry is purely Euclidean:

$${\lambda }_2={\overline{x}}^2{R}_1^2{\lambda }_1{\overline{x}}_1+t_1^2$$

Taking the cross product of both sides of the above equation with $t_1^2$:

$$\begin{array}{rl}{t}_1^2\times {\lambda }_2{\overline{x}}^2& =t_1^2\times R_1^2{\lambda }_1{\overline{x}}^1+\cancel{t_1^2\times t_1^2}\\ ⟹\lambda {\hat{t}}_1^2{\overline{x}}^2& ={\lambda }_1{\hat{t}}_1^2{R}_1^2{\overline{x}}^1\end{array}$$

Finally, taking the dot product with ${\overline{x}}_2$ on both sides:

$$\begin{array}{r}\cancel{\lambda ({\overline{x}}_2{)}^T(t_1^2\times {\overline{x}}^2)}={\lambda }_1({\overline{x}}^2{)}^T{\hat{t}}_1^2{R}_1^2{\overline{x}}^1\\ ⟹({\overline{x}}^2{)}^T({\hat{t}}_1^2{R}_1^2)({\overline{x}}^1)=0\end{array}$$

where:

• ${\hat{t}}_1^2$ is the skew-symmetric matrix that implements the cross product with $t_1^2$
• $E=({\hat{t}}_1^2{R}_1^2)$ is called the essential matrix
• $({\overline{x}}^2{)}^{T}E({\overline{x}}^1)=0$ is called the epipolar constraint

SfM Procedure

In general, the SfM procedure involves:

1. Computing the essential matrix
2. Extracting $R$ and $t$
3. Triangulating to retrieve 3D coordinates

Triangulation

Once the relative camera poses are known, each pair of corresponding rays ${\bar{x}}_i^1$ and ${\bar{x}}_i^2$ can be intersected to recover the 3D point $P_i$.

Conceptually:

• Each image point defines a ray in space.
• The 3D point is the intersection (or best intersection) of these rays.

This process is called triangulation.

Mathematically, we solve for the depths ${\lambda }_1,{\lambda }_2$ that best satisfy:

$${\lambda }_2{\bar{x}}^2=R{\lambda }_1{\bar{x}}^1+t$$

In practice, triangulation is done using least-squares linear or nonlinear optimization.