Minimal Problems in Computer Vision
- Kathlén Kohn (KTH Royal Institute of Technology, Stockholm)
A well-studied problem in computer vision is ""structure from motion"", where 3D structures and camera poses are reconstructed from given 2D images taken by the unknown cameras. The most classical instance is the 5-point problem: given 2 images of 5 points, the 3D coordinates of the points and the 2 camera poses can be reconstructed. In fact, given 2 generic images of 5 points, this problem has 20 solutions (i.e., 3D coordinates + 2 camera poses) over the complex numbers. Reconstruction problems which have a finite positive number of solutions given generic input images, such as the 5-point problem, are called ""minimal"". These are the most relevant problem instances for practical algorithms, in particular those with a small generic number of solutions. We formally define minimal problems from the point of view of algebraic geometry. Our algebraic techniques lead to a classification of all minimal problems for point-line arrangements completely observed by any number of cameras. We compute their generic number of solutions with symbolic and numerical methods. This is joint work with Timothy Duff, Anton Leykin, and Tomas Pajdla.