## 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 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.

## 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

## 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.