N-view triangulation: DLT homogeneous method 1 (1).
30 Oct 2021I’ve become interested in N-view triangulation methods recently, so I started with the most straightforward of them: the DLTs, of Direct Linear Transformation algorithms. It turns out there are three variants on the DLT algorithm for N-view triangulation.
The first DLT algorithm I’ll describe is a homogeneous DLT algorithm, from a 2004 CVPR paper by Richard Hartley and Frederick Schaffalitzky, HS2004. Don’t get too excited about DLTs for final solutions though; in R. Hartley’s papers, comments such as these are common:
Though this method of triangulation may seem attractive, the cost function that it is minimizing has no particular meaning, and the method is not reliable.
Let
- \(\mathbf{P}\): \(3 \times 4\) camera calibration matrix.
- \(\mathbf{X}\) (world point): column vector, size \(4\).
- \(\mathbf{x}\) (image point): column vector, size \(3\).
Then the method mentioned in HS2004 is as follows.
The relationship of \(\mathbf{x} = \mathbf{PX}\) for the \(n\) correspondences is in terms of homogeneous coordinates, and can be written with the unknown scale factor \(k_i\),
\[k_i\mathbf{x} = \mathbf{PX}\]Rewriting,
\[\mathbf{PX} - \mathbf{x}k_i = 0\]Then, this relationship is linear in the unknowns \(\mathbf{X}\), \(k_i\)s,
\[\begin{bmatrix} \mathbf{P}_1 & \mathbf{x}_1 & & & \\ \mathbf{P}_2 & & \mathbf{x}_2 & &\\ \vdots & & & \ddots & \\ \mathbf{P}_n & & & & \mathbf{x}_n \end{bmatrix} \begin{bmatrix} \mathbf{X}\\ -k_1\\ -k_2\\ \vdots\\ -k_n\end{bmatrix} = \mathbf{0}\]I use SVD to solve these type of \(\mathbf{AX} = 0\) problems. The solution with norm equal to 1 is the last column of the V matrix from SVD. The triangulated point is the first four rows of the last column of the V matrix, and remember to normalize by the fourth element such that
\[\mathbf{X} = \begin{bmatrix} X\\ Y\\ Z\\ 1 \end{bmatrix}\]There’s two more versions, continue to Page 2, and a discussion of normalization relevant to this method on Page 3.
Listing of N-view Triangulation posts.
References
[HS2004] Richard Hartley and Frederick Schaffalitzky, “L\(_\infty\) minimization in geometric reconstruction problems,” CVPR 2004. link