Fundamental Matrix
- Problems with essential matrix $$p'^TEp = 0$$
- Works with ray vectors, which depends on camera intrinsic parameters
- Desirable to express epipolar constraint directly in pixel coordinates
First correlate pixel coordinates and rays:
$$ \begin{aligned} \begin{bmatrix} u \ v \ 1 \end{bmatrix} &= \begin{bmatrix} k_u & 0 & u_0 \ 0 & k_v & v_0 \ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} x \ y \ 1 \end{bmatrix} \ &= \frac{1}{f}\begin{bmatrix} fk_u & 0 & u_0 \ 0 & fk_v & v_0 \ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} x \ y \ f \end{bmatrix} \ &= \frac{1}{f}Kp \end{aligned}
$$
Then express epipolar constraint in pixel coordinates:
$$ p'^TEp = 0\ \tilde{w}'^T K'^{-T}EK^{-1}\tilde{w} = 0\ \tilde{w}'^T F\tilde{w} = 0
$$
Hence
$$ F = K'^{-T}EK^{-1}
$$
- Properties
- Given a point $$\tilde{w}$$ in one image, the corresponding point in the other image $$\tilde{w}'$$ is constrained to line $$l' = F\tilde{w}$$
- Zero determinant, i.e. max rank 2
- Because $$E$$ is rank 2
- Degrees of freedom: 7
- Rank 2
- Scale not important
Computing F from Projection Matrices
Using Essential Matrix & Camera Calibration Matrices
We have two cameras:
$$ P_1 = K_1 \begin{bmatrix} R_1 & T_1\end{bmatrix}\ P_2 = K_2 \begin{bmatrix} R_2 & T_2\end{bmatrix}
$$
To retrieve relative rotation $$R$$ and translation $$T$$ between the two cameras, make use of common world coordinate $$X$$ w.r.t. camera coordinates $$X{C1}$$, $$X{C2}$$:
$$ \begin{aligned} X{C1} &= R_1X + T_1\ X &= R_1^T(X{C1} - T_1) \end{aligned}
$$
$$ \begin{aligned} X{C2} &= R_2X + T_2\ &= R_2(R_1^T(X{C1}-T1))+T_2\ &= R_2R_1^TX{C1} - R2R_1^TT_1+T_2\ &= RX{C1}+T \end{aligned}
$$
where
$$ \begin{aligned} R &= R_2R_1^T\ T &= T_2 - RT_1\end{aligned}
$$
Then the fundamental matrix is given by:
$$ E = [T]_x R\ F = K_2^{-T}EK_1^{-1}
$$
Using Components of the Projection Matrices
Each row vector in the projection matrix represents a plane passing through the optical center:
where
$$ P = \begin{bmatrix} p_0^T \ p_1^T \ p_2^T \end{bmatrix}
$$
Since optical center is at the intersection of the planes:
$$ P \begin{bmatrix} C \ 1 \end{bmatrix} = 0
$$
Rewrite with $$P = \begin{bmatrix}Q & q \end{bmatrix}$$:
$$ QC + q = 0\ C = -Q^{-1}q
$$
Next, consider an image point $$\tilde{w}$$, ray vector $$D$$ pointing from $$C$$ to $$\tilde{w}$$, vanishing point along the ray vector $$\tilde{X}{inf} = \begin{bmatrix}D^T 0\end{bmatrix}^T$$. $$\tilde{X}{inf}$$ will project to image point $$\tilde{w}$$:
$$ \tilde{w} = P\tilde{X}_{inf}
$$
Rewrite with $$P = \begin{bmatrix}Q & q \end{bmatrix}$$:
$$ \tilde{w} = QD\ D = Q^{-1}\tilde{w}
$$
Now, we have two cameras:
$$ P_1 = \begin{bmatrix} Q_1 & q_1 \end{bmatrix}\ P_2 = \begin{bmatrix}Q_2 & q_2 \end{bmatrix}
$$
Given a point $$\tilde{w}_1$$ in the first camera, define an epipolar line $$l_2$$ in the second camera with:
- The epipole $$\tilde{e}_2$$ in the second camera, which is the image of $$C_1$$
- $$\tilde{e}_2 = P_2 \begin{bmatrix}C_1 \ 1\end{bmatrix} = -Q_2Q_1^{-1}q_1 + q_2$$
- The image point $$\tilde{w}_2$$ in the second camera, which is the image of the point at infinity along the ray defined by $$C_1$$ and $$\tilde{w}_1$$
- $$\tilde{X}_{inf} = \begin{bmatrix}D & 0\end{bmatrix}^T = \begin{bmatrix} Q_1^{-1}\tilde{w}_1 & 0\end{bmatrix}^T$$
- $$\tilde{m} = P2 \tilde{X}{inf} = Q_2Q_1^{-1}\tilde{w}_1$$
Thus,
$$ l2 = \tilde{e}_2 \times \tilde{m} = [-Q_2Q_1^{-1}q_1 + q_2]{\times} Q_2Q_1^{-1}\tilde{w}_1
$$
And the equation follows due to epipolar constraint:
$$ \begin{aligned} \tilde{w}2^Tl_2 &= 0\ \tilde{w}_2^T[-Q_2Q_1^{-1}q_1 + q_2]{\times} Q_2Q_1^{-1}\tilde{w}_1 &= 0\ \tilde{w}_2^T F \tilde{w}_1 &= 0 \end{aligned}
$$
where
$$ F = [-Q2Q_1^{-1}q_1 + q_2]{\times} Q_2Q_1^{-1}
$$
Computing F from Corresponding Points
Each pair of corresponding points $$(\tilde{w}, \tilde{w}')$$ generates one constraint on the unknown elements $$f_{ij}$$ of $$F$$:
$$ \begin{bmatrix} u' & v' & 1 \end{bmatrix}\begin{bmatrix} f{00} & f{01} & f{02} \ f{10} & f{11} & f{12} \ f{20} & f{21} & f_{22} \ \end{bmatrix}\begin{bmatrix} u & v & 1 \end{bmatrix} = 0
$$
$$ \begin{bmatrix} u1'u_1 & u_1'v_1 & u_1' & v_1'u_1 & v_1'v_1 & v_1' & u_1 & v_1 & 1\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \ u_n'u_n & u_n'v_n & u_n' & v_n'u_n & v_n'v_n & v_n' & u_n & v_n & 1 \end{bmatrix}\begin{bmatrix}f{00} \ f{01} \ \vdots \ f{21} \ f_{22} \end{bmatrix} = 0
$$
Since scale is not important, need 8 or more pairs to determine $$F$$ using linear least squares.
Data Normalization
Since pixel scales are pretty large ($$\approx 10^2)$$, data normalization is needed before estimation to avoid numerical instability, and also makes the estimation invariant to arbitrary choices of the coordinate systems.
- Translation: place centroid at origin
- $$\breve{u_i} = u_i - \bar{u}$$, $$\breve{v_i} = v_i - \bar{v}$$
- $$\bar{u} = \frac{1}{n}\sum u_i$$, $$\bar{v} = \frac{1}{n} \sum v_i$$
- Scaling (isotropic): average distance from origin = $$\sqrt{2}$$
- $$\hat{u_i} = \frac{\sqrt{2}}{d}\breve{u_i}$$, $$\hat{v_i} = \frac{\sqrt{2}}{d}\breve{v_i}$$
- $$d = \frac{1}{n} \sum \sqrt{(\breve{u}_i)^2 + (\breve{v}_i)^2}$$
The overall transformation matrix:
$$ \hat{w}_i = M \tilde{w}_i \ M = \begin{bmatrix} \frac{\sqrt{2}}{d} & 0 & -\frac{\sqrt{2}}{d}\bar{u} \ 0 & \frac{\sqrt{2}}{d} & -\frac{\sqrt{2}}{d}\bar{v} \ 0 & 0 & 1 \end{bmatrix}
$$
The fundamental matrix $$\hat{F}$$ is first computed from the normalized data, then the actual fundamental matrix is given by:
$$ F = M^T \hat{F} M
$$
Rank 2 Constraint
The estimated $$F$$ may not conform to the rank 2 constraint, i.e. have zero determinant & epipolar lines meet at a single point.
To enforce the constraint:
- Perform SVD on $$F$$
- Replace the smallest singular value in the diagonal matrix with 0
The resultant $$F'$$ is the closest to $$F$$ in terms of Frobenius norm:
$$ |F - F'|F = \sqrt{\sum^2{i=0}\sum^2{j=0}(f{ij} - f_{ij}')^2}
$$
RANSAC
Random Sample Consensus, an iterative method for estimating parameters of a mathematical model from a set of data with outliers. Uses the smallest set possible & enlarge the set with consistent data points.
Algorithm
- Randomly sample a minimum data set $$s_i$$
- Estimate model parameters $$\theta_i$$ with $$s_i$$
- E.g. for a line, $$l = \begin{bmatrix}a & b & c\end{bmatrix}^T$$
- Determine a set of inliers within a distance threshold $$t$$, i.e. the consensus set $$S_i$$
- $$dist = \frac{|ax_i + by_i + c|}{\sqrt{a^2 + b^2}} < t$$ for lines
- $$dist = \frac{({w'}_i^T F w_i)^2}{(Fw_i)_0^2 + (Fw_i)_1^2} + \frac{(w_i^T F^T {w'}_i)^2}{(F^T{w'}_i)_0^2 + (F^T{w'}_i)_1^2} < t$$ for epipolar lines (symmetric transfer error)
- If size of $$S_i$$ is greater than threshold $$T$$, re-estimate the model with $$S_i$$; otherwise, repeat from 1.
- Usually set $$T = \omega \cdot n$$
- $$\omega$$: probability that a data point is an inlier
- $$n$$: number of data points
- Usually set $$T = \omega \cdot n$$
- After $$N$$ trials, the largest consensus set is selected, and the model is re-estimated with this set
- $$N$$ should be large to ensure $$S$$ is free from outliers
- $$P(\text{a sample set not free from outliers}) = 1 - \omega^d$$
- $$\omega$$: probability that a data point is an inlier
- $$d$$: size of minimum data set
- $$P(\text{all sample sets not free from outliers}) = (1 - \omega^d)^N = 1 - p$$
- $$p$$: $$P(\text{at least 1 sample set is free from outliers})$$
- $$N = \frac{log(1 - p)}{log(1 - \omega^d)}$$
- $$P(\text{a sample set not free from outliers}) = 1 - \omega^d$$
- $$N$$ should be large to ensure $$S$$ is free from outliers