Polypols are natural generalizations of polytopes, with boundaries given by non-linear algebraic hypersurfaces.We describe polypols in the plane and in 3-space that admit a unique adjoint hypersurface and study them from an algebro-geometric perspective. We relate planar polypols to positive geometries introduced originally in particle physics, and identify the adjoint curve of a planar polypol with the numerator of the canonical differential form associated with the positive geometry.We settle several cases of a conjecture by Wachspress claiming that the adjoint curve of a regular planar polypol does not intersect its interior. In particular, we provide a complete characterization of the real topology of the adjoint curve for arbitrary convex polygons. Finally, we determine all types of planar polypols such that the rational map sending a polypol to its adjoint is finite, and explore connections of our topic with algebraic statistics.

In recent work, algebraic computational software was used to provide the exact algebraic conditions under which a six-tuple of fundamental matrices, corresponding to 4 images, is compatible, i.e., there exist 4 cameras such that each pair has the appropriate fundamental matrix. It has been further demonstrated that quadruplewise compatibility is sufficient when the number of cameras greater than 4. We expand on these prior results by proving equivalent geometric conditions for compatibility. We find that compatibility can be characterized via the intersections of epipolar lines in one of the images.

 Computer Vision is the study of how computers can understand and classify images as well as or better than humans, at a fraction of the time. A fundamental problem in this field, Structure-from-Motion, aims to build a 3D model of an object based on 2D images. Applications include self-driving cars, autonomous vehicles and visual media such as movies and video games.  

 The geometry that arises in 3D reconstruction is called Multiview Geometry, and the study of algebraic structures that arise from Multiview Geometry is called Algebraic Vision. The latter is the subject of this thesis. Our focus is on optimization problems, finding polynomials constraints and the construction of new algorithms. A main goal of this thesis is to generalize concepts and ideas in Algebraic Vision to new settings.     

 In Paper A, we investigate a classic question in Computer Vision, namely the compatibility of fundamental matrices. We prove that quadruplewise compatibility implies global compatibility. Given a sextuple of compatible fundamental matrices, there are four possible cases for the geometry of their epipoles. In each case, we provide necessary and sufficient conditions for compatibility in terms of explicit homogeneous polynomials in the fundamental matrices and their epipoles. 

 In Paper B, we build on the theory of Paper A. More precisely, we equivalently express the necessary and sufficient conditions in terms of intuitive geometrical conditions. In the process, we get simpler proofs.

 In Paper C, we consider the problem of how to best identify and filter out outliers from a given data set. A data point is an inlier if its Euclidean distance to the mathematical model is small enough. This distance is expensive to compute. In applied settings, it is efficiently approximated by the Sampson error. We provide theoretical bounds for when the Sampson error is a good approximation of the Euclidean distance, and show, via numerical experiments, new scenarios where it can be applied, such as in three-view geometry. 

 In Paper D, we study the projection of lines in 3-space onto a given set of camera planes. The closure of this projection map is a line multiview variety. Our main theorem is that a line multiview variety is cut out by the condition that the back-projected planes meet in a line if and only if all centers are pairwise distinct and no four centers are collinear. Here, smooth quadrics and their families of lines are important tools. We also study smoothness, multidegrees, and Euclidean distance degrees. 

 In Paper E, we use the theory of Cohen--Macaulay ideals to prove that under sufficient genericity, the ideal described in Paper D is the defining ideal of the line multiview variety. We compute Gröbner bases and discuss to what extent our results carry over to the case of cameras with collinear centers.   In Paper F, we solve the problem of how to do 3D reconstruction such that point and line incidence relations are preserved. In this direction, we introduce anchored multiview varieties. We describe new reconstruction algorithms based on these. On simulated data, we compare the different approaches with individual reconstruction of points and lines. Our approach yields comparable accuracy and a significant speed improvement. This improvement in speed is theoretically supported by our Euclidean distance degree computations. We make use of the observation that these anchored multiview varieties are linearly isomorphic to multiview varieties arising from the projection of points in 2-space and 1-space. 

 In Paper G, we explore the observation above from Paper F in great detail. We start by considering all possible anchored multiview varieties arising from projections of points and lines in 1, 2, and 3-dimensional projective space. We say that two such varieties are ED-equivalent if there is a linear isomorphism between them that preserves ED-critical points. This gives rise to fourteen equivalence classes; a multiview catalogue. In the case of points, we also present a study of all associated resectioning varieties. Finally, we propose conjectures for the Euclidean distance degrees of all varieties appearing in our comprehensive list.

 In Paper H, we present an algebraic study of the projection of plane curves and twisted cubics in space onto multiple images of pinhole cameras. The Zariski closure of the image of the projection of conics is called a conic multiview variety. Extending previous work for point and line multiview varieties, we make use of back-projected cones. For two views, we provide the defining ideals of conic multiview varieties. For any number of views, we state when the simplest possible set-theoretic description is achieved based on the geometry of the camera centers. Finally, we conjecture the Euclidean distance degree for the conic multiview variety given two cameras.  

 In Paper I, we introduce a generalization of multiview varieties as closures of images obtained by projecting subspaces of a given dimension onto several views, from the photographic and geometric points of view. We investigate when the associated projection map is generically injective; an essential requirement for successful triangulation. We give a complete characterization of this property by determining two formulae for the dimensions of these varieties. Similarly, we describe for which center arrangements calibration of camera parameters is possible. We determine precisely when the multiview variety is naturally isomorphic to its associated blowup, in the case of generic centers.

 At the end of this thesis, four additional papers and one extended abstract is attached. As these are not part of the Algebraic Vision story, we do not describe them here. They are included in the thesis as part of the complete collected works of the PhD candidate. 

 Datorseende är vetenskapen kring hur datorer kan förstå och klassificera bilder lika väl eller bättre än människor, på en bråkdel av tiden. Ett fundamentalt problem inom detta område är Struktur-från-Rörelse, vilket ämnar att skapa en 3D-modell av ett objekt utifrån 2D-fotografier. Tillämpningar inkluderar självkörande bilar, autonoma fordon och visuell media så som filmer och datorspel.  

