Robust Algorithms for Multiple View Geometry: Outliers and Optimality
(2011)- 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) - 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)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1852369
- author
- Enqvist, Olof LU
- supervisor
-
- Fredrik Kahl LU
- Karl Åström LU
- Fredrik Andersson LU
- opponent
-
- Professor Pollefeys, Marc, ETH Zürich
- organization
- publishing date
- 2011
- 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:00
- ISBN
- 978-91-7473-102-6
- language
- English
- LU publication?
- yes
- id
- 77e0b6a0-b2e0-4314-862c-a384dce1d54d (old id 1852369)
- date added to LUP
- 2016-04-04 14:22:14
- date last changed
- 2018-11-21 21:19:55
@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}}, school = {{Lund University}}, title = {{Robust Algorithms for Multiple View Geometry: Outliers and Optimality}}, url = {{https://lup.lub.lu.se/search/files/6344645/1852371.pdf}}, year = {{2011}}, }