Special Seminar in Computing & Mathematical Sciences
October 27, 2016
Using Algebraic Geometry for Computer Vision
In computer vision, 3D reconstruction is a fundamental task: starting from photographs of a world scene, taken by cameras with unknown positions and orientations, how can we best create a 3D model of that world scene? Algorithms that do this built Street View (Google) and are instrumental in autonomous robotics.
In 2004, David Nister (Tesla) used Grobner bases to build a solver for robust reconstruction given just two photographs. This is a key routine in much larger-scale reconstructions today.
In this talk, I will discuss reconstruction given three photographs, where efforts to replicate Nister have so far proven elusive. My approach relies on applied algebraic geometry. In particular, I shall introduce an algebraic variety whose points are 3x3x3 tensors in correspondence with configurations of three calibrated cameras. Special linear sections of this variety recover camera configurations from image data. The main result is the determination of the algebraic degree of minimal problems for this recovery. These comprise interesting enumerative geometry problems; the solution is by way of homotopy continuation calculations.
Special Seminars in Computing + Mathematical Sciences