Assignments

The theory parts of the assignments, with solutions. They practice exactly the derivations the exam hints point to: SVD for homogeneous least squares, projecting onto a rotation matrix, and the epipolar constraint.

Why these matter

The tutor called epipolar geometry a “popular exam topic”. The recipe “solve $M\theta =0$ with SVD, then fix the constraints with a second SVD” appears in pose estimation (here), in the 8-point algorithm, in triangulation and in Procrustes.

Assignment 1

Programming part: look_at (rotate the camera towards an object), perspective and orthographic projection, camera pose estimation. Related: Lecture 2.1, Lecture 2.2.

Exercise 1: 3D Transformations

In homogeneous coordinates, a projective 3D transformation is an invertible $4\times 4$ matrix $H$. There is a hierarchy, each level less restrictive:

Type	Matrix	Preserves	DoF
Rigid	$\left[\begin{array}{cc}R& t\\ 0& 1\end{array}\right]$	lengths	6
Similarity	$\left[\begin{array}{cc}sR& t\\ 0& 1\end{array}\right]$	angles	7
Affine	$\left[\begin{array}{cc}A& t\\ 0& 1\end{array}\right]$	parallelism	12
Projective	$H$	straight lines	15

$t\in {\mathbb{R}}^3$, $R\in SO(3)$, $A\in GL(3)$, $s\in \mathbb{R}$.

Affine = rotation + scaling + rotation + translation

From the SVD $A=U\Sigma V^T$: an affine map is a rotation (or mirroring), a non-uniform scaling, another rotation (or mirroring) and a translation. Shearing is affine too.

The key step for (a). For $H=\left[\begin{array}{cc}A& t\\ 0& 1\end{array}\right]$ and points with 4th coordinate 1, the translation cancels in the difference:

$$Hx-Hy=\left[\begin{array}{c}Ax+t\\ 1\end{array}\right]-\left[\begin{array}{c}Ay+t\\ 1\end{array}\right]=\left[\begin{array}{c}A(x-y)\\ 0\end{array}\right]$$

So every question reduces to the linear $3\times 3$ part.

(a) i) Rigid transformations preserve lengths

$\Vert Hx-Hy\Vert =\Vert R(x-y)\Vert =\Vert x-y\Vert$, because a rotation does not change the norm: $\Vert Rv{\Vert }^2=v^T{R}^{T}Rv=v^{T}v$.

(a) ii) Similarity transformations preserve angles

$$\angle (Hx-Hy,Hz-Hy)=\arccos \frac{⟨sR(x-y),sR(z-y)⟩}{\Vert sR(x-y)\Vert \Vert sR(z-y)\Vert }=\arccos \frac{⟨R(x-y),R(z-y)⟩}{\Vert R(x-y)\Vert \Vert R(z-y)\Vert }$$

The $s^2$ cancels. A rotation preserves the inner product, $⟨Ru,Rv⟩=u^T{R}^{T}Rv=u^{T}v$, so the angle equals $\angle (x-y,z-y)$.

(a) iii) Affine transformations preserve parallelism

If $x_1-x_0\parallel y_1-y_0$, then $x_1-x_0=\lambda (y_1-y_0)$ for some $\lambda$. By linearity of $A$:

$$H{x}_1-H{x}_0=\left[\begin{array}{c}A\lambda (y_1-y_0)\\ 0\end{array}\right]=\lambda (H{y}_1-H{y}_0)$$

So the images are parallel again.

(a) iv) Projective transformations preserve straight lines (bonus)

Not in the handed-in solution; a short argument. The points of a line are, in homogeneous coordinates, the linear combinations $\tilde{x}(\lambda )=\tilde{a}+\lambda \tilde{b}$ of two points. $H$ is linear, so $H\tilde{x}(\lambda )=H\tilde{a}+\lambda H\tilde{b}$: again the linear combinations of two homogeneous points, i.e. a line. The division by the last coordinate changes where on the line a point lands, but not that it is on the line.

(b) Length ratios under affine maps

i) Parallel segments: from (a) iii), $H{x}_1-H{x}_0=\lambda (H{y}_1-H{y}_0)$, so the ratio $\lambda$ of the lengths is preserved.

ii) Counterexample for non-parallel segments: non-uniform stretch $A=\text{diag}(2,1,1)$, $t=0$, segments from the origin to $(1,0,0)$ and to $(0,1,0)$. Before: ratio 1. After: lengths 2 and 1, ratio 2.

(c) Degrees of freedom

• Rigid: 6. 3 for $R$ (e.g. axis-angle: 2 for the axis, 1 for the angle) + 3 for $t$.
• Similarity: 7. Rigid + 1 for the scale.
• Affine: 12. 9 for $A$ + 3 for $t$.
• Projective: 15. 16 entries minus 1, because $H$ and $kH$ give the same transformation in homogeneous coordinates ($\tilde{x}\sim k\tilde{x}$).

