CH3: Multiview geometry for ophthalmic surgery simulation

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

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 Agarwal	Google Inc.
	Rekha R. Thomas	U Washington
	Xi Wang	TU Berlin
	VRmagic Holding AG
	Imaginary
	Fraunhofer Heinrich Hertz Institute

Events

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

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.

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 partially classify both robust and degenerate configurations of the 8-point-algorithm. Further we could improve the 8-point-algorithm for pictures of cubes.

Additionally the set-theoretical description of the rigid multiview variety was detremined. 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.

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.