Essential matrix is not new to anybody being familiar with Epipolar Geometry. Here is the famous epipolar constraint:

\[ x_2^\top E x_1 = 0 \]

Recall that when the essential matrix is obtained by 8-point algorithm, one has to decompose the result with SVD to make its third singular value 0 and the other two singular values equal. Here is a short derivation of this property of essential matrix.

According to the definition of essential matrix:

\[ E = \{ S R | S = t^\wedge \in \mathfrak{so}(3), R \in SO(3)\} \tag{1-1} \]

According to the definition of SVD, a singular value \(\sigma\) of a matrix A, equals to the square root of correspondent eigenvalue \(\lambda\) of matrix \(A^\top A\):

\[ \sigma_{A,i} = \sqrt{\lambda_{A^\top A,i}} \tag{1-2} \]

Meanwhile,

\[ E^\top E = R^\top S^\top S R = -R^\top (t^\wedge)^2 R \tag{1-3} \]

According to the property of askew-symmetric matrix:

\[ (t^\wedge)^2 = \|t\|^2 I - t t^\top \tag{1-4} \]

The first term is a scalar matrix with three equal eigenvalues \(\|t\|^2\)

The second term \(t t^\top\) is a symmetric matrix, which is therefore semi-positive definite. It can be diagonalized^[1]:

\[ t t^\top = \|t\|^2 R_t^\top diag(1, 0, 0) R_t \tag{1-5} \]

Thus, equation (1-3) becomes:

\[ E^\top E = \|t\|^2 R^\top R_t^\top ( I - diag(1, 0, 0)) R_t R \] \[ = \|t\|^2 (R_t R )^\top diag(1, 1, 0) (R_t R) \tag{1-6} \]

Therefore, eigenvalues of \(E^\top E\) are: \(\|t\|^2 (1, 1, 0)\).

Finally, according to (1-3), singular values of essential matrix \(E\) are: \(\|t\|(1, 1, 0)\).

References

1. Xiaoxing. Property of Matrix Generated by Outer Product

Given vector \(a\) with length \(m\) and \(b\) with length \(n\), the outer product of them defined as:

\[ a b^\top = C \tag{1-1} \]

While matrix \(C\) has dimension \(m \times n\).

Here is a brief discussion of the property of matric \(C\)

Special Case: \(a = b\)

Then we have:

\[ A = a a^\top \tag{1-2} \] \[ A = \left[ \begin{matrix} a_1 a & a_2 a & \cdots & a_n a \end{matrix} \right] = \left[ \begin{matrix} a_1 a^\top \\ a_2 a^\top \\ \vdots \\ a_n a^\top \end{matrix} \right] \tag{1-3} \] \[ A = \left[ \begin{matrix} a_1 a_1 & a_1 a_2 & \cdots & a_1 a_n \\ a_2 a_1 & a_2 a_2 & \cdots & a_2 a_n \\ \vdots & \vdots & \ddots & \vdots \\ a_n a_1 & a_n a_2 & \cdots & a_n a_n \\ \end{matrix} \right] \tag{1-4} \]

Here are several properties of matrix A:

1. \(det(A) = 0\)
2. \(trace(A) = \|a\|^2\)
3. \(rank(A) = 1\)
4. Eigenvalues of \(A\) are: \([\|a\|^2, 0, \cdots, 0]\)

According to equation (1-3), all column or row vectors of matrix \(A\) are linear correlated, so its rank is 1. Meanwhile, \(A\) is a symmetrical semi positive definite matrix, \(trace(A) = \Sigma_{i = 1}^n \lambda_i\), \(\lambda\) is the eigenvalue of \(A\). Because \(rank(A) = 1\), only the first eigenvalue of \(A\) is not zero. Therefore, \(trace(A) = \lambda_1 = \|a\|^2\).

General Case

\[ a b^\top = C \tag{2-1} \]

Properties of matrix C:

1. Denote \(k = \text{min}(m,n)\)
2. \(\text{det}(C) = 0\)
3. \(\text{trace}(C) = a[0:k]^\top b[0:k] \)
4. \(\text{rank}(C) = 1\)
5. Singular values of \(C\) are: \([\|a\|\|b\|, 0, \cdots, 0]\)

Decomposition

