Search

A scientific paper titled "Trifocal Relative Pose from Lines at Points" co-funded by the H2020 Research and Innovation Action ARtwin (GA:856994)

We introduce an atlas of algebro-geometric objects associated with image formation in pinhole cameras. The nodes of the atlas are algebraic varieties or their vanishing ideals related to each other by projection or elimination and restriction or specialization respectively. This atlas offers a unifying framework for the study of problems in 3D computer vision. We initiate the study of the atlas by completely characterizing a part of the atlas stemming from the triangulation problem. We conclude with several open problems and generalizations of the atlas., Comment: 47 pages with references and appendices, final version

Plato’s Charmides is notable as being the only Platonic text in which Socrates admits to feeling sexual desire for a young man. This paper examines three different receptions of this text: Oscar Wilde’s 666-line poem Charmides, C. P. Cavafy’s 8-line poem In a town of Osroene (Ἐν πόλeι τῆς Ὀσροηνῆς), and Plutarch’s much earlier Life of Alcibiades. It focus on how the three authors respond to the erotic and philosophical element in the Charmides. Wilde’s 1881 Charmides provides an example of minimal textual engagement: the name Charmides is invoked solely for its connotations of young, male beauty; the tone is erotically charged but the homoerotic content is muted, and the philosophical element entirely absent. In Cavafy’s In a town of Osroene, first printed in 1917, explicit allusion to ‘the Platonic Charmides’ in the last line recasts the poem an expression of homoerotic desire, and endows its group of young men with the prestige of a Platonic gathering and Platonic love. In contrast, Plutarch’s engagement with the Charmides in his Life of Alcibiades is implicit, and depends entirely on the reader’s ability to recognise a series of detailed verbal echoes. Furthermore, while calling to mind the educational conversation with which Socrates engaged Charmides, Plutarch denies that Socrates’ motivation was sexual, and integrates allusion to the Charmides into a broader network of allusions to other passages in which Plato describes Socrates’ encounters with beautiful young men, or the ideal relationship of a mature man with a younger beloved, in which the sexual element is entirely absent. In so doing, Plutarch “corrects” Plato with Plato, and removes what had become an embarrassment in his period.

We showcase applications of nonlinear algebra in the sciences and engineering. Our review is organized into eight themes: polynomial optimization, partial differential equations, algebraic statistics, integrable systems, configuration spaces of frameworks, biochemical reaction networks, algebraic vision, and tensor decompositions. Conversely, developments on these topics inspire new questions and algorithms for algebraic geometry.

We apply numerical algebraic geometry to the invariant-theoretic problem of detecting symmetries between two plane algebraic curves. We describe an efficient equality test which determines, with "probability-one", whether or not two rational maps have the same image up to Zariski closure. The application to invariant theory is based on the construction of suitable signature maps associated to a group acting linearly on the respective curves. We consider two versions of this construction: differential and joint signature maps. In our examples and computational experiments, we focus on the complex Euclidean group, and introduce an algebraic joint signature that we prove determines equivalence of curves under this action. We demonstrate that the test is efficient and use it to empirically compare the sensitivity of differential and joint signatures to noise.

Code available at http://github.com/rfabbri/minus; International audience; We present a method for solving two minimal problems for relative camera pose estimation from three views, which are based on three view correspondences of (i) three points and one line and (ii) three points and two lines through two of the points. These problems are too difficult to be efficiently solved by the state of the art Grobner basis methods. Our method is based on a new efficient homotopy continuation (HC) solver, which dramatically speeds up previous HC solving by specializing HC methods to generic cases of our problems. We show in simulated experiments that our solvers are numerically robust and stable under image noise. We show in real experiment that (i) SIFT features provide good enough point-and-line correspondences for three-view reconstruction and (ii) that we can solve difficult cases with too few or too noisy tentative matches where the state of the art structure from motion initialization fails.

We apply numerical algebraic geometry to the invariant-theoretic problem of detecting symmetries between two plane algebraic curves. We describe an efficient equality test which determines, with "probability-one", whether or not two rational maps have the same image up to Zariski closure. The application to invariant theory is based on the construction of suitable signature maps associated to a group acting linearly on the respective curves. We consider two versions of this construction: differential and joint signature maps. In our examples and computational experiments, we focus on the complex Euclidean group, and introduce an algebraic joint signature that we prove determines equivalences of curves under this action and the size of a curve's symmetry group. We demonstrate that the test is efficient and use it to empirically compare the sensitivity of differential and joint signatures to different types of noise., Comment: journal submission of v1, 25 pages

We present a complete classification of minimal problems for generic arrangements of points and lines in space observed partially by three calibrated perspective cameras when each line is incident to at most one point. This is a large class of interesting minimal problems that allows missing observations in images due to occlusions and missed detections. There is an infinite number of such minimal problems; however, we show that they can be reduced to 140616 equivalence classes by removing superfluous features and relabeling the cameras. We also introduce camera-minimal problems, which are practical for designing minimal solvers, and show how to pick a simplest camera-minimal problem for each minimal problem. This simplification results in 74575 equivalence classes. Only 76 of these were known; the rest are new. In order to identify problems that have potential for practical solving of image matching and 3D reconstruction, we present several smaller natural subfamilies of camera-minimal problems as well as compute solution counts for all camera-minimal problems which have less than 300 solutions for generic data.

