Advanced

Robust Algorithms for Multiple View Geometry: Outliers and Optimality

Enqvist, Olof LU (2011)
Abstract (Swedish)
Popular Abstract in Swedish

Hur kan man skapa en tredimensionell modell av ett objekt eller en plats från tvådimensionella bilder? Det

är den centrala frågan i den här avhandlingen och en viktig fråga i datorseende generellt. Normalt delar man

upp problemet i en serie basproblem. Ett basproblem kan till exempel vara att skatta kamerans rörelse

mellan två bilder eller kamerapositionen för en ny bild givet en 3d-modell. Lösningarna till dessa

basproblem kan vara intressanta i sig eller som delsteg i skattning av en större modell.



Den första delen av avhandlingen beskriver nya algoritmer för ett antal sådana basproblem. Till exempel för

problemet att skatta den... (More)
Popular Abstract in Swedish

Hur kan man skapa en tredimensionell modell av ett objekt eller en plats från tvådimensionella bilder? Det

är den centrala frågan i den här avhandlingen och en viktig fråga i datorseende generellt. Normalt delar man

upp problemet i en serie basproblem. Ett basproblem kan till exempel vara att skatta kamerans rörelse

mellan två bilder eller kamerapositionen för en ny bild givet en 3d-modell. Lösningarna till dessa

basproblem kan vara intressanta i sig eller som delsteg i skattning av en större modell.



Den första delen av avhandlingen beskriver nya algoritmer för ett antal sådana basproblem. Till exempel för

problemet att skatta den relativa rörelsen mellan två bilder. Man vill alltså beräkna hur kameran har flyttats

och vridits mellan två tagna bilder. Det första steget för att åstadkomma detta är att detektera

korrespondenser mellan bilderna. Vi säger att två punkter är korresponderande om de är projektioner av

samma punkt i världen. Om du till exempel har en fläck på skjortan som syns i två bilder så är de punkterna

korresponderande. När man hittat sådana punkter så är nästa steg att räkna ut en kamerarörelse som

stämmer med dessa korrespondenser. Ett problem här är att andra punkter i bilden kan likna fläcken på

skjortan och leda till felaktiga korresponser, så kallade outliers. Huvudfokus för algoritmerna i avhandlingen

är just att uppnå robusthet för den sortens fel.



I den andra delen av avhandlingen lämnar vi basproblemen och tittar på geometriska problem med multipla

kameror. Kapitel 5 diskuterar en generell metod för att bygga 3d-modeller från flera vyer. Metoden bygger

på såväl grafteori som moderna metoder från konvex optimering. Vidare visas en del teoretiska resultat som

styrker den föreslagna metoden.



Endimensionella kameror kan vara en ekonomiskt alternativ för till exempel robotnavigering. Systemet

bygger på att en slags reflekterande tejp har satts upp på olika ställen i lokalen. Den endimensionella

kameran registrerar när en roterande laser reflekteras mot tejpen. En endimensionell bild är alltså ett samling

riktningar för vilka reflektion uppmättes. I kapitel 6 visas hur ett flertal problem för endimensionella

kameror kan lösas med hjälp effektiva optimeringsmetoder. (Less)
Abstract
This thesis is concerned with the geometrical parts of computer vision, or more precisely, with the three-dimensional geometry. The overall aim is to extract geometric information from a set of images. Most methods for estimating the geometry of multiple views rely on the existence of robust solvers for a set of basic problems. Such a basic problem can be estimating the relative orientation of two cameras or estimating the position of a camera given a model of the scene.







The first part of this thesis presents a number of new algorithms for attacking different instances of such basic problems.



Normally methods for these problems consist of two parts. First, interest points are... (More)
This thesis is concerned with the geometrical parts of computer vision, or more precisely, with the three-dimensional geometry. The overall aim is to extract geometric information from a set of images. Most methods for estimating the geometry of multiple views rely on the existence of robust solvers for a set of basic problems. Such a basic problem can be estimating the relative orientation of two cameras or estimating the position of a camera given a model of the scene.