Given a 1-rank matrix \(A \in \mathbb{R}^{m \times n}\), it can be decomposed to:

\[ A = u v ^\top \] \[ u = k \left[ \begin{matrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \\ \end{matrix} \right] \qquad v ^\top = \frac{1}{k a _{11}} \left[ \begin{matrix} a_{11} & a_{12} & \cdots & a_{1n} \end{matrix} \right] \quad (k \neq 0) \tag{2-2} \]

Because of the existence of \(k\), the decomposition is not unique.

Specially, if \(u = v\), \(u = \frac{1}{\sqrt{a_{11}}}[ \begin{matrix}a_{11} & a_{12}& \cdots& a_{1n} \end{matrix} ] ^\top\).

Motivation

The dot product of two vectors \(a = [a_1, a_2, \cdots, a_n]\) and \(b = [b_1, b_2, \cdots, b_n]\) is defined as^[1]:

\[ \mathbf{a} \cdot \mathbf{b} = \sum_{i=1}^n a_i b_i = a_1 b_1 + a_2 b_2 + \cdots + a_n b_n \tag{1-1} \]

The result can be regarded as a linear combination of elements of \(\mathbf{b}\). It is still valid when \(\mathbf{b}\) is a vector of functions, polynomials and matrices.

There is an exception when \(\mathbf{b}\) is a vector of rotations: The result of the product is not guaranteed to stay in the \(S^3\) manifold. However the the linear combination of rotations is useful to represent the concepts of Rotation like: mean, weighted average. In this article I will give one intuitive explanation of the derivation.

Cumulative Form of Inner Product

A scalar \(c\) was produced by inner product of two vectors:

\[ c = \mathbf{a}^\top \mathbf{b} \tag{2-1} \]

For any \(k\)th element of \(\mathbf{a}\):

\[ c = \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{matrix} \right]^\top \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{matrix} \right] = \left( \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{k-1} \\ a_k \\ \vdots \\ a_n \end{matrix} \right]^\top - \left[ \begin{matrix} 0 \\ 0 \\ \vdots \\ 0 \\ a_{k-1} \\ \vdots \\ 0 \end{matrix} \right]^\top \right) \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_{k-1} \\ b_k \\ \vdots \\ b_n \end{matrix} \right] + a_{k-1} b_k = \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{k-1} \\ a_k - a_{k-1} \\ \vdots \\ a_n \end{matrix} \right]^\top \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_{k-1} + b_k \\ b_k \\ \vdots \\ b_n \end{matrix} \right] \tag{2-2} \]

After applying transform (2-2) to equation (2-1) for \((n - 1)\) times, start from \(n\), end at \(2\):

\[ \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{n-2} \\ a_{n-1} \\ a_n \end{matrix} \right]^\top \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_{n-2} \\ b_{n-1} \\ b_n \end{matrix} \right] = \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{n-2} \\ a_{n-1} \\ a_n - a_{n-1} \end{matrix} \right]^\top \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_{n-2} \\ b_{n-1} + b_n \\ b_n \end{matrix} \right] \\ = \left[ \begin{matrix} a_1 \\ a_2 \\ \vdots \\ a_{n-2} \\ a_{n-1} - a_{n-2} \\ a_n - a_{n-1} \end{matrix} \right]^\top \left[ \begin{matrix} b_1 \\ b_2 \\ \vdots \\ b_{n-2} + b_{n-1} + b_n\\ b_{n-1} + b_n \\ b_n \end{matrix} \right] \\ \vdots \\ = \left[ \begin{matrix} a_0\\ a_1 - a_0\\ \vdots \\ a_{n-2} - a_{n-3} \\ a_{n-1} - a_{n-2} \\ a_n - a_{n-1} \end{matrix} \right]^\top \left[ \begin{matrix} \sum_{i = 0} ^ n b_i \\ \sum_{i = 1} ^ n b_i \\ \vdots \\ b_{n-2} + b_{n-1} + b_n\\ b_{n-1} + b_n \\ b_n \end{matrix} \right] \tag{2-3} \]

We obtain:

