Fundamental matrix from optical flow: optimal computation and reliability evaluation

Kenichi Kanatani, Yoshiyuki Shimizu, Naoya Ohta, Michael J. Brooks, Wojciech Chojnacki, Anton van den HengelJ. Electronic Imaging 2000 · DOI

TL;DR

This paper introduces a statistically optimal method for computing the "flow fundamental matrix" from optical flow data, which is crucial for 3D scene reconstruction. The method addresses noise in optical flow measurements and provides a theoretical accuracy bound, demonstrating that their algorithm achieves near-optimal performance.

What Problem Does This Paper Address?

Extracting 3D information from motion sequences is a fundamental problem in computer vision. Two main approaches exist: using point correspondences and using optical flow. Optical flow, representing the instantaneous velocity field of image points, offers a direct way to compute camera motion and 3D structure. However, optical flow estimation is inherently noisy due to approximations in algorithms like the gradient constraint. This noise degrades the accuracy of subsequent 3D reconstruction. This paper focuses on improving the accuracy of a specific geometric structure derived from optical flow, the "flow fundamental matrix," by developing a statistically optimal method that accounts for noise and provides a reliability estimate.

Methods

The paper proposes a two-stage algorithm for computing the flow fundamental matrix:

  1. Renormalization: This stage estimates the flow fundamental matrix without strictly enforcing the "decomposability condition" (a constraint related to the epipolar geometry). It uses a technique called renormalization, which iteratively refines an initial estimate by removing statistical bias introduced by noise. This process aims to find an estimate that is statistically close to the true value, even in the presence of noise.
  2. Optimal Correction: In the second stage, the algorithm imposes the decomposability condition on the result from the renormalization stage. This is done by finding the "nearest" matrix that satisfies the condition in a statistically optimal sense, using eigenvalues and eigenmatrices derived from the previous step. This ensures the computed matrix adheres to the underlying geometric constraints of optical flow.

A key contribution is the derivation of a theoretical accuracy bound for the flow fundamental matrix estimate under a specific noise model (independent, Gaussian, potentially anisotropic noise). The algorithm is designed to approach this bound.

Datasets

The paper uses simulated datasets for evaluation. Specifically, it generates synthetic images of a 3D environment with grid patterns and adds Gaussian noise to simulate real-world conditions. It also evaluates the method on two real-image examples: one with large displacements of salient feature points and another with optical flow detected by a conventional gradient constraint method.

Key Insights and Ideas

  • Flow Fundamental Matrix: The paper formalizes the concept of a "flow fundamental matrix," analogous to the fundamental matrix in stereo vision, which captures the epipolar geometry of optical flow.
  • Noise Model: The authors explicitly model noise as independent, Gaussian, and potentially anisotropic, which is more general than previous assumptions.
  • Theoretical Accuracy Bound: Deriving a theoretical lower bound on the accuracy of the flow fundamental matrix estimate is crucial. It provides a benchmark against which any algorithm's performance can be objectively measured.
  • Two-Stage Approach: The separation into renormalization (for initial estimation) and optimal correction (for enforcing geometric constraints) is a robust strategy for handling noisy data and complex constraints.
  • Reliability Evaluation: The algorithm not only computes the matrix but also provides a quantitative measure of its reliability, which is essential for downstream 3D reconstruction tasks.

Key Results

  • The proposed algorithm's estimated errors closely match the theoretical lower bound derived for the root-mean-square error of the flow fundamental matrix.
  • The algorithm's solutions are shown to be statistically superior to those obtained by a standard least-squares method, particularly in terms of avoiding statistical bias.
  • The method successfully computes epipoles and epipolars, and their uncertainties are evaluated, demonstrating the algorithm's ability to quantify reliability.
  • The algorithm is available as a public-domain C++ program, facilitating its adoption by the research community.

Limitations and Future Work

  • Noise Model Assumption: While the noise model is more general than some previous work, it still assumes Gaussian noise. Performance with significantly non-Gaussian noise might differ.
  • Degenerate Configurations: The paper notes that the flow fundamental matrix is not uniquely defined for degenerate configurations (e.g., zero camera translation or all points on a critical surface). The program issues a warning in such cases.
  • Computational Cost: The paper acknowledges that achieving near-optimal accuracy comes at a higher computational cost compared to simpler methods like least-squares.
  • Future Work: The authors suggest that the reliability evaluation is crucial for practical applications, implying that further work could focus on integrating this reliability measure more deeply into 3D reconstruction pipelines. The availability of the code suggests future work could involve applying it to a wider range of real-world scenarios.

Summary updated

BibTeX
@article{kanatani2000fundamental,
  author = {Kenichi Kanatani and Yoshiyuki Shimizu and Naoya Ohta and Michael J. Brooks and Wojciech Chojnacki and Anton van den Hengel},
  title = {{Fundamental matrix from optical flow: optimal computation and reliability evaluation}},
  journal = {J. Electronic Imaging},
  year = {2000},
  doi = {10.1117/1.482739},
}
Figure