Abstract
The field of computer vision studies how computers can gain understanding from images and videos, similar to human cognitive abilities. One of the classical challenges is to reconstruct a 3D object from images taken by several unknown cameras. While the resulting questions in multiview geometry have a long history in computer vision, recent years have seen a confluence with ideas and algorithms from algebraic geometry.
Introduction
The core challenge in computer vision is 3D reconstruction: recovering the shape of a 3D object and the positions of the cameras that photographed it using only 2D images. While engineering solutions often rely on heuristics and optimization, this work explores the underlying algebraic complexity of these tasks. Specifically, it focuses on triangulation—finding the most likely 3D point from noisy 2D measurements—and reconstruction from unknown cameras, identifying "minimal problems" where a finite number of solutions exist.
Theoretical Framework: Algebraic Vision
Computer vision problems can be framed through the lens of Multiview Varieties. A central concept is the Joint Camera Map ($\Phi$), a mathematical function that maps 3D points and camera configurations to their 2D image coordinates. The closure of the image of this map is the multiview variety.
Key tools in this framework include:
- Euclidean Distance (ED) Degree: Used to measure the complexity of triangulation. It represents the number of complex critical points of the distance function from a noisy measurement to the multiview variety.
- Grassmann Tensors: Generalizations of the fundamental matrix into trifocal and quadrifocal tensors, representing the multilinear equations defining the multiview variety in higher dimensions.
- Gröbner Bases: Computational tools used to solve the systems of polynomial equations arising in reconstruction problems.
Experimental Illustration: The Dinosaur Data Set
The theoretical concepts are demonstrated using the Dinosaur Data Set from the Visual Geometry Group at the University of Oxford. This dataset consists of 36 views of a dinosaur model, comprising 4,983 3D points.
The authors use this data to illustrate 3D triangulation from randomly chosen cameras using homotopy continuation methods, bridging the gap between abstract algebra and practical vision tasks.
Key Insights and Results
Triangulation and Complexity
Triangulation is mathematically equivalent to finding the closest point on an affine multiview variety. The "hardness" of this task is quantified by the variety's ED degree. For $m$ cameras, the ED degree follows a cubic polynomial: $\frac{9}{2}m^3 - \frac{21}{2}m^2 + 8m - 4$. Specific degrees for $m=2$ to $7$ cameras are 6, 47, 148, 336, 638, and 1081, respectively.
Minimal Reconstruction Problems
The paper identifies the number of points needed for a finite set of solutions in reconstruction:
- Uncalibrated (Projective) Cameras: 7 points are required, yielding 3 solutions.
- Calibrated Cameras: 5 points are required, yielding 20 solutions. This is explained by the Essential Variety ($\mathcal{E}$), which has a degree of 10, combined with a two-to-one mapping.
Limitations and Future Directions
While algebraic degrees quantify the number of solutions, the condition number—measuring sensitivity to noise—remains a critical area for future research. Current theory does not fully account for the specific linear spaces encountered in vision. Additionally, while algebraic methods assume clean data, real-world "outliers" (incorrectly matched points) require robust statistical methods like RANSAC. Integrating algebraic rigor with robustness to outliers remains an open challenge.
Summary updated