\[ \mathbf{a}^\top \mathbf{b} = \left[ \begin{matrix} a_0\\ a_1 - a_0\\ \vdots \\ a_{n-2} - a_{n-3} \\ a_{n-1} - a_{n-2} \\ a_n - a_{n-1} \end{matrix} \right]^\top \left[ \begin{matrix} \sum_{i = 0} ^ n b_i \\ \sum_{i = 1} ^ n b_i \\ \vdots \\ \sum_{i = n-2} ^ n b_i \\ \sum_{i = n-1} ^ n b_i \\ b_n \end{matrix} \right] \tag{2-4} \]

Formula (2-4) can be written as:

\[ \mathbf{a}^\top \mathbf{b} = \Delta \mathbf{a}^\top \mathbf{\tilde B} \\ \Delta {a}_i = \begin{cases} a_1 & \text{if} \ i = 1 \\ a_{i} - a_{i-1} & \text{otherwise} \end{cases} \\ {\tilde B}_i = \sum_{j = n-i} ^ n b_j \tag{2-5} \]

Examples of Cumulative formula

Midpoint of Two Points

Given two points \(b_1\) and \(b_2\), the midpoint of them is:

\[ b_m = \frac{b_1 + b_2}{2} \tag{2-6} \]

Formulate (2-6) can be converted to inner product form: \(b_m = \mathbf{a}^\top \mathbf{b}\), where \(\mathbf{a} = [\frac{1}{2}, \frac{1}{2}]^\top\). The midpoint can also be represented as position of the first point plus the half-distance between these two points:

\[ b_m = b_1 + \frac{1}{2}(b_2 - b_1) \tag{2-7} \]

Formulate (2-7) corresponds to the cumulative form.

Midpoint of Three Points

Given three points \(b_1\), \(b_2\) and \(b_3\), the midpoint of them is:

\[ b_m = \frac{b_1 + b_2 + b_3}{3} \tag{2-8} \]

In cumulative form:

\[ b_m = b_1 + \frac{2}{3}(b_2 - b_1) + \frac{1}{3}(b_3 - b_2) \tag{2-9} \]

From the two examples above we can see, the cumulative formula converts the combination of vector elements to the combination of the difference between vector elements.

Linear Combination of Rotations

As we know, the Addition was not defined in \(SO(3)\). One can not calculate the "midpoint" of two rotations by adding two rotations. Similarly, the Multiplication between scalar and matrices, which means the "cumulation of addition" is also invalid. Instead, the "cumulation" of a rotation is defined by exponential operation and the "distance" between rotations is be calculated by:

\[ \Delta R = R_2 R_1^\top \tag{3-1} \]

Therefore, the interpolation between two rotations can be represented as:

\[ R(t) = (R_2 R_1^\top)^t R_1 \tag{3-2} \]

Finally, the linear combination \(R_m\) of rotations \(R_i\) with weights \(w_i\) can be derived from cumulative formula (2-5)^[2]:

\[ R_m = \prod_{i = 1}^n (\Delta R_i) ^{\tilde w_i} \\ \Delta {R}_i = \begin{cases} R_1 & \text{if} \ i = 1 \\ R_{i}R_{i-1}^T & \text{otherwise} \end{cases} \\ {\tilde w}_i = \sum_{j = n-i} ^ n w_j \tag{3-3} \]

Example: Average of Four Rotations

Given four rotations \(R_1\), \(R_2\), \(R_3\) and \(R_4\), the midpoint of them is:

\[ R_m = (R_4 R_3^\top)^{\frac{1}{4}} (R_3 R_2^\top)^{\frac{2}{4}} (R_2 R_1^\top)^{\frac{3}{4}} R_1 \tag{3-4} \]

References

1. S. Lipschutz; M. Lipson (2009). Linear Algebra (Schaum’s Outlines) (4th ed.). McGraw Hill
2. Kim, M.J., Kim, M.S. and Shin, S.Y., 1995, September. A general construction scheme for unit quaternion curves with simple high order derivatives. In Proceedings of the 22nd annual conference on Computer graphics and interactive techniques (pp. 369-376).
3. Moakher, Maher, Means and averaging in the group of rotations ,SIAM journal on matrix analysis and applications 24.1 (2002): 1-16.
4. Markley, F. Landis, et al. "Averaging Quaternions." Journal of Guidance, Control, and Dynamics 30.4 (2007): 1193-1197.
5. Hartley, Richard, et al. "Rotation averaging." International journal of computer vision 103.3 (2013): 267-305.

