This thesis uses tools from algebraic geometry to solve problems about three-dimensional scene reconstruction. 3D reconstruction is a fundamental task in multiview geometry, a field of computer vision. Given images of a world scene, taken by cameras in unknown positions, how can we best build a 3D model for the scene? Novel results are obtained for various challenging minimal problems, which are important algorithmic routines in Random Sampling Consensus pipelines for reconstruction. These routines reduce overfitting when outliers are present in image data.
Our approach throughout is to formulate inverse problems as structured systems of polynomial equations, and then to exploit underlying geometry. We apply numerical algebraic geometry, commutative algebra and tropical geometry, and we derive new mathematical results in these fields. We present simulations on image data as well as an implementation of general-purpose homotopy-continuation software for implicitization in computational algebraic geometry.
Chapter 1 introduces some relevant computer vision. Chapters 2 and 3 are devoted to the recovery of camera positions from images. We resolve an open problem concerning two calibrated cameras raised by Sameer Agarwal, a vision expert at Google Research, by using the algebraic theory of Ulrich sheaves. This gives a robust test for identifying outliers in terms of spectral gaps. Next, we quantify the algebraic complexity for notorious poorly understood cases for three calibrated cameras. This is achieved by formulating in terms of structured linear sections of an explicit moduli space and then computing via homotopy-continuation. In Chapter 4, a new framework for modeling image distortion is proposed, based on lifting algebraic varieties in projective space to varieties in other toric varieties. We check that our formulation leads to faster and more stable solvers than the state of the art. Lastly, Chapter 5 concludes by studying possible pictures of simple objects, as varieties inside products of projective planes. In particular, this dissertation exhibits that algebro-geometric methods can actually be useful in practical settings.
|Commitee:||Eisenbud, David, El Ghaoui, Laurent, Srivastava, Nikhil|
|School:||University of California, Berkeley|
|School Location:||United States -- California|
|Source:||DAI-B 78/11(E), Dissertation Abstracts International|
|Keywords:||Algebraic geometry, Chow form, Commutative algebra, Computer vision, Homotopy continuation, Minimal problems|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be