Exercise 2: Camera Pose from 3D-2D Correspondences

Usually we know $P=K[R\mid t]$ and 3D points $x_i$ and compute the image points $u_i$. Here it is the other way around: given pairs $\{x_i,u_i\}$, recover $R$ and $t$. This is the Direct Linear Transform (DLT). Assume $K=I$:

$$\left[\begin{array}{c}{u}_i\\ 1\end{array}\right]\sim P\left[\begin{array}{c}{x}_i\\ 1\end{array}\right],P=[R\mid t]=\left[\begin{array}{cccc}{r}_{11}& r_{12}& r_{13}& t_1\\ r_{21}& r_{22}& r_{23}& t_2\\ r_{31}& r_{32}& r_{33}& t_3\end{array}\right],\theta =(r_{11},r_{12},r_{13},t_1,r_{21},\dots ,t_3{)}^T\in {\mathbb{R}}^{12}$$

(a) From a known $K$ to the calibrated case

$K$ maps camera coordinates to pixels, so apply its inverse: $u_i^c=K^{-1}{u}_i$ (in homogeneous coordinates).

(b) One correspondence → linear equations

Write the $\sim$ with an unknown scale $\lambda$: $\lambda (u_1,u_2,1{)}^T=P(x_1,x_2,x_3,1{)}^T$. Three rows:

$$\lambda u_1=r_{11}{x}_1+r_{12}{x}_2+r_{13}{x}_3+t_1\lambda u_2=r_{21}{x}_1+r_{22}{x}_2+r_{23}{x}_3+t_2\lambda =r_{31}{x}_1+r_{32}{x}_2+r_{33}{x}_3+t_3$$

Substitute the third into the first two and move everything to one side:

$$\begin{array}{rl}[-x_1,-x_2,-x_3,-1,0,0,0,0,u_1{x}_1,u_1{x}_2,u_1{x}_3,u_1]\theta & =0\\ [0,0,0,0,-x_1,-x_2,-x_3,-1,u_2{x}_1,u_2{x}_2,u_2{x}_3,u_2]\theta & =0\end{array}$$

(c) How many correspondences?

2 equations per correspondence, 12 unknowns → at least 6 correspondences. (Strictly 11 would do because of the free scale, i.e. 5.5 pairs.)

(d) Least squares with SVD

$${\theta }^{\ast }=\arg \underset{\Vert \theta \Vert =1}{\min }\Vert M\theta {\Vert }_2^2=\text{last column of }V,M=U\Sigma V^T$$

Why: $U$ is orthogonal, so $\Vert U\Sigma V^T\theta \Vert =\Vert \Sigma V^T\theta \Vert$. With $y=V^T\theta$ (still $\Vert y\Vert =1$) the objective is ${\sum }_k{\sigma }_k^2{y}_k^2$. It is smallest when all weight is on the smallest singular value: $y=(0,\dots ,0,1{)}^T$, so ${\theta }^{\ast }=Vy$ = the last column of $V$.

(e) Recover $R$ and $t$ from ${\theta }^{\ast }$

${\theta }^{\ast }$ has unit norm and a free sign, so $\hat{R}$ is not a rotation: ${\hat{R}}^T\hat{R}\ne I$, $\det \hat{R}\ne 1$.

1. Reshape ${\theta }^{\ast }$ into $\hat{P}=[\hat{R}\mid \hat{t}]$.
2. Fix the sign: if $\det \hat{R}<0$, multiply the whole ${\theta }^{\ast }$ by $-1$. (DLT only knows $P$ up to scale, so this is allowed. It keeps $\hat{t}$ consistent with $\hat{R}$.)
3. Fix the scale: the columns of a rotation have norm 1, so estimate $s=\frac{1}{3}(\Vert {\hat{r}}_1\Vert +\Vert {\hat{r}}_2\Vert +\Vert {\hat{r}}_3\Vert )$ and set $R_0=\hat{R}/s$, $t=\hat{t}/s$.
4. Project onto the nearest rotation with a second SVD: $R_0=U\Sigma V^T$, $R=U{V}^T$ (drop $\Sigma$).

The determinant trick

Many groups (including the handed-in solution) forced $\det R=1$ with $R=U\text{diag}(1,1,\det (U{V}^T))V^T$. The tutorial called this the “wrong” way here: it flips one axis of $R$ but leaves $t$ with the wrong sign. In DLT we have the extra freedom of flipping the sign of the whole $P$, and we should use it (step 2).

(f) Camera-to-world rotation and camera position

$X_{cam}=R{X}_{world}+t$, so $X_{world}=R^T(X_{cam}-t)=R^T{X}_{cam}-R^{T}t$. Hence