Geometrin som uppstår i 3D-rekonstruktion kallas multivygeometri, och studiet av algebraiska strukturer som uppstår från multivygeometri kallas algebraiskt seende. Det senare är ämnet för denna avhandling. Vårt fokus ligger på optimeringsproblem, att hitta relevanta polynomekvationer och konstruktionen av nya algoritmer. Ett huvudmål med avhandlingen är att generalisera begrepp och idéer inom algebraiskt seende.

I Artikel A undersöker vi en klassisk fråga inom datorseende, nämligen kompatibiliteten hos fundamentala matriser. Vi bevisar att fyrfaldig kompatibilitet implicerar global kompatibilitet. Givet en sexfald av kompatibla fundamentala matriser, finns det fyra möjliga fall för geometrin hos deras epipoler. För varje fall ger vi nödvändiga och tillräckliga villkor för kompatibilitet i termer av explicita homogena polynom i de fundamentala matriserna och deras epipoler.

I Artikel B bygger vi vidare på teorin från Artikel A. Närmare bestämt uttrycker vi nödvändiga och tillräckliga villkor på ett ekvivalent sätt med intuitiva geometriska villkor. Som medföljd får vi enklare bevis.

I Artikel C undersöker vi problemet om hur man bäst identifierar och filtrerar bort avvikande data från en given datamängd. En datapunkt bör behållas om dess euklidiska avstånd till den matematiska modellen är tillräckligt litet. Detta avstånd är dyrt att beräkna. I praktiken skattas det effektivt av Sampsonfelet. Vi ger teoretiska gränser för när Sampsonfelet är en bra skattning av det euklidiska avståndet och visar, via numeriska experiment, nya scenarier där det kan tillämpas, såsom trevygeometri.

