introduction.tex

\chapter{Introduction}
In geometry of computer vision, many problems are formulated as systems of polynomial equations.
The state of the art methods are based on polynomial algebra, i.e.\ on Gr\"obner bases and multiplication matrices computation.
Contrary to this approach, this work applies non-linear optimization techniques to solve the polynomial systems, which is a novel idea in the field of geometry of computer vision.
Moreover, the application of the optimization techniques allows us to enrich the polynomial systems with polynomial inequalities or to solve polynomial optimization problems, i.e.\ optimizing a polynomial function with given polynomial constraints.

\section{Motivation}
Object recognition and localization, reconstruction of 3D scenes, self-driving cars, film production, augmented reality and robotics are only few of many applications of geometry of computer vision.
Thus, one would like to solve geometric problems efficiently, since these problems often have to be solved in real-time applications.
Typical geometric problems from computer vision are the minimal problems, which arise when estimating geometric models of scenes from given images.
To be able to solve these problems computationally, they are often represented by systems of algebraic equations.
Hence, one of the issues of computer vision is, how to solve systems of polynomial equations efficiently, which is the scope of this work.

The polynomial systems obtained from the geometric problems are often not trivial, but usually consist of many polynomial equations of high degree in several unknowns.
From that reason, general algorithms for polynomial systems solving are not efficient for them, and therefore special solvers have been developed for different problems to solve these problems efficiently and robustly.
Previously, these solvers were handcrafted, which is quite time demanding process that has to be done for each problem from scratch.
Then, the process was automated by automatic generators \cite{autogen, larsson}, which automatically generate efficient solver for a given type of the polynomial system.
These solvers obtain the Gr\"obner basis of the system and then construct the multiplication matrix, from which solutions are extracted by eigenvectors computation.
The side effect of this approach is that some non-real solutions often appear amongst real solutions, which are not solutions to the original geometric problem.
Since the computation of the non-real solutions takes time, a method which would find real solutions only may be faster than the contemporary approach.

Some of the arisen systems may be overconstrained.
Such systems have a solution when solved on precise data using precise arithmetic, but they have no solution when solved on real noisy data.
However, these systems may be transformed into optimization problem by relaxing some of the constrains and by minimizing the error of these constraints.
Therefore, an efficient polynomial optimization method may prove useful for overconstrained systems.

\section{Contributions}
To solve polynomial systems over real numbers only, we apply the moment method introduced by J. B. Lasserre et al.
This method uses hierarchies of semidefinite programs to find a Gr\"obner basis of real radical ideal constructed from the ideal generated by the given polynomials.
Then, a multiplication matrix is constructed and solutions are obtained from it.
In this case, the multiplication matrix should have smaller size than a multiplication matrix obtained from the automatic generator, which can save some computation time.
We implement this method in Python and MATLAB and examine its properties on several minimal problems from geometry of computer vision on real 3D scenes.
We show that this method is applicable on problems from computer vision.

The second contribution of this work is, that we describe and review a method for polynomial optimization problems.
This method solves hierarchies of semidefinite programs to find the optimal value.
An application of this method can, for example, be a solver of overconstrained polynomial systems.
We implement our own implementation of this method in Python and compare it to the state of the art methods on synthetic polynomial optimization problems.

Since semidefinite programs solving is a key element in both previously mentioned methods, we review and describe an interior-point method for semidefinite programs solving.
To be able to use this method in implementations of the moment method and the polynomial optimization method, we implement this interior-point method in Python.
To verify our implementation we compare it to the state of the art semidefinite solvers on synthetic semidefinite programs.

\section{Thesis structure}
In this work, we first review an interior-point method for semidefinite programs solving.
To do so, general properties of self-concordant functions and barriers need to be introduced, since they are key elements in convex optimization.
Then, a specialized barrier function for semidefinite programming will be described.
%The knowledge of semidefinite programming is important for us, since it plays crucial role in polynomial optimization techniques described later in the text.
We describe our implementation of the semidefinite programs solver and compare it to the state of the art methods.

Secondly, we focus on polynomial optimization.
After an introduction to polynomial algebra and moment matrices, we describe and implement a method, which solves polynomial optimization problems by relaxations of semidefinite programs.
Then, we review the moment method and describe its implementation in Python.
%The moment method allows us to solve systems of polynomial equations over real numbers.

To compare the implementation of the moment method to the state of the art methods, we introduce two minimal problems from computer vision on which we perform the experiments.
The minimal problems are the estimation (i) of the calibrated camera pose and (ii) of the calibrated camera pose with unknown focal length.
We show that our implementation of the moment method is applicable to these selected geometric problems from computer vision.