In the field of computer vision, reconstructing a 3D scene from 2D images typically relies on a fundamental assumption: we know the camera's internal parameters and the general nature of its motion. This CVPR paper, "What Correspondences Reveal about Unknown Camera and Motion Models?", addresses a critical "chicken-and-egg" problem. To find the correct geometric relationship between two views, one needs to know the camera and motion model; yet, to identify the model, one often needs to have already solved the geometry. The authors propose a method to jointly estimate these relationships and identify the underlying models without prior knowledge.
The Causality Dilemma in 3D Vision
Classic Structure-from-Motion (SfM) pipelines usually assume a perspective pinhole camera model and general motion involving translation. However, real-world scenarios often involve different constraints. For instance, satellite imagery utilizes affine cameras, and panoramic captures involve pure rotation.
Applying a standard "Fundamental Matrix" (which assumes perspective projection and translation) to these "degenerate" cases often leads to mathematical failures or "ghost" geometries. The authors aim to break this cycle by identifying the model directly from noisy image correspondences.
Methodology: Sparse Basis Estimation
The proposed approach operates in two primary stages:
- Sparse Basis Estimation: Rather than selecting a specific model (like the 8-point algorithm) and attempting to fit data to it, the authors treat the relationship between point correspondences as an unknown set of polynomials. They utilize a Vandermonde Matrix to represent potential polynomial relationships and formulate the search as a Mixed-Integer Programming (MIP) problem. The objective is to find the sparsest set of polynomials (the "sparse basis") that explains at least 50% of the data points, solved via a Branch-and-Bound (BnB) approach.
- Model Disambiguation: Once the sparse basis is identified, its algebraic properties—such as the number of independent polynomials, their degrees of freedom, and specific matrix constraints—are analyzed. These properties act as a unique signature that maps back to specific camera types (Calibrated/Uncalibrated Perspective, Orthographic, Affine) and motion types (Full motion, Rotation, Translation) using a theoretical lookup table.
Experimental Validation and Results
The authors evaluated their method using synthetic data with varying noise and outlier levels, as well as real-world datasets like the Oxford RobotCar and TUM RGBD.
Key Performance Insights
- Robustness to Noise and Outliers: As shown in the performance metrics, the
sparse-basismethod maintains a high inlier detection rate even as pixel noise increases, performing comparably to RANSAC when the model is known (ransac-M) and significantly better when the model is unknown. - Sparsity as a Proxy for Truth: The core insight is that the simplest algebraic explanation for correspondences is typically the correct one. Models that are too complex overfit noise, while overly simple models fail to capture the data's structure.
- Real-World Motion Tracking: On the Oxford RobotCar dataset, the method successfully captured smooth transitions in camera poses. It correctly identified when a vehicle was turning versus driving straight based solely on the algebraic sparsity of point matches, a task where standard SfM pipelines often struggle without manual tuning.
Conclusion and Future Work
By moving beyond model-specific algorithms like RANSAC, this research provides a robust, model-agnostic framework for two-view geometry. While the MIP formulation is computationally intensive (NP-hard), the use of Branch-and-Bound makes it tractable for these specific geometric problems.
Future work may address the "Bas-Relief Ambiguity" inherent in certain geometries and explore higher-order polynomials to account for exotic camera distortions. Currently, the degree-2 polynomial assumption covers the vast majority of standard 3D vision models, providing a powerful tool for autonomous systems operating with unknown or changing camera configurations.
Summary updated