Keywords

1 Introduction

The fundamental matrix describes the relationship between two images of the same scene taken from two different viewpoints, namely, the epipolar geometry. The epipolar constraint is the only geometric information could available from two uncalibrated images [1]. Therefore, precise estimation of fundamental matrix is one of the most crucial steps in many computer vision applications such as 3D reconstruction, visual navigation, stereo vision and motion segmentation [2, 3].

The fundamental matrix is most of the time evaluated from point correspondences. However, the point correspondences inevitable contain noise and outliers, thus affect the precise of the fundamental matrix. Noise calls for estimating fundamental matrix over the largest possible set of correspondences but outliers make it awkward. In recent years, it has been done a lot of work on how to accurately and robustly estimate fundamental matrix. From these studies, it showed that the main difficulty of fundamental matrix estimation is how to quick and accurately eliminate the outliers. The robust algorithms are used to solve this problem. These methods are based on random selecting the points, so the quality of the sampling has a direct impact on the precise of the fundamental matrix. Previous studies showed that the evenly distribution can better represent the variation of the image due to camera motion. So it is important to select a better inlier set for a more precise fundamental matrix. However, only a few studies have taken into account the distribution of the inlier set when estimating the fundamental matrix [4, 5].

Various properties and calculation methods for the fundamental matrix have been studies in the last two decades. They can be roughly divided into three different approaches: the linear, the iterative and the robust [6]. The linear methods [6, 7] estimate the fundamental matrix by using seven or eight corresponding points. With more than eight points, a least-squares technique is used. The advantages of the linear methods are its simplicity for implementation and computational efficiency, but they are very sensitive to noise. In order to obtain a better result, the iterative and robust algorithms have to be considered. The iterative approach [1, 3] has been proposed to minimize the sum of geometric distances between the points and the corresponding epipolar lines, or the gradient-weighted epipolar errors. Although iterative method is direct relation to a meaningful geometric measure and the result is more accurate than linear method, it time consuming and cannot cope with potential outliers. The third one are the robust methods, they can alleviate the effect of outliers to the fundamental matrix estimation. The three representative robust methods are M-Estimators, LMedS and RANSAC [8, 9]. Robust methods can deal with the noise and false point correspondences, but they require much more computational time and they still have their limitations. In addition, in recent years, the genetic algorithm was introduced to the fundamental matrix estimation [10, 11]. This could improve the accuracy of the result, but the genetic algorithm is time consuming and thus result the algorithm need more time.

This paper present a novel method to estimate the fundamental matrix, it based on the RANSAC method and consider the inlier set distribution. Traditional RANSAC method selects the biggest consensus set of inliers to estimate fundamental matrix, no previous methods have consider whether such a choice really is the best. In our algorithm, we select these inlier sets that contain a large number of inliers to construct a candidate set. Then calculate the mean of the epipolar distances and the density of the inlier sets in the candidate set. Finally choose the minimum mean of the epipolar distances which need to meet the condition that it distribution should better than the one that has the largest number of inliers. After selecting the proper inlier set, we use the M-Estimators method to estimate the fundamental matrix.

The rest of this paper is organized as follows. Section 26.2 introduce the epipolar geometry and review the traditional algorithms for fundamental matrix estimation. Section 26.3 we introduce the density of the inlier set and the strategy of the proper inlier set selection. In Sect. 26.4, we describe the proposed algorithm for fundamental matrix estimation. Some experiment results for synthetic and real scenes are given in Sect. 26.5. Finally, the conclusion is described in the last section.

2 Point Density and Proper Inlier Set Selection

2.1 Point Density

Previous studies show that the evenly distributed point set is effective for the fundamental matrix estimation [4, 5]. This is mainly due to the fundamental matrix contains the relative orientation and position between two cameras, so the inlier set should reflect the variation of the images. Seo and Hong et al. proposed that the standard deviation of the point density in sub-regions and an entire image can be used to evaluate whether the inlier set is evenly distributed [5]. According the number of the inliers, the image is divided into several uniform sub-regions by Eq. (26.1).

$$ W_{s} = W/int\left( {\sqrt N } \right),\;H_{s} = H/int\left( {\sqrt N } \right) $$
(26.1)

where W s and H s denote the width and the height of the sub-region, N is the number of the inliers, W and H are the width and height of the image. After divided the image into sub-regions, then calculate the number of the sub-regions and the inliers in each sub-regions, respectively using N s and P si denote it. At last, compute the standard deviation of the point density by Eq. (26.2)

$$ \sigma_{p} = \sqrt {\frac{1}{{N_{s} }}\sum\nolimits_{i = 1}^{{N_{s} }} {\left( {P_{si} - \frac{N}{{N_{s} }}} \right)^{2} } } $$
(26.2)

2.2 Proper Inlier Set Selection

The traditional RANSAC method selects the biggest consensus set of inliers to estimate the fundamental matrix. But this selection scheme always does not guarantee the result is the best one. During the experiment, we found that sometimes using these inlier sets which are contain less number of inliers than the largest one could obtain better results. So, if the proper inlier selected satisfy the following two conditions: the first condition is that its standard deviation of the point density should not larger than the one which has the largest number of inliers; the other condition is that the average geometry distance should be the minimum one, we can achieve a more precise estimation of the fundamental matrix.