The first part of this thesis presents a number of new algorithms for attacking different instances of such basic problems.



Normally methods for these problems consist of two parts. First, interest points are extracted from the images and point-to-point correspondences between images are determined. In the second step these correspondences are used to estimate the geometry. A major difficulty lies in the existence of incorrect correspondences, often called outliers. Not modelling these outliers will result in very poor accuracy. Hence, the algorithms in this thesis are designed to be robust to such outliers. In particular, focus lies on obtaining optimal solutions in presence of outliers. For example, it is shown how optimal solutions can be found in cases when the residuals are quasiconvex functions. Moreover, optimal algorithms for the non-convex problems of calibrated camera pose estimation, registration and relative orientation estimation are presented.







The second part of the thesis discusses how the solutions from these basic problems can be combined and refined to form a model of the whole scene. Again, robustness is crucial. In this case robustness with respect to incorrect solutions from the basic problems. In particular, a complete system for estimating muliple view geometry is proposed. Often this problem has been solved in a sequential manner, but recently there has been a large interest in non-sequential methods. The results in this thesis show the advantages of a non-sequential approach based on graph methods as well as convex optimization. The last chapter of the thesis is concerned with structure from motion for the special case of one-dimensional cameras. It is shown how optimal solutions can be obtained using linear programming. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Pollefeys, Marc, ETH Zürich
organization
publishing date
type
Thesis
publication status
published
subject
pages
133 pages
defense location
Lecture Hall C at the Centre for Mathematical Sciences, Sölvegatan 18, Lund University Faculty of Engineering
defense date
2011-04-08 13:15
ISBN
978-91-7473-102-6
language
English
LU publication?
yes
id
77e0b6a0-b2e0-4314-862c-a384dce1d54d (old id 1852369)
date added to LUP
2011-03-14 14:20:53
date last changed
2016-09-19 08:45:19
@phdthesis{77e0b6a0-b2e0-4314-862c-a384dce1d54d,
  abstract     = {This thesis is concerned with the geometrical parts of computer vision, or more precisely, with the three-dimensional geometry. The overall aim is to extract geometric information from a set of images. Most methods for estimating the geometry of multiple views rely on the existence of robust solvers for a set of basic problems. Such a basic problem can be estimating the relative orientation of two cameras or estimating the position of a camera given a model of the scene.<br/><br>
<br/><br>
<br/><br>
<br/><br>
The first part of this thesis presents a number of new algorithms for attacking different instances of such basic problems.<br/><br>
<br/><br>
Normally methods for these problems consist of two parts. First, interest points are extracted from the images and point-to-point correspondences between images are determined. In the second step these correspondences are used to estimate the geometry. A major difficulty lies in the existence of incorrect correspondences, often called outliers. Not modelling these outliers will result in very poor accuracy. Hence, the algorithms in this thesis are designed to be robust to such outliers. In particular, focus lies on obtaining optimal solutions in presence of outliers. For example, it is shown how optimal solutions can be found in cases when the residuals are quasiconvex functions. Moreover, optimal algorithms for the non-convex problems of calibrated camera pose estimation, registration and relative orientation estimation are presented. <br/><br>
<br/><br>
<br/><br>
<br/><br>
The second part of the thesis discusses how the solutions from these basic problems can be combined and refined to form a model of the whole scene. Again, robustness is crucial. In this case robustness with respect to incorrect solutions from the basic problems. In particular, a complete system for estimating muliple view geometry is proposed. Often this problem has been solved in a sequential manner, but recently there has been a large interest in non-sequential methods. The results in this thesis show the advantages of a non-sequential approach based on graph methods as well as convex optimization. The last chapter of the thesis is concerned with structure from motion for the special case of one-dimensional cameras. It is shown how optimal solutions can be obtained using linear programming.},
  author       = {Enqvist, Olof},
  isbn         = {978-91-7473-102-6},
  language     = {eng},
  pages        = {133},
  school       = {Lund University},
  title        = {Robust Algorithms for Multiple View Geometry: Outliers and Optimality},
  year         = {2011},
}