# Evolutionary Optimization for Robust Epipolar-Geometry Estimation and Outlier Detection
## 3 Problem Formulation
### Fundamental Theories: Two-View Epipolar Geometry  
Epipolar geometry defines the geometry of stereo vision, all elements of which can be captured by a matrix called the fundamental matrix. It can also be captured by an essential matrix in the case of calibrated images, where the parameters of intrinsic camera calibration are known. There are different methods for estimating the fundamental matrix: linear, iteration-based and robust techniques [41]. Robust techniques, which use linear techniques as their base, are the most applicable ones since they can handle the presence of outliers and, finally, can detect the inlier correspondences required for structure reconstruction. This category of estimation is considered in this study. The following paragraphs present the theoretical background with this regard. For any pair of homogeneous coordinates of correspondences \(\mathbf{u}\leftrightarrow\mathbf{u}^{\prime}\) in two images, the fundamental matrix (\(F\)) is defined by Equation (1). \[\mathbf{u}^{\prime\intercal}F\mathbf{u}=0 \tag{1}\]  
It can be noticed that \(F\) is defined up to an unknown scale. It is also a rank-two matrix with zero determinant. Consequently, it has only seven degrees of freedom [42]. Given \(m\) matches \(\mathbf{u}_{i}\leftrightarrow\mathbf{u}^{\prime}{}_{i}\), it would be possible to form a linear homogeneous system of equations in the nine unknown coefficients of matrix \(F\) as:  
\[Af=0, \tag{2}\]  
where \(\mathbf{f}=(F_{11},F_{12},F_{13},F_{21},F_{22},F_{23},F_{31},F_{32},F_{33})^{ \intercal}\), and matrix \(A\) is the \(m\times 9\) coefficient matrix as \(A=[\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{m}]^{\intercal}\). The coordinates of the points are also usually normalized so that \(A\) can gain a better condition number [43]. Given a pair of matching points with normalized coordinates \(\mathbf{u}_{i}=(u_{i},v_{i},1)^{\intercal}\) and \(\mathbf{u}^{\prime}{}_{i}=(u^{\prime}_{i},v^{\prime}_{i},1)^{\intercal}\), the row \(\mathbf{a}_{i}\) corresponding to this match is defined as:  
\[\mathbf{a}_{i}=(u_{i}u^{\prime}_{i},v_{i}u^{\prime}_{i},u^{\prime}_{i},u^{\prime} _{i},v_{i}v^{\prime}_{i},v^{\prime}_{i},u_{i},v_{i},1)^{\intercal}. \tag{3}\]  
In robust estimation, non-parameterized linear methods of fundamental-matrix estimation are used due to the reasonable agreement between the speed and accuracy yielded from these methods [44]. Given exactly seven matches (\(m=7\)), it would be possible to determine \(f\) by spanning the two-dimensional nullspace of \(A\) and applying the rank deficiency constraint to it (seven-point algorithm). However, this results in up to three fundamental matrices. Thus, when the goal is the robust estimation of the fundamental matrix, computational expenses for hypothesis evaluation would increase up to three times. Depending on the total number of correspondences and the percentage of outliers, this can be a major drawback. Therefore, eight or more matches (\(m\geq 8\)) are required to determine a single solution for the fundamental matrix (eight-point algorithms). Using at least eight points, the solution to \(F\) can be found from Equation (2) by linear least-squares methods. In the end, the rank deficiency constraint must be applied to the estimated \(F\) by setting its smallest singular value to zero [43]. In the case of the eight-point algorithm, an additional constraint should be imposed to define an arbitrary scale factor for \(F\) and to prevent the trivial solution \(F=0\). There are two options in this regard. One would be to fix the two-norm of the fundamental matrix (e.g., \(\|\mathbf{f}\|=1\)). The other would be to fix one element of the matrix (e.g., \(F_{33}=1\)). In the first case (\(\|\mathbf{f}\|=1\)), an orthogonal least-square minimization should be applied. It can be shown that the solution is the right singular vector of \(A\) corresponding to the smallest eigenvalue of \(AA^{\intercal}\), which can be determined by singular value decomposition (SVD) of matrix \(A\).