I Artikel D studerar vi projektionen av linjer i rummet på en given uppsättning kameraplan. Slutna höljet av denna projektionsavbildning är en linjemultivyvarietet. Vårt huvudteorem är att en linjemultivyvarietet skärs ut av villkoret att de bakprojicerade planen möts i en linje om och endast om alla centra är parvis distinkta och inga fyra centra ligger på en linje. Här är släta kvadratiska ytor och deras familjer av linjer viktiga verktyg. Vi studerar också släthet, multigrader och euklidiska avståndsgrader.

I Artikel E använder vi teorin om Cohen--Macaulay ideal för att under tillräckligt allmänna situationer bevisa att idealet beskrivet i Artikel D är det definierande idealet för linjemultivyvarieten. Vi beräknar Gröbnerbaser och diskuterar i vilken utsträckning våra resultat överförs till fallet med kameror vars centra ligger på en linje.

I Artikel F löser vi problemet om hur man utför 3D-rekon- struktion så att incidensrelationer mellan punkter och linjer bevaras. I denna riktning introducerar vi förankrade multivyvarieteter. Baserat på dessa beskriver vi nya rekonstruktionsalgoritmer. På simulerade data jämför vi de olika tillvägagångssätten med individuell rekonstruktion av punkter och linjer. Vårt tillvägagångssätt ger jämförbar noggrannhet och betydande förbättring av hastighet. Denna hastighetsförbättring stöds teoretiskt av våra beräkningar av euklidiska avståndsgrader. Vi utnyttjar observationen att dessa förankrade multivyvarieteter är linjärt isomorfa med multivyvarieteter som uppstår från projektionen av punkter från plan och linjer.

 I Artikel G utforskar vi den ovanstående observationen från Artikel F i större detalj. Vi börjar med att bestämma alla möjliga förankrade multivyvarieteter som uppstår från projektioner av punkter och linjer i 1, 2 och 3-dimensionella projektiva rum. Vi säger att två sådana varieteter är ED-ekvivalenta om det finns en linjär isomorfi mellan dem som bevarar ED-kritiska punkter. Detta ger upphov till fjorton ekvivalensklasser; en multivyvarietetskatalog. I fallet med punkter presenterar vi också en studie av alla associerade resektionsvarieteter. Slutligen föreslår vi förmodanden om euklidiska avståndsgrader för alla varieteter som förekommer i vår omfattande lista.

I Artikel H presenterar vi en algebraisk studie av projektionen av plankurvor och vridna kubiska kurvor i rummet på flera bilder givet hålkameror. Zariski-slutna höljet av bilden av projektionen av andragradskurvor kallas en kägelsnittsmultivyvarietet. Vi utökar tidigare arbete för punkt- och linjemultivyvarieteter genom att arbeta med bakprojicerade koner. För två vyer ger vi de definierande idealen för kägelsnittsmultivyvarieteter. För godtyckligt antal vyer anger vi när den enklaste möjliga mängdteoretiska beskrivningen uppnås baserat på geometrin hos kamerornas centra. Slutligen ger vi en förmodan om den euklidiska avståndsgraden för kägelsnittsmultivyvarieteter givet två kameror.

I Artikel I introducerar vi en generalisering av multivyvarieteter som slutna höljet av bilder som erhålls genom att projicera delrum av en given dimension på flera vyer, från fotografiska och geometriska perspektiv. Vi undersöker när den associerade projektionsavbildningen är generellt injektiv, vilket är ett avgörande krav för framgångsrik triangulering. Vi ger en komplett karaktärisering av denna egenskap genom att bestämma två formler för dimensionerna hos dessa varieteter. På liknande sätt beskriver vi för vilka arrangemang av centra som kalibrering av kameraparametrar är möjlig. Vi bestämmer exakt när multivyvarieter är naturligt isomorfa med sin associerade uppblåsning, i fallet med generiska centra.

I slutet av denna avhandling bifogas fyra ytterligare artiklar och ett utökat abstrakt. Eftersom dessa inte ingår i temat om algebraiskt seende, beskriver vi dem inte här. De inkluderas i avhandlingen som en del av den kompletta samlingen av kandidatens arbeten.