$$R_{cw}=R^T,C=-R^{T}t$$

The same as $T=-RC$ in Lecture 2.1.

Assignment 2

Programming part: 8-point algorithm and relative pose, triangulation, image rectification and view morphing, stereo matching with cost functions and later a Siamese CNN, depth from disparity, linear triangulation and a simple bundle adjustment (fixed cameras). Related: Lecture 3, Lecture 4.

Exercise 1: Epipolar Geometry Conventions

Two cameras $C_0$, $C_1$; $C_0$ is aligned with the world frame.

	Lecture	Hartley-Zisserman
$R$	maps vectors from camera 1’s frame to camera 0’s frame	$\hat{R}$ = rotation of camera 1’s extrinsics
$t$	position of camera 1 in world (= camera 0) frame	$\hat{t}$ = translation of camera 1’s extrinsics
Cameras	$P_0=K_0[I\mid 0]$, $P_1=K_1[R^T\mid -R^{T}t]$	${\hat{P}}_1=K_1[\hat{R}\mid \hat{t}]$
Constraint	$x_0^T\underset{E}{\underbrace{[t{]}_{\times }R}}{x}_1=0$	$x_1^T\underset{\hat{E}}{\underbrace{[\hat{t}{]}_{\times }\hat{R}}}{x}_0=0$ (note: $x_0$ and $x_1$ swapped)

Relation: $\hat{R}=R^T$, $\hat{t}=-R^{T}t$.

(a) Show $E={\hat{E}}^T$

With $R={\hat{R}}^T$ and the hint $[Rv{]}_{\times }=R[v{]}_{\times }{R}^T$:

$$\begin{array}{rl}{\hat{E}}^T& ={\left([\hat{t}{]}_{\times }\hat{R}\right)}^T={\left([-R^{T}t{]}_{\times }{R}^T\right)}^T=-{\left(R^T[t{]}_{\times }R{R}^T\right)}^T\\ & =-{\left(R^T[t{]}_{\times }\right)}^T=-[t{]}_{\times }^{T}R=[t{]}_{\times }R=E\end{array}$$

using $R{R}^T=I$ and that $[t{]}_{\times }$ is skew-symmetric, $[t{]}_{\times }^T=-[t{]}_{\times }$.

(b) Derive the pose theorem for the lecture convention

Theorem (Hartley-Zisserman): for $\hat{E}=\hat{U}\text{diag}(1,1,0){\hat{V}}^T$: $\hat{t}=\pm {\hat{u}}_3$, $\hat{R}=\hat{U}W{\hat{V}}^T$ or $\hat{U}{W}^T{\hat{V}}^T$.

Goal (lecture): for $E=U\text{diag}(1,1,0)V^T$: $t=\pm u_3$, $R=UW{V}^T$ or $U{W}^T{V}^T$.

Step 1, identify $U$ and $V$. $E={\hat{E}}^T=\hat{V}\text{diag}(1,1,0){\hat{U}}^T$, so $U=\hat{V}$ and $V=\hat{U}$.

Step 2, rotation. $R={\hat{R}}^T$:

$$\hat{R}=\hat{U}W{\hat{V}}^T\Rightarrow R=\hat{V}{W}^T{\hat{U}}^T=U{W}^T{V}^T,\hat{R}=\hat{U}{W}^T{\hat{V}}^T\Rightarrow R=UW{V}^T$$

The two cases swap, but the set of candidates is the same.

Step 3, translation direction. $u_3$ is the left singular vector of the zero singular value: $u_3^{T}E=0$. With $E=[t{]}_{\times }R$ and $R$ invertible: $u_3^T[t{]}_{\times }=0$. Transposing, $[t{]}_{\times }{u}_3=0$, so $u_3\parallel t$: $t=\alpha u_3$.

Step 4, length. $\hat{t}=\pm {\hat{u}}_3=\pm v_3$ and $\hat{t}=-R^{T}t$ give $t=\mp R{v}_3$, so $\Vert t\Vert =\Vert v_3\Vert =1=\Vert u_3\Vert$. Hence $\alpha =\pm 1$ and $t=\pm u_3$.

Intuition

Both conventions describe the same geometry. One uses where camera 1 is ($R$, $t$), the other how to transform points into camera 1 ($\hat{R}$, $\hat{t}$). The only visible difference is a transpose of $E$ and swapped roles of $x_0$ and $x_1$. See Notation.

Related

• Lecture 3, Recovering the relative pose from E
• Lecture 3, The 8-point algorithm
• Concepts: Essential and Fundamental Matrix, Epipolar Geometry, Eight-Point Algorithm, Rotation Matrix, Projection Matrix, Homogeneous Coordinates
• Exam Structure · Study Plan · Formula Sheet · Notation