We present a complete classification of all minimal problems for generic arrangements of points and lines completely observed by calibrated perspective cameras. We show that there are only 30 minimal problems in total, no problems exist for more than 6 cameras, for more than 5 points, and for more than 6 lines. We present a sequence of tests for detecting minimality starting with counting degrees of freedom and ending with full symbolic and numeric verification of representative examples. For all minimal problems discovered, we present their algebraic degrees, i.e. the number of solutions, which measure their intrinsic difficulty. It shows how exactly the difficulty of problems grows with the number of views. Importantly, several new mini- mal problems have small degrees that might be practical in image matching and 3D reconstruction.

We consider numerical certification of approximate solutions to a system of polynomial equations with more equations than unknowns by first certifying solutions to a square subsystem. We give several approaches that certifiably select which are solutions to the original overdetermined system. These approaches each use different additional information for this certification, such as liaison, Newton-Okounkov bodies, or intersection theory. They may be used to certify individual solutions, reject nonsolutions, or certify that we have found all solutions., 21 pages. Final version accepted to JSC special issue

&nbsp

We describe, study, and experiment with an algorithm for finding all solutions of systems of polynomial equations using homotopy continuation and monodromy. This algorithm follows a framework developed in previous work and can operate in the presence of a large number of failures of the homotopy continuation subroutine. We give special attention to parallelization and probabilistic analysis of a model adapted to parallelization and failures. Apart from theoretical results, we developed a simulator that allows us to run a large number of experiments without recomputing the outcomes of the continuation subroutine., 19 pages, accepted to ISSAC 2018

Let I be a toric ideal. We say I is robust if its universal Groebner basis is a minimal generating set. We show that any robust toric ideal arising from a graph G is also minimally generated by its Graver basis. We then completely characterize all graphs which give rise to robust ideals. Our characterization shows that robustness can be determined solely in terms of graph-theoretic conditions on the set of circuits of G., Comment: 16 pages, 9 figures

We introduce a generalisation of weighted automata over a field, called polynomial automata, and we analyse the complexity of the Zeroness Problem in this model, that is, whether a given automaton outputs zero on all words. While this problem is non-primitive recursive in general, we highlight a subclass of polynomial automata for which the Zeroness Problem is primitive recursive. Refining further, we identify a subclass of affine VAS for which coverability is in 2EXPSPACE. We also use polynomial automata to obtain new proofs that equivalence of streaming string transducers is decidable, and that equivalence of copyless streaming string transducers is in PSPACE.

We study methods for finding the solution set of a generic system in a family of polynomial systems with parametric coefficients. We present a framework for describing monodromy based solvers in terms of decorated graphs. Under the theoretical assumption that monodromy actions are generated uniformly, we show that the expected number of homotopy paths tracked by an algorithm following this framework is linear in the number of solutions. We demonstrate that our software implementation is competitive with the existing state-of-the-art methods implemented in other software packages., 30 pages

International audience; Si l’on tente de dresser un tableau de la présence de la figure d’Alcibiade dans la littérature latine (des premières mentions du personnage, chez Cicéron dans ses traités ou sa correspondance, jusqu’à Pétrone et son Satyricon), il convient noter que les images romaines de l’Athénien frappent par leur caractère protéiforme, mais surtout par leur ambivalence. Alcibiade y est en effet tour à tour un personnage public (homme d’État, militaire , orateur ) et un personnage privé, enfant manipulateur face à Périclès , disciple de Socrate, musicien déçu , prompt à l’ivresse …voire une figure littéraire quelque peu scabreuse du fait de l’intertexte du Banquet platonicien. Cette diversité de la référence latine à Alcibiade s’accompagne d’un regard contrasté, qui dénote d’une forme de fascination pour le personnage : si Pline l’Ancien s’interroge sur le choix d’une statue d’Alcibiade incarnant le plus courageux des Grecs pour rendre grâce à Apollon Pythien lors de la guerre samnite, pour Cornélius Népos, l’homme se caractérise par ses excès, que ces derniers s’expriment dans les vertus ou dans les vices. Nous nous proposons donc d’étudier la construction contrastée de la figure d’Alcibiade dans la littérature latine, entre admiration et rejet, en accordant une place particulière au rôle qu’il joue en tant qu’interlocuteur de Socrate. En effet, ce sont avant tout les textes de Cicéron et de Sénèque qui donnent une profondeur au personnage d’Alcibiade : lorsque ce dernier rit face au physiognomoniste Zopyre , il souligne l’inanité de cette pratique lorsqu’elle s’affranchit du rôle joué par la volonté humaine ; lorsqu’il pleure en prenant conscience du chemin à parcourir avant d’atteindre la vertu , il incarne les tourments de l’homme effectuant les premiers pas d’une conversion philosophique. Alcibiade jouerait alors le rôle d’un révélateur des propos socratiques, tantôt exemplum à suivre, tantôt modèle rejeté.