Mathematical Methods for Image Based Localization

Abstract

The underlying question in localization is, where am I? In this thesis a purely image based approach is proposed to solve this problem. In order to create a complete image based system, there are many subproblems that have to be addressed. The localization problem can also be solved in other ways, for example, with a GPS. Two advantages with using images compared to GPS are that no open sky is needed and that a higher precision is possible to achieve.



The thesis consists of an introductory chapter followed by six papers. In the first paper, enhancements of Gröbner basis techniques to solve systems of polynomial equations are presented. The new strategies improve the numeric stability with several orders of magnitudes, compared to previous state of the art. This framework is then applied in the next three papers to solve several geometrical pose problems relevant for localization. The main difference between the papers is the level of knowledge of the inner calibration of the cameras. The calibration knowledge ranges from completely calibrated cameras to uncalibrated cameras with unknown radial distortion. The fifth paper of the thesis also treats the pose problem, but the method differs from the previous papers. In this paper a method is presented that guarantees a globally optimal solution at the price of computational complexity. To achieve this, the pose problem is reformulated and solved via a minimal vertex cover. The final paper is devoted to large-scale localization. Methods from image retrieval are utilized, and extended, to be able to perform city-scale localization. Moreover geometry is directly incorporated in the retrieval stage.

Abstract (Swedish)

Popular Abstract in Swedish

Var är bilden tagen? Det är en fråga som vi ofta ställer oss och som denna avhandling innehåller matematiska metoder för att låta en dator besvara. Om vi lyckas svara på frågan kan metoderna för att hitta svaret användas till vitt skilda saker. Det går att använda för att låta robotar navigera med hjälp av kameror men också för att sortera privata bilder i digitala fotoalbum efter var de är tagna.



För att lösa lokaliseringsproblemet har flera delproblem studerats. I ett av delproblemen har en tredimensionell modell av Malmö byggts upp utifrån 95~000 bilder tagna utmed stadens gator. Med hjälp av modellen går det för en ny bild, tagen någonstans i Malmö att avgöra var fotografen befann sig. Det görs genom att titta på många små områden i den nya bilden. De områdena beskrivs sedan med en uppsättning tal så att liknande områden går att hitta i den tredimensionella modellen. Om tillräckligt mycket är känt om kameran som tagit bilden går det att räkna ut vilken vinkel det är mellan riktningarna till två punkter som avbildats i bilden, sett från kameran. Tack vare den tredimensionella modellen av staden är det sedan möjligt att räkna ut var i Malmö den vinkeln kan uppstå mellan punkterna. Med hjälp av det går det att få fram en lista på platser där bilden kan vara tagen.



Det som hittills har beskrivits kan fungera som ett första steg i en lokaliseringsprocess. För att ta reda på mera om kamerans position, så som riktning, eller för att få en högre precision i resultatet kan man utgå från resultatet av den första delen för att hitta positioner att undersöka noggrannare. Även de fortsatta algoritmerna för att söka efter position har utvecklats i avhandlingen. När antalet tänkbara platser begränsats efter det första steget är det möjligt att utföra mera resurskrävande beräkningar som en dator inte skulle klara av för en hel stad på rimlig tid. I arbetet har det utvecklats två typer av algoritmer för detta problem, dels en som är optimal, alltså att det är säkert att det inte finns en bättre lösning, dels metoder som går snabbare men som inte garanterat ger ett optimalt resultat.



Det kan låta konstigt att inte nöja sig med en metod som ger ett optimalt svar, men dessa algoritmer tar ofta för lång tid att använda, och då får vi hoppas på att kunna ta en genväg för att hitta en nästan lika bra lösning. Det visar sig också att det i de flesta fallen blir fullt tillfredsställande lösningar även när den snabba vägen används.



Det arbete som gjorts på de snabbare metoderna i avhandlingen handlar till stor del om beräkningar kopplade till hur kameror avbildar omgivningen. För olika matematiska modeller av en kamera, som är beroende av hur mycket som är känt om kamerans konstruktion och även vilken brännvidd som användes vid fototillfället, blir det olika geometriska problem att lösa. Vid användning av de snabba algoritmerna utnyttjas ett minimalt antal punkter i bilden, som har kopplats samman med punkter i den tredimensionella modellen, för att problemet ska kunna lösas. Sedan löses problemet för denna minimala uppsättning punkter. Lösningen testas hur väl den stämmer överens med de övriga punkterna som kopplats samman mellan bilden och modellen. Många tidigare olösta sådana problem, där ett minimalt antal punkter är kopplade mellan kameran och modellen, presenteras det lösningar på i avhandlingen. Lösningarna blir då en viktig kugge i ett fullständigt lokaliseringssystem.

• author: Josephson, Klas
• supervisor: Fredrik Kahl
• opponent: Professor Vidal, Rene, Center for Imaging Sciences, Johns Hopkins University, Baltimore, USA
• organization: Mathematics (Faculty of Engineering); Mathematical Imaging Group (research group)
• publishing date: 2010
• type: Thesis
• publication status: published
• subject: Mathematics; Computer Vision and Robotics (Autonomous Systems)
• keywords: Multiple View Geometry, Image Based Localization, Computer Vision, Gröbner Basis, Minimal Problems
• pages: 216 pages
• defense location: Lecture hall MH:B, Centre for Mathematical Sciences, Sölvegatan 18, Lund University Faculty of Engineering
• defense date: 2010-05-12 13:15:00
• external identifiers: other:LUTFMA-1040-2010
• ISBN: 978-91-628-8062-0
• language: English
• LU publication?: yes
• id: cf04de44-7590-4c5c-a9e2-be439a1a0f02 (old id 1585793)
• date added to LUP: 2016-04-01 12:55:57
• date last changed: 2018-11-21 20:10:24