CH3: Multiview geometry for ophthalmic surgery simulation

This research is carried out in the framework of Matheon supported by Einstein Foundation Berlin

Meeting picture

Project Members

Project Head: Michael Joswig
Research Staff: André Wagner

Cooperation

Internal: Bernd Sturmfels Einstein Visiting Fellow
Roland Hildebrand SE7
Volker Mehrmann SE1
Martin Skutella, Nicole Megow, Julie Meißner MI1
External: Sameer AgarwalGoogle Inc.
Rekha R. ThomasU Washington
Xi WangTU Berlin
VRmagic Holding AG
Imaginary

Events

Oct. 8-9, 2015 Meeting on Algebraic Vision 2015, Berlin
Jan. 28-30, 2016 7th polymake Conference and Developer Meeting, Berlin

Support

ECMath - Einstein Center for Mathematics Berlin

ECMath Matheon

Background

A fundamental problem in machine vision asks to generate geometric information about a scene in 3D-space from several camera images. At the core of most applications is the innocent looking problem of identifying points seen from different cameras. For this it is standard to employ linear algebra and projective geometry techniques which go by the names of multiview geometry or epipolar geometry. Typical challenges include imprecision due to less than perfect camera calibration or (partial) camera occlusion as well as the general speed of computation. The latter is particularly important for real-time augmented reality applications. It was the idea of Heyden and Åström to describe the space of pictures seen from more than one camera as an algebraic variety. More recently, this was modified and extended by Aholt, Sturmfels and Thomas. Especially Aholt, Agarwal and Thomas then showed that it is possible to approximate the Euclidean distance of noisy image points to the multiview variety by a quadratically constrained quadratic program. In contrast to more elementary techniques from computer vision the sketched approach is somewhat involved. The overall idea is to employ this much deeper geometric analysis of the picture space to allow for a profound computational pre-processing. This should be useful for careful planning of the positioning of the cameras for specific setups as well as a reduced computational effort for subsequent real-time applications.

Meeting picture Meeting picture

Goals

This project aims to solve a multitude of different questions relating algebra and computer vision. It should carry out a complete analysis of the 8-point-algorithm and develop new methods using real algebraic geometry combined with numerical linear algebra to reduce noise in reconstruction problems from computer vision. The key goals are:

  • forward and backward error analysis of the 8-point-algorithm
  • a classification of robust marker configurations for a more flexible positioning of markers
  • simplified camera calibration using algebraic properties of the marker configuration
  • Highlights

    We were able to determine the set-theoretical description of the rigid multiview variety. This extends the study of the multiview variety (which parameterizes the pictures of a single point on several cameras) to the setting of a pair of points at a given distance. Our results generalize to other algebraic varieties naturally arising in computer vision.

    Rigid Points

    Journal Publications

  • X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Combinatorial simplex algorithms can solve mean payoff games, SIAM J. Opt., 24(4):2096–2117, 2014.
  • X. Allamigeon, P. Benchimol, S. Gaubert, M. Joswig, Tropicalizing the simplex algorithm, SIAM J. Discrete Math. 29.2, pp. 751–795. doi: 10.1137/130936464
  • S. Brodsky, M. Joswig, R. Morrison, B. Sturmfels, Moduli of plane tropical curves, Res. Math. Sci. 2.4. doi: 10.1186/s40687-014-0018-1.
  • M. Joswig, G. Loho, Weighted digraphs and tropical cones, to appear in Linear Algebra Appl. Preprint arXiv:1503.04707. doi: 10.1016/j.laa.2016.02.027.
  • M. Joswig, J. Kileel, B. Sturmfels, A. Wagner, Rigid Multiview Varieties, Int. J. Algebra Comput. 26, 775 (2016). DOI: 10.1142/S021819671650034X
  • Proceedings

  • M. Joswig, G. Loho, B. Lorenz, B. Schröter Linear programs and convex hulls over fields of Puiseux fractions, to appear in Proceedings of MACIS 2015, Berlin, November 11–13, 2015. Preprint arXiv:1507.08092.
  • S. Agarwal, M. Joswig, R. Thomas, Meeting on Algebraic Vision 2015, Proceedings of the Meeting on Algebraic Vision 2015, http://www3.math.tu-berlin.de/combi/AlgebraicVision/mavProceedings.pdf.
  • Preprints

  • X. Allamigeon, P. Benchimol, M. Joswig, S. Gaubert, Long and winding central paths , arXiv:1405.4161v2
  • T. Kahle, A. Wagner, Veronesean almost binomial almost complete intersections, arXiv:1608.03499
  • M. Joswig, B. Schröter, The degree of a tropical basis , arXiv:1511.08123
  • Poster

  • J. Kileel, A. Wagner, Rigid Multiview Varieties, Meeting on Algebraic Vision 2015
  • Software

    Polymake 3.0, 2016

    Other Publications

  • M. Joswig, M. Mehner, S. Sechelmann, J. Techter, A. Bobenko DGD Gallery: Storage, sharing, and publication of digital research data, Advances in Discrete Differential Geometry. Ed. by Alexander I. Bobenko. Springer.