Problems in Algebraic Vision

Thesis (Ph.D.)--University of Washington, 2016-08

This thesis studies several fundamental mathematical problems that arise from computer vision using techniques in algebraic geometry and optimization. Chapters 2 and 3 consider the fundamental question of the existence of a fundamental (resp. essential) matrix given $m$ point correspondences in two views. We present a complete answer for the existence of fundamental matrices for any value of $m$. We disprove the widely held beliefs that fundamental matrices always exist whenever $m \leq 7$. At the same time, we prove that they exist unconditionally when $m \leq 5$. Under a mild genericity condition, we show that an essential matrix always exists when $m \leq 4$. We also characterize the six and seven point configurations in two views for which all matrices satisfying the epipolar constraint have rank at most one. Chapter 3 discusses the existence of an essential matrix when $m=6, 7$ via Chow forms. We shift gears in Chapters 4 and 5 to study the problem of minimizing the Euclidean distance to a set which arises frequently in various applications, and in particular in computer vision. When the set is algebraic, a measure of complexity of this optimization problem is its number of critical points. We provide a general framework to compute and count the real smooth critical points of a data matrix on an orthogonally invariant set of matrices, for instance, the set of essential matrices. The technique relies on ``transfer principles'' that allow calculations to be done in the space of singular values of the matrices in the orthogonally invariant set. As a result, the calculations often simplify greatly and yield transparent formulas. We illustrate the method on several examples, and compare our results to the recently introduced notion of Euclidean distance degree of an algebraic variety. In contrast to Chapter 4, Chapter 5 considers the complex regular critical points of the Euclidean distance problem. We show that the Euclidean distance degree of an orthogonally invariant matrix variety equals the Euclidean distance degree of its restriction to diagonal matrices. We illustrate how this result can greatly simplify calculations in concrete circumstances. Chapter 6 studies critical points for two-view triangulation. Two-view triangulation is a problem of minimizing a quadratic polynomial under an equality constraint. We derive a polynomial that encodes the local minimizers of this problem using the theory of Lagrange multipliers. This offers a simpler derivation of the critical points that are given in Hartley-Sturm [36]. Finally, Chapter 7 studies the connection between the existence of a projective reconstruction and the existence of a fundamental matrix satisfying the epipolar constraints.