Many problems in computer vision can be formulated as geometric estimation problems, i.e. given a collection of measurements (e.g. point correspondences) we wish to fit a model (e.g. an essential matrix) that agrees with our observations. This necessitates some measure of how much an observation "agrees" with a given model. A natural choice is to consider the smallest perturbation that makes the ob-z2 servation exactly satisfy the constraints. However, for many problems, this metric is expensive or otherwise intractable to compute. The so-called Sampson error approximates this geometric error through a linearization scheme. For epipolar geometry, the Sampson error is a popular choice and in practice known to yield very tight approximations of the corresponding geometric residual (the reprojection error). In this paper we revisit the Sampson approximation and provide new theoretical insights as to why and when this approximation works, as well as provide explicit bounds on the tightness under some mild assumptions. Our theoretical results are validated in several experiments on real data and in the context of different geometric estimation tasks.

AbstractThis paper studies the problem of recovering cameras from a set of fundamental matrices. A set of fundamental matrices is said to be compatible if a set of cameras exists for which they are the fundamental matrices. We focus on the complete graph, where fundamental matrices for each pair of cameras are given. Previous work has established necessary and sufficient conditions for compatibility as rank and eigenvalue conditions on the n-view fundamental matrix obtained by concatenating the individual fundamental matrices. In this work, we show that the eigenvalue condition is redundant in the generic and collinear cases. We provide explicit homogeneous polynomials that describe necessary and sufficient conditions for compatibility in terms of the fundamental matrices and their epipoles. In this direction, we find that quadruple-wise compatibility is enough to ensure global compatibility for any number of cameras. We demonstrate that for four cameras, compatibility is generically described by triple-wise conditions and one additional equation involving all fundamental matrices.

We present an algebraic study of line correspondences for pinhole cameras, in contrast to the thoroughly studied point correspondences. We define the line multiview variety as the Zariski closure of the image of the map projecting lines in 3-space to tuples of image lines in 2-space. We prove that in the case of generic camera matrices the line multiview variety is a determinantal variety, and we provide a complete set-theoretic description for any camera arrangement. We investigate basic properties of this variety, such as dimension, smoothness, and multidegree. Finally, we give experimental results for the Euclidean distance degree and robustness under noise for the triangulation of lines.

Flat tori are among the only types of Riemannian manifolds forwhich the Laplace eigenvalues can be explicitly computed. In 1964, Milnorused a construction of Witt to find an example of isospectral nonisometricRiemannian manifolds, a striking and concise result that occupied one page inthe Proceedings of the National Academy of Science of the USA. Milnor’s example is a pair of 16-dimensional flat tori, whose set of Laplace eigenvalues areidentical, in spite of the fact that these tori are not isometric. A natural question is, What is the lowest dimension in which such isospectral nonisometricpairs exist? This isospectral question for flat tori can be equivalently formulated in analytic, geometric, and number theoretic language. We explore thisquestion from all three perspectives and describe its resolution by Schiemannin the 1990s. Moreover, we share a number of open problems.

We study the joint image of lines incident to points, meaning the set of image tuples obtained from fixed cameras observing a varying 3D point-line incidence. We prove a formula for the number of complex critical points of the triangulation problem that aims to compute a 3D point-line incidence from noisy images. Our formula works for an arbitrary number of images and measures the intrinsic difficulty of this triangulation. Additionally, we conduct numerical experiments using homotopy continuation methods, comparing different approaches of triangulation of such incidences. In our setup, exploiting the incidence relations gives a notably faster point reconstruction with comparable accuracy.

We study the problem of maximum likelihood estimation for 3-dimen-sional linear spaces of 3 x 3 symmetric matrices from the point of view of algebraic statistics where we view these nets of conics as linear concen-tration or linear covariance models of Gaussian distributions on R-3. In particular, we study the reciprocal surfaces of nets of conics which are rational surfaces in P5. We show that the reciprocal surfaces are projections from the Veronese surface and determine their intersection with the polar nets. This geometry explains the maximum likelihood degrees of these linear models. We compute the reciprocal maximum likelihood degrees. This work is based on Wall's classification of nets of conics from 1977.