Separable Four Points Fundamental Matrix

Gil Ben-ArtziWACV 2021

TL;DR

This paper introduces a novel RANSAC-based method for computing the fundamental matrix by decomposing it into an epipolar homography. This approach significantly reduces the number of required RANSAC iterations by leveraging the geometric insight that four points lying on a single image line can be used to estimate the epipolar homography, a simpler model than the full fundamental matrix.

What Problem Does This Paper Address?

Estimating the fundamental matrix, a crucial component for understanding epipolar geometry between two uncalibrated cameras, is often challenged by the presence of noisy or mismatched point correspondences. Standard RANSAC-based methods require a significant number of iterations to achieve robust results, especially with high outlier rates. While minimal solvers exist that reduce the number of points needed for a hypothesis (e.g., 5 or 7 points), this paper aims to further reduce the computational cost by decreasing the number of hypotheses evaluations within RANSAC, even when dealing with a large number of correspondences.

Methods

The core of the proposed method lies in a two-step RANSAC process:

  1. Epipolar Homography Estimation: Instead of directly estimating the 7-parameter fundamental matrix, the paper first focuses on estimating the epipolar homography. This is achieved by identifying image lines that contain at least four putative correspondences. Using these line segments, the epipolar homography is computed. This step is presented as a more robust and efficient initial estimation.
  2. Fundamental Matrix Refinement: Once the epipolar homography is robustly estimated, the method proceeds to estimate the fundamental matrix. This is done by sampling additional correspondences and using a standard algorithm (either the 7-point or 8-point algorithm), but with a significantly reduced number of required iterations due to the prior estimation of the homography.

The paper also introduces a novel way to find corresponding lines across images using a Hough transform and a shared accumulator, which allows for parallel processing and efficient matching of lines with a high number of correspondences.

Datasets

The paper evaluates its approach on the following real-world datasets:

  • Strecha dataset: Includes ground truth camera poses and reconstructions.
  • Tower of London sequence (Flickr dataset): Images captured in diverse urban outdoor scenes with varying camera positions.
  • Family sequence (Tanks and Temples dataset): Features wide-baseline camera poses and medium-sized images from urban yard scenes.

For the Flickr and Tanks and Temples datasets, the authors sampled 2000 image pairs with at least 20 matches and a symmetric epipolar distance of less than 1 pixel to establish ground truth fundamental matrices using COLMAP.

Key Insights and Ideas

  • Geometric Decomposition: The fundamental matrix can be effectively decomposed into an epipolar homography, which is a simpler model and can be estimated more efficiently.
  • Line-based Correspondences: Leveraging points that lie on image lines provides a strong geometric constraint that can be exploited for robust initial estimation.
  • Reduced RANSAC Iterations: By first estimating the epipolar homography (a 3-parameter model), the subsequent estimation of the fundamental matrix (a 7-parameter model) requires significantly fewer RANSAC iterations.
  • Parallel Line Matching: The proposed Hough transform-based line matching allows for independent processing of images, enabling parallel implementation.

Key Results

  • Theoretical Reduction in RANSAC Iterations: The paper theoretically shows that its approach can drastically reduce the number of RANSAC hypotheses evaluations compared to standard 7-point or 8-point algorithms, especially at higher outlier rates. For example, at a 60% outlier rate, the 7-point algorithm requires approximately 178 iterations with their method, compared to potentially millions for standard RANSAC.
  • Practical Efficiency: Experimental results demonstrate that the proposed method achieves comparable or better accuracy than existing methods while requiring fewer RANSAC iterations.
  • Robustness: The method is shown to be robust across various datasets with different scene structures and image distances.
  • Line Quality: The method successfully matches lines with a high number of inliers and low homography error, with 99% of inliers having a homography error below 0.5.

Limitations and Future Work

  • Requirement for Line Correspondences: The core assumption of the method is the existence of at least four correspondences on an image line. If such configurations are rare, the advantage of the method diminishes.
  • Failure Cases: The paper acknowledges that in cases with a very small number of inliers, the method can fail to recover the homography.
  • Future Work: The authors suggest that their approach is well-suited for Structure from Motion (SfM) pipelines and could be further integrated for improved efficiency. The paper also implicitly suggests exploring other geometric decompositions or constraints that could further reduce computational complexity.

Summary updated

BibTeX
@inproceedings{benartzi2021separable,
  author = {Gil Ben-Artzi},
  title = {{Separable Four Points Fundamental Matrix}},
  booktitle = {IEEE/CVF Winter Conference on Applications of Computer Vision},
  year = {2021},
}
Figure