10:00am - 12:00pmAlgebraic vision
Chair(s): Max David Lieblich (University of Washington, United States of America), Tomas Pajdla (Czech Technical University in Prague), Matthew Trager (Courant Institute of Mathematical Sciences at NYU)
There has been a burst of recent activity focused on the applications of modern abstract and numerical algebraic geometry to problems in computer vision, ranging from highly-optimized Gröbner-basis techniques, to homotopy continuation methods, to Ulrich sheaves and Chow forms, to functorial moduli theory. We will discuss this recent progress, with a focus on multiview geometry, both in theory and in practice.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Solving for camera configurations from pairs
Brian Osserman
University of California, Davis
We study the question of when a configuration of multiple cameras can be recovered when one has information about a subset of the pairs (given for instance as a collection of fundamental matrices). We find the minimal number of pairs which can suffice, and analyze more generally what sorts of conditions can ensure either that a given set of pairs does or does not suffice to determine the configuration. This is joint work with Matthew Trager.
Ideals of the Multiview Variety
Andrew Pryhuber
University of Washington
The multiview variety of an arrangement of cameras is the Zariski closure of the images of world points in the cameras. The prime vanishing ideal of this complex projective variety is called the multiview ideal. We show that the bifocal and trifocal polynomials from the cameras generate the multiview ideal when the foci are distinct. In the computer vision literature, many sets of (determinantal) polynomials have been proposed to describe the multiview variety. While the ideals of these polynomials are all contained in the multiview ideal, we show that none of them coincide with the multiview ideal. We establish precise algebraic relationships between the multiview ideal and these various determinantal ideals. When the camera foci are non-coplanar, we prove that the ideal of bifocal polynomials saturate to give the multiview ideal. Finally, we prove that all the ideals we consider coincide when dehomogenized to cut out the space of finite images.
Estimation under group action and fast polynomial solvers, with applications to cryo-EM
Joe Kileel
Princeton
In many applied contexts, the task is to estimate latent variables from noisy observations involving unknown rotations. One challenging example comes from cryo-electron microscopy (cryo-EM), recognized by the 2017 Nobel Prize in Chemistry, where the objective is to estimate a 3D molecule from highly noisy 2D projection images taken from unknown viewing directions.
In this talk, we introduce an abstract framework for statistical estimation under noisy group actions. We prove, for this class of problems, sample complexity relates to invariant rings and secant varieties, while method-of-moments is sample-efficient. In special cases, we find a computationally-efficient algorithm for inverting moments, using tensor decomposition and polynomial solving.
In particular, for one model of cryo-EM we present a polynomial solver for ~10000 variables running in ~2 minutes. Further, we develop a new variant of the power method for symmetric tensor decomposition, e.g. decomposing random 15^6 symmetric tensors of rank 450 in ~45 seconds. Our principled approach is validated on a real cryo-EM dataset, in the context of ab initio modeling.
Joint work with Amit Singer’s group and Afonso Bandeira’s group.