# Evolutionary Optimization for Robust Epipolar-Geometry Estimation and Outlier Detection
## 4 Robust Estimation via the Genetic Algorithm
### Encoding  
A significant step in the design of the GA is to find an appropriate representation of individuals, which is an encoding of candidate solutions to the problem as a chromosome. Assume that the input dataset contains n putative correspondences as (\(\boldsymbol{u}_{k}\leftrightarrow\boldsymbol{u^{\prime}}_{k},k=1,\ldots,n\)). Each correspondencehas an index, \(k\), which is given to it based on a random permutation of numbers from one to \(n\). In previous studies ([PERSON] and [PERSON], 2006), the genes are directly defined as the index of each correspondence. However, GA operators take these integers as inputs to create new solutions. Therefore, these integers would better represent the correspondences in a way that makes geometrical or physical sense. To this end, in this study, each correspondence is labelled with a triplet of integers: one integer, \(k\), as its index, as well as two integers, \(h\) and \(v\), as the horizontal and vertical coordinates of the left point relative to the other points on the left image. In this study, the length of the chromosomes (the size of each minimal sample set) is set to 12. Therefore, each individual can be encoded as a sample set \(\mathbf{M}=\left\{\mathbf{m}_{i}(k_{i},h_{i},v_{i}),k=1,\ldots,12|k_{i}\in\{1,\ldots,n \}\wedge h_{i}\in\{1,\ldots,\vartheta\}\wedge v_{i}\in\{1,\ldots,\infty\}\right\}\). Values \(\eta\) and \(\omega\) represent the vertical and horizontal dimensions of an overlapping rectangle, which is defined as the rectangle that minimally bounds all of the putative correspondences on the left image (Figure 2a). Note that the reason why the size of \(\mathbf{M}\) is set to 12 is explained in Section 4.2.  
Given this encoding, to reach the coordinates of the i-th gene inside an individual \(\mathbf{M}\) (i.e., \(\mathbf{u}_{m_{i}}\leftrightarrow\mathbf{u}^{\prime}{}_{m_{i}}\)), the index \(k_{i}\) is used. However, the genetic operators are applied to \(h_{i}\) and \(v_{i}\). One may note that applying the genetic operators to \(h_{i}\) and \(v_{i}\) can result in new integers, where no correspondence might be located. To resolve this issue, a 2D lookup table is produced, by which an index is assigned to any empty pixel of the overlapping rectangle based on its proximity to the putative correspondences. In other words, the lookup table, T, finds the closest match to any arbitrary coordinates, \((\tilde{h},\tilde{v})\), inside the overlapping rectangle:  
\[\text{T}(\tilde{h},\tilde{v})=k\,\text{where}\] \[k=\arg\min_{j=1,\ldots,n}\left(|\tilde{h}-h_{j}|,|\tilde{v}-v_{j} |\right). \tag{6}\]  
The lookup table in Equation (6) is identical to the indices in the Voronoi diagram of the points in the left image, measured with Manhattan distances. As an example, consider the matches in Figure 2b and their corresponding lookup table in Figure 2c. An instance of an encoded gene would be \(\mathbf{m}=(5,6,7)\). Now, consider the application of the mutation operator to this gene. The mutation operator randomly changes the values of the genes. Assume that the application of the mutation operator to \(\mathbf{m}\) (indeed to values of \(h=6\) and \(v=7\)) has resulted in new integers \(\tilde{h}=8\) and \(\tilde{v}=9\). From the lookup table (Figure 2c), it can be seen that these integers correspond to \(k=\text{T}(8,9)=1\). Therefore, the mutation operator changes \(\mathbf{m}=(5,6,7)\) to \(\mathbf{m}=(1,7,9)\).  
Figure 2: Encoding scheme: (**a**) the overlapping rectangle, (**b**) an example list of some putative correspondences, which are identified by their indices, and their positions relative to the overlapping rectangle and (**c**) a part of the 2D lookup table constructed using Equation (6); the bold numbers show the indices of the original matches, and the regular numbers show the indices assigned to the other pixels.