Background

While implementing a 2D LiDAR simulator, the calculation of the LiDAR measurement was a bottleneck for performance improvement. For example, in a particle filter with 1024 particles and each particle represents a 256-line LiDAR, running in a map was represented by line segments. For a map with 16 line segments, the estimator have to calculate intersection for \(1024 \times 256 \times 16 = 4194304\) times each update. Therefore, an effective method which determines the intersection of line segments is necessary.

Statement of Problem

Given two line segments defined by points: \(AB\) and \(CD\), check whether two segments intersect.

Intersection of a line and line segment

Given line \(l\), line segment \(AB\) and its correspondent line \(l_{AB}\). The intersection \(K\) of \(l\) and \(l_{AB}\). Then point \(K\) can be expressed as:

\[ K = A + t \overrightarrow{AB} \tag{3-1} \]

Here is the relationship between \(t\) and \(l\), \(AB\):

\[ \begin{cases} l \ \text{intersects} \ AB, & t \in (0, 1) \\ l \ \text{touches} \ AB, & t = 0 \ \text{or} \ t = 1 \\ l \ \text{misses} \ AB, & t \in (-\infty, 0) \cup (1, \infty) \end{cases} \]

Fig. 3-1: Intersect

Fig. 3-2: Touch

Fig. 3-2: Miss

Therefore, the sufficient and necessary condition of \(l\) intersecting \(AB\) is:

\[ K = A + t \overrightarrow{AB}, \ t \in (0, 1) \tag{3-2} \]

Lemma A. Determine if Two Line Segments Intersect

Given line segments \(AB\), \(CD\) and their correspondent line \(l_{AB}\), \(l_{CD}\). It is obvious if and only if \(l_{AB}\) intersects \(CD\) and \(l_{CD}\) intersects \(AB\), these two line segments intersect.

A Rapid Method

Line segments \(AB\) intersects \(CD\) if and only if:

\[ (\overrightarrow{AC} \times \overrightarrow{AB}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) > 0 \\ \text{and} \\ (\overrightarrow{CA} \times \overrightarrow{CD}) \cdot (\overrightarrow{CD} \times \overrightarrow{CB}) > 0 \tag{4-1} \]

Proof:

According to formula (3-2)

\[ m \overrightarrow{AB} = \overrightarrow{AK} = \overrightarrow{AC} + t \overrightarrow{CD} = \overrightarrow{AD} + (1-t) \overrightarrow{DC} \tag{4-2} \]

\(m\) is random none-zero constant. Then we have:

\[ \overrightarrow{AB} = \frac{1}{m}(\overrightarrow{AC} + t \overrightarrow{CD}) \tag{4-3} \] \[ \overrightarrow{AB} = \frac{1}{m}(\overrightarrow{AD} + t \overrightarrow{DC}) \tag{4-4} \]

Then the first term of (4-1) becomes:

\[ \frac{t(1-t)}{m^2} (\overrightarrow{AC} \times \overrightarrow{CD}) \cdot (\overrightarrow{DC} \times \overrightarrow{AD}) > 0 \tag{4-5} \]

For any triangle \(ACD\)：

\[( \overrightarrow{AC} \times \overrightarrow{CD}) \cdot (\overrightarrow{DC} \times \overrightarrow{AD}) = |AC||CD|\sin \alpha \cdot |DC||AD| \sin \beta \tag{4-6} \]

There are two cases listed in Fig. 4-1 and Fig. 4-2. No matter in which case, \(\sin \alpha \sin \beta > 0\).

Fig. 4-1: \(\alpha \in (0, \pi)\), \(\beta \in (0, \pi)\), therefore, \(\sin \alpha \sin \beta > 0\).

Fig. 4-2: \(\alpha \in (\pi, 2\pi)\), \(\beta \in (\pi, 2 \pi)\), \(\sin \alpha \sin \beta > 0\) as well.

Becasue \(m^2 > 0\), formula (4-5) becomes:

\[ t(1-t) > 0 \] \[ 0 < t < 1 \tag{4-7} \]

Therefore, the first term of formula (3-1) means \(l_{AB}\) intersects \(CD\). Similarly, the second term means \(l_{CD}\) intersects \(AB\). According to Lemma A., \(AB\) intersects \(CD\).