Project Head: | Michael Joswig |

Research Staff: | André Wagner |

Oct. 8-9, | 2015 | Meeting on Algebraic Vision 2015 |

Jan. 28-30, | 2016 | 7th polymake Conference and Developer Meeting |

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.

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:

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.

Polymake 3.0, 2016