In order to show whether this hypothesis is correct, we use the simulated data which are provided by Armangue and Salvi [6] to test it. The simulated data contains 125 pairs of points. We added the random noise and the percentage of mismatched data in it. Using the vector (a, b) to denote the noise is a Gaussian distribution N(0, a) and the percentage of the mismatched data is b. After sometimes of random sampling, we choose these sets which should contain large number of inliers. Among these sets, the largest number should have 10 % more points than the one which has the least numbers. Then calculate the fundamental matrix and the average geometry distance. At last select the inlier set which should satisfy above conditions. Table 26.1 shows the experiment results.

Table 26.1 The results under different noise levels and different percentages of mismatched
Full size table

From Table 26.1 we can see that, there are a total of nine groups of data, except the one which contain no noise and mismatched data, due to all points in this group are inliers, so the selected set contains all the points. Among the other eight groups, only 50 % of the results choose the largest number of consensus as the proper inlier set, the rest 50 % select the other set as the proper inlier set. Both the density and the average distance are better than the traditional selection. So we can conclude that select the proper inlier set can obtain a more precise result.

3 Proposed Fundamental Matrix Estimation Algorithm

Because using the traditional RANSAC algorithm always does not guarantee the result is the best one, we propose a new algorithm to solve this problem. Due to the point density has an important influence on the fundamental estimation, so the proposed algorithm considers these factors when selecting the inlier set. The basic idea of the proposed algorithm is as follows: at first randomly selecting some subsets to estimate the fundamental matrix and statistical the number of inliers. Then choose some sets which have large number of inliers to calculate the point density. The range of the candidate set can be determined by the number of the inliers, in the range, the largest number of inliers should have 10 % more points than the least one. Then select inlier set use the strategy that was proposed above. At last use the M-Estimators method to estimate the fundamental matrix based on the selected inlier set.

The complete procedure of the proposed method is summarized as follow:

  1. (1)

    Select a random sample of eight point correspondences and estimate the fundamental matrix by using the normalized eight-points algorithm. Then compute the distance of point to its epipolar line for each point correspondence and statistical the number of inliers, at the same time record the average distance.

  2. (2)

    Repeat (26.1) for K times and store fundamental matrix, the number of inliers and the average distance.

    $$ {\text{K}} = \log \left( {1 - P} \right)/\log \left( {1 - \left( {1 - \varepsilon } \right)^{\gamma } } \right) $$
    (26.3)

    where P is the probability that these points are the inliers in sampling γ points at K times, ε is the ratio of the outlier to the entire set.

  3. (3)

    Select some inlier sets to construct a candidate inlier set.

  4. (4)

    Compute the standard deviation of point density of the selected inlier sets.

  5. (5)

    Select the inlier set by using the method that proposed above as the proper inlier set.

  6. (6)

    Re-estimate the fundamental matrix from the proper inlier set by using the M-Estimators algorithm.

4 Experimental Results and Discussion

In this section, we show some experimental results of the proposed method. We compare it with the results in the survey by Armangue and Salvi [6]. The test data that used in our method are also provided by them, it includes synthesis data and real image data.

First of all, Table 26.2 gives the result of the experiment on the simulation data. From the table we can see that except the proposed algorithm, the LMedS method can provide better result than others. But compared with our method, the result that obtained by our method are better than the LMedS algorithm. So, we can conclude that our proposed method can provide precise fundamental matrix under different levels of noise and different percentages of mismatched.

Table 26.2 Average distances under different noise and percentage of mismatched (unit: pixel)
Full size table

We choose four real images to test our algorithm. The average distances of the four data sets are summarized in Table 26.3. Figure 26.1 gives the epipolar lines of the point correspondences computed from the fundamental matrix estimated by the proposed algorithm. It is obvious from Table 26.3 that our method outperforms the others.

Table 26.3 Average distances of the real images (unit: pixel)
Full size table
Fig. 26.1
figure 1

The epipolar lines of the inliers computed by the proposed method for real images

Full size image

From the experiment results of the simulate data sets and the real images sets, we can conclude that the proposed algorithm can select the proper inlier set to estimate the fundamental matrix and the precise of the result is better than the other algorithms.

5 Conclusions

In this paper, we proposed a precise fundamental matrix estimation algorithm. The proposed algorithm takes into account the average distance of the points to its epipolar lines and the distribution of the inlier set to select the proper inlier set. The traditional RANSAC algorithm choose the set that has the biggest number of inliers to estimate the fundamental matrix, but the experimental results show that this select strategy does not always guarantee a precise solution. Compared with the traditional RANSAC algorithm, our algorithm select the inlier set is better than the traditional one. Experimental results on synthetic and real images show that our algorithm can obtain a more precise fundamental matrix. This method can be used in the further work such as camera calibration and 3D scene reconstruction.