Applied Algebra Seminar: Using algebraic geometry for computer vision

Seminar | January 26 | 5:15-6:15 p.m. | 891 Evans Hall

 Joe Kileel, University of California, Berkeley

 Department of Mathematics

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 $3\times 3 \times 3$ 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.