Camera Calibration
Discovering the intrinsic (camera calibration matrix) & extrinsic parameters (position & orientation) of a camera, from the pixel coordinates of extracted features with their known world coordinates.
Steps
- Estimate projection matrix $$P$$
- Decompose $$P$$ into camera calibration matrix $$K$$ and rigid body motion $$[R | T]$$
Estimation of Projection Matrix
We have pixel coordinates $$(u_i, v_i)$$ from image, and world coordinates $$(X_i, Y_i, Z_i, 1)$$,
$$ \begin{bmatrix} si u_i \ s_i v_i \ s_i \end{bmatrix} = \begin{bmatrix} p{00} & p{01} & p{02} & p{03}\ p{10} & p{11} & p{12} & p{13}\ p{20} & p{21} & p{22} & p_{23}\ \end{bmatrix}\begin{bmatrix} X_i \ Y_i \ Z_i \ 1 \end{bmatrix}
$$
Turn into 2 equations of $$ui$$ and $$v_i$$, rearrange will get 11 unknowns (setting $$p{23}$$ to 1). Need 5.5 (or 6) non-coplanar points to solve.
$$ Ap = 0\ \begin{bmatrix} X1 & Y_1 & Z_1 & 1 & 0 & 0 & 0 & 0 & -u_1X_1 & -u_1Y_1 & -u_1Z_1 & -u_1\ 0 & 0 & 0 & 0 & X_1 & Y_1 & Z_1 & 1 & -v_1X_1 & -v_1Y_1 & -v_1Z_1 & -v_1\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \end{bmatrix}\begin{bmatrix} p{00} \p_{01} \ \vdots \end{bmatrix} = \begin{bmatrix} 0 \ 0 \ \vdots \end{bmatrix}
$$
where solving $$p$$ equals solving the nullspace of $$A$$, which can be approximated using linear least squares (pseudo-inverse).
Nullspace
$$Ax = 0$$
The set of all vectors $$x$$ (i.e. a subspace) that are mapped to zeros is the nullspace of $$A$$.
Nullity
Dimension of the nullspace = number of L.I. vectors forming the basis of nullspace.
Rank
Dimension of the range (column space) of $$A$$ = number of L.I. vectors in rows or columns of $$A$$.
Rank-Nullity Theorem
$$rank(A) + nullity(A) = N$$
Linear Least Squares (Pseudo-Inverse)
Step 1: Find the Best Approximation
Find a unit vector $$x$$ that minimizes the sum of squares of residual errors $$r$$:
$$Ax = 0 + r\ \sum_i r_i^2 = |r|^2 = r^T r = x^T A^T A x$$
According to elementary eigenvector theory,
$$\lambda_1 \le \frac{x^T A^T A x}{x^T x} \le \lambda_2$$
where $$\lambda_1$$ and $$\lambda_2$$ are the min & max eigenvalues of $$A^T A$$.
To find the eigenvalues & eigenvectors, apply Singular Value Decomposition (SVD):
$$A = UDV^T$$
$$det(A - \lambda I) = 0$$
- $$U$$: orthogonal matrix composed of unit eigenvectors of $$AA^T$$ in descending order of eigenvalues
- $$V$$: orthogonal matrix composed of unit eigenvectors of $$A^T A$$ in descending order of eigenvalues
- $$D$$: square roots of the non-zero eigenvalues (singular values) of $$AA^T$$ and $$A^T A$$ in descending order along the diagonal
Hence, $$|r|^2 = \lambda_1$$ is the corresponding eigenvalue when $$x$$ is the last column of $$V$$.
Step 2: Nonlinear Optimization
Iteratively minimize the errors between measured image points $$(u_i, v_i)$$ & reprojected image points $$(\hat{u_i}, \hat{v_i})$$.
$$min_P \sum_i((u_i - \hat{u_i})^2 + (v_i - \hat{v_i})^2)$$
Decomposition of the Projection Matrix
$$ \begin{aligned} P &= \begin{bmatrix} p0 & p_1 & p_2 & p_3 \end{bmatrix}\ &= K \begin{bmatrix}R | T\end{bmatrix} \ &= \begin{bmatrix} \alpha_u & \varsigma & u_0 \ 0 & \alpha_v & v_0 \ 0 & 0 & 1 \end{bmatrix}\begin{bmatrix} r{00} & r{01} & r{02} & Tx \ r{10} & r{11} & r{12} & Ty \ r{20} & r{21} & r{22} & T_z \ \end{bmatrix}\end{aligned}
$$
where $$\varsigma$$ is the skew of image axes.
- QR decomposition on $$P^{-1}$$ into $$QR'$$
- $$P^{-1} = QR'$$
- $$P = (QR')^{-1} = R'^{-1} Q^{-1}$$
- $$K = R'^{-1}$$, since inverse of upper triangular matrix = upper triangular matrix
- $$R = Q^T$$, since inverse of orthogonal matrix = orthogonal matrix = transpose
- Normalize $$K$$
- Scale factor $$\alpha = k_{22}$$, $$P = \alpha KR$$
- If $$k{00} < 0$$, column $$k{i0}$$ & row $$r_{0j}$$ multiplied by -1
- If $$k{11} < 0$$, column $$k{i1}$$ & row $$r_{1j}$$ multiplied by -1
- $$T = \frac{1}{\alpha} K^{-1} p_3$$
QR Decomposition
$$A = QR$$
where $$A$$ has linearly independent columns, $$Q$$ is orthogonal, and $$R$$ is upper triangular.
Gram-Schmidt Process
Obtain orthonormal basis of $$A$$,
$$qi = \frac{a'_i}{|a'_i|}$$, where $$a'_i = a_i - \sum^{i-1}{k=0}(q_k^T a_i)q_k$$
Then retrieve $$A$$ in the representation of $$q$$s,
$$ai = \sum^i{k=0}(q_k^Ta_i)q_k$$
$$\begin{bmatrix} a_0 & a_1 & a_2 \end{bmatrix} = \begin{bmatrix} q_0 & q_1 & q_2 \end{bmatrix}\begin{bmatrix} q_0^T a_0 & q_0^T a_1 & q_0^T a_2\ 0 & q_1^T a_1 & q_1^T a_2\ 0 & 0 & q_2^T a_2\ \end{bmatrix}$$
Planar Scenes
Solve for 8 unknowns. 4 non-collinear points needed.
$$ \begin{bmatrix} si u_i \ s_i v_i \ s_i \end{bmatrix} = \begin{bmatrix} p{00} & p{01} & p{02}\ p{10} & p{11} & p{12}\ p{20} & p{21} & p{22}\ \end{bmatrix}\begin{bmatrix} X_i \ Y_i \ 1 \end{bmatrix}
$$
Linear Scenes
Solve for 5 unknowns. 3 image points needed.
$$ \begin{bmatrix} si u_i \ s_i v_i \ s_i \end{bmatrix} = \begin{bmatrix} p{00} & p{01}\ p{10} & p{11}\ p{20} & p_{21}\ \end{bmatrix}\begin{bmatrix} X_i \ 1 \end{bmatrix}
$$
Vanishing Points
Project point at infinity along each coordinate axis onto the image:
$$ \begin{aligned} \begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix} &= P \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ 0 & 0 & 0 \ \end{bmatrix}\ &= K\begin{bmatrix}R & T\end{bmatrix}\begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 0 \ 0 & 0 & 1 \ 0 & 0 & 0 \ \end{bmatrix}\ &= KR \end{aligned}
$$
where $$\lambda_i$$ are some unknown scalars.
Eliminate $$R$$,
$$\begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix}\begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix}^T = KRR^TK^T = KK^T$$
since $$RR^T = I$$.
Then,
$$ \omega = KK^T = \begin{bmatrix} \alpha_u^2 + \varsigma^2 + u_0^2 & \varsigma \alpha_v + u_0 v_0 & u_0 \ \varsigma \alpha_v + u_0 v_0 & \alpha_v^2 + v_0^2 & v_0 \ u_0 & v_0 & 1 \end{bmatrix}
$$
Assume CCD array to be square pixels ($$\varsigma = 0$$, $$\alpha_u = \alpha_v = \alpha$$),
$$ \omega = \begin{bmatrix} \alpha^2 + u_0^2 & u_0 v_0 & u_0 \ u_0 v_0 & \alpha^2 + v_0^2 & v_0 \ u_0 & v_0 & 1 \end{bmatrix}
$$
Equality 1
$$ \omega{01} \omega{22} = \omega{02}\omega{12}\ a_1 \lambda_1^2 \lambda_2^2 + b_1 \lambda_1^2 \lambda_3^2 + c_1 \lambda_2^2 \lambda_3^2 = 0
$$
where $$a_1 = (u_1 - u_2)(v_1 - v_2)$$, $$b_1 = (u_1 - u_3)(v_1 - v_3)$$, $$c_1 = (u_2 - u_3)(v_2 - v_3)$$.
Equality 2
$$ \omega{00}\omega{22} - \omega{02}^2 = \omega{11}\omega{22} - \omega{12}^2\ a_2 \lambda_1^2 \lambda_2^2 + b_2 \lambda_1^2 \lambda_3^2 + c_2 \lambda_2^2 \lambda_3^2 = 0
$$
where $$a_2 = (u_1 - u_2)^2 - (v_1 - v_2)^2$$, $$b_2 = (u_1 - u_3)^2 - (v_1 - v_3)^2$$, $$c_1 = (u_2 - u_3)^2 - (v_2 - v_3)^2$$.
Equality 3
$$ \omega_{22} = 1\ \lambda_1^2 + \lambda_2^2 + \lambda_3^2 = 1
$$
Solving equality 1 & 2 gives $$\lambda_1^2\lambda_2^2 : \lambda_1^2\lambda_3^2 : \lambda_2^2\lambda_3^2$$ and hence $$\lambda_1^2:\lambda_2^2:\lambda_3^2$$.
Then use equality 3 to solve for $$\lambda_i^2$$.
Solve for K
Plug the $$\lambda_i^2$$s back.
$$ \begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix}\begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix}^T = KK^T
$$
Solve for R
$$ \begin{bmatrix} \lambda_1 u_1 & \lambda_2 u_2 & \lambda_3 u_3\ \lambda_1 v_1 & \lambda_2 v_2 & \lambda_3 v_3\ \lambda_1 & \lambda_2 & \lambda_3\ \end{bmatrix} = KR
$$
$$ R = \begin{bmatrix}r_0 & r_1 & r_2\end{bmatrix}\ r_i = \frac{q_i}{|q_i|}\ q_i = K^{-1}\begin{bmatrix}u_i & v_i & 1\end{bmatrix}^T \text{ for } i = 0, 1\ r_2 = r_0 \times r_1
$$
Solve for T
Choose an arbitrary image point $$(u_4, v_4)$$ as the image of the world origin,
$$ \begin{bmatrix} \lambda_4 u_4 \ \lambda_4 v_4 \ \lambda_4 \end{bmatrix} = P \begin{bmatrix} 0 \ 0 \ 0 \ 1 \end{bmatrix} = K \begin{bmatrix}R | T\end{bmatrix} \begin{bmatrix} 0 \ 0 \ 0 \ 1 \end{bmatrix} = KT\ T = \lambda_4 K^{-1}\begin{bmatrix} u_4 \ v_4 \ 1 \end{bmatrix}
$$
where $$\lambda_4$$ is an unknown scalar.
- $$\lambda_4$$ depends on the depth of the world origin
- $$\lambda_4$$ can be chosen arbitrarily for a single image
- But need to ensure the scales are consistent among multiple images