# Evolutionary Optimization for Robust Epipolar-Geometry Estimation and Outlier Detection
## 4 Robust Estimation via the Genetic Algorithm
### Sampling GA Individuals  
The first step to initiate GA is to generate a random population of individuals. As mentioned in Section 3.1, at least eight points are required to form a minimal sample set from which the fundamental matrix can be calculated. As discussed in Section 2, random sampling can be either done uniformly or with an order based on the quality of the correspondences. However, none of these sampling strategies avoids degenerate configurations. To decrease the degenerate solutions, guided sampling based on the spatial distribution of the correspondences is proposed in this paper. To this end, first, the overlapping rectangle (shown in Figure 3a) is divided into 12 sub-regions of equal area as in Figure 3b. Then, the density of each region is calculated as the number of correspondences enclosed by it, normalized by the total number of correspondences.  
For the first half of the population, the 12 correspondences are picked up from the regions that are selected successively in a roulette-wheel selection. The density of a region determines its probability to participate in sampling. In simple words, the wheel is turned 12 times, and every time, a region is selected from which to draw a match. For the other half of the GA population, every individual is made of twelve correspondences in a way that at least one match is sampled from each region. The reason for introducing this two-step sampling is to avoid high-density regions having full dominance in the population. Figure 3c illustrates an example of putative correspondences distributed on the overlapping rectangle, and the roulette wheel corresponding to it is shown in Figure 3d. Once the population is formed, the correspondences of every sample set \(M\) in the population should be substituted into Equation (2) to determine the fundamental matrix (\(F\)). Then, each fundamental matrix is evaluated using the cost function in Equation (5), and its fitness is decided; the lower the value of the cost function, the fitter the individual.  
The primary goal of the proposed scheme for subdividing the overlapping rectangle is to decrease the risk of sampling ill-configured points. Evidently, more than 12 sub-grids could be considered for sampling. However, the greater the number of points, the higher the risk of encountering outliers  
Figure 3: Guided sampling: (**a**) a stereo pair and the putative correspondences; the bounding rectangle on the left image represents the overlapping rectangle; (**b**) dividing the overlapping rectangle into 12 sub-regions of equal area; (**c**) the minimal rectangle and the distribution of putative matches over the sub-regions; (**d**) density-based roulette-wheel for region selection.  
and the lower the probability of reaching outlier-free sample sets. Besides, 12 data points are already proposed by other studies such as [38; 51]. Of course, there would still be a probability that the sampled points are too close to each other and cause ill-configurations. Such cases might especially happen when the points are selected from the regions close to the same edges or the same corners of the grid cells. It can be shown that the gridding scheme of Figure 3b is up to two-times more robust to this type of ill-configuration compared to a simple regular \(4\times 3\) grid.