I have made an investigation into the epipolar geometry connected to the robust matching and how it affects the final reconstruction. The result suggests that there is a probability for the robust matching to include false inliers which will not be excluded further down the pipeline. The result applies to tracks with a length of two when growing a reconstruction by resection and is therefore certainly an edge case. All tests have been run using the default configuration values and SIFT features for the Berlin data set.
RANSAC Fundamental matrix estimation
When running the RANSAC fundamental matrix estimation any symmetric match satisfying the epipolar geometry will be regarded as an inlier. To get an idea of the probability of false inliers the estimation can be run many times. After each run a homography can be estimated and matches whose mapping error are above a certain threshold can be chosen as false inliers.
The following shows the result when running the fundamental matrix estimation 1000 times for the symmetric matches of images 01.jpg and 03.jpg. Fundamental matrix inliers with homography mapping error larger than a threshold of 0.3 are plotted with red on top of an example set of green inliers. Below, the epipolar lines and epipoles for all estimated fundamental matrices where a false inlier was included are shown. The false inlier observations are also plotted:
The homography was calculated using the default config threshold of 0.006. The number of false inliers for 1000 runs where 397 and the number of times at least one false inlier appeared where 354.
The following match was chosen for further studies:
Specifically, the results for the feature point in the right image, 03.jpg, will be studied in more detail.
Inlier probability when shifting coordinates
To get an idea of the influence of the position of the match in an area close to the epipolar line the observation coordinates for one of the images can be shifted before fundamental matrix estimation.
The observation coordinates for the image on the left above, 01.jpg, have been kept fixed and the coordinates for the image on the right, 03.jpg, have been moved. For each new point correspondence the fundamental matrix estimation have been run 100 times and the probability for each point correspondence to be an inlier of the estimation can be seen below. Each row consists of 100 points with about 10 pixels between each point. The colors correspond to the following probabilities:
- Black: < 0.02
- Blue: < 0.05
- Magenta < 0.1
- Red: < 0.15
- Yellow: < 0.25
- White: > 0.25
The same probabilities as a bar plot without the underlying image:
It can be seen that the probability peeks with a probability of almost 1.0 around the true matching point. Along the epipolar line the probability is more uniform and broader without any peaks.
Choosing the row of points containing the original observation the result is shown below:
As a ar plot:
The original point corresponds to the bar at position 46. It can be seen that the probability is quite stable between bar 30 and 80 with the probability mostly in the interval [0.05, 0.1]. These bars correspond to a width of about 500 pixels.
Reconstruction inlier probability
Continuing with the row containing the original observation point, it is interesting to determine the probability for each point to be included in the final reconstruction given that it has been included in the robust matching and therefore the tracks. To do this a complete matching for all images can be performed in a loop until the chosen correspondence is included. After that a complete reconstruction for the matches (and therefore tracks) including the false inlier match can be performed a number of times. It can then be verified how many times the track were included in the final reconstruction.
To do this the matching was run 100 times for each point. If the correspondence were included for one of the matching iterations, the matching was stopped and 100 reconstructions for that match set were run. If the correspondence were not included after 100 matching iterations no reconstructions were run. When running the reconstruction the image pair 01.jpg - 02.jpg were always chosen as the initial image pair by the bootstrapping which means that the result of the test only apply to growing a reconstruction. No tests have been performed on the false inlier probability for the initial two view reconstruction.
The results are shown below with the colors corresponding to the following probabilites:
- Black: < 0.01
- Blue: < 0.1
- Magenta < 0.2
- Red: < 0.3
- Yellow: < 0.4
- White: > 0.4
As a bar plot:
It can be seen that the probability is in the interval [0.2, 0.65] for the bars at positions from 30 to 43 which corresponds to a width of 130 pixels. The probability for the original observation (the bar at position 46) is a little less. Most of the points of correspondences with bars at positions 0-20 and 80-100 were not included by the matching and therefore the reconstruction were not run for theses points.
The points with bars at postion 27, 28 and 32 were included in a matching iteration. These points and the peaks for points at positions 61 and 70 suggest that the reconstruction inlier probability is largely affected by the rest of the included matches. The most important factor along the pipeline is the result of the resection algorithm since that determines whether the triangulation of the false match will succeed. The result indicate that the resection is favorable for the points corresponding to bars at poistion 30 - 43 but that the instability mentioned above can cause unexpected peaks and lows.
Visualization of included false inlier
Using a reconstruction where the original observation was included the result can be visualized.
The epipolar geometry for the match based on the reconstruted camera matrices is shown below. It can be noted that the point for image 03.jpg is 57 pixels from the epipolar line whereas the reprojection error is only 1.3 pixels. This suggests that once the match is included in the resection the bundle adjustment will tend to minimize the reprojection error regardless of the actual epipolar geometry.
The track rays:
From another angle:
The image below shows the meshed reconstruction for image 01.jpg:
The meshed reconstruction for 03.jpg:
The false inlier match is clearly visible as the conic to the point closest to the camera for 03.jpg in the images above. The result when viewing the image from the position of the camera for 03.jpg is satisfying because of the epipolar geometry:
It is only when navigating to and from the images with the false inlier that the conic is visible and the behavior is non perfect. Below is a transition from 02.jpg to 03.jpg:
Summary
- This test only applies to tracks of length two. For tracks including a false robust match with more than two connected images the probability of inclusion in the reconstruction will be considerably lower since the epipolar geometry must be satisfied for all correspondences during triangulation.
- Only false robust matches for images used when growing reconstructions have been tested. When doing large reconstructions, a large part of the images will be included through resection so this is the most probable way and therefor the most important to test.
- The reconstruction is also very small. No tests have been conducted on a reconstruction with a large amount of images. The statistics for the number of tracks that have a length of two in larger reconstructions is also important.
- The probabilty of inclusion for points on the row containing the original observation was around 0.05 for a width of 500 pixels. Once included in the matches the probability was shown to be up to 0.6 for an interval of 150 pixels. The combined probability is at most 0.03 for this particular correspondence. While this probability is quite small, with a large amount of images it will certainly happen from time to time.
- No complete tests have been carried out with other feature types than SIFT but running the initial fundamental matrix estimation test indicates that similar false inliers arises, although not with the same frequence as for SIFT.
- The test used only a false inlier for which the correspondance was clearly false. False inliers that are closer to the true point correspondence can also exist.
Conclusion
While the robust matches are robust in an epipolar sense they are maybe not robust enough in a general reconstruction sense if having a small probability of false inliers is seen as a problem. The result is an edge case but the knowledge of it can maybe be good for the understanding of certain results.
The code (which is very specific to the chosen correspondence) is available on a branch. It is not intended to be PR-able...
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent